PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimistic Rates for Learning with a Smooth Loss

Nathan Srebro, Karthik Sridharan, Ambuj Tewari

arXiv:1009.3896v2cs.LG

TL;DR

The paper addresses guarantees that apply only to bounded-derivative losses and develops bounds for smooth losses instead. It relates smoothness to function values, derives ERM and optimization guarantees, and identifies fast rates alongside limits on Rademacher-complexity generalization.

  • Problem

    Existing guarantees apply only to loss functions with bounded derivative and are not directly applicable to the squared loss; the paper asks what bounds follow from controlling the second derivative instead.

  • Method

    The paper defines H-smoothness through an H-Lipschitz derivative, bounds derivatives using function values, and extends the analysis to vector smoothness for ERM and convex optimization.

  • Results

    A 1/n separable rate is possible, while for non-parametric classes the non-separable squared-loss rate of 1/√n is unavoidable; convex-optimization bounds avoid polylogarithmic factors.

  • Takeaways & Limitations

    When H is chosen so that L* is small, the optimistic bounds imply fast learning rates, including convergence as HR/n under the stated example.

  • Takeaways & Limitations

    The theorem cannot generally be restated using expected or empirical Rademacher complexity for squared loss, even under a uniform distribution with well-behaved expected complexity.

Abstract

from arXiv · show

