Generalization Properties and Implicit Regularization for Multiple Passes SGM

Motivation

• Generalization properties of practical SGM variants remain relatively little understood, especially when multiple passes over the data are used.Earlier work often focused on one pass, while the generalization role of multiple passes was less clear.Source: §1 · p. 1
• Least-squares results do not directly extend to the broader setting of possibly non-smooth convex loss functions.The paper therefore targets a setting where the loss need not be smooth.Source: §1 · p. 1

Contribution

• Without penalties or explicit constraints, SGM performance relies on a bias-variance trade-off controlled by the step-size and number of passes.These parameters therefore act as implicit regularization rather than explicit penalization or constraints.Source: §1 · p. 2

Method

• The paper studies two main variants: one pass with tuned step-size, or fixed step-size with an appropriately tuned number of passes.Cross-validation can implement adaptive choices, but the variants entail different computations.Source: §1 · p. 2

Results

• Both algorithm variants achieve optimal results, although the first requires multiple single-pass SGM runs and the second uses early stopping.Numerical experiments complement the theoretical analysis.Source: §1 · p. 2

Learning Setting

• The learning problem uses an unknown distribution over X × Y and seeks a function minimizing expected risk.The associated empirical-risk formulation is also introduced.Source: §2 · p. 2
• Functions are linearly parameterized through a feature map into a finite- or infinite-dimensional Hilbert space.The formulation includes infinite dictionaries and reproducing-kernel Hilbert spaces.Source: §2 · p. 3
• The framework includes kernel methods by taking Φ(x)=K(x, ·) in the reproducing-kernel Hilbert space associated with a positive definite kernel.This gives the corresponding reproducing property representation.Source: §2 · p. 3

Stochastic Gradient Method

• SGM initializes at w1=0 and updates using independent uniformly sampled training indices, a non-increasing step-size sequence, and a stopping rule.The stopping time may exceed the sample size, allowing the data to be reused across multiple passes.Source: §2 · p. 3
• The analysis estimates expected excess risk for the last or averaged iterate and studies how step-size and stopping choices affect those estimates.Expectations are taken over the sampling sequence and then over the training sample.Source: §2 · p. 3

3 Implicit Regularization for SGM

• The section develops a universal convergence result, smooth- and non-smooth-loss finite-sample bounds, and implicit regularization strategies for SGM.Its convergence analysis imposes conditions on both step-sizes and iteration counts.Source: §3 · p. 3, §3.1 · p. 4

3.1 Convergence

• Under Assumption 1, consistency requires appropriately chosen step-sizes and running iterations, with parameter choices yielding different implicit regularization strategies.The analysis permits more than one pass over the data; alternatively, fixed step-sizes can be paired with a suitable stopping rule.Source: §3.1 · p. 4

3.2 Finite Sample Bounds for Smooth Loss Functions

• A result characterizes the excess risk of both the last and average iterates, while its error bounds comprise three terms related to sample error, computational error, and another term.Source: §3.2 · p. 5
• Balancing sample, computational, and approximation errors makes both step-sizes and iteration counts regularization parameters, yielding four corresponding strategies.Stopping too late can increase sample error, whereas stopping too early can increase approximation error, producing a bias-variance trade-off that may require more than one pass.Source: §3.2 · pp. 5–6
• A suitably tuned step-size can achieve good performance with one pass, whereas fixed step-sizes generally require multiple passes unless β = 1.The constant and decaying step-size choices achieve the same bounds, but the constant choice can require fewer iterations; when β = 1, the rates are O(m^-1/2).Source: §3.2 · pp. 6–7
• For smooth losses, hold-out cross-validation can adaptively achieve the rate in (9).The approximation properties are otherwise unknown, motivating data-driven parameter selection.Source: §3.2 · p. 7

3.3 Finite Sample Bounds for Non-smooth Loss Functions

• For non-smooth losses such as hinge loss, analogous finite-sample results hold, although current bounds are less sharp.The resulting bounds yield explicit error estimates and stopping rules; the bound in (11) is slightly worse than that in (9).Source: §3.3 · pp. 7–8
• A constant step-size 1/√m can stop earlier than a decaying step-size, while one-pass SGM realizes regularization through the step-size.The section also gives corresponding one-pass choices, including t∗ = m for the stated corollaries.Source: §3.3 · p. 8

3.4 Discussion and Proof Sketch

• The proof decomposes excess risk into generalization, computational, and approximation errors, then balances them through the step-size and number of passes.The analysis uses intermediate iterates, controls computational error for averaged and last iterates, and treats almost minimizers when exact minimizers may not exist.Source: §3.4 · pp. 8–9
• For the considered function space, the obtained bound is optimal because it matches the best available Tikhonov-regularization bound, while the corresponding non-smooth bound is not sharp.Source: §3.4 · p. 9
• The analysis leaves accelerated iterations, sharper or high-probability bounds, and online parameter tuning as directions for future work.The paper uses a simple iteration and a simple cross-validation strategy, while online tuning is reported as possible in the capacity-independent setting [15].Source: §3.4 · p. 9

