Smoothness, Low Noise and Fast Rates

Nathan Srebro, Karthik Sridharan, Ambuj TewariNeurIPS 2010 · OpenReview

Introduction: The Quest for Fast Rates

In statistical learning theory, a fundamental question is how quickly the "excess risk"—the gap between a learned model's performance and the best possible performance within a hypothesis class—diminishes as the number of training samples ($n$) increases. Historically, these rates have fallen into two distinct regimes:

  1. The $1/\sqrt{n}$ "Slow" Rate: This is the standard baseline for general settings, particularly for "scale-sensitive" (non-parametric) classes like kernel methods or high-dimensional linear predictors.
  2. The $1/n$ "Fast" Rate: This rate is typically reserved for "parametric" classes with finite VC dimension, often under the assumption of "separability" (where at least one model in the class achieves zero error).

This paper addresses a critical gap in this landscape: Can we achieve fast rates for non-parametric, scale-sensitive classes? The authors demonstrate that the smoothness of the loss function is the key to unlocking these "optimistic" learning rates, allowing for a graceful interpolation between $1/n$ and $1/\sqrt{n}$ based on the inherent noise of the problem.

The Power of Smoothness and Self-Bounding

The core of the authors' approach lies in the property of $H$-smoothness. A loss function is considered $H$-smooth if its derivative is Lipschitz continuous, meaning its second derivative is bounded by a constant $H$.

The mathematical leverage provided by smoothness comes from a "self-bounding" property of non-negative smooth functions: the magnitude of the gradient is bounded by the square root of the function value ($|f'(t)| \le \sqrt{4Hf(t)}$). This implies that as the loss approaches zero, the gradient (and thus the variance of the estimates) also vanishes. This property is absent in non-smooth losses like the hinge loss or absolute-value loss, where the gradient remains large even near the optimum.

Local Rademacher Complexity

To translate smoothness into tighter risk bounds, the authors employ Local Rademacher Complexity. Traditional analysis often looks at the complexity of the entire hypothesis class $\mathcal{H}$. However, as learning progresses, we only care about the subset of functions that perform well on the data.

By focusing on this "local" neighborhood of the optimal predictor, the complexity measure effectively shrinks as the training error decreases. When combined with the self-bounding property of smooth losses, this allows for much more refined bounds than global complexity measures would suggest.

Comparing Parametric and Scale-Sensitive Regimes

The paper's main theoretical contribution is an excess risk bound of: $$\mathbb{E}[L(\hat{h})] \le L^* + \tilde{O}\left(\frac{HR}{n} + \sqrt{ rac{HRL^*}{n}}\right)$$ where $R$ represents the complexity of the class, $H$ is the smoothness constant, and $L^*$ is the optimal risk (noise level).

This result highlights how smoothness enables "optimism": if the problem is separable ($L^*=0$), the rate becomes $O(1/n)$. As noise increases, the rate degrades gracefully toward $O(1/\sqrt{n})$. The following table summarizes how these rates vary across different loss properties and hypothesis class types:

Table 1: Comparison of excess risk bounds across different loss function properties and hypothesis class types.

As shown in the table, for $H$-smooth losses in the scale-sensitive regime, we achieve a rate that depends on $\sqrt{L^*/n}$. Crucially, the authors prove that for non-smooth Lipschitz losses, the $1/\sqrt{n}$ rate is unavoidable even in the separable case, marking smoothness as a prerequisite for fast rates in non-parametric settings.

Conclusion and Future Directions

This work establishes that smoothness is a fundamental driver of generalization performance. While the paper focuses on Empirical Risk Minimization (ERM), the authors extend these insights to Online and Stochastic Convex Optimization.

However, some challenges remain. The current bounds rely on "worst-case" Rademacher complexity, which may be overly pessimistic for certain classes like trace-norm constrained matrices. Additionally, the presence of polylogarithmic factors in the ERM bounds suggests room for further refinement. Despite these technical hurdles, the connection between smoothness and local complexity provides a foundational framework for understanding why modern, high-capacity models—often trained with smooth losses—can generalize so effectively.

Summary updated

Abstract

We establish an excess risk bound of O(H R<em>n^2 + sqrt{H L*} R</em>n) for ERM with an H-smooth loss function and a hypothesis class with Rademacher complexity R<em>n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R</em>n = sqrt{R/n}, this translates to a learning rate of ̃ O(RH/n) in the separable (L* = 0) case and O(RH/n + sqrt{L* RH/n}) more generally. We also provide similar guarantees for online and stochastic convex optimization of a smooth non-negative objective.
BibTeX
@inproceedings{srebro2010smoothness,
  author = {Nathan Srebro and Karthik Sridharan and Ambuj Tewari},
  title = {{Smoothness, Low Noise and Fast Rates}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=HJN8nP-dbB},
}
Figure