We establish an excess risk bound of O(H R_n^2 + R_n \sqrt{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 = \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 with a smooth non-negative objective.

1 Introduction

The paper addresses limitations of Lipschitz-based learning guarantees by analyzing smooth losses and optimistic rates through Rademacher complexity. It also extends related guarantees to online and stochastic convex optimization.

  • Broader settings: The paper studies stochastic learning through ERM using Rademacher complexity and also analyzes online and stochastic optimization for non-negative smooth convex objectives.The optimization guarantees use norm properties rather than statistical complexity and are more restrictive because convexity is required.
  • Optimistic rates: For finite-dimensional classes with VC-subgraph dimension d, separability permits improvement from 1/√n to 1/n learning rates.Here separability means that some h ∈ H achieves zero risk, so L* = 0.
  • Optimistic rates: Optimistic rates scale roughly as 1/ε when L* = 0 or ε is not much smaller than L*, degrading to roughly 1/ε^2 only for much smaller excess errors.The associated sample complexity depends on the ratio (L* + ε)/ε.
  • Motivation and contribution: The classical Lipschitz-loss analysis can yield 1/√n excess-risk scaling even in the separable case for non-parametric classes.This motivates exploiting smoothness instead of relying only on a bounded first derivative.
  • Motivation and contribution: H-smooth non-negative losses can achieve a 1/n separable rate, including settings where the loss has bounded second rather than first derivative.This directly includes smooth losses such as the squared loss.
  • Broader settings: For smooth convex optimization over a domain bounded by B, average online regret and stochastic excess risk are bounded at O(HB^2/n + ...), without polylogarithmic factors.The framework also generalizes to smoothness and boundedness measured with respect to non-Euclidean norms.

2 Empirical Risk Minimization with a Smooth Loss

The section replaces first-derivative control for Lipschitz losses with second-derivative control for smooth, non-negative losses, yielding optimistic excess-risk guarantees for ERM. Its proof uses local Rademacher complexity, while the result requires worst-case complexity and retains confidence-related boundedness terms.

  • Scope and limitations: The analysis specifically uses worst-case Rademacher complexity, and the theorem cannot generally be restated using expected or empirical complexity for squared loss.The paper identifies this as a contrast with Lipschitz bounded losses and leaves Lipschitz-and-smooth losses as an open question.
  • Setup: H-smoothness means the loss derivative is H-Lipschitz, equivalently |φ′′| ≤ H when twice differentiable.This smoothness condition is used instead of directly assuming a global first-derivative bound.
  • Key intuition: A non-negative H-smooth function has a derivative bounded by its function value, so small loss near the optimum implies a small local derivative.This observation motivates restricting analysis to behavior around the ERM.
  • Main guarantee: Theorem 1 gives a high-probability excess-risk bound for any H-smooth non-negative loss using the hypothesis class’s worst-case Rademacher complexity.The theorem assumes the loss difference is bounded by b and holds uniformly over h with probability at least 1 − δ.
  • Rates: The resulting sample-complexity corollary guarantees L(ĥ) − L* ≤ ϵ with probability at least 1 − δ under a Rademacher-complexity bound.The stated sample requirement includes logarithmic factors and assumes the loss is bounded by b.
  • Proof strategy: The proof controls the locally restricted loss class through local Rademacher complexity rather than the unrestricted loss class.Lemma 2.2 obtains an r-dependent complexity bound using smoothness, covering numbers, and fat-shattering dimensions.

3 A Sharp Understanding of Slow, Optimistic and Fast Rates

This section compares slow, optimistic, and fast rates across parametric and scale-sensitive classes and across loss-function geometries. It argues that the stated n-dependencies are unavoidable through explicit lower-bound constructions.

  • Comparison framework: Table 1 compares excess-risk bounds for parametric and scale-sensitive classes under Lipschitz, smooth, and strongly convex losses.The comparison is stated up to polylogarithmic factors.
  • Lower bounds: For non-parametric scale-sensitive classes, the section tests whether the n-dependencies in the summarized bounds are unavoidable.The lower bounds use ℓ2-bounded linear predictors with dimension allowed to grow with n.
  • Lower bounds: An infinite-dimensional Lipschitz-loss construction with L* = 0 leaves at least n of 2n unseen signs after n samples, forcing nonzero loss for some learner.The construction uses absolute difference loss and uniformly sampled standard basis vectors.
  • Lower bounds: A squared-loss construction examines the infinite-dimensional, smooth, non-separable case even though squared loss is 2-smooth and 2-strongly convex.The distribution uses random Gaussian labels conditional on uniformly sampled basis vectors.
  • Lower bounds: For a finite-dimensional smooth but non-strongly-convex loss, with probability at least 0.25 the empirical minimizer selects the wrong sign and incurs excess risk greater than 0.4q.The construction uses d = 1 and a 1-smooth loss that is quadratic near the correct prediction and linear farther away.

4 Online and Stochastic Optimization of Smooth Convex Objectives

The section extends optimistic-rate analysis from ERM to online and stochastic convex optimization with smooth, non-negative objectives, obtaining guarantees that support efficient one-pass methods and regularized batch optimization.

  • 4.1 Online Optimization Setting: Smoothness implies a self-bounding property for non-negative objectives, which underlies optimistic online-learning rates.The analysis generalizes scalar smoothness to vector-valued optimization over normed domains.
  • 4.1 Online Optimization Setting: Online Mirror Descent achieves optimistic average-regret guarantees for arbitrary instance sequences relative to the best comparator in hindsight.The comparator is constrained by the regularizer, and the stepsize depends on the optimal-loss bound.
  • 4.2 Stochastic Optimization I: Stochastic Mirror Descent: The online guarantee converts to an excess-risk bound for stochastic optimization when Mirror Descent runs on an i.i.d. sample.This setting recovers supervised-learning risk when instances are input-label pairs and the objective is a prediction loss.
  • 4.2 Stochastic Optimization I: Stochastic Mirror Descent: The stochastic optimization procedure requires a bound on L* to choose its stepsize.The paper explicitly identifies this quantity as necessary for the prescribed parameter choice.
  • 4.3 Stochastic Optimization II: Regularized Batch Optimization: Regularized empirical minimization obtains a similar excess-risk guarantee through expected-stability arguments rather than uniform stability.This avoids the uniform-stability rate limitation and uses a regularizer added to empirical loss.

5 Implications

The paper applies its smooth-loss framework to margin bounds, high-dimensional regression, and sparse prediction, illustrating improved rates and regime-dependent behavior.

  • 5.1 Improved Margin Bounds: Non-smooth ramp-loss analyses retain a 1/√n rate in the separable case, whereas the paper uses a smooth ramp to obtain faster margin bounds.The smooth ramp is 4γ^2-smooth and relates margin loss to zero-one loss.
  • 5.1 Improved Margin Bounds: Theorem 6 gives a simultaneous margin bound for every γ > 0 and every h in a bounded hypothesis class.The bound applies generically to hypothesis classes satisfying the theorem’s boundedness condition.
  • 5.2 Understanding the Bounds: In the asymptotic Gaussian regression regime, excess risk behaves as dσ^2/n and depends to first order on dimensionality rather than B.The paper explains this as parametric complexity eventually dominating scale-sensitive complexity.
  • 5.2 Understanding the Bounds: For ridge regression, the expected excess risk passes through random, low-noise, slow, and asymptotic regimes as sample size increases.The low-noise regime behaves as B^2/n, while the asymptotic regime behaves as d/n.
  • 5.3 Sparse Prediction: For sparse prediction, entropy-regularized stochastic mirror descent achieves the same performance guarantee as regularized batch optimization in the stated setting.The result requires a good predictor using a small number of fairly uncorrelated features, rather than a well-specified sparse optimum.

6 Discussion

The discussion distinguishes optimistic rates from fast rates and identifies limits of replacing worst-case Rademacher complexity with expected or empirical complexity for smooth losses.

  • 6 Discussion: Optimistic rates include an L*HR/n term relative to fast rates, although they yield O(HR/n) when L* is smaller than R.The distinction concerns the dependence on optimal risk in the excess-risk bound.
  • 6 Discussion: Rewriting the bound shows that L(hat h) − 1.01L* converges at rate HR/n when a = 0.01.The paper notes that this can imply fast learning rates in practice when L* is small.
  • 6 Discussion: The theorem uses worst-case Rademacher complexity rather than expected or empirical Rademacher complexity.For Lipschitz losses, analogous guarantees can use the latter complexity notions, but the smooth-loss extension is not generally available.
  • 6 Discussion: For squared loss with trace-norm constraints, meaningful generalization in terms of expected or empirical Rademacher complexity is not possible in the cited setting.The paper leaves optimistic rates for Lipschitz-and-smooth losses in expected or empirical complexity as an open direction.

A Relating Covering Numbers, Fat Shattering Dimension, and Rademacher Complexity

The appendix relates covering numbers, fat-shattering dimensions, and worst-case Rademacher complexity through a sequence of quantitative bounds.

  • A Relating Covering Numbers, Fat Shattering Dimension, and Rademacher Complexity: The appendix establishes relationships among L2 covering numbers, L∞ covering numbers, fat-shattering dimensions, and Rademacher complexity.These relationships support the main proof by allowing movement between complexity measures.
  • A Relating Covering Numbers, Fat Shattering Dimension, and Rademacher Complexity: L2 and L∞ covering numbers quantify the size of minimal covers over samples, with L∞ coverage controlling maximum pointwise deviation.The L∞ definition requires every function to have a cover element within ε on all sampled points.
  • A Relating Covering Numbers, Fat Shattering Dimension, and Rademacher Complexity: The fat-shattering dimension at scale ε is the largest number of points that the class can ε-shatter using witnesses.Shattering requires realizing every sign pattern with deviations of at least ε/2 from the witnesses.

A.1 The Refined Dudley Integral: Bounding Rademacher Complexity with L2 Covering Numbers

This section relates empirical Rademacher complexity to sample-specific L2 covering numbers through a refined Dudley integral and chaining argument.

  • Refined Dudley integral: The refined Dudley integral bounds empirical Rademacher complexity using L2 covering numbers for the sampled function class.The bound is stated for arbitrary function classes and is based on refinements of the classical Dudley integral.
  • Chaining: Chaining approximates each function at progressively finer cover scales and expresses it through successive cover differences.For each scale, a cover element approximates the function, while differences between consecutive scales are controlled separately.
  • Finite-class control: Massart’s finite class lemma controls the Rademacher contribution of each cover-difference class.The argument applies the lemma to differences between adjacent covers and combines the resulting bounds across scales.
  • Scale selection: The proof selects a truncation scale based on the cover radii and then takes an infimum over the free parameter.The construction uses a scale threshold defined through the sequence of cover radii before optimizing the resulting inequality.

A.2 Bounding L∞covering number by Fat-shattering Dimension

This section bounds L∞ covering numbers through discretization and the fat-shattering dimension, showing that discretized covers also cover the original bounded class.

  • Covering-number bound: Lemmas and propositions connect L∞ covering numbers of a bounded hypothesis class to its fat-shattering dimension.The section states the relevant covering-number and fat-shattering results and supplies proofs for the needed form.
  • Discretization: α-discretization replaces each function value by a nearby grid point, with pointwise error at most α/2.The discretization is defined over the bounded interval [−B, B] and applied pointwise to every function.
  • Cover transfer: A minimal α/2-cover of the discretized class provides an L∞ cover at scale α for the original class.The discretization error combines with the cover error to establish the final scale-α cover.
  • Shattering transfer: The proof transfers shattering from the discretized class back to the original class using the α/2 approximation guarantee.The same witness values certify α-shattering by the original hypothesis class after accounting for discretization error.

A.3 Relating Fat-shattering Dimension and Rademacher complexity

This section relates fat-shattering dimension to Rademacher complexity, yielding a scale-dependent dimension bound above the complexity threshold.

  • General relation: For any ε > R_n(H), the fat-shattering dimension is bounded by the sample size n.This threshold condition is used to construct a repeated sample and apply Rademacher arguments.
  • Typical complexity rate: When R_n(H) = √(R/n), fat_ε(H) ≤ 4R/ε^2.This gives the typical scale-sensitive dimension estimate in terms of the class parameter R and scale ε.
  • Proof construction: The proof repeats shattered points to form a larger sample and uses the functions witnessing the shattering structure.Rademacher signs and the corresponding witness functions are then used in the argument.
  • Sample-size control: The final comparison uses monotonicity of Rademacher complexity as the sample size increases within n ≤ n′ ≤ 2n.The enlarged sample remains within a constant factor of the original sample size.

B Proof of Lemma 2.2

The proof of Lemma 2.2 moves from Rademacher complexity to covering numbers, exploits smoothness for a radius-dependent cover, and returns to Rademacher complexity.

  • Proof of Lemma 2.2: The proof uses a refined Dudley bound to control the loss-class Rademacher complexity through empirical L2 covering numbers.This is the first step in the proof pipeline.
  • Key lemma: The smoothness inequality follows from the self-bounding property and is the key property used in the proof.The appendix proves the inequality by applying the mean value theorem and splitting into two cases.
  • Smoothness step: Smoothness and the self-bounding property yield an r-dependent L2 cover of the empirically restricted loss class.For non-negative H-smooth functions, squared differences are controlled by the function values and squared input differences.
  • Complexity conversion: The L∞ covering number of the hypothesis class is bounded through fat-shattering dimension and then through Rademacher complexity.The proof invokes the covering-number and fat-shattering lemmas to complete this complexity conversion.
  • Integral control: The remaining integral is split into ranges and bounded using the fat-shattering estimates before substitution into the main inequality.The proof selects γ through a fat-shattering condition and combines the resulting integral bounds.
Loading 1009.3896v2…