PaperlayerView exact revision on arXiv

Source-linked AI summary

The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares

Rong Ge, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli

arXiv:1904.12838v2cs.LGmath.OCstat.ML

TL;DR

The paper asks how well SGD’s final iterate can perform for streaming least squares without iterate averaging. It establishes upper and lower bounds for polynomially decaying and Step Decay schedules, showing near-minimax fixed-horizon behavior for Step Decay but poor anytime behavior across stepsizes.

  • Problem

    The study addresses the limited understanding of SGD’s final iterate for streaming least squares, where prior minimax results primarily use iterate averaging.

  • Method

    The paper analyzes upper and lower bounds for SGD’s final iterate under polynomially decaying and geometrically decaying Step Decay schedules, with and without strong convexity.

  • Results

    For a fixed horizon, Step Decay is off the minimax rate by only a log(T) factor, whereas polynomial decay is condition-number or T-suboptimal; anytime final-iterate behavior is poor for every stepsize.

  • Takeaways & Limitations

    Final-iterate learning-rate design is substantially more nuanced than iterate-averaged analysis, with Step Decay effective in fixed-horizon least-squares settings.

  • Takeaways & Limitations

    The non-strongly convex Step Decay bound has a dimension-factor-worse initial-error rate than the best known iterate-averaged result, and broader-function extensions remain open.

Abstract

from arXiv · show

Minimax optimal convergence rates for classes of stochastic convex optimization problems are well characterized, where the majority of results utilize iterate averaged stochastic gradient descent (SGD) with polynomially decaying step sizes. In contrast, SGD's final iterate behavior has received much less attention despite their widespread use in practice. Motivated by this observation, this work provides a detailed study of the following question: what rate is achievable using the final iterate of SGD for the streaming least squares regression problem with and without strong convexity? First, this work shows that even if the time horizon T (i.e. the number of iterations SGD is run for) is known in advance, SGD's final iterate behavior with any polynomially decaying learning rate scheme is highly sub-optimal compared to the minimax rate (by a condition number factor in the strongly convex case and a factor of $\sqrt{T}$ in the non-strongly convex case). In contrast, this paper shows that Step Decay schedules, which cut the learning rate by a constant factor every constant number of epochs (i.e., the learning rate decays geometrically) offers significant improvements over any polynomially decaying step sizes. In particular, the final iterate behavior with a step decay schedule is off the minimax rate by only $log$ factors (in the condition number for strongly convex case, and in T for the non-strongly convex case). Finally, in stark contrast to the known horizon case, this paper shows that the anytime (i.e. the limiting) behavior of SGD's final iterate is poor (in that it queries iterates with highly sub-optimal function value infinitely often, i.e. in a limsup sense) irrespective of the stepsizes employed. These results demonstrate the subtlety in establishing optimal learning rate schemes (for the final iterate) for stochastic gradient procedures in fixed time horizon settings.

1 Introduction

The paper studies the final iterate of SGD for streaming least squares, contrasting polynomial decay with geometrically decaying Step Decay schedules in known-horizon and anytime settings. It finds that Step Decay approaches minimax rates for a fixed horizon, while polynomial decay can be substantially sub-optimal and anytime behavior remains poor.

  • Motivation: Final-iterate guarantees for smooth stochastic least squares are less mature than results relying on iterate averaging, motivating this study.The paper asks whether polynomial decay can achieve minimax rates without averaging and whether another schedule can do so.
  • Known horizon: Polynomial decay is off the minimax rate dσ2/T by a condition-number factor in strongly convex least squares.The result applies to ηt ∝ 1/t^α with α ∈ [0.5, 1].
  • Known horizon: Any polynomially decaying stepsize in the non-strongly convex case achieves no better than dσ2/T up to log factors, versus the minimax rate dσ2/T.
  • Known horizon: With a fixed end time T, Step Decay is off the statistical minimax rate by only a log(T) factor for both strongly convex and non-strongly convex least squares.A refined decay scheme can improve the strongly convex dependence to log of the condition number.
  • Anytime behavior: In the anytime setting, stochastic gradient procedures must query sub-optimal final iterates infinitely often for strongly convex least squares.The sub-optimality is nearly a condition-number factor in a limsup sense.
  • Empirical validation: Experiments on CIFAR-10 residual-network training find that continuous Step Decay, or exponential decay, compares favorably with polynomial decay.The empirical evaluation systematically searches learning-rate parameters.
  • Scope and limitations: The paper’s upper bounds are established for least squares, with extensions to broader smooth convex functions identified as an open direction.The non-strongly convex Step Decay result also has a dimension-factor-worse initial-error rate than the best known averaged result.

