Papers › Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and...
Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n²)-type of Risk Bounds
Lijun Zhang, Tianbao Yang, Rong Jin
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 O(d/n + √(F_*/n)) risk bound when the random function is nonnegative, convex and smooth, and the expected function is Lipschitz continuous, where d is the dimensionality of the problem, n is the number of samples, and F_* is the minimal risk. Thus, when F_* is small we obtain an O(d/n) risk bound, which is analogous to the O(1/n) optimistic rate of ERM for supervised learning. Second, if the objective function is also λ-strongly convex, we prove an O(d/n + κF_*/n ) risk bound where κ is the condition number, and improve it to O(1/[λn²] + κF_*/n) when n=Ω(κd). As a result, we obtain an O(κ/n²) risk bound under the condition that n is large and F_* is small, which to the best of our knowledge, is the first O(1/n²)-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 O(1/[λn²] + κF_*/n) risk bound for supervised learning, the Ω(κd) requirement on n can be replaced with Ω(κ²), which is dimensionality-independent.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
No code repository is listed for this paper in the archive or in Syntology's graph.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
| Task | Dataset | Model | Metric | Value | Rank at snapshot | Leaderboard | Report |
|---|---|---|---|---|---|---|---|
| Image Classification | Colored-MNIST(with spurious correlation) | MLP-ERM | Accuracy | 17.10 | #5 of 6 | Archive leaderboard | report |
Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections