PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Block BFGS: Squeezing More Curvature out of Data

Robert M. Gower, Donald Goldfarb, Peter Richtárik

arXiv:1603.09649v1math.OC

TL;DR

Large-scale ERM makes classical per-iteration curvature computations costly, while single Hessian-vector updates provide limited curvature information. The paper introduces stochastic block BFGS with Hessian sketches and SVRG, showing improved results over SVRG-based baselines and linear convergence under stated conditions.

  • Problem

    Large datasets make classical iteration costs prohibitive, and single Hessian-vector updates provide limited curvature information for effective metric matrices.

  • Method

    The method updates a limited-memory inverse-Hessian estimate using randomly sketched subsampled Hessians and combines stochastic block BFGS with SVRG.

  • Results

    The resulting method achieves linear convergence under stated conditions and yields dramatically better results than SVRG and SVRG with classical L-BFGS.

  • Takeaways & Limitations

    Stochastic block BFGS provides a way to incorporate richer curvature information while retaining efficient stochastic updates for large-scale problems.

  • Takeaways & Limitations

    The analysis assumes convex, twice-differentiable loss functions and focuses on settings with very large numbers of data points.

Abstract

from arXiv · show

We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.

1 Introduction

The paper develops stochastic block BFGS methods that use block sketches of subsampled Hessians to obtain richer curvature information for large-scale stochastic optimization. It combines limited-memory updates and sketching strategies with SVRG, proving linear convergence and reporting substantially better practical performance than existing methods.

  • Motivation: Large datasets make full-gradient and classical second-order iterations prohibitively expensive, motivating subsampling-based stochastic optimization.The paper assumes convex, twice-differentiable losses and focuses on settings with very large numbers of examples.
  • Motivation: Single Hessian-vector-product updates provide limited curvature information and may produce ineffective metric matrices.This motivates replacing single-vector curvature updates with block sketches.
  • Stochastic block BFGS: The stochastic block BFGS update uses actions of a subsampled Hessian on multiple random vectors rather than one deterministic vector.A random sketch matrix D_t has relatively few columns, allowing the sketched Hessian to be computed through multiple directional derivatives.
  • Evaluation: Combining limited-memory stochastic block BFGS with SVRG yields a linearly convergent method that substantially outperforms SVRG and SVRG with classical L-BFGS in numerical tests.The paper also positions the method as more versatile and practically superior to SQN because it captures more useful curvature information.
  • Limited-memory method: The limited-memory variant stores recent curvature information in Hessian sketches while allowing a user-defined memory budget.This differs from L-BFGS by using available memory for sketches of previous Hessians.
  • Sketching strategies: The method introduces factored and adaptive sketching forms to preserve positive definiteness, precondition the inverse equation, and improve practical efficiency.The paper reports that adaptive sketching can significantly speed up computation relative to fixed-distribution sketching.

2 Stochastic Block BFGS Update

The stochastic block BFGS update projects the previous metric onto a sketched inverse-Hessian constraint, producing a low-rank stochastic correction whose fixed-matrix analogue converges linearly to the inverse.

  • Stochastic block BFGS update: The update obtains H_t by projecting H_{t−1} onto symmetric matrices satisfying a sketched inverse equation.The constraint acts as a fidelity term, while the objective regularizes the change from the previous metric and yields a low-rank update.
  • Convergence motivation: When applied to a fixed invertible matrix A, the iteration converges to A^-1 at a linear rate.This result motivates using the stochastic iteration to approximately track the inverse Hessian.
  • Stochastic block BFGS update: The projection solution is invariant to replacing the sketch with another matrix having the same column span.It is generally not equivalent to applying sequential rank-two BFGS updates to the sketch columns.
  • Relationship to SDNA: With H_{t−1}=0 and identity-column sketches, stochastic block BFGS recovers the positive semidefinite matrix used by SDNA.The correspondence is a special case, while SDNA operates in the dual formulation.

3 Stochastic Block BFGS Method

