PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Robert M. Gower, Filip Hanzely, Peter Richtárik, Sebastian Stich

arXiv:1802.04079v2math.OCcs.NAmath.NA

TL;DR

The paper addresses the cost of large-scale second-order optimization and the absence of accelerated quasi-Newton updates. It develops accelerated sketch-and-project methods for linear systems and positive definite matrix inversion, then applies them to stochastic and deterministic BFGS; experiments report speed-ups over classical BFGS.

  • Problem

    Large-scale Newton and quasi-Newton optimization requires costly Hessian-related computation, while acceleration had previously focused on gradient updates.

    Source: §1 · pp. 1–2

  • Method

    The paper accelerates sketch-and-project methods in Euclidean spaces, specializes them to positive definite matrix inversion, and uses the resulting symmetric iterates in stochastic and deterministic BFGS.

    Source: §3 · p. 4, §7 · p. 23

  • Results

    The accelerated methods can produce speed-ups over classical BFGS, with experiments showing accelerated BFGS outperforming classic BFGS on all four datasets.

    Source: §5.2 · p. 10, §7 · p. 23

  • Takeaways & Limitations

    Nesterov’s acceleration can be applied to quasi-Newton updates, opening an acceleration direction beyond gradient methods.

    Source: §7 · p. 23

    The accelerated BFGS method lacks a convergence analysis on a suitable function class, and parameter selection under enforced symmetry cannot generally be estimated.

    Source: §3.4 · p. 7, §7 · p. 23

Abstract

from arXiv · show

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices in such a way that all iterates (approximate solutions) generated by the algorithm are positive definite matrices themselves. This opens the way for many applications in the field of optimization and machine learning. As an application of our general theory, we develop the {\em first accelerated (deterministic and stochastic) quasi-Newton updates}. Our updates lead to provably more aggressive approximations of the inverse Hessian, and lead to speed-ups over classical non-accelerated rules in numerical experiments. Experiments with empirical risk minimization show that our rules can accelerate training of machine learning models.

1 Introduction

The paper targets large-scale second-order optimization by accelerating sketch-and-project methods for linear systems and using them to construct accelerated quasi-Newton updates. It addresses Newton’s computational cost while preserving symmetry and positive definiteness for matrix-inversion iterates.

1 Introduction

  • Newton’s method is inefficient for large-scale problems because it computes the Hessian and solves a linear system at every iteration.Source: §1 · pp. 1–2
  • The paper proposes accelerating BFGS by replacing random Hessian sketching with deterministic updates, extending acceleration beyond gradient methods.Source: §1 · p. 2
  • Quasi-Newton methods approximate inverse-Hessian updates, while stochastic variants enforce exact inverse behavior over a randomly sketched subspace.Source: §1 · p. 2

1.1 Sketch-and-project for linear systems

  • The paper develops accelerated sketch-and-project methods for general Euclidean-space linear systems and applies them to positive definite matrix inversion.Source: §1.1 · pp. 2–3
  • Prior sketch-and-project work includes randomized Kaczmarz, coordinate-style methods, stochastic reformulations, and accelerated variants with limitations on the acceleration setting.Source: §1.1 · pp. 2–3
  • The approach constructs special sketch operators that preserve symmetry and positive definiteness across matrix-inversion iterates, a property needed for quasi-Newton use.Source: §1.1 · p. 3

2 Contributions

The contributions generalize accelerated sketch-and-project theory, develop faster positive definite matrix inversion, and derive stochastic and deterministic accelerated quasi-Newton methods. The deterministic BFGS scheme is supported empirically rather than by transferred theoretical convergence rates.

