PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic gradient descent with initial regularization

Nabil Kahalé

arXiv:2608.22953v1cs.LGmath.OCstat.ML

TL;DR

The paper asks how SGDIR can achieve dimension-free excess-risk guarantees while retaining favorable behavior relative to ridge regression. It analyzes SGDIR under noiseless and noisy squared-loss settings, obtaining fast rates, matching lower bounds in some regimes, and an instance-based comparison with ridge regression. The conclusions remain bounded by explicit assumptions and an unresolved comparison question.

  • Problem

    The paper studies dimension-free learning guarantees for SGDIR, motivated by the need to analyze stochastic-gradient methods when feature spaces are very large or infinite.

  • Method

    The paper analyzes averaged and non-averaged SGDIR under moment, source, and capacity assumptions, and compares its expected excess risk instance-by-instance with ridge regression.

  • Results

    When r = 1/2, SGDIR achieves bounds of order m^-2 log^2 m; when r = 1, it achieves m^-3+ε for any ε > α^-1, while its noisy risk is no larger than ridge regression's up to log^2 n.

  • Takeaways & Limitations

    The paper reports convergence rates under comparable assumptions that no existing algorithm had previously been shown to achieve, plus a near-ridge comparison for SGDIR.

  • Takeaways & Limitations

    The paper leaves open whether a similar SGDIR–ridge comparison holds beyond the stated setting, and identifies closing the upper–lower-bound gap for r > 1/2 as future work.

Abstract

from arXiv · show

We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order $m^{-2}\log^{2}m$, where the number of training samples is of order $m$. For another value of the source parameter, we obtain, for any $ε>0$, bounds of order $m^{-3+ε}$, provided that the capacity parameter exceeds $ε^{-1}$. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.

1 Introduction

The paper studies SGDIR, a stochastic-gradient method with initial regularization, in dimension-independent settings where feature spaces may be very large or infinite. It derives excess-risk bounds, lower bounds, and comparisons with ridge regression under stated assumptions.

  • Problem and approach: SGDIR applies initial regularization before continuing with unregularized stochastic gradient updates, using averaged and non-averaged estimators.The regularization parameter is active for an initial phase, after which the recursion corresponds to standard SGD.
  • Main contributions: Dimension-free upper bounds for averaged and non-averaged SGDIR are strictly sharper than existing bounds in some regimes or hold under weaker assumptions.The results target expected excess risk under moment, source, and capacity conditions.
  • Main contributions: For noisy problems, explicit parameter choices make SGDIR's expected excess risk at most log^2 n times ridge regression's, improving to log n or a constant in specified regimes.The comparison requires λ of order 1/n or larger; the factor becomes log n when λ is of order √log n/n or larger, and constant in the noiseless case when λ is of order (log n)/n or larger.
  • Main contributions: A new minimax lower bound matches the upper bound up to a polylogarithmic factor for a range of source-parameter values.The lower-bound exponent depends only on the source parameter.

2 Notation and main Assumptions

The paper formulates least-squares learning in a separable Hilbert space, defines covariance-based excess risk, and imposes moment, noise, source, capacity, and step-size conditions. It motivates SGDIR through its regularized initial phase and analyzes bias–variance structure.

  • Notation: The covariance operator Σ is positive semidefinite, self-adjoint, and trace-class, with an orthonormal eigenbasis used to express spectral assumptions.The notation includes powers of Σ and regularized operators such as Σ + λI.
  • Assumptions: The assumptions include moment and noise controls, together with source and capacity conditions that govern the stated convergence bounds.Bounded features imply a moment condition, while bounded or independent residuals provide corresponding noise controls.
  • SGDIR intuition: During its initial phase, SGDIR performs SGD on a regularized objective, then switches to unregularized SGD after the initial regularization period.The regularized Hessian has smallest eigenvalue at least Λ, motivating faster early contraction under suitable choices.
  • SGDIR intuition: The informal intuition is that initial regularization moves the iterate toward a regularized minimizer before later unregularized updates, but this argument is not used formally.The paper explicitly qualifies this as an informal explanation.
  • Risk analysis: Expected excess risk decomposes into a covariance-weighted squared bias and variance, and averaging independent estimator copies provides a corresponding risk bound.This decomposition is used to organize the analysis of estimators of θ∗.
  • RKHS specialization: The main RKHS specialization assumes θ∗ belongs to the RKHS, although the authors state that the results can be extended beyond this assumption.The RKHS represents functions through a positive-definite kernel with bounded diagonal evaluations.