The proposed method combines SVRG gradients with stochastic block BFGS curvature updates and several sketching strategies, while limited-memory and factored representations make the method applicable at large scale.

  • Algorithm: The method combines SVRG variance-reduced gradients with stochastic block BFGS updates to incorporate curvature information during optimization.The outer loop computes a full gradient, while the inner loop updates both the gradient estimate and metric.
  • Sketching strategies: Three sketching strategies are provided: Gaussian sketches, delayed previous search directions, and self-conditioning sketches.The delayed strategy stores L recent search directions and updates the metric once every L inner iterations.
  • Sketching strategies: Self-conditioning forms sketches from randomly selected columns of a factored metric matrix to compress and precondition the inverse equation.The construction is motivated by an ideal sketch based on the inverse square root of the subsampled Hessian and can accelerate fixed-matrix convergence.
  • Algorithm: Each iteration computes a variance-reduced gradient, Hessian actions on sketch directions, and a metric-based search direction without forming the full Hessian.The two algorithmic options differ in how the metric action is evaluated and how the next outer iterate is selected.
  • Limited-memory implementation: The limited-memory implementation stores M block curvature triples and applies the metric implicitly through a block two-loop recurrence.It uses recent triples and sets the unavailable base matrix H_{t−M} to the identity in the experiments.
  • Limited-memory implementation: The two-loop implementation costs Mq(4d + 2q) floating-point operations, while forming D_t^T Y_t costs O(q^2d) and its Cholesky factorization costs O(q^3).The stated application cost is approximately O(d^3/2) under the paper’s experimental setting, excluding those additional operations.
  • Factored form: A limited-memory factored form maintains the metric factor through recursive updates using stored curvature pairs and sketch-index sets.The paper presents this as a new limited-memory factored form and uses it to support self-conditioning sketches.

4 Convergence

Under the stated assumptions, the analysis proves linear convergence of Algorithm 1, using bounded metric estimates and an SVRG variance bound with suitable stepsize and inner-loop conditions.

  • Convergence result: The paper proves that Algorithm 1 converges linearly under its stated assumption.The convergence analysis combines new insights with techniques from prior work.
  • Metric bounds: The proof relies on positive constants Γ ≥ γ > 0 that uniformly bound the limited-memory block BFGS metric estimates.The lower bound satisfies γ ≥ 1/(1+MΛ).
  • Gradient estimate: The analysis uses a bound on the variance-reduced minibatch gradient under the paper’s assumptions.The gradient estimator is defined from a minibatch difference plus the full gradient at the outer iterate.
  • Conditions: Linear convergence requires η < γλ/(2Γ^2Λ^2) and an inner-loop length satisfying m ≥ 1/[2η(γλ − ηΓ^2Λ(2Λ − λ))].The stepsize condition also ensures that the right-hand side of the lower bound on m is nonnegative.
  • Proof strategy: The proof derives the result by applying the metric-based update, conditioning on the current iterate, and summing the resulting inequalities over the inner loop.Telescopic cancellation and the relation between the randomly selected output and inner iterates complete the argument.

5 Numerical Experiments

The experiments evaluate stochastic block BFGS variants against SVRG and MNJ on logistic-regression ERM problems, exploring parameter choices, data-pass efficiency, and runtime. Curvature-based methods generally outperform SVRG, while the prev variant is usually the most robust and efficient.

  • Experimental setup: The study compares three stochastic block BFGS variants with SVRG and MNJ on seven logistic-regression ERM problems.All methods use MATLAB implementations and are evaluated using function-value error; the compared block BFGS variants are gauss, prev, and fact.
  • Parameter investigation: For large-scale tests, the experiments use memory M = 5 and default gradient and Hessian subsampling sizes |St| = |Tt| = n1/2.The memory choice follows the parameter study; equal subsampling is used as a practical compromise between time and data-pass efficiency.
  • Parameter investigation: The prev method performs well across a range of parameter choices, although stepsize selection can determine whether it diverges or converges quickly.The method is not overly sensitive to the tested memory, subsampling, and direction parameters, unlike the stepsize.
  • Data passes: On problems with d significantly smaller than n, curvature-based methods perform similarly and significantly better than SVRG.The experiments attribute the broader efficiency gains to incorporating curvature information.
  • Data passes: The prev method is generally the most robust and efficient, except on url-combined, where MNJ is most efficient.The added flexibility of block BFGS can improve convergence relative to the single-vector Hessian sketch used by MNJ.
  • Timed experiments: Timed experiments corroborate the data-pass conclusions, although runtime comparisons are implementation- and machine-dependent.The methods were implemented without sophisticated tricks such as lazy gradient updates.

