PaperlayerView exact revision on arXiv

Source-linked AI summary

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, Simon Lacoste-Julien

arXiv:1905.09997v5cs.LGmath.OCstat.ML

TL;DR

SGD’s fast interpolation-based convergence depends on step-sizes that may be unknown in practice. This paper uses stochastic line-search methods to adapt those step-sizes, proving deterministic-rate guarantees in convex settings and fast rates in broader interpolating problems. Experiments report competitive, hyper-parameter-robust performance, including faster convergence and better generalization for deep-network classification.

  • Problem

    SGD’s interpolation-based fast rates rely on constant step-sizes involving problem-specific quantities that are generally unknown in practice.

  • Method

    The paper uses stochastic Armijo and Lipschitz line-searches to adapt step-sizes for SGD and stochastic extra-gradient under interpolation.

  • Results

    The methods attain deterministic convergence rates in convex settings, linear rates for specified non-convex and saddle-point problems, and competitive empirical performance.

  • Takeaways & Limitations

    Line-search can make interpolating stochastic optimization practical while reducing sensitivity to precise hyper-parameter choices.

  • Takeaways & Limitations

    The non-convex SGD rate requires the strong growth condition and knowledge of ρL_max to bound the maximum step-size; the SEG guarantee requires RSI and step-size bounds.

Abstract

from arXiv · show

Recent works have shown that stochastic gradient descent (SGD) achieves the fast convergence rates of full-batch gradient descent for over-parameterized models satisfying certain interpolation conditions. However, the step-size used in these works depends on unknown quantities and SGD's practical performance heavily relies on the choice of this step-size. We propose to use line-search techniques to automatically set the step-size when training models that can interpolate the data. In the interpolation setting, we prove that SGD with a stochastic variant of the classic Armijo line-search attains the deterministic convergence rates for both convex and strongly-convex functions. Under additional assumptions, SGD with Armijo line-search is shown to achieve fast convergence for non-convex functions. Furthermore, we show that stochastic extra-gradient with a Lipschitz line-search attains linear convergence for an important class of non-convex functions and saddle-point problems satisfying interpolation. To improve the proposed methods' practical performance, we give heuristics to use larger step-sizes and acceleration. We compare the proposed algorithms against numerous optimization methods on standard classification tasks using both kernel methods and deep networks. The proposed methods result in competitive performance across all models and datasets, while being robust to the precise choices of hyper-parameters. For multi-class classification using deep networks, SGD with Armijo line-search results in both faster convergence and better generalization.

1 Introduction

The paper addresses SGD’s sensitivity to unknown step-size choices by applying line-search methods under interpolation. It establishes convergence guarantees for SGD and stochastic extra-gradient, and reports competitive empirical performance.

  • Motivation: SGD can match full-batch convergence rates under interpolation, but prior step-sizes depend on unknown problem-specific quantities.Interpolation is common in over-parameterized deep networks and other expressive models.
  • Method: Classical line-search is adapted to automatically set SGD step-sizes despite the additional noise of stochastic gradients.The paper positions its method as simpler and more robust than some prior stochastic line-search approaches.
  • Theory: Under interpolation, stochastic Armijo line-search attains full-batch convergence rates for convex and strongly-convex functions without explicit problem constants.The paper identifies these as the first line-search convergence rates for SGD in the interpolation setting across convex and non-convex functions.
  • Theory: Lipschitz line-search yields linear convergence for stochastic extra-gradient on RSI non-convex functions and interpolating saddle-point problems.The result covers strongly convex-concave and bilinear saddle-point problems as well.
  • Experiments: Experiments across matrix factorization, kernel classification, and deep-network classification find competitive performance and robustness to precise hyper-parameter choices.The paper also reports faster convergence and better generalization for deep-network multi-class classification with SGD Armijo line-search.

2 Assumptions