3 Bounding the expected excess risk

This section develops expected excess-risk bounds for noiseless and noisy SGDIR, including averaged iterates and independent-copy averages. The analysis combines bias, variance, and effective-dimension quantities under stated assumptions.

  • 3.1 The noiseless process: The noiseless analysis defines a process with w_0 = 0 by replacing y_t with ⟨x_t, θ∗⟩, yielding w_t = θ_t almost surely.
  • 3.1 The noiseless process: E[R(w_N)] ≤ 16R(θ_Λ) when Λ ≥ log(m)/(γm), consistent with the interpretation that w_m is close to θ_Λ.
  • 3.1 The noiseless process: Theorem 1 provides a third bound on E[R(w_N)] that essentially combines two generally incomparable bounds.
  • 3.2 Incorporating noise: For noisy SGDIR, Theorem 2 bounds the squared bias and variance of the averaged iterate and its independent-copy averages.
  • 3.2 Incorporating noise: Var_Σ(δ̄_2m:3m) ≤ 8γσ^2Λ̃, which is of order σ^2d/m when H has finite dimension d.

4 Convergence results

The paper derives noiseless SGDIR convergence rates under capacity and source assumptions, then compares them with prior SGD and kernel-ridge bounds. The rates improve across source regimes but saturate for sufficiently large source parameters.

  • 4.1 Capacity and Source assumptions: The capacity assumption μ_i ≤ ci^-α uses α to quantify eigenvalue decay; larger α indicates stronger capacity and can correspond to lower effective dimension.
  • 4.1 Capacity and Source assumptions: The source assumption θ∗ = Σ^r v∗ holds automatically for r = -1/2 with ρ∗ = 2R(0), while larger r imposes stronger alignment.
  • 4.2 Implications on Convergence: Theorem 3 and Corollary 1 derive convergence bounds for E[R(w_N)] under moment, source, and capacity conditions with Λ = log(m)/(γm).
  • 4.2 Implications on Convergence: m^-2 log^2 m is obtained when r = 1/2, while E[R(w_N)] converges strictly faster than m^-2 when r > 1/2 and α > 1.
  • 4.2 Implications on Convergence: E[R(w_N)] = O(m^-3+ε) for any ε > α^-1 when r = 1, but values of r > 1 do not improve the Corollary 1 bounds.
  • 4.3 Relation with previous work: Unlike preceding bounds that saturate for r ≥ 1/2, the SGDIR bounds saturate only for r ≥ 1; convergence of the last iterate remains future work.
  • 4.3 Relation with previous work: For 0 < r < 1/2, the averaged and non-averaged SGDIR bounds are either sharper than existing bounds or hold under weaker assumptions.

5 Comparison with ridge regression

The paper compares SGDIR with ridge regression through operator inequalities and derives an instance-based excess-risk comparison under moment assumptions. With suitable regularization, SGDIR matches ridge regression up to logarithmic factors.

  • Proof strategy: The analysis establishes operator Jensen-type and trace inequalities to lower-bound terms involving empirical and population covariance operators.Lemma 6 handles the operator analogue of a scalar convexity argument, while Lemma 7 lifts scalar inequalities to trace inequalities.
  • Comparison setup: SGDIR and ridge regression are compared using expected excess-risk bounds under Assumptions A1 and Acm.The comparison uses m=n/3 so both estimators consume roughly the same number of samples.
  • Main comparison: For λ of order 1/n or larger, SGDIR’s expected excess risk is bounded by ridge regression’s up to a log^2 n factor in noiseless and noisy cases.The result holds for a suitable choice of γ.
  • Regularization regimes: In the noiseless case, the comparison gap reduces to a constant factor when λ is of order (log n)/n or larger.
  • Regularization regimes: In the noisy case, the gap reduces to a log n factor when λ is of order √log n/n or larger.