2 Problem Setup

The paper studies streaming least squares regression through stochastic gradients, modeling excess risk under strong and non-strong convexity. It specifies the stochastic-gradient update, noise and covariate assumptions, and the statistical minimax benchmark.

  • The objective is an expected square loss for streaming least squares regression.
  • SGD updates the current iterate using a stochastic gradient computed from a newly sampled example.The update uses the stepsize sequence {η_t}.
  • The model imposes assumptions on example noise and a fourth moment inequality for the covariates.The covariate condition is satisfied when covariate norms are uniformly bounded, but it is more general than bounded norms.
  • The analysis distinguishes strongly convex problems, where μ > 0, from smooth non-strongly convex problems.
  • Iterate-averaged SGD with constant stepsizes achieves the statistical minimax rate σ2d/t.The rate is stated as (1 + o(1)) · σ2d/t.

3 Main results

The main results compare polynomially decaying and geometrically decaying stepsizes for the final iterate of SGD in fixed-horizon and anytime settings. Step decay is near-optimal when the horizon is known, whereas no stepsize achieves near-minimax anytime behavior.

  • 3.1 Suboptimality of polynomial decay: Polynomially decaying stepsizes can be suboptimal by a condition-number factor in the strongly convex case and by a √T factor in the smooth case.The comparison is against the statistical minimax rate σ2d/T.
  • 3.2 Near optimality of Step Decay schemes: With a known end time T, step decay reaches rates off the minimax rate by only a log(T) factor in both convexity regimes.The schedule reduces the stepsize by a constant factor after every constant number of epochs.
  • 3.2 Near optimality of Step Decay schemes: The smooth-case step-decay result has an initial-error dependence worse by a dimension factor than the best known iterate-averaged result.The paper leaves open whether this factor can be improved and suggests the smoothness dependence may also be improvable.
  • 3.2 Near optimality of Step Decay schemes: In the strongly convex case, the variance dependence can improve from log(T) to log(κ) when μ, R2, and T are known.Proposition 3 gives a bound with a log2 κ variance term under the stated horizon condition.
  • 3.3 Anytime behavior: Without horizon knowledge, every stepsize scheme has infinitely many final iterates with excess risk at least Ω(κ/log κ) · σ2d/T.The paper further states that such bad points occur at least once in O(·) iterations.
  • 3.3 Anytime behavior: Learning rates above 2/R2 cause the algorithm to diverge.

4 Experimental Results

The experiments compare polynomial and exponential learning-rate decay schemes for residual-network training on CIFAR-10, including final versus suffix-averaged iterates and horizon-specific exponential tuning.

  • Experimental setup: The study evaluates polynomial and exponential decay schemes for a 44-layer pre-activation residual network on CIFAR-10.Training uses Nesterov momentum, batch size 128, 100 epochs, and ℓ2 regularization of 0.0005.
  • Experimental setup: A systematic grid search selects η0 and b using a validation split before final models are trained on all 50,000 samples.Reported results average runs over 10 random seeds.
  • Decay-scheme comparison: The exponential scheme convincingly outperforms the two polynomial step-size schemes on the CIFAR-10 comparison.Figure 2 and Table 2 compare training function value and test 0/1 error across the three schedules.
  • Iterate averaging: Suffix averaging is evaluated against the final iterate for polynomial schedules, with averaging begun at nine different epochs during 100-epoch training.The tested starting epochs are 5, 10, 20, 40, 80, 85, 90, 95, and 99.
  • Horizon-specific tuning: Exponential schedules are separately optimized for end times of 33, 66, and 100 epochs to assess horizon-specific hyperparameter selection.The best hyperparameters at 33 and 66 epochs are not the best at 100 epochs.

