PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Rates for Multi-pass Stochastic Gradient Methods

Junhong Lin, Lorenzo Rosasco

arXiv:1605.08882v3cs.LGmath.OCstat.ML

TL;DR

The paper asks how stochastic gradient learning should choose step-size, stopping time, and mini-batch size when multiple data passes are allowed. It develops a unified square-loss analysis for stochastic and batch methods, showing that early stopping with a universal step-size can attain optimal rates, including in non-attainable settings. The results also show that larger mini-batches permit larger step-sizes while preserving optimal statistical accuracy.

  • Problem

    The generalization effects of multiple passes and mini-batches, especially beyond worst-case assumptions, were not fully characterized for stochastic gradient methods.

    Source: §1 · p. 1

  • Method

    The paper analyzes least-squares stochastic gradient methods with random gradients and mini-batches through a unified approach that relates stochastic sequences to batch gradient descent.

    Source: §1 · p. 2, §3.7 · p. 13

  • Results

    Multi-pass stochastic gradient methods with early stopping and a universal step-size achieve optimal convergence rates matching ridge regression, while mini-batches allow larger step-sizes.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The number of passes can serve as a practical regularization parameter, and mini-batches can support parallel computation while preserving optimal statistical accuracy.

    Source: §1 · p. 2, §3.3 · p. 8

    A conventional proof decomposition yields sub-optimal rates because it cannot fully exploit target regularity in the bias estimate, motivating a square-loss-specific decomposition.

    Source: §3.7 · p. 13

Abstract

from arXiv · show

We analyze the learning properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. We study how regularization properties are controlled by the step-size, the number of passes and the mini-batch size. In particular, we consider the square loss and show that for a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on a unifying approach, encompassing both batch and stochastic gradient methods as special cases. As a byproduct, we derive optimal convergence results for batch gradient methods (even in the non-attainable cases).

1. Introduction

The paper studies how multiple passes, step-size, and mini-batch size regulate stochastic gradient learning under square loss. It establishes optimal-rate guarantees for early-stopped multi-pass methods and extends convergence results to batch methods and non-attainable cases.

Motivation

  • Stochastic gradient methods are motivated by their combination of practical performance on large-scale problems and theoretical integration of statistical and computational aspects.This motivation contrasts them with approaches such as empirical risk minimization and Tikhonov regularization.Source: §1 · p. 1

Problem

  • The paper addresses the unclear generalization role of multiple passes and the previously unexamined effect of mini-batches in stochastic gradient methods.Earlier analyses often focused on one pass or worst-case settings and did not capture benign assumptions that can yield faster rates.Source: §1 · pp. 1–2

Contribution

  • Multi-pass stochastic gradient methods with early stopping and a universal step-size can achieve optimal convergence rates matching ridge regression under square loss.The number of passes acts as a regularization parameter, while larger mini-batches permit larger step-sizes without losing optimal learning bounds.Source: §1 · p. 2

Method

  • A unifying proof approach approximates the stochastic learning sequence by batch gradient descent, treating batch and stochastic methods together.The paper presents a novel error decomposition and uses the square-loss structure to obtain sharper bounds than a decomposition that upper-bounds the learning sequence.Source: §1 · p. 2

Novelty

  • The analysis covers attainable and non-attainable cases, including optimal batch gradient rates without extra unlabeled data.The non-attainable batch result matches prior optimal rates up to a logarithmic factor and may be the first such result without additional unlabeled data.Source: §1 · pp. 2–3

2. Learning with SGM

The paper formulates square-loss learning in a Hilbert-space setting and studies a mini-batch stochastic gradient method using repeated passes over sampled data. Its estimator is controlled by the step-size sequence, mini-batch size, and stopping time, without an explicit penalty or projection parameter.

2.1 Learning Problems

  • The learning problem minimizes square-loss risk over linear functions represented in a separable Hilbert space from an i.i.d. sample.The framework includes reproducing kernel Hilbert spaces as a special case and reduces to standard finite-dimensional linear regression.Source: §2 · p. 3, §2.1 · p. 3
  • The analysis measures estimator quality through excess risk under an unknown data distribution observed only through an i.i.d. sample.The setup introduces the distribution, its marginal and conditional measures, and assumptions on the input space before defining the empirical learning procedure.Source: §2.1 · p. 3