6 Extensions

The paper identifies extensions based on richer and more adaptive sketching choices, including combining the block BFGS framework with other stochastic optimization algorithms. It also contrasts the finer prev sketch with MNJ’s coarser single-vector strategy.

  • Future sketching methods: New sketching methods, such as Walsh-Hadamard matrices, could further improve the efficiency and accuracy of block BFGS estimates.The paper presents these methods as future research directions rather than established results.
  • Sketching strategies: MNJ uses a single-vector Hessian sketch, whereas prev uses all previous search directions to form a finer sketching matrix.The paper frames these as opposite sketching strategies whose combination or intermediate design remains open.
  • Algorithmic extensions: The metric-learning techniques can be combined with SGD, SDCA, and other optimization algorithms beyond SVRG.The paper focuses experimentally on SVRG but does not restrict the techniques to that method.

7 Proof of Lemma 2

The proof derives a gradient-based inequality for the subsampled objective from smoothness and strong convexity. Taking expectations then relates stochastic gradient norms to function suboptimality terms.

  • Auxiliary-function bound: The auxiliary function hS is minimized at w∗ and has Hessian bounded above by ΛI.This establishes the smoothness ingredients used in the subsequent inequality.
  • Auxiliary-function bound: Minimizing the quadratic upper bound in b yields ∥∇hS(w)∥2^2 ≤ 2ΛhS(w).The result follows from the displayed inequality after optimizing the displacement b.
  • Expected-gradient relation: After switching back to f and taking expectation over S, the proof obtains a stochastic-gradient bound in terms of function suboptimality.The expectation step uses the notation δf(x) = f(x) − f(w∗).
  • Expected-gradient relation: The final bound combines smoothness and strong convexity through terms involving Λ, λ, δf(x), and δf(w).The displayed inequality includes 4Λδf(x) + 4(Λ − λ)δf(w).

8 Proof of Lemma 1

The proof analyzes the block BFGS metric update and establishes conditions under which the updated inverse-Hessian approximation remains positive definite. It then bounds its largest and smallest eigenvalues using the limited-memory representation and matrix identities.

  • Block update: The block BFGS update can be expressed using G, Δ, Y, H, and the sketch-derived matrix V = YΔDᵀ.This notation identifies the components used in the update formula.
  • Block update: The update has the form H+ = H − VᵀH − HV + VᵀHV + DΔDᵀ.The formula describes how the previous metric is modified by the block curvature information.
  • Positive definiteness: If G and H are positive definite and D has full rank, then H+ and its inverse B+ are positive definite and well defined.The proof invokes the Sherman-Morrison-Woodbury identity to derive the inverse-update formula.
  • Spectral bounds: The analysis bounds λmax(H+) from above and λmin(H+) from below through operator-norm estimates.The lower eigenvalue is represented as 1/∥B+∥2.
  • Spectral bounds: The conditioning analysis introduces κ = Λ/λ and α = (1 + √κ)^2 alongside projection-based matrix expressions.These quantities parameterize the resulting spectral estimates.
  • Limited-memory bound: The limited-memory metric uses at most M block updates because Ht−M = I.This identity provides the starting point for the limited-memory bound.
Loading 1603.09649v1…