PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Online Limited Memory BFGS

Aryan Mokhtari, Alejandro Ribeiro

arXiv:1409.2045v1math.OCcs.LGstat.ML

TL;DR

Large-scale stochastic optimization needs methods that handle infeasible full gradients and difficult curvature. The paper analyzes online limited-memory BFGS using stochastic gradients, proves almost-sure convergence under bounded sample-function curvature, and reports computational advantages in synthetic SVM and advertising applications.

  • Problem

    Full gradients are infeasible for large stochastic objectives, while stochastic quasi-Newton curvature estimates can become nearly singular and amplify noise.

  • Method

    oLBFGS uses stochastic gradients with a fixed moving window of past gradients and analyzes curvature approximations through trace, determinant, and condition-number bounds.

  • Results

    oLBFGS converges to the optimum with probability 1, has expected rate at least O(1/t), and reduces convergence time or computation relative to competing stochastic methods in reported experiments.

  • Takeaways & Limitations

    oLBFGS offers a limited-memory stochastic quasi-Newton approach whose convergence and efficiency advantages extend from synthetic SVMs to a search-engine advertising application.

  • Takeaways & Limitations

    The convergence analysis assumes sample functions have well-behaved Hessians, including curvature bounds that prevent arbitrarily small eigenvalues.

Abstract

from arXiv · show

Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample functions are shown to suffice to guarantee that the curvature approximation matrices have bounded determinants and traces, which, in turn, permits establishing convergence to optimal arguments with probability 1. Numerical experiments on support vector machines with synthetic data showcase reductions in convergence time relative to stochastic gradient descent algorithms as well as reductions in storage and computation relative to other online quasi-Newton methods. Experimental evaluation on a search engine advertising problem corroborates that these advantages also manifest in practical applications.

1. Introduction

The paper addresses stochastic optimization in large-scale machine learning, where full gradient evaluation is infeasible and ill-conditioned objectives limit SGD. It introduces oLBFGS and establishes convergence guarantees alongside computational and empirical advantages.

  • Problem setting: Large-scale stochastic objectives are expectations over random sample functions, with SVM training providing a canonical example.For SVMs, the random function represents sample loss and the expected objective is mean training loss.
  • Motivation: Full objective gradients become intractable when the sample space is large, motivating stochastic-gradient estimates from small subsamples.The paper places SGD, stochastic Newton, and stochastic quasi-Newton methods in this setting.
  • Motivation: SGD can remain slow on high-dimensional, ill-conditioned objectives because stochastic gradients do not address difficult curvature.Reducing gradient randomness improves asymptotic rates but may not resolve curvature-related practical slowdown.
  • Existing methods: Stochastic quasi-Newton methods adapt curvature without Hessian evaluations, but stochastic Hessian estimates can become nearly singular and amplify noise.This issue undermines oBFGS convergence analysis and can cause erratic numerical behavior.
  • Proposed method: oLBFGS uses a fixed moving window of stochastic gradients, reducing memory and computational cost relative to using all past gradients.Its construction continuously satisfies a secant condition while remaining close to previous curvature estimates.
  • Theory: Under strongly convex sample functions, bounded curvature-approximation traces and determinants yield almost-sure convergence and an expected rate of at least O(1/t).The analysis bounds the condition-number variation of the approximations before proving convergence to the optimum.
  • Empirical evaluation: On synthetic SVMs, oLBFGS matches oBFGS and RES by processed feature vectors, outperforms SGD, and has lower computation time than all three methods.Its advantages increase with feature dimension and can be arbitrarily large.

2. Algorithm definition

oLBFGS combines stochastic gradients with limited-memory curvature updates, using a moving window of recent gradient and variable variations. Its recursive implementation avoids storing full inverse-Hessian matrices while retaining the online quasi-Newton structure.

  • The average objective F(w) is strongly convex when the sample functions are strongly convex, supporting descent toward the optimal argument w∗.
  • Quasi-Newton descent selects positive definite inverse-Hessian approximations B_t^-1 to generate directions, with BFGS approximating curvature from variable and gradient variations.
  • LBFGS restricts curvature information to the most recent τ pairs, reducing storage and computation from O(n^2) to O(τn) per iteration.
  • The inverse-Hessian approximation is formed through τ recursive rank-one updates using an initial positive definite matrix and recent curvature pairs.
  • The recursion computes the inverse-Hessian approximation applied to a vector through τ recursive inner products, without explicitly computing or storing the full matrix.
  • oLBFGS replaces exact gradients with stochastic gradients for descent and curvature estimation, using the same sample set at consecutive iterates to define gradient variation.
  • The stochastic gradient at the next iterate is computed with the current step’s samples because using the next step’s samples for variation does not guarantee convergence.

