Source-linked AI summary
A Linearly-Convergent Stochastic L-BFGS Algorithm
Philipp Moritz, Robert Nishihara, Michael I. Jordan
TL;DR
Large-scale optimization requires methods that handle high-dimensional models and very large datasets without the costs of Hessian inversion or full-batch updates. The paper introduces stochastic L-BFGS with variance-reduced gradients and stochastic curvature estimates. It proves linear convergence in the strongly convex case and reports strong performance, including high-precision solutions and robustness across a wide range of step sizes.
Problem
Large-scale problems make Hessian-based methods computationally expensive, while stochastic gradient variance can slow convergence near the optimum and require diminishing step sizes.
Method
The algorithm combines L-BFGS curvature approximations with variance-reduced stochastic gradients, periodically computing full gradients and updating curvature from stochastic Hessian estimates.
Results
The paper proves a linear convergence rate in the strongly convex case and reports that SLBFGS performs well on large-scale convex and non-convex optimization problems, often reaching high precision.
Takeaways & Limitations
SLBFGS is reported to perform well over a wide range of step sizes, whereas competing stochastic methods have narrower effective step-size windows.
Takeaways & Limitations
The proof constants scale poorly with problem size, limiting the sharpness of the theoretical bounds.
Abstract
from arXiv · showhide
We propose a new stochastic L-BFGS algorithm and prove a linear convergence rate for strongly convex and smooth functions. Our algorithm draws heavily from a recent stochastic variant of L-BFGS proposed in Byrd et al. (2014) as well as a recent approach to variance reduction for stochastic gradient descent from Johnson and Zhang (2013). We demonstrate experimentally that our algorithm performs well on large-scale convex and non-convex optimization problems, exhibiting linear convergence and rapidly solving the optimization problems to high levels of precision. Furthermore, we show that our algorithm performs well for a wide-range of step sizes, often differing by several orders of magnitude.
1 Introduction
The paper targets large-scale empirical risk minimization, where both model dimension and dataset size can make second-order and batch methods expensive. It introduces stochastic L-BFGS with variance reduction to obtain linear convergence theoretically and strong practical performance.
- Motivation: Large-scale learning problems can have extremely large parameter dimension d and dataset size N.These challenges arise in empirical risk minimization for machine-learning models.
- Motivation: Newton’s method can be too expensive in high dimensions because it computes and inverts the Hessian, motivating first-order and quasi-Newton methods.L-BFGS incorporates curvature information without computing second derivatives.
- Motivation: Batch gradient methods slow down when N is large because they process every data point before each update.Stochastic methods update after processing only a small subset of data.
- Contribution: The proposed stochastic L-BFGS combines variance reduction with minibatch Hessian-vector products to address stochastic curvature-estimation challenges.It guarantees a linear rate in the strongly convex case without requiring a diminishing step size and performs qualitatively linearly in practice.
- Motivation: Stochastic gradient estimates can have high variance near the optimum, often making convergence guarantees depend on diminishing step sizes.Variance reduction is presented as an approach for speeding convergence of stochastic first-order methods.
2 The Algorithm
The algorithm combines L-BFGS curvature information with variance-reduced stochastic gradients, periodically refreshing full gradients and updating curvature from stochastic Hessian estimates. It avoids explicitly forming the inverse-Hessian approximation and applies it through the two-loop recursion.
- Sampling: Distinct subsets S and T decouple stochastic gradient estimation from stochastic Hessian estimation.Their sizes are b = |S| and b_H = |T|.
- Update: The update uses an L-BFGS inverse-Hessian approximation together with a variance-reduced stochastic gradient.This contrasts with the identity matrix in gradient descent and the exact inverse Hessian in Newton’s method.
- Variance reduction: Every m iterations, the algorithm computes a full gradient to reduce the variance of subsequent stochastic gradient estimates.The variance-reduced gradient combines minibatch gradients at the current inner iterate and snapshot point with the full gradient.
- Curvature updates: Every L iterations, it updates the inverse-Hessian approximation using progress and stochastic Hessian information.The vector s_r records average progress, while y_r is obtained by multiplying s_r by a stochastic Hessian estimate.
- Implementation: The method directly computes H_rv with the L-BFGS two-loop recursion instead of constructing H_r, avoiding O(d^2) computation.The recursion uses stored (s_j, y_j) pairs and preserves positive definiteness under the stated update.
3 Preliminaries
The analysis assumes convex, twice continuously differentiable component functions and conditions supporting strong convexity and Hessian bounds. Under these assumptions, it establishes bounded positive-definite curvature approximations and develops the variance bound needed for convergence.
- Assumptions: Each component function f_i is convex and twice continuously differentiable.This is stated as Assumption 1.
- Assumptions: Strong convexity is typically enforced by adding a strongly-convex regularizer, yielding a unique minimizer w*.The regularizer can be absorbed into the component functions.
- Curvature bounds: Under the assumptions, the inverse-Hessian approximations H_r satisfy uniform spectral bounds with constants 0 < γ ≤ Γ.The corresponding inverse approximations are also controlled through the stated lemma.
- Variance analysis: The analysis bounds the variance-reduced stochastic gradient using the function gaps at the current inner iterate and snapshot point.The estimator is v_t = ∇f_S(x_t) − ∇f_S(w_k) + μ_k.
4 Convergence Analysis
The analysis establishes a linear convergence guarantee for the proposed stochastic L-BFGS method under the stated assumptions. The proof chooses parameters so the convergence factor α is less than one.
- Theorem 7 provides the main convergence result for the unique minimizer under Assumptions 1 and 2.
- Parameter condition: Choosing η < γλ/(2Γ^2Λ^2) and m sufficiently large ensures that the rate α is less than one.
- Proof strategy: The proof uses Lipschitz gradient continuity, conditional expectations, Hessian-approximation bounds, and variance bounds for the stochastic gradients.
- Proof strategy: A telescoping sum over the stochastic updates yields the inequality used to derive the convergence rate.
- Empirical illustration: The convergence analysis is illustrated alongside optimization-error plots for SLBFGS, SVRG, SQN, and SGD.
5 Related Work
Related work develops variance-reduced stochastic first-order methods and stochastic quasi-Newton methods. This paper distinguishes its approach by guaranteeing a linear convergence rate and using Hessian-vector products to stabilize the inverse-Hessian approximation.
- Variance reduction: Variance-reduction research includes SDCA, SAG, SVRG, control-variate methods, and online gradient-estimation approaches.
- Stochastic quasi-Newton methods: Prior stochastic quasi-Newton analyses cited here establish O(1/k) rates in strongly convex settings or convergence in nonconvex settings.
- Novelty: The paper differs from preceding work by guaranteeing a linear convergence rate.
- Novelty: Compared with Lucchi et al., the method uses Hessian-vector products to stabilize the approximation rather than a similar L-BFGS-style update.
6 Experimental Results
Experiments compare SLBFGS with SVRG, SQN, and SGD on ridge regression, support vector machines, and matrix completion. SLBFGS performs well across these large-scale problems and remains effective over broad step-size ranges.
- Experimental setup: The experiments evaluate SLBFGS, SVRG, SQN, and SGD on ridge regression, support vector machines, and matrix completion.
- Experimental setup: The experiments account for full-gradient and Hessian-vector-product costs by measuring error against passes through the data.
- Results by problem: On Millionsong ridge regression, SLBFGS and SVRG rapidly solve the problem to high precision; on RCV1, SLBFGS finds a better optimum after SGD and SQN initially progress faster.
- Results by problem: On Netflix matrix completion, SVRG and SGD perform poorly, while curvature information presumably helps SLBFGS and SQN escape the near-zero stationary point faster.
- Robustness to choice of step size: Across Millionsong and RCV1, SLBFGS maintains high-precision performance over a large step-size range, whereas the other methods degrade more rapidly.
7 Proofs of Preliminaries
The preliminary analysis bounds properties of the inverse-Hessian approximation and the variance-reduced gradients used in the convergence proof. It combines trace, determinant, convexity, and conditional-expectation arguments.
- Inverse-Hessian bounds: The analysis invokes the Sherman-Morrison-Woodbury formula to express the update in terms of the Hessian approximation.
- Inverse-Hessian bounds: The inverse-Hessian approximation is analyzed by bounding its trace and determinant, which supports eigenvalue control.
- Determinant bound: The determinant derivation uses det(AB) = det(A) det(B) and a rank-one determinant identity.
- Variance reduction: The variance-reduced gradient is defined as ∇f_S(x_t) − ∇f_S(w_k) + μ_k, and its second moment is bounded conditionally.
8 Discussion
The paper presents SLBFGS as a stochastic L-BFGS method with a proven linear convergence rate in the strongly convex case. It identifies poorly scaling proof constants and superlinear convergence as directions for future work.
- SLBFGS is a stochastic L-BFGS algorithm with a proved linear convergence rate for strongly convex objectives.
- Theorem 7 captures SLBFGS’s qualitatively linear convergence rate, which is reflected in the experimental results.
- The authors expect SLBFGS to help when curvature information is valuable, including poorly conditioned problems and high-precision optimization.
- The proof of Theorem 7 yields constants that scale poorly with problem size, as do many related quasi-Newton analyses.
- Future work could seek stochastic quasi-Newton methods with provable superlinear convergence, as achieved in the non-stochastic case.