5 Conclusions and Discussion

The paper concludes that final-iterate SGD behavior for least squares is more nuanced than prior results suggest, exposing limitations of polynomial decay and effectiveness of step decay.

  • Conclusions: Final-iterate SGD behavior for least squares is more nuanced than prior work focused primarily on non-smooth stochastic convex optimization.The conclusion frames this difference as the paper’s main contribution.
  • Conclusions: Polynomially decaying stepsizes have striking limitations for SGD’s final iterate, while step-decay schedules show effectiveness in the studied setting.The paper connects these theoretical findings with practical implementations that return final SGD iterates under step decay.

A Preliminaries

The preliminaries decompose SGD’s least-squares error into bias and variance processes and develop covariance recursions used to analyze their evolution under learning-rate schedules.

  • Error decomposition: The analysis separates SGD into a noiseless bias process and a noise-driven variance process initialized at the optimum.The total error is bounded by analyzing these two simpler recursions.
  • Variance process: The variance covariance V_t tracks the covariance of the variance error and evolves through a recursion involving prior covariance and stochastic-gradient noise.The covariance sequence grows toward a steady-state covariance under constant-step behavior.
  • Covariance bounds: For constant stepsize η < 1/R^2, SGD attains a steady-state covariance, while bounded learning rates permit corresponding covariance bounds.The stated admissible schedule satisfies η_t ≤ 1/(2R^2).
  • Bias process: In the strongly convex case, the bias recursion is analyzed using the minimum Hessian eigenvalue μ > 0 and a stepsize η = 1/(2R^2).The contraction argument relates the bias decay to the condition-number structure.
  • Smooth-case bias: The bias process in the smooth non-strongly convex case admits an analogous variance-style bound with R^2·||w0 − w*||^2 playing the role of the variance scale σ^2.This identifies the initial-error dependence used in the subsequent analysis.
  • Noise-oracle reduction: The multiplicative-noise variance process can be lower-bounded in positive-semidefinite order by a deterministic-gradient process with additive noise.This reduction transfers lower-bound arguments between the two oracle models.

B Proofs of results in Section 3.1

The proofs establish lower bounds for polynomially decaying schedules by tracking directional variances toward schedule-dependent stationary points and constructing strongly convex and smooth instances.

  • Strongly convex lower bound: For polynomial schedules η_t = a/(b+t^α), the strongly convex theorem constructs an instance yielding a final-iterate lower bound for every a, b ≥ 0 and 0.5 ≤ α ≤ 1.The construction uses condition number κ and applies for horizons satisfying the theorem’s stated lower-bound conditions.
  • Strongly convex lower bound: The strongly convex construction uses coordinates with distinct eigenvalue scales and additive noise to force persistent error in at least one direction.The proof considers coordinates associated with eigenvalues κ and 1.
  • Directional variance: The directional variance v_t^(i) converges toward the stationary value s(η_t, λ_i), with s(η, λ) approximately σ^2η/2 when ηλ is small.This stationary-point behavior supplies the core variance lower-bound mechanism.
  • Smooth lower bound: The smooth-case proof forces the final stepsize to be sufficiently small in one direction while retaining large variance in another, producing a nontrivial final function value.The argument splits according to whether b is at least T^α.

C Proofs of results in Section 3.2