3. Convergence analysis

Under strong-convexity and stochastic-optimization assumptions, oLBFGS maintains well-conditioned curvature approximations and converges toward an optimum almost surely. Its expected objective error is O(1/t), matching SGD’s theoretical rate, while the bounded curvature matrices control stochastic-gradient amplification.

  • Under bounded stochastic-gradient moments and nonsummable, square-summable step sizes, the expected objective error after t iterations is O(1/t).The rate is dominated by stochastic-gradient noise and is therefore no better theoretically than conventional SGD.
  • Strong convexity of the instantaneous functions ensures positive curvature updates and positive-definite Hessian inverse approximations throughout the oLBFGS recursion.The inner product of variable and stochastic-gradient variations is positive, making the initialization and subsequent updates positive definite.
  • Uniform trace and determinant bounds on the Hessian approximations imply lower and upper eigenvalue bounds, cI ⪯ ˆB_t ⪯ CI.These bounds limit the condition number and prevent curvature estimates from becoming arbitrarily ill-conditioned.
  • Under Assumptions 1–3, the limit infimum of the squared distance to the optimum is zero almost surely over random sample realizations.The analysis also establishes almost-sure summability of a weighted gradient norm and an equivalent subsequential approach to the optimum.
  • The eigenvalue bounds limit stochastic-gradient amplification and prevent arbitrarily small curvature-approximation norms from nullifying progress.The lower bound on ˆB_t bounds the inverse approximation from above, while the upper bound prevents the inverse approximation from becoming arbitrarily small.
  • The paper characterizes oLBFGS as an adaptive reconditioning strategy because its theoretical convergence rate matches SGD despite significant convergence-time improvements in experiments.The convergence-rate limitation persists even if exact Hessians are available, because stochastic-gradient noise remains.

4. Support vector machines

The SVM experiments compare oLBFGS with oBFGS, RES, SGD, and SAG using objective values per processed feature vector and CPU convergence time. oLBFGS matches the other quasi-Newton methods on objective values while offering favorable computation-time performance, especially as feature dimension increases.

  • Experimental setup: The experiments use squared hinge loss on synthetic SVM data with feature dimensions n = 10^2 and n = 10^3, comparing oLBFGS, oBFGS, RES, SGD, and SAG.The training set contains 10^4 feature vectors, with oLBFGS memory set to τ = 10; SGD and SAG use sample size L = 1, while the quasi-Newton methods use L = 5.
  • Convergence versus processed data: After processing L_t = 4 × 10^4 feature vectors at n = 10^2, oLBFGS, oBFGS, and RES achieve objective values close to one another and below SAG and SGD.The average objective values for oLBFGS, oBFGS, and RES are 1.7 × 10^-5, 1.4 × 10^-5, and 1.9 × 10^-5, respectively; SAG and SGD are at least an order of magnitude larger.
  • Convergence versus processed data: At n = 10^3, oLBFGS, oBFGS, and RES remain similar, while their objective values are more than three orders of magnitude below those of SAG and SGD.The respective averages are 9.9 × 10^-6, 9.8 × 10^-6, and 9.5 × 10^-6 for the quasi-Newton methods, versus 2.1 × 10^-2 for SAG and 4.5 × 10^-2 for SGD.
  • Convergence versus processing time: Per-iteration costs scale as O(n) for SGD and SAG, O(τn) for oLBFGS, O(n^2) for oBFGS, and O(n^3) for RES.The differing computational orders make oLBFGS more suitable for higher-dimensional feature vectors than the other online quasi-Newton methods.
  • Convergence versus processing time: For n = 10^2 and target F(w_t) = 10^-4, oLBFGS has the lowest reported average convergence time at 0.073 s.The average times for oBFGS, RES, SGD, and SAG are 0.14 s, 0.26 s, 0.63 s, and 0.50 s, respectively.
  • Convergence versus processing time: For n = 10^3 and target F(w_t) = 10^-5, oLBFGS averages 0.11 s, outperforming SAG, SGD, oBFGS, and RES.The corresponding average times are 1.4 s, 2.0 s, 4.1 s, and 7.7 s for SAG, SGD, oBFGS, and RES, respectively.

5. Search engine advertising

