PaperlayerView exact revision on arXiv

Source-linked AI summary

Barzilai-Borwein Step Size for Stochastic Gradient Descent

Conghui Tan, Shiqian Ma, Yu-Hong Dai, Yuqiu Qian

arXiv:1605.04131v2math.OCcs.LGstat.ML

TL;DR

Choosing step sizes is difficult in stochastic gradient methods because line search is computationally prohibited, while diminishing or hand-tuned fixed steps can be inefficient. The paper uses the Barzilai-Borwein method to create SGD-BB and SVRG-BB, proves linear convergence for SVRG-BB and SVRG-I, and reports competitive or superior numerical performance.

  • Problem

    Line search is computationally prohibited for stochastic gradient methods, leaving diminishing or hand-tuned fixed step sizes that can be inefficient.

  • Method

    The paper uses the Barzilai-Borwein method to compute step sizes for SGD and SVRG, producing SGD-BB and SVRG-BB.

  • Results

    SGD-BB and SVRG-BB are comparable to and sometimes better than SGD and SVRG with best-tuned step sizes, while SVRG-BB and SVRG-I have linear convergence results for strongly convex functions.

  • Takeaways & Limitations

    The proposed methods automatically compute stochastic-gradient step sizes and can match or exceed the performance of hand-tuned methods in the reported experiments.

  • Takeaways & Limitations

    For ill-conditioned problems, the convergence rate given for SVRG-I might be slow because its epoch length depends quadratically on the condition number.

Abstract

from arXiv · show

One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step size by hand, which can be time consuming in practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to automatically compute step sizes for SGD and its variant: stochastic variance reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective functions. As a by-product, we prove the linear convergence result of SVRG with Option I proposed in [10], whose convergence result is missing in the literature. Numerical experiments on standard data sets show that the performance of SGD-BB and SVRG-BB is comparable to and sometimes even better than SGD and SVRG with best-tuned step sizes, and is superior to some advanced SGD variants.

1 Introduction

The introduction frames step-size selection as a central difficulty in stochastic optimization and presents BB-based methods for automatically setting SGD and SVRG step sizes. It also states theoretical convergence results and empirical comparisons with established methods.

  • Motivation: SGD is challenging on very large finite-sum problems because full objective and gradient evaluations may be prohibited, while its strongly convex smooth convergence is sublinear and variance-dependent.The paper motivates stochastic methods as alternatives when the sample size is extremely large.
  • Motivation: Choosing an appropriate step size is difficult because stochastic methods cannot use computationally prohibited line searches and instead commonly use diminishing or hand-tuned fixed step sizes.The paper describes both common practices as potentially inefficient.
  • Contributions: The paper proposes using the Barzilai-Borwein method to compute step sizes for SGD and SVRG, producing SGD-BB and SVRG-BB with nearly unchanged per-iteration costs.The proposed methods target automatic step-size computation for stochastic optimization.
  • Contributions: The authors prove linear convergence of SVRG-BB for strongly convex functions and establish the previously missing linear-convergence result for SVRG-I.The introduction contrasts this result with prior analysis that covered only SVRG-II.
  • Experiments: Experiments on logistic regression and SVM problems show that SGD-BB and SVRG-BB are comparable to, and sometimes better than, SGD and SVRG with best-tuned step sizes.The paper also reports that SGD-BB is superior to some advanced SGD variants.
  • Contributions: The paper develops, analyzes, and experimentally evaluates BB-based stochastic methods, including a smoothing technique for SGD-BB and an extension to variants such as SAG.The paper is organized around BB background, SVRG-BB, SGD-BB, experiments, and conclusions.

2 The Barzilai-Borwein Step Size

The Barzilai-Borwein method replaces a costly matrix approximation with a scalar step-size model derived by minimizing the secant-equation residual. Its step size is computed during optimization without an additional parameter.

  • Quasi-Newton background: Quasi-Newton iterations use an approximate Hessian matrix that must satisfy a secant equation, but solving the associated linear system can be costly when the matrix is large and dense.The secant equation links iterate and gradient changes through the Hessian approximation.
  • BB construction: The BB method replaces the Hessian approximation with the scalar matrix 1/η_t I, avoiding the need to solve a large dense linear system.A scalar step-size model cannot generally satisfy the secant equation exactly.
  • BB construction: BB chooses η_t by minimizing the residual of the secant equation rather than enforcing the equation exactly.This residual-minimization principle leads to the paper’s selected BB step-size formula.
  • BB iteration: A typical BB iteration updates the iterate using the step size computed by the BB formula.The paper focuses on the choice in equation (2.4) because its practical performance is similar to the alternative choice in (2.6).

3 Barzilai-Borwein Step Size for SVRG

