PaperlayerView exact revision on arXiv

Source-linked AI summary

Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

Aymeric Dieuleveut, Nicolas Flammarion, Francis Bach

arXiv:1602.05419v2math.OCcs.LGstat.ML

TL;DR

The paper asks how to optimize least-squares objectives when gradients contain stochastic noise, while achieving optimal prediction-error behavior. It introduces averaged accelerated regularized gradient descent, analyzes adaptation to finer Hessian and initialization structure, and tests tightness through non-parametric regression. The resulting method jointly achieves the stated optimal bias and variance rates, with bounds matching statistical lower bounds in broad non-parametric trade-offs.

  • Problem

    The paper studies stochastic optimization of quadratic least-squares objectives when gradients are observed only through a noisy, zero-mean finite-variance oracle.

  • Method

    It introduces averaged accelerated regularized gradient descent and analyzes finer dependence on initialization, Hessian structure, and non-parametric regression settings.

  • Results

    The algorithm jointly attains optimal bias and variance rates, while its non-parametric single-pass bounds match known statistical lower bounds across many bias–variance trade-offs.

  • Takeaways & Limitations

    The method is robust to structured least-squares gradient noise and can adapt to fast covariance decay or large-norm optimal predictors.

  • Takeaways & Limitations

    The accelerated analysis assumes additive noise and population covariance knowledge; extensions to least-mean squares and mini-batches remain open directions.

Abstract

from arXiv · show

