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
2950933581 2951171906 1755884204 2291950750
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ( juntas ). Our main results are tight bounds on the number of variables required to approximate a function @math within @math -error @math over the uniform distribution: 1. If @math is submodular, then it is @math -close to a function of @math variables. This is an exponential improvement over previously known results. We note that @math variables are necessary even for linear functions. 2. If @math is fractionally subadditive (XOS) it is @math -close to a function of @math variables. This result holds for all functions with low total @math -influence and is a real-valued analogue of Friedgut's theorem for boolean functions. We show that @math variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a PAC learning algorithm that runs in time @math . For submodular functions we give an algorithm in the more demanding PMAC learning model (Balcan and Harvey, 2011) which requires a multiplicative @math factor approximation with probability at least @math over the target distribution. Our uniform distribution algorithm runs in time @math . This is the first algorithm in the PMAC model that over the uniform distribution can achieve a constant approximation factor arbitrarily close to 1 for all submodular functions. As follows from the lower bounds in (, 2013) both of these algorithms are close to optimal. We also give applications for proper learning, testing and agnostic learning with value queries of these classes. Let @math be a finite lattice and let @math be a positive integer. A function @math is said to be submodular if @math for all @math . In this paper we study submodular functions when @math is a diamond. Given oracle access to @math we are interested in finding @math such that @math as efficiently as possible. We establish a min--max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular @math and an integer @math such that @math , there is a proof of this fact which can be verified in time polynomial in @math and @math ; and a pseudo-polynomial time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular @math one can find @math in time bounded by a polynomial in @math and @math . We show that all non-negative submodular functions have high noise-stability . As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on @math (for any constant accuracy parameter @math ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular functions required either query access or strong assumptions about the types of submodular functions to be learned (and did not hold in the agnostic setting). In this paper we propose a distributed version of a randomized block-coordinate descent method for minimizing the sum of a partially separable smooth convex function and a fully separable non-smooth convex function. Under the assumption of block Lipschitz continuity of the gradient of the smooth function, this method is shown to have a sublinear convergence rate. Linear convergence rate of the method is obtained for the newly introduced class of generalized error bound functions. We prove that the new class of generalized error bound functions encompasses both global local error bound functions and smooth strongly convex functions. We also show that the theoretical estimates on the convergence rate depend on the number of blocks chosen randomly and a natural measure of separability of the objective function.