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 .
 A core element of microeconomics and game theory is that consumers have valuation functions over bundles of goods and that these valuations functions drive their purchases. A common assumption is that these functions are subadditive meaning that the value given to a bundle is at most the sum of values on the individual items. In this paper, we provide nearly tight guarantees on the efficient learnability of subadditive valuations. We also provide nearly tight bounds for the subclass of XOS (fractionally subadditive) valuations, also widely used in the literature. We additionally leverage the structure of valuations in a number of interesting subclasses and obtain algorithms with stronger learning guarantees. We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercubef0; 1g n . Our main result is the following structural theorem: any submodular function is -close in‘2 to a real-valued decision tree (DT) of depth O(1= 2 ). This immediately implies that any submodular function is -close to a function of at most Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes of set functions can be sketched. More formally, let f be a function mapping subsets of some ground set [n] to the non-negative real numbers. We say that f' is an α-sketch of f if for every set S, the value f'(S) lies between f(S) α and f(S), and f' can be specified by poly(n) bits. We show that for every subadditive function f there exists an α-sketch where α = n1 2. O(polylog(n)). Furthermore, we provide an algorithm that finds these sketches with a polynomial number of demand queries. This is essentially the best we can hope for since: 1. We show that there exist subadditive functions (in fact, XOS functions) that do not admit an o(n1 2) sketch. (Balcan and Harvey [3] previously showed that there exist functions belonging to the class of substitutes valuations that do not admit an O(n1 3) sketch.) 2. We prove that every deterministic algorithm that accesses the function via value queries only cannot guarantee a sketching ratio better than n1−e. We also show that coverage functions, an interesting subclass of submodular functions, admit arbitrarily good sketches. Finally, we show an interesting connection between sketching and learning. We show that for every class of valuations, if the class admits an α-sketch, then it can be α-approximately learned in the PMAC model of Balcan and Harvey. The bounds we prove are only information-theoretic and do not imply the existence of computationally efficient learning algorithms in general.