The analysis assumes finite-sum machine-learning objectives with smooth component losses and allows strongly-convex, convex, or non-convex overall functions. Its central structural assumption is interpolation.

  • Objective: The objective has finite-sum form, with each component representing the loss for one training point.The paper assumes access to noisy stochastic gradients of this objective.
  • Objective: The overall function may be strongly-convex, convex, or non-convex, and is assumed lower-bounded and smooth.Smoothness means the gradient is Lipschitz continuous.
  • Interpolation: Interpolation requires every individual loss gradient to vanish at an optimum where the overall gradient vanishes.This condition is exactly satisfied by a linear model with squared hinge loss on linearly separable binary data.

3 Stochastic Gradient Descent for Convex Functions

The paper adapts Armijo backtracking to stochastic gradients using mini-batch evaluations and proves full-batch-like rates under interpolation for strongly-convex and convex objectives.

  • SGD: SGD samples one example or mini-batch per iteration, uses an unbiased stochastic gradient, and takes a step with a selected learning rate.The update is w_k+1 = w_k − η_k∇f_i_k(w_k).
  • Armijo line-search: Armijo line-search selects a step-size using a condition evaluated on the current mini-batch.Compared with SGD, the procedure requires additional mini-batch function evaluations but not additional gradients.
  • Armijo line-search: Backtracking starts from η_max and repeatedly decreases the step-size until the Armijo condition holds.Resetting strategies can avoid backtracking in most iterations.
  • Armijo line-search: For sufficiently large η_max and c ≤ 1/2, the returned step-size is at least 1/L_i_k, matching the interpolation-setting constant step-size.The condition holds for smooth functions without requiring convexity and guarantees termination at a non-zero step-size.
  • Convergence rates: Under interpolation and smooth convex component losses, Armijo SGD matches full-batch gradient descent rates in strongly-convex and convex cases.The strongly-convex theorem uses c = 1/2; the convex theorem uses c > 1/2 with iterate averaging.

4 Stochastic Gradient Descent for Non-convex Functions

Under interpolation and the strong growth condition, Armijo line-search SGD obtains a fast non-convex convergence rate, but the guarantee requires a bound involving problem-specific smoothness quantities.

  • The strong growth condition bounds expected stochastic-gradient norms by the full-gradient norm and implies interpolation.It holds for smooth functions satisfying a PL condition.
  • Under the strong growth condition and smooth component functions, Armijo line-search SGD achieves a non-convex convergence rate.The theorem also imposes a condition on the Armijo parameter and maximum step-size.
  • The non-convex guarantee requires knowledge of ρL_max to bound the maximum step-size, reducing its practical appeal.The authors leave relaxing this requirement for future work.
  • With non-increasing step-sizes or an independently sampled mini-batch for the Armijo condition, a similar O(1/T) rate holds under slightly relaxed conditions.

5 Stochastic Extra-Gradient Method

The paper extends line-search adaptation to stochastic extra-gradient methods, using a Lipschitz condition to select steps without knowing the Lipschitz constant and proving rates for minimization and saddle-point problems.

  • 5.1 Lipschitz line-search: Stochastic extra-gradient evaluates a gradient at an extrapolated point and uses it to update the current iterate.The same sample and step-size are used for both steps in the analyzed method.
  • 5.1 Lipschitz line-search: The Lipschitz line-search uses backtracking from η_max and returns η_k ≥ min{c/L_ik, η_max} for L_ik-smooth component functions.It does not require prior knowledge of the Lipschitz constant.
  • 5.2 Convergence rates for minimization: Under interpolation, smoothness, and the restricted secant inequality, SEG with Lipschitz line-search achieves linear convergence for the specified non-convex class.The RSI condition is weaker than strong convexity and applies to models including single-hidden-layer neural networks, matrix completion, and phase retrieval.
  • 5.2 Convergence rates for minimization: For convex functions under interpolation, SEG with Lipschitz line-search also achieves an O(1/T) rate.
  • 5.3 Convergence rates for saddle point problems: For strongly-convex-strongly-concave and bilinear saddle-point problems satisfying interpolation, SEG with Lipschitz line-search achieves linear convergence.The strongly-convex-strongly-concave setting includes robust optimization with expressive interpolating models.

6 Practical Considerations