2.2 Stochastic Gradient Method

  • Unlike variants with explicit regularization or projection, the studied method requires no penalty or projection parameter to tune.Regularization is instead controlled through algorithmic choices such as stopping and step-size.Source: §2.2 · pp. 3–4
  • The algorithm uses mini-batch stochastic gradients with a non-increasing step-size sequence and samples indices uniformly and independently from the training set.The total iteration count can exceed the sample size, allowing the data to be processed over multiple passes.Source: §2.2 · p. 4
  • Mini-batch size selects the algorithmic regime: b = 1 gives simple stochastic gradient descent, whereas b = m gives a stochastic version of batch gradient descent.The paper focuses particularly on b = 1 and b = √m.Source: §2.2 · p. 4

3. Main Results with Discussions

This section formulates the assumptions and error decomposition underlying convergence guarantees for stochastic and batch gradient methods. It derives and discusses attainable and non-attainable rates, while characterizing how passes, step sizes, mini-batch size, and computational error regulate learning and relate SGM to batch GM.

3.1 Assumptions

  • The assumptions control output moments, approximation of the projected regression function fH by Hρ, and effective dimension, with larger ζ imposing stricter regularity and γ governing capacity.The framework includes the capacity-independent setting γ=1 and allows improved rates under polynomial eigenvalue decay.Source: §3.1 · p. 5

3.2 Optimal Rates for SGM and Batch GM: Simplified Versions

  • Under the stated assumptions, SGM achieves optimal learning bounds after p∗ passes, while mini-batches permit larger step-sizes without worsening the error rate.In the capacity-independent attainable case with fH ∈ Hρ, the error is O(m−1/2) with p∗=⌈√m⌉; batch GM also attains optimal rates, including the non-attainable case.Source: §3.2 · pp. 6–7

3.3 Main Results for SGM: Attainable Case

  • In the attainable case, the error bound decomposes into bias, sample variance, and computational variance, whose balance determines η, T, and b.The number of passes acts as regularization: too few increases bias, whereas too many increase sample error; early stopping or cross-validation can select the stopping rule.Source: §3.3 · pp. 7–8
  • Fixed-step-size SGM in the attainable case reaches rates optimal up to logarithmic factors, and both simple and mini-batch SGM require m^(1/(2ζ+γ)) passes.Mini-batch SGM allows a larger step-size, while the corresponding H-norm convergence rate is also optimal up to logarithmic factors.Source: §3.3 · pp. 8, 10

3.4 Main Results for SGM: Non-attainable Case

  • In the non-attainable case ζ<1/2, the main theorem gives high-probability SGM error bounds separately for 2ζ+γ>1 and 2ζ+γ≤1, with an extra logarithmic factor.The bounds use fixed step-sizes and depend on the problem parameters and, in the second regime, an additional ϵ.Source: §3.4 · p. 10
  • In the non-attainable case, SGM achieves rates m^(-2ζ/(2ζ+γ)) when 2ζ+γ>1 and m^(-2ζ(1−ϵ)) otherwise, up to logarithmic factors.With b=1 and η_t ≃ 1/m, the first regime has bound m^(-2ζ/(2ζ+γ)) log^4 m log^2(1/δ), while analogous mini-batch choices also satisfy these rates.Source: §3.4 · pp. 10–11

3.5 Main Results for Batch GM

  • Batch GM attains convergence guarantees under η_t ≃1 with stopping determined by 2ζ+γ, including the non-attainable optimal rates without extra unlabeled data.Theorem 4 is described as achieving the same optimal non-attainable rates as prior work up to a logarithmic factor and possibly being the first such result for batch GM.Source: §3.5 · p. 11, §3.6 · p. 12