6 Lower bound

The lower-bound analysis studies minimax expected excess risk in an infinite-dimensional Hilbert-space setting. It constructs two admissible noiseless distributions that are difficult for any estimator to distinguish, yielding a theorem-level lower bound and explicit scope caveats.

  • Construction: The proof constructs two noiseless pairs satisfying the assumptions while generating identical training samples with constant probability.This indistinguishability makes it difficult for any learning algorithm to distinguish the two distributions.
  • Construction: The construction uses a one-hot distribution for x and chooses between two target vectors along an eigenbasis direction.The resulting pairs satisfy the moment and source assumptions with σ=0.
  • Lower-bound statement: Theorem 5 gives a minimax lower bound on expected excess risk for any measurable estimator based on n training samples.The construction assumes r≥−1/2, σ=0, and nµ1>tr[Σ].
  • Scope caveat: For r<0, the constructed responses are unbounded, so the lower bound may not apply when boundedness of y is imposed.This is especially relevant for α≥1 and −1/2<r≤0.
  • Relation to prior bounds: The lower bound matches Dieuleveut and Bach’s noisy upper bound of order n^−2r−1 when 2αr<−1, up to a polylogarithmic factor more generally.

7 Numerical experiments

Numerical experiments evaluate SGDIR, SGD, ridge regression, and kernel ridge regression on synthetic and real data. The observed slopes and comparisons broadly align with the theoretical rates, while SGDIR remains computationally feasible at a scale where KRR overflows memory.

  • Experimental design: The experiments evaluate multiple SGD variants, SGDIR, ridge regression, and KRR over repeated random training runs.Each estimator is evaluated over 5 × 10^5/n independent runs, with n random training samples per run.
  • Synthetic experiments: Synthetic experiments use d=2000 Gaussian inputs with covariance Σ=diag(i^−α) and noiseless responses, using step size γ=1/R2.Figure 1 reports average test error as a function of n.
  • Synthetic experiments: For n≤d in the synthetic setting, ridge regression outperforms SGDIR and uses an optimal λ of order 10^−6 or smaller.Ridge error is not reported for n≥d because it is essentially zero when λ=0.
  • Synthetic experiments: The observed log-log slopes for tail-averaged SGDIR are −1.75, −1.98, and −2.33 across the three Figure 1 panels.These slopes are compared with the theoretical rates implied by Corollary 1 and the discussion in Section 4.1.
  • Real-data experiments: On the MSD dataset with n=3 × 10^4, tail-averaged SGDIR achieves average test error 84.07 in 260 seconds per run, while KRR overflows memory.KRR’s O(n^2) space requirement causes the reported memory overflow.
  • Real-data experiments: Figure 3 reports ratios of SGDIR to ridge-regression expected risks, with observed values at most 3, consistent with the O(log^2 n) bound under suitable conditions.The plotted ratios use n values from Figure 2 and a reference SGDIR estimator trained on 14000 samples.
  • Real-data experiments: The elevators dataset suggests that the theoretical requirement λ* of order 1/n or larger is not satisfied in practice.

8 Conclusion

The paper derives dimension-free SGDIR risk bounds, establishes a matching lower bound in several regimes, and compares noisy SGDIR with ridge regression. It also identifies open directions beyond the current assumptions and squared-loss setting.

  • SGDIR yields dimension-free expected excess-risk upper bounds for averaged and non-averaged methods.
  • The bounds are strictly sharper than existing ones or require weaker assumptions, and saturation occurs only for r ≥ 1 rather than r ≥ 1/2.
  • m^-2 log^2 m bounds hold at r = 1/2, while m^-3+ϵ bounds hold at r = 1 for any ϵ > α^-1.
  • A lower bound of order m^(-2r−1) matches the upper bound up to a log^2 m factor when −1/2 ≤ r ≤ 1/2.
  • Whether the comparison extends to SGD, and how SGDIR applies beyond squared loss or machine learning, remain open questions.
  • For noisy problems, SGDIR has expected excess risk no larger than ridge regression up to a log^2 n factor when regularization is of order 1/n or larger.