2 Contributions

  • The paper generalizes accelerated sketch-and-project analysis to linear operator systems in Euclidean spaces with a self-contained convergence analysis.Source: §2 · p. 3
  • The accelerated positive definite matrix-inversion algorithm depends on spectral parameters µ and ν, and with correct values is always faster than the non-accelerated method.Source: §2 · p. 3
  • Symmetric iterates allow the matrix-inversion algorithm to estimate inverse Hessians, yielding the first accelerated stochastic quasi-Newton method.Source: §2 · p. 3
  • The deterministic accelerated BFGS scheme replaces random Hessian sketches with deterministic updates, but its theoretical convergence rates do not transfer.Source: §2 · p. 4
  • Numerical experiments show that an appropriate parameter combination can make accelerated BFGS converge slightly faster.Source: §2 · p. 4

2.1 Outline

  • The paper’s workflow develops Euclidean-space linear-system acceleration, applies it to matrix inversion, uses that result for BFGS acceleration, and evaluates the methods numerically.Source: §2.1 · p. 4

3 Accelerated Stochastic Algorithm for Matrix Inversion

The paper develops an accelerated randomized sketch-and-project method for linear systems in Euclidean spaces and applies it to matrix inversion. Its convergence can improve substantially over non-accelerated sketch-and-project, including potentially reducing iteration counts to their square-root scale.

3 Accelerated Stochastic Algorithm for Matrix Inversion

  • The method extends accelerated sketch-and-project to linear systems in general finite-dimensional Euclidean spaces and uses the result for matrix inversion and quasi-Newton updates.The framework samples random linear operators and applies accelerated iterates to obtain successive approximations.Source: §3 · p. 4, §3.1 · pp. 4–5

3.2 Key assumptions and quantities

  • The algorithm assumes an exactness condition linking the system operator to the expected sketch operator, under which the associated Z operator is self-adjoint and positive.The exactness assumption holds for the matrix-inversion sketching strategies considered.Source: §3.2 · p. 5

3.3 Convergence and change of the norm

  • Accelerated sketch-and-project converges linearly with iteration complexity O((sqrt(ν)/µ) log(1/ϵ)), versus O((1/µ) log(1/ϵ)) for the non-accelerated method.Because each iteration has the same order of cost, the method can be as fast as the square root of the non-accelerated iteration count.Source: §3.3 · p. 6

3.4 Coordinate sketches with convenient probabilities

  • For coordinate sketches with probabilities proportional to A_i,i, the parameters are µ_P = λ_min(A)/Tr(A) and ν_P = Tr(A) min_i A_i,i.The accelerated rate improves over the non-accelerated rate when the smallest diagonal element is substantially larger than the smallest eigenvalue.Source: §3.4 · p. 6
  • These coordinate-sketch parameters are correct for matrix inversion without symmetry enforcement, but their behavior under enforced symmetry and different sketching strategies remains unquantified.The paper therefore evaluates parameter selection empirically and considers how to choose µ and ν safely in practice.Source: §3.4 · p. 7

4 Accelerated Stochastic BFGS Update

The paper accelerates stochastic BFGS updates by viewing inverse-Hessian updates as symmetric sketch-and-project steps for AX = I, then incorporates the resulting matrix-inversion method into BFGS. It also proposes a deterministic accelerated BFGS variant, but leaves its convergence analysis open.

4 Accelerated Stochastic BFGS Update

  • The inverse-Hessian update in quasi-Newton methods is a symmetric sketch-and-project step for solving AX = I, motivating accelerated stochastic BFGS updates.The matrix A represents an approximation of the Hessian, and symmetry is enforced throughout the update.Source: §4 · p. 7

4.1 Accelerated matrix inversion

  • Algorithm 2 accelerates the symmetric matrix-inversion sketch-and-project update, with convergence inherited from the general accelerated theory.The construction applies the accelerated method to the corresponding linear-operator equation.Source: §4.1 · pp. 7–8
  • With symmetry preserved, the rate parameter satisfies λ_min(E[Z]) between λ_min(E[P]) and twice λ_min(E[P]), potentially doubling the corresponding lower bound.This improved rate is identified as new relative to the method without symmetry preservation.Source: §4.1 · p. 8