3.6 Discussions

  • The derived SGM rates are comparable to prior one-pass results, improve them under broader regularity or capacity conditions, and match known capacity-independent rates in the stated regimes.For multi-pass SGM, larger step sizes and mini-batches can preserve optimal rates while reducing computational complexity; comparisons with incremental gradient methods also favor the derived capacity-dependent rates.Source: §3.4 · p. 11, §3.6 · p. 12
  • Every m iterations of SGM with η_t ≃m^-1 correspond to one batch-GM iteration with η_t ≃1, so SGM refines the batch regularization path and may stop earlier with larger steps.Ignoring computational error, the SGM bound can be smaller; larger SGM step sizes retain optimal rates while reducing computational complexity.Source: §3.6 · pp. 12–13

3.7 Proof Sketch (Error Decomposition)

  • The proof uses a novel error decomposition separating deterministic bias, sample variance, and computational variance, with the latter two estimated as the main technical contribution.A conventional decomposition yields suboptimal rates because it cannot fully exploit regression-function regularity, whereas the square-loss decomposition enables sharper bounds.Source: §3.7 · pp. 13–14
  • The population and sample iterations connect the ideal deterministic sequence to the stochastic learning sequence, allowing the decomposed error bounds to imply Theorems 1–3.The population iteration uses the input distribution, while replacing it with empirical data produces the implementable sample iteration and its associated stochastic sequence.Source: §3.7 · pp. 13–14

4. Preliminary Analysis

This section establishes the operator notation, concentration tools, and parameter dependencies used to derive the paper’s error bounds.

4.1 Notation

  • The operator framework uses a Hilbert space H, identity and expectation notation, operator norms, and products over iteration indices.Source: §4.1 · pp. 14–15
  • The analysis introduces sampling, adjoint, covariance, and empirical covariance operators for the Hilbert-space learning setting.Source: §4.1 · p. 15

4.2 Concentration Inequality

  • A Hilbert-space concentration lemma provides high-probability bounds for independent random variables under boundedness and variance conditions.Source: §4.2 · pp. 15–16

4.3 Basic Estimates

  • The subsequent bounds track step-size η_t, iterations T, regularization λ, sample size m, mini-batch size b, and failure probability δ.Source: §4.3 · p. 16

5. Estimating Bias and Sample Variance

The section separately controls approximation bias and sample variance, using square-loss structure and concentration arguments to obtain bounds across attainable and non-attainable regimes.

5.1 Bias

  • The proof uses spectral inequalities for compact positive operators to control powers of the covariance operator and derive the bias estimate.Source: §5.1 · p. 17
  • The bias analysis bounds the deterministic learning sequence under decaying step-sizes and operator assumptions, including attainable and non-attainable settings.Source: §5.1 · pp. 17–18

5.2 Sample Variance

  • The variance argument introduces regularized operator quantities and decomposes stochastic terms so that capacity assumptions can be exploited.Source: §5.2 · pp. 19–20
  • Under Assumptions 1, 2 and 3, Proposition 3 separately treats ζ ≥ 1/2 and ζ < 1/2 when η1κ2 ≤ 1, 0 < λ ≤ ∥Tρ∥, and the corresponding conditions hold.Source: §5.2 · pp. 21–22
  • Explicit sample-variance bounds follow for η_t = η_1t^-θ over all iterations, with high-probability guarantees under the stated assumptions.Source: §5.2 · pp. 23–24

6. Estimating Computational Variance

This section controls computational variance by relating stochastic updates to weighted empirical risks, then combines cumulative-error, empirical-risk, and weighted-factor bounds.

6.1 Cumulative Error

  • Computational variance is controlled through a sum of weighted empirical risks generated by the stochastic updates.Source: §6.1 · pp. 25–26

6.2 Bounding the Empirical Risk

  • The empirical-risk analysis exploits square-loss properties, weighted-average decompositions, independence, and recursive inequalities for expected risks.Source: §6.2 · pp. 26, 27, 30
  • A condition on the step-size sequence ensures the recursive empirical-risk bound remains stable across iterations.Source: §6.2 · pp. 29–30, §6.4 · p. 33

