Although there exist plentiful theories of empirical risk minimization (ERM) for supervised learning, current theoretical understandings of ERM for a related problem---stochastic convex optimization (SCO), are limited. In this work, we strengthen the realm of ERM for SCO by exploiting smoothness and strong convexity conditions to improve the risk bounds. First, we establish an @math risk bound when the random function is nonnegative, convex and smooth, and the expected function is Lipschitz continuous, where @math is the dimensionality of the problem, @math is the number of samples, and @math is the minimal risk. Thus, when @math is small we obtain an @math risk bound, which is analogous to the @math optimistic rate of ERM for supervised learning. Second, if the objective function is also @math -strongly convex, we prove an @math risk bound where @math is the condition number, and improve it to @math when @math . As a result, we obtain an @math risk bound under the condition that @math is large and @math is small, which to the best of our knowledge, is the first @math -type of risk bound of ERM. Third, we stress that the above results are established in a unified framework, which allows us to derive new risk bounds under weaker conditions, e.g., without convexity of the random function and Lipschitz continuity of the expected function. Finally, we demonstrate that to achieve an @math risk bound for supervised learning, the @math requirement on @math can be replaced with @math , which is dimensionality-independent.
As we mentioned earlier, there are few works devoted to ERM for stochastic optimization. When @math is bounded and @math is Lipschitz continuous, @cite_5 demonstrate that @math converges to @math uniformly over @math with an @math error bound that holds with high probability, implying an @math risk bound of ERM. They further establish an @math risk bound of ERM that holds in expectation when @math is @math -strongly convex and Lipschitz continuous. Stochastic optimization with exp-concave functions is studied recently , Their excess risk bound is for a regularized empirical risk minimizer. and @cite_6 proves an @math bound of ERM that holds with high probability when @math is @math -exp-concave, Lipschitz continuous, and bounded. Lower bounds of ERM for stochastic optimization is investigated by @cite_8 , who exhibits (i) a lower bound of @math sample complexity for uniform convergence that nearly matches the upper bound of @cite_5 ; and (ii) a lower bound of @math sample complexity of ERM, which is matched by our @math bound when @math is small.
@cite_5 @cite_6 @cite_8
1537193711 2547508527 2517669009
Introduction 1. Notation and preliminary background 2. Gaussian variables. K-convexity 3. Ellipsoids 4. Dvoretzky's theorem 5. Entropy, approximation numbers, and Gaussian processes 6. Volume ratio 7. Milman's ellipsoids 8. Another proof of the QS theorem 9. Volume numbers 10. Weak cotype 2 11. Weak type 2 12. Weak Hilbert spaces 13. Some examples: the Tsirelson spaces 14. Reflexivity of weak Hilbert spaces 15. Fredholm determinants Final remarks Bibliography Index. We present an algorithm for the statistical learning setting with a bounded exp-concave loss in @math dimensions that obtains excess risk @math with probability at least @math . The core technique is to boost the confidence of recent in-expectation @math excess risk bounds for empirical risk minimization (ERM), without sacrificing the rate, by leveraging a Bernstein condition which holds due to exp-concavity. We also show that with probability @math the standard ERM method obtains excess risk @math . We further show that a regret bound for any online learner in this setting translates to a high probability excess risk bound for the corresponding online-to-batch conversion of the online learner. Lastly, we present two high probability bounds for the exp-concave model selection aggregation problem that are quantile-adaptive in a certain sense. The first bound is a purely exponential weights type algorithm, obtains a nearly optimal rate, and has no explicit dependence on the Lipschitz continuity of the loss. The second bound requires Lipschitz continuity but obtains the optimal rate. In stochastic convex optimization the goal is to minimize a convex function @math over a convex set @math where @math is some unknown distribution and each @math in the support of @math is convex over @math . The optimization is commonly based on i.i.d. samples @math from @math . A standard approach to such problems is empirical risk minimization (ERM) that optimizes @math . Here we consider the question of how many samples are necessary for ERM to succeed and the closely related question of uniform convergence of @math to @math over @math . We demonstrate that in the standard @math setting of Lipschitz-bounded functions over a @math of bounded radius, ERM requires sample size that scales linearly with the dimension @math . This nearly matches standard upper bounds and improves on @math dependence proved for @math setting by Shalev- (2009). In stark contrast, these problems can be solved using dimension-independent number of samples for @math setting and @math dependence for @math setting using other approaches. We further show that our lower bound applies even if the functions in the support of @math are smooth and efficiently computable and even if an @math regularization term is added. Finally, we demonstrate that for a more general class of bounded-range (but not Lipschitz-bounded) stochastic convex programs an infinite gap appears already in dimension 2.