A Preliminary inequalities

This section develops operator inequalities used in the proofs, including bounds for powers of self-adjoint operators and a way to combine compatible upper bounds.

  • The analysis rewrites the recursion using P_t = I − γ(x_t ⊗ x_t + λ_tI) and its expectation A_t = I − γ(Σ + λ_t).
  • The proofs use common orthonormal eigenbases, independence between iterates and update operators, and the condition γλ_t ≤ 1.
  • For suitable self-adjoint operators, the lemmas establish inequalities involving powers, eigenvalues, and positive-semidefinite order.
  • When operators commute, Lemma 12 combines bounds 0 ≼ B ≼ C and 0 ≼ B ≼ D through CD(C + D)^−1.

B Proof of Lemma 1

The proof of Lemma 1 separates bias and variance, controls their evolution through operator recursions, and combines the resulting bounds into an excess-risk estimate.

  • Variance analysis defines ϵ_t = w_t − E[w_t] and uses independence of ϵ_t and P_t to control covariance recursively.
  • The expected iterate follows a recursion centered at θ_Λ = Σ(Σ + Λ)^−1θ*, enabling bias analysis.
  • For 0 ≤ t ≤ m, the bias satisfies ||E[w_t] − θ_Λ|| ≤ (1 − γΛ)^t||θ_Λ||.
  • After t ≥ m, the distance ||E[w_t] − θ*|| does not exceed its value at t = m.
  • The proof combines bias–variance decomposition with operator inequalities to obtain the lemma’s bound.

C Proof of Lemma 2

The proof of Lemma 2 establishes covariance bounds for the stochastic iterates and then combines alternative operator bounds to control averaged-iterate quantities.

  • Independence and zero-mean properties remove cross terms when decomposing stochastic updates into propagated error and update noise.
  • The covariance C_t = E[ϵ_t ⊗ ϵ_t] is bounded simultaneously by scalar and covariance-operator expressions.
  • Lemma 12 combines bounds involving Σ and regularized operators to produce a uniform covariance control for t ≥ m.
  • The iterate can be represented as w_t = M_tθ* with M_t independent of θ*, allowing covariance bounds to be converted into operator inequalities.
  • The argument uses induction and operator comparisons related to prior SGD covariance analyses.

F Proof of Theorem 2

The proof derives operator inequalities under bounded self-adjointness assumptions and combines intermediate bounds with earlier lemmas to obtain the stated results. It also controls the expected error relative to θ∗ after sufficiently many iterations.

  • Proof of Theorem 2: For t ≥ 2m, the expected iterate satisfies ||E[wt] − θ∗||Σ ≤ 2||A_m mθ∗||Σ.This bound is then used with convexity of Σ to imply equation (15).
  • Proof of Theorem 2: Equation (16) follows by combining an intermediate bound with Lemma 3 and a stated operator relation.The passage does not include the intermediate bound or relation explicitly.
  • Proof of Theorem 2: Lemma 19 applies to operators satisfying 0 ≼ B and 0 ≼ I−B ≼ A ≼ I, yielding B ≼ 4A−1BA−1.The proof establishes these conditions using B = I−(V+I)−1 and A = (V+I)−1/2P−1(V+I)−1/2, with P = E[(U+I)−1].
  • Proof of Theorem 2: Operator Jensen’s inequality is used because X 7→ (X+I)−1 is operator convex on positive semidefinite self-adjoint operators.The resulting bounds rely on 0 ≼ (U+I)−1 ≼ I and (V+I)−1 ≼ P ≼ I.
Loading 2608.22953v1…