In this paper, we study a family of non-convex and possibly non-smooth inf-projection minimization problems, where the target objective function is equal to minimization of a joint function over another variable. This problem includes difference of convex (DC) functions and a family of bi-convex functions as special cases. We develop stochastic algorithms and establish their first-order convergence for finding a (nearly) stationary solution of the target non-convex function under different conditions of the component functions. To the best of our knowledge, this is the first work that comprehensively studies stochastic optimization of non-convex inf-projection minimization problems with provable convergence guarantee. Our algorithms enable efficient stochastic optimization of a family of non-decomposable DC functions and a family of bi-convex functions. To demonstrate the power of the proposed algorithms we consider an important application in variance-based regularization, and experiments verify the effectiveness of our inf-projection based formulation and the proposed stochastic algorithm in comparison with previous stochastic algorithms based on the min-max formulation for achieving the same effect.
Another important result is following the Bennett's inequality. Corollary 5 in @cite_7 shows that: where @math is the sample variance. It is notable that @math is equivalent (with a constant scaling) to the empirical variance @math . Similarly, the above uniform estimate can be extended to infinite loss classes using different complexity measures .
@cite_7
1786332878
We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph @math with @math vertices, and define (for @math ) @math . Our aim is to estimate @math within a multiplicative error of @math (for a given approximation parameter @math ) in sublinear time. We consider the sparse graph model that allows access to: uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of @math (the average degree), @math queries suffice for any constant @math (Feige, SICOMP 06 and Goldreich-Ron, RSA 08). Gonen-Ron-Shavitt (SIDMA 11) extended this result to all integral @math , by designing an algorithms that performs @math queries. We design a new, significantly simpler algorithm for this problem. In the worst-case, it exactly matches the bounds of Gonen-Ron-Shavitt, and has a much simpler proof. More importantly, the running time of this algorithm is connected to the degeneracy of @math . This is (essentially) the maximum density of an induced subgraph. For the family of graphs with degeneracy at most @math , it has a query complexity of @math . Thus, for the class of bounded degeneracy graphs (which includes all minor closed families and preferential attachment graphs), we can estimate the average degree in @math queries, and can estimate the variance of the degree distribution in @math queries. This is a major improvement over the previous worst-case bounds. Our key insight is in designing an estimator for @math that has low variance when @math does not have large dense subgraphs. We give improved constants for data dependent and variance sensitive confidence bounds, called empirical Bernstein bounds, and extend these inequalities to hold uniformly over classes of functions whose growth function is polynomial in the sample size n. The bounds lead us to consider sample variance penalization, a novel learning method which takes into account the empirical variance of the loss function. We give conditions under which sample variance penalization is effective. In particular, we present a bound on the excess risk incurred by the method. Using this, we argue that there are situations in which the excess risk of our method is of order 1 n, while the excess risk of empirical risk minimization is of order 1 √n. We show some experimental results, which confirm the theory. Finally, we discuss the potential application of our results to sample compression schemes. We give improved constants for data dependent and variance sensitive confidence bounds, called empirical Bernstein bounds, and extend these inequalities to hold uniformly over classes of functionswhose growth function is polynomial in the sample size n. The bounds lead us to consider sample variance penalization, a novel learning method which takes into account the empirical variance of the loss function. We give conditions under which sample variance penalization is effective. In particular, we present a bound on the excess risk incurred by the method. Using this, we argue that there are situations in which the excess risk of our method is of order 1 n, while the excess risk of empirical risk minimization is of order 1 sqrt n . We show some experimental results, which confirm the theory. Finally, we discuss the potential application of our results to sample compression schemes. In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by (2006) that ensures that the output of an algorithm leaks little information about the data point provided by any of the participating individuals. Sample complexity of private PAC and agnostic learning was studied in a number of prior works starting with (, 2008) but a number of basic questions still remain open, most notably whether learning with privacy requires more samples than learning without privacy. We show that the sample complexity of learning with (pure) differential privacy can be arbitrarily higher than the sample complexity of learning without the privacy constraint or the sample complexity of learning with approximate differential privacy. Our second contribution and the main tool is an equivalence between the sample complexity of (pure) differentially private learning of a concept class @math (or @math ) and the randomized one-way communication complexity of the evaluation problem for concepts from @math . Using this equivalence we prove the following bounds: 1. @math , where @math is the Littlestone's (1987) dimension characterizing the number of mistakes in the online-mistake-bound learning model. Known bounds on @math then imply that @math can be much higher than the VC-dimension of @math . 2. For any @math , there exists a class @math such that @math but @math . 3. For any @math , there exists a class @math such that the sample complexity of (pure) @math -differentially private PAC learning is @math but the sample complexity of the relaxed @math -differentially private PAC learning is @math . This resolves an open problem of (2013b).