4.2 Vectorizing – a different insight

  • Vectorization converts the symmetric matrix-inversion update into a sketch-and-project iteration for a linear system in R^n2, providing an alternative proof route.The operator C encodes the constraint X = X^⊤.Source: §4.2 · p. 8

4.3 Accelerated BFGS as an optimization algorithm

  • The deterministic accelerated BFGS variant applies the accelerated update to the matrix Y_k, but the paper gives no convergence theorem and does not recommend it as a default solver.Its theoretical analysis is left for future work, while numerical experiments examine its potential and limitations.Source: §4.3 · pp. 8–9

5 Numerical Experiments

The experiments evaluate accelerated matrix inversion across sketching strategies and matrix spectra, then test accelerated BFGS on logistic-regression datasets. Acceleration provides speedups when parameters are well estimated, including faster BFGS convergence on all four tested datasets.

5.1 Accelerated Matrix Inversion

  • The study evaluates symmetric positive definite matrix inversion using convenient-probability coordinate, uniform coordinate, and Gaussian sketches on artificial matrices and LIBSVM ridge-regression Hessians.The experiments vary eigenvalue spectra and sketching distributions.Source: §5.1 · p. 9

5 Numerical Experiments

  • Parameter sensitivity is tested because exact µ and ν may be unavailable, including alternative µ choices and settings where µ is chosen heuristically.The BFGS experiments manually probe parameters because the matrix-inversion theory does not apply directly in that setting.Source: §5.1 · p. 9, §5.2 · p. 10

5.1 Accelerated Matrix Inversion

  • Acceleration speedups depend on the structure of A and the sketching strategy, with especially large gains for ill-conditioned matrices whose eigenvalues cluster near the largest value.Using parameters from (16) is robust across sketching strategies and is worst-case no slower than the nonaccelerated algorithm.Source: §5.1 · pp. 9–10

5.2 BFGS Optimization Method

  • The BFGS evaluation centers and normalizes data, adds an intercept, sets λ = 1/m, and uses a fixed grid-searched stepsize.The accelerated method is denoted BFGS-a-µ-ν in the plots.Source: §5.2 · p. 10
  • On all four datasets, accelerated BFGS outperforms classic BFGS and also converges faster in time.The comparison uses phishing, mushrooms, australian, and splice datasets.Source: §5.2 · p. 10, Figure 2 · p. 10

6 Further Experiments with Accelerated quasi-Newton Updates

Further experiments examine accelerated inverse-Hessian updates across controlled spectra, parameter choices, and LIBSVM problems. Gains are strongest with suitable parameters and favorable matrix structure, while inaccurate parameters or some optimization datasets can remove the advantage.

6.1 Simple and well understood artificial example

  • Coordinate-sketch acceleration can achieve arbitrary speedup as β = −n−1 and α → 1, whereas Gaussian sketches can slow down under mismatched parameters.For symmetry-enforced coordinate sketches, the authors suspect substantial speedups even with parameters estimated without symmetry.Source: §6.1 · p. 12

6.2 Random artificial example

  • Across random spectra, acceleration and symmetry preservation combine to improve convergence, but the practical speedup depends strongly on A's structure.The experiments cover uniform eigenvalue grids, one-small-rest-larger spectra, and one-large-rest-smaller spectra.Source: §6.2 · pp. 12–14
  • When acceleration parameters are reasonable but not exact, accelerated performance is essentially the same as the nonaccelerated method on artificial and LIBSVM examples.This behavior is reported for settings without access to λmin(A) and for Gaussian sketches with reused parameters.Source: §6.2 · pp. 14, 16, §6.3 · pp. 20, 22

6.2.1 Sensitivity to the acceleration parameters

  • The accelerated method requires ν to be large enough; small ν combined with small µ is usually non-convergent, while sufficiently large µ can yield fast convergence once ν is appropriate.This sensitivity study uses exponential grids of µ and ν and compares fixed-time progress against nonaccelerated updates.Source: §6.2.1 · pp. 16, 18

6.3 Experiments with LIBSVM

  • The LIBSVM tests use ridge-regression Hessians ∇2f(x) = A⊤A + λI with normalized datapoints and λ = 1/m.Both artificial examples and LIBSVM data are tested, with parameters precomputed where possible.Source: §6 · p. 11, §6.3 · p. 18
  • On most LIBSVM problems, accelerated coordinate sketches significantly outperform nonaccelerated updates, while Gaussian sketches are generally comparable.Finely tuned parameters can produce substantial gains for some problem classes.Source: §6.3 · pp. 18, 20

6.4 Additional optimization experiments

  • Despite more costly iterations, accelerated BFGS can converge faster in time than classic BFGS.The time-versus-residual comparison is reported for the same problems used in the earlier BFGS experiments.Source: §6.4 · p. 22, Figure 29 · p. 22
  • Madelon, covtype, and a9a show little benefit because accelerated inverse-Hessian estimates remain close to standard BFGS even with extreme µ and ν.These datasets therefore offer little room for improvement from acceleration.Source: §6.4 · p. 22, Figure 31 · p. 22, Figure 30 · p. 22

7 Conclusions and Extensions

The paper develops accelerated sketch-and-project inversion for positive definite matrices and uses it to construct accelerated stochastic and deterministic BFGS updates. Under suitable parameters and problem conditioning, the methods can provide significant speedups, including experimentally over classical BFGS.

7 Conclusions and Extensions

  • Accelerated sketch-and-project inversion preserves positive definiteness and supports accelerated stochastic and deterministic BFGS updates.The authors describe these as the first accelerated quasi-Newton updates, to the best of their knowledge.Source: §7 · p. 23
  • Significant speedups may occur for matrix inversion and stochastic BFGS when parameters are chosen carefully and the problem structure and conditioning are favorable.Source: §7 · p. 23
  • Experiments confirm that the accelerated methods can speed up optimization relative to classical BFGS.Source: §7 · p. 23
  • A supported future direction is convergence analysis of accelerated deterministic or stochastic BFGS on a suitable class of functions.Source: §7 · p. 23
  • The authors also identify limited-memory extensions and efficient competition with first-order methods for empirical risk minimization as further research directions.Source: §7 · p. 23

A Proofs for Section 3

The appendices establish operator bounds, invariant-range properties, and parameter choices supporting the accelerated sketch-and-project analysis, then extend the framework to changed norms and non-unit stepsizes.

A.1 Proof of Lemma 2

  • Lemma 2’s proof uses self-adjointness, convexity, and Jensen’s inequality to derive bounds involving the expected sketch operator and its pseudoinverse.Source: §A.1 · pp. 26–27

A.2 Technical lemmas to prove Theorem 3

  • The technical lemmas show that y_k−x*, x_k−x*, and v_k−x* remain in Range(A*) throughout the iterations.Source: §A.2 · p. 27

A.3 Proof of Theorem 3

  • Theorem 3’s proof forms a recurrence by choosing γ, α, and β so that P1=γ^2ν and P2=0, while making β as small as possible.Source: §A.3 · pp. 28–29

A.4 Changing norm

  • Changing variables with an invertible positive self-adjoint B reduces the least-norm problem to Algorithm 1 applied to the transformed system matrix AB^-1/2.Source: §A.4 · pp. 29–30
  • Reversing the variable transformation recovers the main theorem’s form and the exact result from [24] in a more general setting.Source: §A.4 · p. 30

B Proof of Corollary 4

C Adding a stepsize ω

D Allowing for different α

This section studies how α changes the convergence rate and relates the accelerated method to non-accelerated behavior at limiting parameter choices.

D Allowing for different α

E Proof of Theorem 9

The proof of Theorem 9 adapts the key contraction lemma to the stepsize update and follows the proof of Theorem 3 with the modified bound.

E Proof of Theorem 9

  • The stepsize update gives x_{k+1}−x*= (1−ωZ_k)(y_k−x*), enabling a corresponding adaptation of Lemma 8.Source: E Proof of Theorem 9 · p. 32
  • Replacing Lemma 8 with Lemma 14 in the recurrence proof yields the parameter condition needed to establish Theorem 9.Source: E Proof of Theorem 9 · p. 32

F Proof of Theorem 10

The proof derives a convergence rate governed by ρ = max{β, sβ} and selects parameters to make β as small as possible while ensuring convergence.

F Proof of Theorem 10

  • ρ = max{β, sβ} gives the convergence rate in the notation of Theorem 10.Source: F Proof of Theorem 10 · p. 33
  • Choosing β and γ so that β is as small as possible yields the best convergence rate regardless of s.The value of s itself depends on γ.Source: F Proof of Theorem 10 · p. 33
  • ν ≤ 2s implies β⋆(s) ≤ 1, and the associated parameter setting guarantees ρ ≤ 1.The setting uses γ⋆(s) = 1 (1−sβ⋆(s))ν.Source: F Proof of Theorem 10 · p. 33

G.1 Proof of Theorem 5

The proof transforms matrix inversion into a linear-system framework, analyzes the resulting operators and accelerated iterates, and connects the construction to Theorem 5 through coordinate changes and sketch-and-project formulations.

G.1 Proof of Theorem 5

  • The proof uses a weighted-to-standard Frobenius-norm coordinate change, defining P and the constraint operator in transformed coordinates.The transformed matrix is ˆX = A1/2XA1/2, with P = A1/2S(S⊤AS)−1S⊤A1/2.Source: §G.1 · pp. 33–34
  • The operator Z is represented as Z(X) = X − (I − P)X(I − P) = XP + PX(I − P).Source: §G.1 · p. 34
  • Vectorization and spectral bounds are used to analyze the operator parameter µ, including λmin bounds involving E[P] and E[Z].The proof denotes x = Vec(X) and uses the Frobenius inner-product representation.Source: §G.1 · p. 34, §G.2 · p. 35
  • The accelerated iterates are written in transformed coordinates, and Theorem 3 gives convergence of ˆVk and ˆXk to the identity matrix.The updates use ˆYk, ˆGk, ˆXk+1, and ˆVk+1 with parameters α, β, and γ.Source: §G.1 · p. 34

G.2 Matrix inversion as linear system

  • Matrix inversion is formulated as a linear system in vectorized variables, with symmetry enforced by a matrix C satisfying Cx = 0 if and only if X = X⊤.General linear sketches are represented by a suitable n2 × n2 matrix S0, with left-multiplication sketches using S0 = (I ⊗S).Source: §G.2 · p. 35, §G.2.1 · p. 35

G.2.1 Alternative proof of Theorem 5

  • The alternative proof identifies the formulation as sketch-and-project, derives its update, and applies prior results to recover Theorem 5.The update is expressed in vectorized form and compared with the operator P after a coordinate transformation.Source: §G.2.1 · p. 35

H Linear Operators in Euclidean Spaces

  • The appendices define Euclidean-space operator notions, positive operators and square roots, traces of projections, and pseudoinverses used by the proofs.The pseudoinverse is unique and bounded under closed-range assumptions, and remains self-adjoint and positive for self-adjoint positive operators.Source: H Linear Operators in Euclidean Spaces · pp. 35–36, §H.1 · p. 36

H.2 Pseudoinverse

  • For closed-range operators, the pseudoinverse projects onto Range(T∗) along Null(T) and characterizes minimum-norm solutions of Tx = d.The stated properties include positivity for self-adjoint positive operators and the minimum characterization for d ∈ Range(T).Source: §H.2 · p. 37
Loading 1802.04079v2…