We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves jointly the optimal prediction error rates for least-squares regression, both in terms of forgetting of initial conditions in O(1/n 2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small while the " optimal " terms above are large. In order to characterize the tightness of these new bounds, we consider an application to non-parametric regression and use the known lower bounds on the statistical performance (without computational limits), which happen to match our bounds obtained from a single pass on the data and thus show optimality of our algorithm in a wide variety of particular trade-offs between bias and variance.

1 Introduction

The paper studies stochastic optimization for least-squares regression and introduces an averaged accelerated method that jointly attains optimal bias and variance rates. Finer analyses and non-parametric results show adaptation beyond worst-case dimension-dependent bounds.

  • Large-scale supervised learning problems commonly use low-cost gradient iterations because high-dimensional problems are difficult to solve precisely.
  • The stochastic oracle adds zero-mean finite-variance error to the gradient, making noise covariance and initialization central to performance.
  • Accelerated gradient descent achieves the optimal bias rate L∥θ0−θ∗∥2/n2, while averaged gradient descent achieves the optimal variance rate proportional to σ2d/n.
  • Averaged accelerated gradient descent jointly attains optimal rates for both bias and variance while providing robustness to gradient noise.
  • Additional regularization adapts bounds to finer assumptions on initialization and the Hessian, producing dimension-free quantities when d or L∥θ0−θ∗∥2 is large relative to n.
  • In non-parametric regression, the algorithm’s single-pass bounds match known computationally unrestricted statistical lower bounds across many bias–variance trade-offs.

2 Least-Squares Regression

The paper formulates least-squares regression in a Euclidean space and analyzes stochastic gradient methods under additive and multiplicative/additive gradient oracles. It develops assumptions and algorithmic structures used to study averaged and accelerated methods.

  • Two oracle types are considered: additive noise independent of the iterate, and multiplicative/additive noise arising from a single observed data pair.
  • The framework minimizes a least-squares objective over a d-dimensional Euclidean space using i.i.d. observations.
  • The population covariance matrix Σ is the Hessian of the objective, with invertibility obtained by restricting to the minimal subspace containing the covariates.
  • Eigenvalue-decay assumptions based on tr Σb provide dimension-free convergence quantities, with b→0 recovering dimension dependence and b=1 giving the weakest assumption.
  • Bounds can depend on ∥Σr/2(θ0−θ∗)∥, linking initialization to covariance ill-conditioning and allowing finer assumptions than dependence on ∥θ∗∥ alone.
  • The paper analyzes stochastic gradient descent, accelerated stochastic gradient descent, and online averages of their iterates.
  • The multiplicative component makes the practical single-observation oracle harder to analyze than the additive oracle, while the additive setting corresponds to known population covariance.

3 Averaged Stochastic Gradient Descent

This section derives convergence bounds for regularized averaged stochastic gradient methods under additive and fully stochastic least-squares oracles. The bounds separate bias and variance, recover ridge-regression behavior, and support single-pass performance with practical step-size constraints.

  • Regularization extends averaged stochastic gradient descent and enables tighter convergence rates, while the quadratic structure permits a simpler direct proof.The analysis treats additive noise first and multiplicative/additive noise second.
  • Bias and variance: The bias combines regularization error with optimization error, respectively depending on λ^2 and (γn)^−2.The regularization component arises because the algorithm minimizes the regularized objective rather than the true function.
  • Statistical performance: The method matches fixed-design empirical risk minimization while requiring only a single pass over the data.For λ = 0, the variance rate is optimal over all estimators using the same information, even without computational limits.
  • Bias and variance: The variance term depends on gradient noise and is bounded using γ tr[Σ(Σ + λI)−1ξn ⊗ξn] for unstructured noise.This bound is useful when the noise is not structured.
  • Multiplicative/additive noise: Under the fully stochastic oracle, an additional residual term appears, vanishing as γ tends to zero, while the variance term remains unchanged.The resulting bounds use fewer assumptions and an efficient single-pass algorithm.
  • Multiplicative/additive noise: The fully stochastic setting requires γ ≤ 1/(2R^2), whereas additive noise permits γ ≤ 1/(L + λ), which may be much larger.Here L is the spectral radius of Σ and R^2 is of the order of tr(Σ), making γ proportional to 1/R^2 a practical choice.

4 Accelerated Stochastic Averaged Gradient Descent

This section analyzes averaged accelerated stochastic gradient descent for quadratic objectives, showing accelerated bias decay while preserving robustness to gradient noise.

  • Algorithm and analysis: Averaged accelerated stochastic gradient descent is rewritten as a constant-coefficient second-order iterative system under the stochastic oracle.The analysis applies to regularized quadratic objectives and constant step sizes satisfying γ(Σ + λI) ≼ I.
  • Algorithm and analysis: The convergence bound is independent of the momentum coefficient δ and valid for every regularization parameter λ ≥ 0.For λ = 0, the method yields a particularly simple averaged recursion with δ = 1.
  • Bias convergence: γn^2∥θ0 − θ∗∥2 recovers the usual accelerated bias rate, which is optimal for first-order quadratic optimization when n ≤ d.Averaging recovers the traditional non-strongly-convex accelerated rate even with λ = 0 and δ = 1.
  • Noise robustness: The second bound matches the optimal statistical variance term τ^2d/n, yielding joint bias/variance optimality.The result is stated in terms of the noise scale τ^2 and the initial-distance quantity ∥θ0 − θ∗∥2.
  • Adaptivity: Under hidden strong convexity, the method can eventually converge linearly, although the displayed accelerated rate is O(1/n^2).The method does not need to know the strong-convexity parameter to exploit this behavior.
  • Noise robustness: Acceleration improves the bias term without degrading the variance term, making the accelerated method robust to stochastic gradient noise.This robustness contrasts with the high noise sensitivity of some second-order methods for singular quadratic problems.

5 Tighter Convergence Rates

This section refines the standard dimension- and distance-based rates using regularization and spectral assumptions, producing adaptive bounds that can remain small in difficult regimes.

  • Adaptive regimes: The algorithm is independent of r and b, so the bounds hold simultaneously across regularity and effective-dimension choices once γ is selected.This gives adaptation to the problem’s regularity and effective dimension.
  • Variance refinement: For b > 0 and fast eigenvalue decay, the variance bound can be much smaller than the standard variance term, although its dependence on n may worsen.For b = 0, the standard variance term is recovered.
  • Bias refinement: For r = 0 the standard bias term is recovered, while stronger source assumptions yield faster bias decay until saturation at the n^-2 rate.The admissible range is r ∈ [0,1] for uniform averaging because the bias cannot forget initial conditions faster than n^-2.
  • Optimality: In finite dimensions, the bounds are not independently optimal asymptotically, but they become statistically optimal in kernel-based non-parametric learning.The next section uses statistical lower bounds to characterize this optimality.

6 Rates of Convergence for Kernel Regression

This section extends the convergence analysis to kernel non-parametric regression, where averaged acceleration achieves optimal statistical rates across a broader range of spectral and smoothness trade-offs.

  • Kernel regression setting: Kernel least-squares regression is formulated in an RKHS using feature maps, turning expected square-loss minimization into an infinite-dimensional linear regression problem.The regression target is the conditional expectation, while the RKHS solution is characterized through the covariance operator Σ.
  • Averaged accelerated SGD: Averaged accelerated SGD reaches the optimal rate under assumptions A6 and A7 for a broader region of source and spectrum parameters than averaged SGD.The paper’s rates match statistical rates for suitable b and r.
  • Rate behavior: As b → 0 and r → −1, the rate recovers the finite-dimensional n^-1 rate.The exponent b + 1 − r lies between 0 and 1 and improves with stronger assumptions.
  • Averaged accelerated SGD: The accelerated rate is optimal when r ≤ b + 1/2; beyond this region, the rate is limited to n^-2(1-r).The restriction follows from the upper bound on γ, which limits how quickly the bias can decrease.
  • Averaged accelerated SGD: Acceleration is uniquely optimal in the region b < r ≤ b + 1/2, extending optimality toward more ill-conditioned problems.Unaccelerated averaged methods have the narrower condition r ≤ b.
  • Practical limitations: Without additional assumptions on the kernel, the accelerated RKHS algorithm cannot be computed under computational limits because covariance-operator images are unavailable.The paper nevertheless uses the result to establish statistical optimality.
  • Practical limitations: The optimal step size depends on unknown parameters b and r, making its practical selection an open problem.This limitation concerns implementation of the theoretically optimal tuning rather than the convergence analysis itself.

7 Experiments

The synthetic experiments separate bias and variance behavior, showing accelerated methods achieve O(1/n^2) bias decay while averaging is needed for convergence under noise.

  • Experimental setup: The synthetic problem uses d = 25, eigenvalues 1/i^3, unit signal-to-noise ratio, γ = 1/R^2, λ = 0, and averages results over 10 replications.The experiments compare AvSGD, AccSGD, and the novel AvAccSGD on deterministic and purely stochastic problems.
  • Bias: For bias, AvSGD converges at O(1/n), whereas AvAccSGD and AccSGD converge at O(1/n^2).The deterministic problem isolates the effect of the initial error.
  • Variance: For variance, AvSGD and AvAccSGD converge at O(1/n), while AccSGD oscillates instead of converging to the optimum.AvSGD is slightly faster at the beginning in the variance experiment.
  • Bias–variance trade-off: When the bias term exceeds the variance term, bias can dominate at small n even though variance dominates asymptotically.The experiments support the need for a method that is optimal in both regimes.

8 Conclusion

The paper concludes that stochastic averaged accelerated gradient descent is robust to structured least-squares noise and remains effective under finer covariance and initialization assumptions, while identifying several extensions.

  • Stochastic averaged accelerated gradient descent is robust to structured gradient noise in least-squares regression.
  • The method is jointly optimal for bias and finite-dimensional variance under the paper’s least-squares setting.
  • Finer assumptions can yield dimension-free quantities when covariance matrices decay quickly or optimal predictors have large norms.
  • The current analysis is limited to least-squares regression, although it could be directly extended to smooth losses through efficient online Newton methods.
  • The analysis assumes additive noise and single observations per iteration; mini-batches may affect the bias term while leaving the variance term unchanged.
  • Extending the analysis to all smooth or self-concordant-like functions and to least-mean-squares robustness remains open.

A Proof of Section 3

The proof analyzes regularized stochastic-gradient recursions for quadratic objectives through linear closed-form dynamics, separating deterministic and stochastic contributions and bounding their moments.

  • Quadraticity makes the recursions linear, allowing θ_n − θ* to be obtained in closed form.
  • For λ ≥ 0 and γ(Σ + λI) ≼ I, the regularized stochastic-gradient recursion is rewritten into a form suitable for analysis.
  • The proof evaluates the average by computing its component sums separately and then combining the resulting terms.
  • Martingale square-moment inequalities reduce the variance calculation to a sum of variances for independent noise terms with covariance V = Eξ_n ⊗ ξ_n.
  • The analysis uses positive-definite matrix ordering and bounds such as I − (I − γΣ − γλI)^(n−k)^2 ≼ I.
  • A scalar inequality for 1 − (1 − u)^n handles cases where ∥Σ^−1(θ_0 − θ*)∥ may be infinite.

A.3 Proof when the noise is not structured

When gradient noise is not structured, the proof replaces the structured-noise bound with a more general matrix inequality and obtains a variance upper bound that remains meaningful in this setting.

  • The structured-noise bound becomes less informative when the noise is not structured.
  • The proof uses I − (I − γΣ − γλI)^(n−k)^2(Σ + λI)^−1 ≼ (n − k)γI to derive a general variance upper bound.
  • The resulting upper bound is meaningful when the noise is not structured.

B Proof of Theorem 1

The theorem proof decomposes the averaged accelerated method’s error into regularization, computation, and variance components, then bounds these terms using linear-system and operator arguments.

  • The proof decomposes the error into three main terms and studies each term separately.
  • The target quantity is ∥Σ^1/2(¯θ_n − θ*)∥, bounded independently for an expected-covariance recursion and its deviation from the actual recursion.
  • Conditional-expectation bounds use E(Σ − x_n ⊗ x_n | F_{n−1}) = 0 and the assumption E[(x_n ⊗ x_n)^2] ≤ R^2Σ.
  • The variance bound recovers the optimal variance term as γ tends to zero.
  • The noiseless component is expressed through the iterates θ_i − θ* = M(i,1)(θ_0 − θ*) and used to bound n^2E∥Σ^1/2(¯θ_n − θ*)∥^2.
  • The accelerated recursion is treated as a second-order linear system under γ(Σ + λI) ≼ I, with its average represented using powers of the transition matrix F.
  • The variance analysis uses martingale square-moment inequalities and V = E[Ξ_n ⊗ Ξ_n] for independent noise terms.
  • The two bias terms arise from regularization and computation, while the third term is the variance contribution.

C.2 Asymptotic expansion

The analysis approximates the averaged iterates through the spectrum of a second-order linear system, separating regularization, bias, and variance contributions. It then controls exponentially decaying remainders to obtain the theorem’s final bound.

  • Asymptotic decomposition: The asymptotic analysis treats powers of F as exponentially decaying and isolates the dominant error terms.The approximation ignores terms containing F^j, while the remainders are analyzed separately for the rigorous result.
  • Asymptotic decomposition: The error decomposition contains separate regularization, bias, and variance terms.The regularization computation is exact, while the bias and variance terms are analyzed through the eigenspaces of F.
  • Variance term: The dominant variance contribution can be written as a trace involving C, V, and (I − F)^−1.When C commutes with Σ, this trace simplifies to tr c(γΣ + γλI)^−1v(γΣ + γλI)^−1.
  • Final bound: The resulting theorem combines the independently bounded terms and uses V ≼ τ^2Σ together with λ^1/2(Σ+λI)^−1/2 ≼ I.The proof carefully controls the exponentially small remainder terms before establishing the final bound.
  • Spectral analysis: The eigenspace analysis reduces the dynamics to two-dimensional recursions governed by the eigenvalues of F.Depending on the discriminant, each reduced matrix has distinct complex eigenvalues, a coalescent eigenvalue, or two real eigenvalues; the analysis focuses on the first two cases.
  • Refined bounds: Finer regularized quantities yield tighter, potentially dimension-free bounds, while choosing γ = (λn)^−1 produces a stated corollary with a residual term.The residual vanishes for r ≤ 0 and is absent for r ≥ 0.

D.2.2 Theorem 3

Theorem 3 follows from the preceding theorems through algebraic bounds on regularized spectral quantities. Its proof analyzes the complex-eigenvalue expressions using trigonometric identities and elementary matrix inequalities.

  • Matrix bounds: The matrix inequalities rely on simultaneous diagonalization and positivity of a Cauchy matrix and its Hadamard product.This establishes the required operator comparison used in the theorem’s proof.
  • Technical caveat: The inverse of (Σ+λI)⊗I + I⊗(Σ+λI) is not necessarily non-decreasing under the semidefinite order.The remark attributes this to the fact that ≼ is not a total order on symmetric matrices.
  • Complex-eigenvalue bounds: The complex-eigenvalue bounds are obtained by rewriting real expressions with sine and cosine identities before bounding their separate terms.The analysis studies dependence on ρ and ω and applies elementary inequalities to the resulting expressions.
Loading 1602.05419v2…