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.
It is worth mentioning the difference among proof techniques in these works. The uniform convergence result of @cite_5 leverages the covering number to bound @math for any @math . The analysis for strongly convex functions by @cite_5 and exp-concave functions by @cite_1 utilize the tool of stability, which only produces risk bounds that hold in expectation. A simple way to achieve a high probability bound is to use ERM combined with a generic or specific boosting-the-confidence method , but the guarantee is not directly on the empirical minimizer as noted by @cite_5 . The convergence of ERM given by @cite_6 relies on a central condition or stochastic mixability'' of the exp-concave function. In this paper, we present a general approach for analyzing ERM for SCO of smooth functions. In particular, our analysis is based on a uniform convergence of @math to @math for any @math , and a concentration inequality of @math , where @math is the optimal solution to ).
@cite_5 @cite_1 @cite_6
1537193711 2189962665 2547508527
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 consider Empirical Risk Minimization (ERM) in the context of stochastic optimization with exp-concave and smooth losses—a general optimization framework that captures several important learning problems including linear and logistic regression, learning SVMs with the squared hinge-loss, portfolio selection and more. In this setting, we establish the first evidence that ERM is able to attain fast generalization rates, and show that the expected loss of the ERM solution in d dimensions converges to the optimal expected loss in a rate of d n. This rate matches existing lower bounds up to constants and improves by a log n factor upon the state-of-the-art, which is only known to be attained by an online-to-batch conversion of computationally expensive online algorithms. 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.