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.
Generally speaking, when @math has finite VC-dimension, the excess risk can be upper bounded by @math , where @math is the VC-dimension of @math . If the loss @math is Lipschitz continuous with respect to its first argument, we have a risk bound of @math , where @math is the Rademacher complexity of @math . The Rademacher complexity typically scales as @math , e.g., @math contains linear functions with low-norm, implying an @math risk bound . There have been intensive efforts to derive rates faster than @math under various conditions , such as low-noise , smoothness , strong convexity , to name a few amongst many. Specifically, when the random function @math is nonnegative and smooth, @cite_4 have established a risk bound of @math , reducing to an @math bound if @math and @math . A generalized linear form of ) is studied by @cite_7 , and a risk bound of @math is proved if the expected function @math is @math -strongly convex.
@cite_4 @cite_7
6657555 2114609025
We establish an excess risk bound of O(H R_n^2 + R_n H L* ) for empirical risk minimization with an H-smooth loss function and a hypothesis class with Rademacher complexity R_n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R_n = R n , this translates to a learning rate of O(RH n) in the separable (L*=0) case and O(RH n + L^* RH n ) more generally. We also provide similar guarantees for online and stochastic convex optimization with a smooth non-negative objective. We study convergence properties of empirical minimization of a stochastic strongly convex objective, where the stochastic component is linear. We show that the value attained by the empirical minimizer converges to the optimal value with rate 1 n. The result applies, in particular, to the SVM objective. Thus, we obtain a rate of 1 n on the convergence of the SVM objective (with fixed regularization parameter) to its infinite data limit. We demonstrate how this is essential for obtaining certain type of oracle inequalities for SVMs. The results extend also to approximate minimization as well as to strong convexity with respect to an arbitrary norm, and so also to objectives regularized using other lp norms.