Unified Optimal Analysis of the (Stochastic) Gradient Method

1 Introduction

• The study considers convergence of SGD with unbiased gradient estimates for convex, continuously differentiable functions under μ-convexity and a generalized smoothness assumption.The μ-convexity condition is stated with respect to the optimum and is weaker than standard convexity or strong convexity, which require the inequality for arbitrary pairs.Source: §1 · p. 1

1.1 Contribution

• A simpler proof gives the result up to polylogarithmic factors and relies only on constant stepsizes.The paper describes this as a simpler alternative to its main result.Source: §1.1 · p. 2
• Suitable stepsizes and an appropriately defined average iterate yield the known stochastic rates, while the deterministic and interpolation cases recover exponential convergence up to a factor of 4 in the exponent.The analysis also recovers best-known rates for the squared distance of the last iterate to the optimum.Source: §1.1 · p. 2

1.2 Related Work

• Earlier bounds by Bach and Moulines (2011) and Needell et al. (2016) achieve the same rate up to polylogarithmic factors, but cover only iterate distance.The paper presents its result in a slightly more general setting.Source: §1.2 · p. 2
• Bounded-gradient analyses are not optimal when σ² = 0, whereas the smoothness condition discussed here allows nontrivial zero-noise cases and faster rates.The paper also notes that adapting an earlier averaging proof to its relaxed assumptions gives a nonoptimal dependence on the initial distance.Source: §1.2 · p. 2

• The gradient-descent example recovers the best-known function-value convergence rate.Source: §2 · p. 3
• The stochastic example recovers best-known last-iterate rates without a bounded-gradient assumption.Source: §2 · p. 3
• The growth conditions described in the examples are also covered by Assumption 2.Source: §2 · p. 3
• For finite-sum empirical risk, a uniformly sampled component gradient is an unbiased gradient oracle.The objective is a sum of convex, L-smooth component functions.Source: §2 · p. 3
• When every component loss has zero gradient at the optimum, interpolation gives σ^2 = 0 and SGD recovers linear convergence.Source: §2 · p. 3

• With constant stepsizes, the expected squared distance contracts by 1 − µγ per iteration while adding a γ^2σ^2 term.Source: §3 · p. 4
• The intermediate result reduces the initial-error term toward a σ^2/µ-neighborhood of the optimum.Source: §3 · p. 4
• A carefully chosen stepsize is needed to obtain a guarantee for arbitrary accuracy.Source: §3 · p. 4
• This result does not establish function-value convergence, and its ˜O notation hides logarithmic factors.The following section addresses both issues.Source: §3 · p. 4

4 Convergence Analysis Part II—Solving the Recursion

• The recursion covers the SGD setting by substituting squared distance, expected function suboptimality, curvature, noise variance, and smoothness parameters.The substitutions are r_t = ||x_t − x⋆||², s_t = E f(x_t) − f⋆, a = µ, b = 1, c = σ², and d = 2L.Source: §4 · p. 5

Constant Stepsizes (with Log Terms).

• A constant stepsize gives a suboptimal solution of the recursion with logarithmic terms.The lemma uses weights w_t = (1 − aγ)^−(t+1) and a weighted average iterate.Source: Constant Stepsizes (with Log Terms) · p. 5

Decreasing Stepsizes (Avoiding Log Terms).

• The decreasing-stepsize scheme combines an initial unaveraged phase with suffix averaging for the remaining iterations.The proposed two-phase scheme spends T/2 iterations without averaging before switching to suffix averaging.Source: Decreasing Stepsizes (Avoiding Log… · p. 5
• The section also records a recursion lemma for the special case a = 0, described as a sublinear-rate case.The theorem’s proof applies the recursion lemmas with a = µ, c = σ², and d = 2L, and uses convexity to relate the averaged function value to the average of function values.Source: Decreasing Stepsizes (Avoiding Log… · pp. 5–6

5 Discussion

• The analysis recovers best-known rates for SGD function-value suboptimality at an average iterate and distance to the optimum at the last iterate.It also recovers exponential convergence rates in the deterministic setting.Source: §5 · p. 6
• The framework is limited to strongly convex functions; extending it to larger function classes is left as future work.Assumption 1 also prevents immediate application to approximate gradient oracles that are not generally unbiased.Source: §5 · p. 6
• Implementing the schemes requires knowledge of T and the problem parameters µ, L, and σ for stepsize and averaging choices.The passage notes that a doubling trick can remedy some of these knowledge limitations.Source: §5 · p. 6

A.1 Constant Stepsizes (with Log Terms).

• The proof rearranges the inequality and multiplies both sides by w_t.This prepares the terms for summation.Source: §A.1 · p. 9
• Summing from t = 0 to T produces a telescoping sum.Source: §A.1 · p. 9
• The proof tunes γ by considering two cases, then combines them to conclude the lemma.Source: §A.1 · p. 9

A.2 Decreasing Stepsizes (Avoiding Log Terms).

• Lemma 6 treats the constant-stepsize recursion by relaxing it and unrolling the resulting relation.Source: §A.2 · pp. 9–10
• The related decreasing-stepsize result requires attention to initial conditions because the stepsizes cannot be chosen arbitrarily large.Source: §A.2 · p. 10
• The proof for the decreasing-stepsize result chooses stepsizes and weights for integer T, then checks cases involving the restart condition.Source: §A.2 · pp. 10–11

A.3 Sub-linear Convergence rate

• The proof rearranges (8), sums from t = 0 to T, and then carefully selects γ.Source: §A.3 · p. 11