4 Numerical Simulations

• Experiments use benchmark datasets, hinge loss, ten repetitions, and hold-out cross-validation with an 80%-20% training-validation split.Source: §4 · p. 10

4.1 Regularization in SGM and SIGM

• SIGM reaches minimum test error before 20 passes, after which error significantly increases, illustrating pass-count regularization.Source: §4.1 · p. 10
• Decaying step-size SIGM shows no overfitting in the first 100 passes but converges more slowly to the optimum.Source: §4.1 · p. 10
• For fixed-step SGM, η = 1 overfits whereas η = 10^-3 is associated with oversmoothing, confirming step-size regularization.Source: §4.1 · p. 11
• For decaying-step SGM, θ = 0 leads to overfitting, while larger θ such as θ = 1 has a regularization effect.Source: §4.1 · p. 11

4.2 Accuracy and Computational Time Comparison

• SGM and SIGM achieve comparable test errors to LIBSVM, except decaying-step SIGM consistently has higher test errors.Source: §4.2 · p. 11
• SGM and SIGM have roughly equal training times, outperform LIBSVM in speed on relatively large datasets, and are comparable or slightly slower on small datasets.Source: §4.2 · p. 11

A Basic Lemmas

• The proofs rely on convexity of V(y, ·) and boundedness of V′_−(y, a).Source: A Basic Lemmas · p. 14
• Lemma 1 bounds the update using convexity of V and the difference between losses at w and w_k.Source: A Basic Lemmas · p. 14
• Lemma 2 takes expectation over the sampled index using independence of w_k and j_k conditional on z.Source: A Basic Lemmas · p. 14

B Sample Errors

• The target is the excess generalization error E[E(w_T) − inf_w∈F E(w)], whose generalization-empirical difference is called sample error.Source: B Sample Errors · p. 14
• Uniform sample-error bounds over BR use symmetrization and Rademacher complexity.Source: B Sample Errors · p. 14
• The bounds are assembled by iterating one-step inequalities over k = 1, ..., t and combining sample-error estimates.Source: B Sample Errors · pp. 15–16
• Under Assumptions 1 and 3, when η_t ≤ 2/(κ^2L), for every (x, y) ∈ z, V(y, ⟨·, Φ(x)⟩) is (κ^2L)-smooth and (κa0)-Lipschitz, and the results follow directly from Theorems 2.2 and 3.8 from [11].Source: B Sample Errors · p. 16

C Excess Errors for Weighted Averages

• Lemma 7 assumes a nondecreasing sequence {b_k > 0}_k to control the iterated sequence underlying the excess-error bound.Source: C Excess Errors for Weighted Averages · pp. 16–17
• Theorem 1 is obtained by combining Lemma 5's condition with Lemma 7 and dividing the resulting inequality by the cumulative weights.Source: C Excess Errors for Weighted Averages · p. 17
• The analysis compares iterates with an approximately optimal w_ε and then lets ε approach zero.Source: C Excess Errors for Weighted Averages · p. 17
• Proposition 1 follows by summing weighted one-step inequalities, taking expectations over J(T) and z, and applying the stated condition.Source: C Excess Errors for Weighted Averages · pp. 16–18

• The convergence analysis expresses the excess generalization error through weighted averages and moving averages of the iterates.Source: D From Weighted Averages to the Last… · p. 18
• The first decomposition term is a weighted excess generalization error, while the second consists of moving averages that are bounded separately.Source: D From Weighted Averages to the Last… · p. 19
• Lemma 10 bounds the relevant iterate differences using independence of earlier iterates from later sampled indices and a stability condition.Source: D From Weighted Averages to the Last… · p. 19
• Proposition 2 combines the decomposition bounds to obtain a convergence guarantee for the last iterate under Lemma 8’s assumptions.Source: D From Weighted Averages to the Last… · p. 20
• The resulting theorem proofs rely on Propositions 1 and 2 together with a non-increasing step-size sequence and bounds on weighted sums.Source: D From Weighted Averages to the Last… · pp. 20–21

• The analysis introduces basic estimates and combines Theorems 2 and 3 to obtain explicit convergence-rate propositions and corollaries.Source: E Explicit Convergence Rates · pp. 21, 23, 24
• Because constants 1/(1−θ) and 1/(1−q) diverge as θ or q approaches 1, the paper introduces complementary results to avoid these factors.Source: E Explicit Convergence Rates · p. 22
• For η_t = ηt^-θ, the resulting bounds depend on θ, with distinct behavior involving t^(1−θ)/(1−θ), log t + 1, or θ/(θ−1).Source: E Explicit Convergence Rates · pp. 21, 23
• The rates incorporate sample-error terms whose forms differ between the weighted-average and last-iterate analyses.Source: E Explicit Convergence Rates · p. 24
• The corollaries instantiate the propositions with specific choices of θ and η to derive rates for several parameter regimes.Source: E Explicit Convergence Rates · pp. 24–25
• Several derived bounds include logarithmic and power-law factors in t and m, as shown in the stated corollary inequalities.Source: E Explicit Convergence Rates · pp. 24–26