The paper applies oLBFGS to search-engine advertising, using sparse binary features for CTR prediction and comparing its classifier and convergence with SGD. On the advertising data, oLBFGS reaches lower objective values faster and produces more accurate predictions, though test-set accuracy is affected by sample bias.

  • Problem: The CTR task predicts whether an advertisement is clicked from ad, query, and user information using logistic regression.The training data include 236 million searches, and the classifier maps feature vectors and labels to click-probability predictions.
  • Data representation: The feature vector has 174,026 binary components, with at most 148 and on average 20.9 nonzero entries in training.This sparsity makes inner-product cost proportional to the number of nonzero feature entries.
  • Convergence: After processing 3 × 10^4 feature vectors, oLBFGS achieves F(w_t) = 0.65 while SGD remains at F(w_t) = 16 from F(w_0) = 30.oLBFGS reaches the minimum possible cost F(w_t) = 0.65 after processing 1.7 × 10^4 feature vectors.
  • Classifier performance: For the unweighted objective, neither classifier predicts clicked-ad probabilities acceptably, while oLBFGS is much more accurate than SGD under the modified objective.The modified objective uses γ = 18.2; oLBFGS assigns CTR(x; w) ∈ [0.9, 1] to 54.7% of clicked ads versus 15.5% for SGD.
  • Caveat: The advertising test set is sample-biased because displayed ads were selected as likely to be clicked, limiting how broadly the relatively high prediction accuracies should be interpreted.The authors state that SGD would require about 10^6 processed feature vectors to achieve the same accuracy as oLBFGS in this experiment.

6. Conclusions

The paper concludes that oLBFGS converges almost surely under bounded-curvature assumptions and achieves practical efficiency advantages in stochastic optimization experiments. Its execution-time and processed-feature-vector reductions increase with problem dimension, while its expected convergence rate remains O(1/t).

  • Theory: oLBFGS achieves almost-sure convergence for strongly convex stochastic objectives by bounding traces and determinants of curvature-estimation matrices.The analysis assumes sample functions have well-behaved Hessians.
  • Convergence rate: The expected objective error decreases at least at rate O(1/t), a rate customary for stochastic optimization.The conclusion attributes this rate to the difficulty of smoothing noise in stochastic gradient estimates.
  • Experiments: On synthetic SVM data, oLBFGS reduces the number of processed feature vectors and execution time needed to reach target accuracy relative to SGD.It also reduces execution time relative to other stochastic quasi-Newton methods.
  • Implications: These execution-time reductions increase with problem dimension and can become arbitrarily large, and search-engine advertising experiments show the advantages in a practical application.

Appendix A. Proof of Proposition 1

The appendix derives an efficient recursive procedure for applying the oLBFGS inverse-Hessian approximation to a vector. It repeatedly reuses products from the limited-memory factors instead of forming the full matrix explicitly.

  • Recursive products: The sequence p_u is defined recursively so that p_{u+1} = Ẑ_{t-u-1}p_u, starting from p_0 = p.
  • Implementation: Applying the procedure to the oLBFGS inverse-Hessian formula computes the matrix-vector product using the limited-memory summands rather than explicitly constructing the full inverse approximation.
  • Factor reuse: The proof identifies shared matrix products across summands and pulls them through the recursive expansion of the inverse-Hessian expression.
  • Nested recursion: The nested q_u recursion reproduces the terms in the expanded representation, allowing the algebraic expression to be evaluated recursively.

Appendix B. Proof of Lemma 2

The appendix proves bounds on oLBFGS curvature quantities from eigenvalue bounds on instantaneous Hessians. It uses mean Hessians along update segments to relate gradient and variable variations, establishing the stated trace and determinant inequalities.

  • Assumption: The instantaneous Hessian eigenvalues are bounded under the stated assumption, providing the curvature bounds used throughout the proof.
  • Mean Hessian: The mean instantaneous Hessian is defined as the average Hessian along the segment between successive iterates.
  • Gradient relation: The fundamental theorem of calculus relates stochastic-gradient variation to the mean instantaneous Hessian multiplied by the variable variation.
  • Bounding ratios: Positive definiteness and eigenvalue inequalities for the mean Hessian yield the required bounds on the curvature inner-product ratios.
  • Conclusion: The proof concludes that the stated bounds hold for all times t, including the trace- and determinant-related claims.

Appendix C. Proof of Lemma 3

