Introduction
Empirical Risk Minimization (ERM) is the foundational workhorse of machine learning. A central question in statistical learning theory is how quickly a model's performance on training data (empirical risk) converges to its performance on unseen data (expected risk). For generic convex functions, this generalization gap typically shrinks at a rate of $O(1/\sqrt{n})$. For strongly convex functions, it accelerates to a "fast rate" of $O(1/n)$.
This paper investigates exp-concave loss functions—a broader, more complex class that includes linear regression, logistic regression, squared hinge-loss SVMs, and portfolio selection. The authors provide the first proof that ERM achieves an optimal fast generalization rate of $O(d/n)$ for exp-concave and smooth losses, where $d$ is the dimensionality and $n$ is the number of samples.
The Theoretical Gap
Previously, it was known that specific, computationally expensive online algorithms (like the Online Newton Step) could achieve a fast rate of $O(d/n)$ for exp-concave losses. However, it remained unclear if the simpler and widely used ERM approach could match this performance. Prior bounds for ERM on exp-concave losses were either stuck at the slow $O(1/\sqrt{n})$ rate or burdened by an extraneous $\log n$ factor.
By eliminating this ubiquitous $\log n$ penalty, the authors demonstrate that ERM is not only statistically optimal but also practically advantageous. Because ERM can be solved using highly efficient, state-of-the-art solvers (like SVRG or SDCA), proving its statistical optimality justifies using these fast solvers for large-scale exp-concave problems instead of relying on complex online-to-batch conversions.
Methodological Innovations
The authors analyze a slightly regularized ERM procedure. Instead of the standard "heavy" penalty of $O(1/\sqrt{n})$, they apply a "light" penalty of $O(1/n)$—just enough to ensure a unique solution without washing out the underlying signal.
The core proof relies on Stability Analysis. A model is considered stable if removing a single random data point from the training set does not significantly alter the resulting model. The technical breakthrough lies in leveraging Local Strong Convexity. While exp-concave functions are not strongly convex everywhere, they exhibit strong convexity locally when evaluated through a "local norm" based on the curvature (Hessian) at a specific point.
By bounding the average leave-one-out stability using these local norms and the Sherman-Morrison identity (a technique for updating matrix inverses), the authors strictly control the model's fluctuations. Notably, they prove that "average stability" is sufficient for exp-concave functions, bypassing the much stricter requirement of "uniform stability" used in previous proofs.
Key Results and Implications
- Optimal $O(d/n)$ Bound: For $\alpha$-exp-concave and $\beta$-smooth losses, the expected excess risk of the regularized ERM solution is strictly bounded by $O(d/n)$.
- Matching Lower Bounds: In specific cases like squared loss (linear regression), this result perfectly matches the known theoretical lower bound of $\Omega(d/n)$, confirming ERM's absolute optimality in this setting.
- State-of-the-Art Improvement: The findings improve upon the best-known rates for the Online Newton Step by a factor of $\log n$, and for algorithms like Vovk-Azoury-Warmuth by a factor of $\log(n/d)$.
- Oblivious Adaptivity: ERM naturally adapts to the "easiness" of the problem without requiring prior knowledge of the specific data distribution properties.
Limitations and Future Directions
As a purely theoretical work, the paper relies on mathematical proofs rather than empirical benchmarks. The authors note several open challenges for future research:
- The Smoothness Requirement: The current proof necessitates a smooth loss function (Lipschitz continuous gradient). It remains an open question whether ERM can achieve fast rates for non-smooth exp-concave losses, a setting where some online algorithms currently succeed.
- High-Probability Bounds: The established rates hold "in expectation." Extending these $O(1/n)$ rates to high-probability guarantees (e.g., proving the rate holds with 99% certainty) without sacrificing the fast convergence rate is a significant next step.
- Regularization-Free ERM: While the $O(1/n)$ regularizer is minimal, proving that ERM can achieve these rates without any regularization across all exp-concave functions remains an open problem.
Summary updated