This section incorporates the Barzilai-Borwein step size into SVRG, yielding SVRG-BB, and analyzes its convergence under strong convexity. It also establishes linear convergence for SVRG-I, whose convergence analysis had been missing.

  • SVRG Method: SVRG uses two loops: each epoch computes a full gradient, then generates lower-variance stochastic gradients in the inner loop.The next outer-loop iterate is selected using either Option I, the latest inner-loop iterate, or Option II, a randomly chosen inner iterate.
  • SVRG-BB Method: SVRG-BB replaces SVRG’s user-provided fixed step size with a BB-computed step size during the algorithm.The BB method computes the step size without requiring a parameter; the first epoch still uses a specified initial step size η0.
  • Linear Convergence Analysis: SVRG-I also converges linearly in expectation, establishing the previously missing convergence result for Option I.The result concerns the iterates ˜xk, whereas the cited SVRG-II theorem concerns objective function values F(˜xk).
  • Linear Convergence Analysis: For ill-conditioned problems, the SVRG-I convergence bound may be slow because its required epoch length depends quadratically on the condition number L/µ.The corresponding SVRG-II condition has linear dependence on L/µ, while the first term in the SVRG-I condition decays linearly as m increases.
  • Linear Convergence Analysis: Under strong convexity and Lipschitz-gradient assumptions, SVRG-BB converges linearly in expectation.The analysis bounds the BB step size using the strong-convexity and Lipschitz constants before applying the epoch-wise convergence inequality.

4 Barzilai-Borwein Step Size for SGD

This section adapts the Barzilai-Borwein step size to SGD and related stochastic methods, using epoch-level gradient estimates and smoothing to automatically adjust learning rates.

  • SGD-BB method: SGD-BB applies one BB-computed step size across each epoch of m SGD iterations.The method calls every m iterations one epoch and updates the step size once per epoch.
  • Gradient estimation: SGD-BB estimates the full gradient by averaging stochastic gradients collected during an epoch.The algorithm recursively weights sampled gradients using β ∈ (0, 1).
  • Step-size computation: The stochastic BB formula may produce negative step sizes because the averaged gradients are not exact full gradients, so SGD-BB takes their absolute value.This differs from SVRG-BB, where the relevant gradient estimate is exact.
  • Initialization: SGD-BB requires η0 and η1 during its first two epochs because two prior averaged gradients are needed to compute later BB step sizes.The reported experiments found performance was not sensitive to these initial choices.
  • Smoothing: A smoothing technique stabilizes stochastic BB step sizes by fitting them to a decreasing form C/φ(k), with φ(k) typically set to k + 1.The smoothed step size replaces ηk in the SGD update.
  • Extension to SAG: The same BB and smoothing ideas extend to SAG, where choosing φ(k) ≡ 1 makes the smoothed step size the geometric mean of previous BB step sizes.This extension is called SAG-BB.

5 Numerical Experiments

Experiments evaluate SVRG-BB and SGD-BB on logistic regression and SVM problems using three LIBSVM data sets, then compare them with tuned and advanced stochastic methods.

  • Experimental setup: Experiments test SVRG-BB and SGD-BB on logistic regression with ℓ2-norm regularization and SVM problems.Three standard real data sets downloaded from LIBSVM are used.
  • SVRG-BB results: Figure 1 compares SVRG-BB with SVRG using fixed step sizes across six sub-figures.The x-axis is epochs, while the y-axes show sub-optimality or step size; dashed lines represent fixed-step SVRG and solid lines represent SVRG-BB.
  • SVRG-BB results: SVRG-BB reaches the best-tuned SVRG performance in about 10 to 15 epochs and is not sensitive to its initial step size.The paper presents this as evidence that SVRG-BB can generate suitable step sizes automatically while running.
  • SGD-BB results: SGD-BB achieves comparable or better sub-optimality than SGD with the best-tuned diminishing step size and outperforms the other tested choices.After a few epochs, its generated step sizes approximately coincide with the best-tuned diminishing step sizes.
  • Comparison with AdaGrad: SGD-BB converges very fast across the three tested problems and is not sensitive to its initial step size, unlike AdaGrad’s later slowdown and sensitivity.The comparison uses CPU time and sub-optimality for methods with different per-iteration costs.
  • Comparison with other methods: SAG-BB is much faster than SAG with line search to reach the same sub-optimality on the tested problems.The paper also reports that oLBFGS is much slower than SGD-BB because it requires more computational effort per iteration.

6 Conclusion

The paper introduces BB-based step sizes for SGD and SVRG, establishes convergence results, stabilizes SGD-BB, and reports competitive or superior empirical performance.

  • Conclusion: The paper proposes SGD-BB and SVRG-BB by incorporating the BB method into SGD and SVRG.It also shows how to incorporate BB step sizes into SAG.
  • Conclusion: SVRG-BB is proved to converge linearly for strongly convex functions, alongside a linear-convergence proof for SVRG with Option I.The Option I result is presented as a by-product of the analysis.
  • Conclusion: Numerical results show that SVRG-BB and SGD-BB are comparable to or sometimes better than best-tuned SVRG and SGD, and superior to some advanced SGD variants.The experiments use real data sets and include a smoothing technique for SGD-BB.
Loading 1605.04131v2…