The proof bounds the trace and determinant of the limited-memory Hessian approximation by recursively analyzing its updates and controlling the initial scaled-identity matrix. These bounds also cover initialization and early iterations, whose differences are asymptotically inconsequential.

  • Trace upper bound: The trace recursion uses positive definiteness to discard a negative term and Lemma 2 to bound the remaining update contribution.The resulting inequality is applied recursively over the τ limited-memory updates.
  • Trace upper bound: The trace bound holds for all t≥1, while t=0 and t<τ receive separate initialization bounds that do not affect asymptotic analysis.For t=0, the initial trace equals n; for t<τ, the bound can be tightened using fewer updates.
  • Determinant lower bound: The determinant recursion is simplified using the determinant of a product and a rank-two determinant identity, then bounded through quadratic-form and trace inequalities.The largest normalized quadratic form is controlled by λmax( B̂t,u), which is at most its trace because the matrix is positive definite.
  • Determinant lower bound: The determinant bound combines recursive update factors with bounds on the curvature vectors and the initial scaled-identity approximation.The resulting inequality is evaluated at u=τ, with separate t=0 and t<τ initialization cases.

Appendix D. Proof of Lemma 4

The proof converts the trace and determinant bounds for the positive definite Hessian approximation into uniform upper and lower bounds on every eigenvalue.

  • Upper eigenvalue bound: Each eigenvalue is at most (n + τ) M̃ because the eigenvalues are positive and their sum is bounded by the trace result.The argument applies the trace bound from Lemma 3 to the ordered eigenvalues of B̂t.
  • Lower eigenvalue bound: The determinant lower bound supplies a lower bound on the product of eigenvalues, while the upper eigenvalue bound controls the product of the remaining n−1 eigenvalues.Combining these inequalities yields the lower bound for each eigenvalue.
  • Lower eigenvalue bound: The resulting lower eigenvalue inequality holds uniformly for every eigenvalue of B̂t.This establishes the left-hand inequality in (31).

Appendix E. Proof of Lemma 5

The proof establishes the expected descent inequality for the stochastic objective by combining smoothness, bounded stochastic-gradient moments, and uniform bounds on the inverse curvature approximation.

  • Expected descent: A Taylor expansion using the upper Hessian-eigenvalue bound controls the objective change between consecutive iterates.The iterate difference is substituted from the oLBFGS update before taking conditional expectation.
  • Expected descent: The stochastic-gradient contribution is bounded using the norm-product inequality and a bounded second moment assumption.These bounds are substituted into the conditional expectation inequality to obtain the result in (33).

Appendix F. Proof of Theorem 6

The proof uses a supermartingale argument to show that the expected descent sequence converges and that the gradient norm has a vanishing subsequence. Under the stated curvature and stepsize assumptions, the iterates approach an optimum along a subsequence almost surely.

  • Supermartingale argument: The proof constructs nonnegative sequences αt and βt whose conditional expectation satisfies the supermartingale convergence conditions.This yields almost-sure convergence of αt and finiteness of the sum of βt.
  • Gradient convergence: Because the stepsizes are nonsummable, finite weighted gradient energy implies lim inf_t→∞ ||∇F(wt)||=0 almost surely.A vanishing subsequence of gradient norms is required for the weighted sum to remain finite.
  • Distance to optimality: The lower Hessian-eigenvalue bound converts the vanishing gradient subsequence into lim inf_t→∞ ||wt−w*||^2=0.The conversion uses a Taylor expansion around the optimal argument and the fact that w* minimizes F.

Appendix G. Proof of Theorem 7

The proof establishes that the expected optimality gap converges to zero at rate O(1/t) under a suitable stepsize condition. It derives this result by applying a sequence-convergence lemma after bounding the gradient through Hessian eigenvalues.

  • Theorem 7 claims that E[F(w_t)] approaches F(w∗) at the linear rate O(1/t).
  • Lemma 8 shows that a nonnegative sequence satisfying the required recursive inequality has the convergence rate used in Theorem 7.
  • The induction proof verifies the sequence bound for t = 0 and propagates it from t = s to t = s + 1, establishing the bound for all t ≥ 0.
  • Applying Lemma 8 with the identified constants yields the bound stated in (35), completing the proof of Theorem 7.
  • The Hessian eigenvalue bounds 0 < m and M < ∞ yield a lower bound relating the gradient norm to the objective-value error.
  • With stepsizes ǫ_t = ǫ_0T_0/(T_0 + t) and 2ǫ_0T_0/C > 1, the expected optimality-gap sequence satisfies Lemma 8’s hypotheses.
Loading 1409.2045v1…