6.3 Bounding

  • Weighted factors involving empirical covariance operators are bounded using regularization conditions and operator-product estimates.Source: §6.3 · p. 31

6.4 Deriving Error Bounds

  • Theorem 6 combines these ingredients into high-probability computational-variance bounds for decaying step-sizes over all iterations.Source: §6.4 · pp. 32–33

7. Deriving Total Error Bounds

The total-error analysis combines bias, sample variance, and computational variance to establish high-probability rates for attainable, non-attainable, and batch-gradient settings.

7.1 Attainable Case

  • Theorem 7 provides general attainable-case error bounds for decaying step-sizes under the paper’s assumptions.Source: §7.1 · p. 34
  • The attainable-case proof selects regularization and verifies concentration conditions before combining the bias, sample-variance, and computational-variance estimates.Source: §7.1 · p. 34

7.2 Non Attainable Case

  • Theorem 8 extends the generalization-error bounds to the non-attainable case for ζ ≤ 1/2, with constants depending on the stated problem parameters.Source: §7.2 · p. 35
  • The non-attainable theorem yields the paper’s stated results by specializing the decay and capacity parameters.Source: §7.2 · p. 35

7.3 Batch GM

  • For batch gradient methods, Theorem 9 gives corresponding attainable and non-attainable bounds under fixed step-size choices.Source: §7.3 · p. 36

8. Convergence in H-norm

This section develops H-norm convergence results for the stochastic gradient algorithm with a fixed step-size sequence. The analysis uses error decompositions and supporting lemmas to establish the stated convergence theorem.

8. Convergence in H-norm

  • The section establishes convergence results in H-norm for the stochastic gradient algorithm with a constant step-size.The analysis focuses on the attainable case and fixes η_t = η for all t.Source: §8 · p. 36
  • The proof strategy is presented as a reusable procedure for deriving error decompositions and convergence bounds.Related intermediate steps repeatedly apply the same decomposition-based reasoning.Source: §8 · pp. 36–37
  • The analysis invokes a lemma under Assumption 2 for constant step-size η ∈ ]0, κ^-2] and ζ ≥ 1/2.This lemma supplies a technical bound used in the convergence analysis.Source: §8 · p. 36
  • A derived error decomposition combines several intermediate bounds to prove the main convergence theorem.The proof introduces auxiliary quantities before applying the decomposition.Source: §8 · pp. 36–37

9. Numerical Simulations

The simulations examine error decompositions on synthetic data and classification errors on BreastCancer. They show the regularization effect of additional passes and similar performance across simple, mini-batch, and batch methods.

Synthetic-data simulations

  • Figure 1 reports error decompositions for gradient-based algorithms on synthetic data with m = 100.The simulations use a Gaussian-kernel RKHS and compare mini-batch SGM, simple SGM, and batch GM under fixed step-size choices.Source: Figure 1 · p. 37, §9 · p. 38

BreastCancer experiment

  • Figure 2 reports training and testing misclassification errors for simple SGM, mini-batch SGM, and batch GM on the BreastCancer dataset.The three algorithms perform similarly in these experiments.Source: Figure 2 · p. 37, §9 · p. 38

Synthetic-data simulations

  • The synthetic-data experiments use mini-batch size b = √m with η_t = 1/(8√m), simple SGM with η_t = 1/(8m), and batch GM with η_t = 1/8.All three methods are evaluated in the same Gaussian-kernel setting.Source: §9 · p. 38
  • As passes increase, bias decreases while sample error increases, computational error remains negligible, and minimum total error occurs when bias and sample error balance.These observations illustrate the three terms in the error decomposition and the regularization role of the number of passes.Source: §9 · p. 38

A. Learning with Kernel Methods

This appendix formulates learning with kernel methods through an RKHS framework. It connects the general setting to standard linear regression in finite dimensions and gives a Sobolev-space example.