The paper proposes practical heuristics for larger line-search steps, alternative Goldstein checks, and momentum-based acceleration, while noting trade-offs in step-size initialization.

  • 6.1 Using larger step-sizes: Initializing each iteration from the previous step-size can reduce unnecessary backtracking, but the step-size then cannot increase and convergence slows.
  • 6.1 Using larger step-sizes: The proposed heuristic initializes backtracking at η_k−1 · γ^b/n, with γ > 1, to increase the initial step-size across iterations.Here b is the mini-batch size.
  • 6.2 Goldstein line-search: Goldstein line-search decreases the step-size when Armijo fails and increases it when the curvature condition is not satisfied.It uses additional function evaluations to check curvature.
  • 6.3 Acceleration: The experiments combine the proposed line-search techniques with simple Polyak or Nesterov acceleration schemes.Momentum or acceleration often produces faster convergence in stochastic methods.

7 Experiments

The experiments evaluate line-search methods on synthetic matrix factorization, kernel classification, and deep-network classification. Results generally support fast convergence under interpolation, with SGD+Armijo especially strong on deep networks.

  • Synthetic experiment: In matrix factorization, rank 4 lacks interpolation and reaches an optimization floor, whereas rank 10 enables SGD with Armijo or Goldstein line-search to converge linearly to machine precision.SEG with Lipschitz line-search also converges quickly, while adaptive-gradient methods stagnate.
  • Binary classification with kernels: For RBF-kernel classification, mushrooms satisfies interpolation while ijcnn does not, yet SGD+Armijo, Nesterov+Armijo, and SEG+Lipschitz converge quickly on both datasets.The experiments use softmax loss and compare training loss and test accuracy.
  • Multi-class classification with deep networks: Across MNIST, CIFAR-10, and CIFAR-100 deep-network experiments, SGD with Armijo line-search achieves the best training-loss and test-accuracy performance and converges faster than the other methods.Line-search with Polyak momentum also outperforms tuned constant-step SGD and Adam, while Goldstein line-search remains competitive.
  • Multi-class classification with deep networks: SGD+Armijo line-search is only marginally slower per iteration than Adam and uses one additional function evaluation on average.For deep networks, it automatically finds a step-size schedule resembling cosine annealing.
  • Multi-class classification with deep networks: On CIFAR10 with ResNet-34, SGD with Armijo line-search is robust to c values from 0.1 to 0.5 and is virtually unaffected by ηmax.The correct step-size range is found in early iterations.

8 Conclusion

The paper concludes that simple line-search techniques make SGD and stochastic extra-gradient fast under interpolation in theory and practice. It identifies stronger non-convex guarantees and stochastic momentum as directions for future work.

  • Conclusion: Under interpolation, line-search techniques for classic SGD and SEG lead to fast convergence in both theory and practice.This conclusion applies to modern over-parameterized models satisfying the interpolation condition.
  • Conclusion: The paper leaves strengthening non-convex SGD line-search results and studying stochastic momentum under interpolation for future work.It also proposes drawing on line-search and trust-region methods to improve stochastic optimization.

D Proof for Theorem 3

The proof derives bounds on the adaptive step-size returned by the line-search and uses interpolation, smoothness, and curvature conditions to establish convergence relations.

  • Step-size bounds: The proof starts from the smoothness-based change in the objective and derives inequalities that constrain the line-search step-size ηk.The stochastic update uses the sampled gradient ∇f_ik(wk).
  • Case analysis: The proof analyzes separately ηmax below and above 1/Lmax, then combines the cases to obtain the final constraints on c and ηmax.The resulting contraction expression includes the averaged curvature parameter μ̄.
  • Final step-size range: The upper and lower bounds on ηk are consistent, and taking c → 1 with ηmax → 2/(ρL) yields an adaptive step-size in (0, 2/(ρL)).The proof uses positivity of the relevant Lipschitz constants to establish a nonempty constraint set.
  • SEG analysis: The proof then compares constant-step-size and Lipschitz-line-search cases using smoothness, expectations over the sampled index, and the interpolation property.The iterate wk and common minimizer w* do not depend on the sampled index ik.
  • Interpolation: Interpolation ensures w* minimizes every component function fi, allowing component losses at w* to be compared directly with losses after the stochastic update.This property is used to replace component-function differences involving w* with nonpositive terms.