The proofs analyze a staged geometrically decaying learning-rate schedule by separately controlling bias and variance across phases. The resulting bounds establish the schedule’s stated dependence on horizon, smoothness, strong convexity, and variance.

  • Proof strategy: The schedule divides the horizon into phases that first reduce initial error, then use polynomial decay, and finally apply geometrically decreasing rates.The first phase uses rate 1/R2, the second uses a decreasing rate involving µ and κ, and the third has log2(κ) phases.
  • Variance control: The first phase contracts coordinate variance geometrically, yielding a residual initial-error term that is reduced to order 1/T^3.The proof uses T/3 iterations and the condition T > κ.
  • Variance control: The second phase bounds each coordinate’s variance by the residual initial-error term plus a term proportional to the current learning rate and noise variance.At the end of this phase, the bound includes 2σ2/[µ(κ+T/6)].
  • Geometric phases: The final phase repeatedly contracts variance within log2(κ) phases, using rates whose scale changes geometrically across phases.The induction relies on exponential contraction over each phase and a relation between coordinate eigenvalues and phase rates.
  • Conclusion: The function-value guarantee follows by combining the coordinate-wise variance bounds with the relevant lemmas for smooth and strongly convex cases.The proofs of the main theorem and proposition instantiate the additive-noise result and then invoke the corresponding variance and function-value lemmas.

D Proofs of results in Section 3.3

The proofs construct a two-eigendirection least-squares instance to show that final-iterate SGD cannot remain near-optimal at all sufficiently late times. A bad iterate requires a substantial recovery period, producing arbitrarily late suboptimal queries.

  • Construction: The counterexample uses a discrete least-squares instance with two groups of Gaussian coordinates and additive independent noise, giving R2 = κ.The first d/2 directions have variance dκ/3 and the remaining directions have variance 1.
  • Construction: The proof contrasts eigendirections with eigenvalues κ and 1: a rate small enough for the former is too small to quickly reduce error in the latter.This incompatibility drives the lower-bound construction for anytime final-iterate behavior.
  • Scope: The result applies under the stability restriction ηt ≤ 1/(2κ), while larger learning rates can make the algorithm diverge.The divergence threshold is stated separately as a condition on the learning rate.
  • Anytime lower bound: For any SGD algorithm and any horizon T, the construction produces a later time T′ whose normalized excess risk is at least τ.The theorem permits τ up to a condition-number-dependent threshold involving κ and log(κ+1).
  • Recovery interval: A bad query point remains bad over an interval of later iterates, rather than being repaired immediately by subsequent updates.The lemma lower-bounds the normalized error throughout an interval beginning at the bad iterate.

E.1 Synthetic 2-d Streaming Least Squares Experiments

The synthetic experiments compare polynomially decaying and step-decay learning-rate schedules on two-dimensional streaming least squares across several condition numbers. The experimental protocol varies schedules and reports averaged results.

  • Experimental setup: The experiments use condition numbers κ ∈ {50, 100, 200, 400} and run each setting for κ^2 iterations.The two Hessian eigenvalues are 1 and 1/κ, the noise level is σ2 = 1, and results are averaged over five seeds.
  • Schedule tuning: Polynomial schedules are tuned over logarithmic grids for their starting learning rates and decay parameters.The search ranges depend on κ and differ between the O(1/t) and fractional-power schedules.
  • Schedule tuning: Step decay keeps the initial learning rate at 0.1 and varies the interval between factor-of-two decays in multiples of T/log T.The decay multiplier c is selected from a fixed set of candidate values.
  • Baselines: Suffix iterate averaging uses a constant stepsize of 0.1 and averages iterates over the final half of optimization.

E.2 Non-Convex experiments on cifar-10 dataset with a 44-layer residual net

The non-convex experiments use a 44-layer residual network on CIFAR-10 and tune learning-rate schedules with validation-based grid search. The protocol includes momentum, minibatches, regularization, and a learning-rate floor.

  • Training setup: The experiments use Nesterov acceleration with momentum 0.9, batch size 128, 100 training epochs, and ℓ2 regularization 0.0005.
  • Learning-rate search: Learning rates are selected from geometrically spaced candidates, while later-stage decay parameters use an additively spaced grid.The minimum learning rate is capped at 0.0001 to ensure optimization continues making progress.
  • Validation protocol: Grid-search configurations are validated by holding out one tenth of the training data and training on the remaining nine tenths.When the best configuration reaches a grid boundary, the grid is extended so the selected value lies in the interior.
Loading 1904.12838v2…