A. Learning with Kernel Methods

  • The kernel framework models i.i.d. data from an unknown distribution on an input-output space and represents functions in an RKHS.The input space is a closed subset of R^d and the output space is real-valued.Source: A. Learning with Kernel Methods · p. 38
  • A reproducing kernel defines the RKHS through kernel sections and satisfies f(ξ) = ⟨K_ξ, f⟩_K.This reproducing property links function evaluation to the RKHS inner product.Source: A. Learning with Kernel Methods · pp. 38–39
  • The Sobolev-space example uses X = [0,1] and a kernel whose induced space contains absolutely continuous functions vanishing at both endpoints.The functions also belong to L2(X).Source: A. Learning with Kernel Methods · p. 39
  • Kernel learning is expressed as a minimization problem whose formulation can be rewritten using the reproducing property.The rewrite replaces function evaluations with RKHS inner products.Source: A. Learning with Kernel Methods · p. 39
  • The formulation covers RKHS learning as a special case and reduces to standard linear regression in finite dimensions.The correspondence is obtained by identifying kernel sections with the inputs of the general learning setting.Source: A. Learning with Kernel Methods · p. 39

B. Further Corollaries for SGM in the non-attainable case

These corollaries give non-attainable-case error bounds for stochastic gradient methods under different mini-batch and step-size choices. They specify optimal stopping regimes across capacity conditions.

B. Further Corollaries for SGM in the non-attainable case

  • The non-attainable results are presented as direct consequences of Theorem 3.The section applies the theorem to several parameter regimes rather than introducing a separate proof strategy.Source: B. Further Corollaries for SGM in the… · p. 39
  • For b = 1, η_t ≃ m^(-1/(2ζ+γ)∨1), and T up to m^2, the corollary provides high-probability non-attainable-case bounds with separate capacity regimes.The stopping choices are T* = ⌈m^(1/(2ζ+γ))⌉ when 2ζ + γ > 1 and T* = ⌈m^(1+2ζ−ε)⌉ otherwise.Source: B. Further Corollaries for SGM in the… · p. 39
  • With b = m and η_t ≃ 1/log m, the optimal stopping exponents are T* = ⌈m^(1/(2ζ+γ))⌉ when 2ζ + γ > 1 and T* = ⌈m^(1−ε)⌉ otherwise.The bounds hold with probability at least 1 − δ under Assumptions 1–3.Source: B. Further Corollaries for SGM in the… · p. 39

C. Proofs for Lemmas

This material supplies proofs for the paper’s lemmas and proposition, using prior lemmas, assumptions, spectral arguments, norm inequalities, and iterative bounds. It also defines the principal operators, sequences, parameters, and stochastic-gradient notation used throughout the analysis.

C. Proofs for Lemmas

  • The cited proof fragments establish Proposition 2 and Lemmas 16 and 27, derive (33) and (34) using Lemmas 15 and 12, and invoke Assumption 2, spectral theory, and Hölder’s inequality.Source: C. Proofs for Lemmas · pp. 40–43
  • Several bounds are obtained by iterating relationships, applying the mean value theorem, and using inequalities such as Hölder’s and the triangle inequality.The proof fragments also use Assumptions 2 and 3 and parameters including κ and v to establish parts of the stated lemmas.Source: C. Proofs for Lemmas · pp. 40–43
  • The proof analysis estimates constants and covariance-related quantities, including B, σ2(w1), and centered operator terms measured with the Hilbert–Schmidt norm.These estimates are connected to the regularized operators Tρ + λ and the sampling operators appearing in the bounds.Source: C. Proofs for Lemmas · pp. 42–43

D. List of Some Notations

  • The notation section defines the hypothesis, input, output, and sample spaces; risks; the regression function; SGM iterates; mini-batch size; iteration limits; and step-size sequences.It also identifies λ as a regularization parameter and records the roles of random index sets and conditional expectations.Source: D. List of Some Notations · p. 44
  • The notation section specifies the regression and covariance operators, sampling operators and adjoints, eigenvalues, population and batch iterations, and regularized operators.These definitions establish the operator vocabulary used in the preceding proof bounds.Source: D. List of Some Notations · p. 44

Related papers

Loading 1605.08882v3…