E.3 Proof of SEG for convex minimization

The section develops convergence guarantees for stochastic extra-gradient with Lipschitz line-search under interpolation and related operator assumptions. It also records Armijo-line-search results for SGD under stochastic growth, smoothness, and structural conditions.

  • Convex minimization: SEG with Lipschitz line-search is analyzed for convex minimization under interpolation, smoothness, and convexity assumptions.The theorem uses a fixed line-search parameter and an upper bound on the maximum step-size.
  • Strongly-monotone operators: Interpolation implies that each component operator vanishes at the solution in the finite-sum strongly-monotone setting.This extends interpolation beyond gradients to general strongly-monotone operators.
  • Strongly-monotone operators: SEG with Lipschitz line-search achieves a linear convergence rate for interpolating, smooth, strongly-monotone operators.The guarantee assumes c = 1/4 and constrains ηmax using the component strong-monotonicity constants.
  • Bilinear saddle-point problems: For bilinear saddle-point problems, interpolation enables SEG with Lipschitz line-search to achieve linear convergence.The method samples rows and columns of the coupling matrix during each iteration.
  • Bilinear saddle-point problems: The bilinear convergence rate depends on the minimum and maximum singular values of the mini-batch matrix.The authors identify these as first results for stochastic bilinear min-max problems in the interpolation setting.
  • SGD with Armijo line-search: Under stochastic growth conditions, SGD with Armijo line-search has convergence guarantees when step-size independence or non-increasing step-sizes is enforced.The independence approach uses a separate mini-batch for the line-search and gradient update.

G.2 Binary Classification using Kernel Methods

The kernel experiments evaluate binary classification optimizers using controlled data splits, cross-validated kernel parameters, and tuned or default optimization settings. Synthetic bilinear experiments compare line-search SEG with methods including Adam, ExtraAdam, and variance reduction.

  • Experimental setup: Binary-classification kernel experiments use LIBSVM training data with an 80:20 train-test split.Kernel bandwidths are selected by 10-fold cross-validation on the training split.
  • Experimental setup: SVRG step-sizes are selected by 3-fold cross-validation, while other baseline optimizers use their default hyper-parameters.The final experiments use five random seeds, mini-batches of 100 examples, and 35 epochs.
  • Robustness and computation: The robustness comparison varies Adam and constant-step-size SGD over [10^-1, 10^-5], while line-search SGD varies c over [0.1, 0.5] and ηmax over [1, 10^3].The experiments directly test sensitivity to optimization hyper-parameters.
  • Synthetic bilinear experiment: On the interpolating synthetic bilinear problem, SEG with Lipschitz line-search converges linearly and empirically faster than SVRE.SEG with Lipschitz line-search does not converge when interpolation is absent, whereas SVRE performs well in both settings.

H.2 Synthetic Experiment and Binary Classification with Kernels

Additional experiments examine kernel classification, step-size evolution, matrix factorization, and line-search implementations. The results emphasize stable optimization across some non-interpolating or ill-conditioned settings, alongside interpolation-dependent behavior.

  • Binary classification with kernels: The proposed line-search methods perform well on rcv1 and w8a even though the selected kernel bandwidths do not satisfy interpolation.On the ill-conditioned w8a dataset, they converge quickly and remain at the global minimum, while Adam fails to converge.
  • Synthetic matrix factorization: L4 Mom is unstable on the matrix-factorization settings where interpolation is not satisfied and converges slowly when interpolation is satisfied.The figure compares the true model with rank 1, 4, and 10 factorizations; only the true model and rank 10 satisfy interpolation.
  • Step-size evolution: On mushrooms, which satisfies interpolation, SGD with Armijo increases its step-size exponentially.For rcv1, ijcnn, and w8a, the step-size adapts upward or downward to the problem smoothness.
  • Line-search implementations: The experiments implement SGD+Goldstein and SEG+Lipschitz with backtracking that multiplies the step-size by β < 1 when the line-search fails.Separate pseudo-code also describes Polyak momentum and Nesterov acceleration with Armijo line-search.
Loading 1905.09997v5…