We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube @math . Informally, a function @math is self-bounding if for every @math , @math upper bounds the sum of all the @math marginal decreases in the value of the function at @math . Self-bounding functions include such well-known classes of functions as submodular and fractionally-subadditive (XOS) functions. They were introduced by (2000) in the context of concentration of measure inequalities. Our main result is a nearly tight @math -approximation of self-bounding functions by low-degree juntas. Specifically, all self-bounding functions can be @math -approximated in @math by a polynomial of degree @math over @math variables. We show that both the degree and junta-size are optimal up to logarithmic terms. Previous techniques considered stronger @math approximation and proved nearly tight bounds of @math on the degree and @math on the number of variables. Our bounds rely on the analysis of noise stability of self-bounding functions together with a stronger connection between noise stability and @math approximation by low-degree polynomials. This technique can also be used to get tighter bounds on @math approximation by low-degree polynomials and faster learning algorithm for halfspaces. These results lead to improved and in several cases almost tight bounds for PAC and agnostic learning of self-bounding functions relative to the uniform distribution. In particular, assuming hardness of learning juntas, we show that PAC and agnostic learning of self-bounding functions have complexity of @math .
In @cite_51 learning of submodular functions over the uniform distribution is motivated by problems in differentially-private data release. They show that submodular functions with range @math are @math -approximated by a collection of @math @math -Lipschitz submodular functions. Each @math -Lipschitz submodular function can be @math -approximated by a constant. This leads to a learning algorithm running in time @math , which however requires value oracle access to the target function, in order to build the collection.
@cite_51
2121372565
Suppose we would like to know all answers to a set of statistical queries C on a data set up to small error, but we can only access the data itself using statistical queries. A trivial solution is to exhaustively ask all queries in C. Can we do any better? We show that the number of statistical queries necessary and sufficient for this task is---up to polynomial factors---equal to the agnostic learning complexity of C in Kearns' statistical query (SQ)model. This gives a complete answer to the question when running time is not a concern. We then show that the problem can be solved efficiently (allowing arbitrary error on a small fraction of queries) whenever the answers to C can be described by a submodular function. This includes many natural concept classes, such as graph cuts and Boolean disjunctions and conjunctions. While interesting from a learning theoretic point of view, our main applications are in privacy-preserving data analysis: Here, our second result leads to an algorithm that efficiently releases differentially private answers to all Boolean conjunctions with 1 average error. This presents progress on a key open problem in privacy-preserving data analysis. Our first result on the other hand gives unconditional lower bounds on any differentially private algorithm that admits a (potentially non-privacy-preserving) implementation using only statistical queries. Not only our algorithms, but also most known private algorithms can be implemented using only statistical queries, and hence are constrained by these lower bounds. Our result therefore isolates the complexity of agnostic learning in the SQ-model as a new barrier in the design of differentially private algorithms.