PaperlayerView exact revision on arXiv

Source-linked AI summary

RES: Regularized Stochastic BFGS Algorithm

Aryan Mokhtari, Alejandro Ribeiro

arXiv:1401.7625v1cs.LGmath.OCstat.ML

TL;DR

Stochastic optimization needs methods that avoid SGD’s large iteration counts without the computational burden of Hessian-based second-order methods. The paper introduces regularized stochastic BFGS, proves convergence under Hessian bounds, and reports reduced convergence time, particularly for challenging problem settings.

  • Problem

    SGD has manageable gradient costs but may require many iterations, while stochastic second-order methods are impractical because Newton-step estimates are difficult to compute.

  • Method

    RES uses stochastic gradients for descent and curvature estimation, regularizing BFGS to prevent near-singular Hessian approximations.

  • Results

    RES converges almost surely under bounded sample-function Hessians, has at least linear expected convergence, and reduces convergence time relative to SGD.

  • Takeaways & Limitations

    RES is particularly advantageous for problems with large condition numbers or dimensionality and is also applied to support vector machines.

Abstract

from arXiv · show

RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments can be prohibitive in high dimensional problems. Application of second order methods, on the other hand, is impracticable because computation of objective function Hessian inverses incurs excessive computational cost. BFGS modifies gradient descent by introducing a Hessian approximation matrix computed from finite gradient differences. RES utilizes stochastic gradients in lieu of deterministic gradients for both, the determination of descent directions and the approximation of the objective function's curvature. Since stochastic gradients can be computed at manageable computational cost RES is realizable and retains the convergence rate advantages of its deterministic counterparts. Convergence results show that lower and upper bounds on the Hessian egeinvalues of the sample functions are sufficient to guarantee convergence to optimal arguments. Numerical experiments showcase reductions in convergence time relative to stochastic gradient descent algorithms and non-regularized stochastic versions of BFGS. An application of RES to the implementation of support vector machines is developed.

I. INTRODUCTION

The paper introduces RES, a regularized stochastic BFGS method for convex stochastic optimization, addressing slow SGD convergence and impractical stochastic second-order methods. It establishes convergence guarantees and reports improved performance, especially for ill-conditioned or high-dimensional problems.

  • Motivation: SGD uses manageable unbiased gradient estimates but may require many iterations, especially as problem dimension and condition number increase.Exact gradients are generally impractical, while unbiased Newton-step estimates are difficult to compute.
  • Method: RES regularizes stochastic BFGS to avoid near-singular curvature estimates while retaining gradient-based curvature information.The method modifies the proximity condition so Hessian-approximation eigenvalues remain above a threshold.
  • Theory: Lower and upper Hessian bounds on sample functions guarantee almost-sure convergence of RES to the optimal argument, with at least linear convergence in expectation.The expected rate is characterized as linear, comparable in order to typical stochastic optimization rates.
  • Numerical results: For ill-conditioned quadratics, RES outperforms SGD by an order of magnitude, while its iteration count doubles when dimension increases tenfold.For well-conditioned objectives, RES and SGD exhibit comparable performance.
  • Applications: RES reduces convergence time relative to SGD and is adapted to support vector machines, where numerical analysis evaluates convergence time, stability, and classification accuracy.The paper also compares RES with non-regularized stochastic BFGS.

B. RES: Regularized Stochastic BFGS

RES combines stochastic gradients with a regularized BFGS curvature update, using the same-sample gradient variation to preserve the required secant condition and ensure valid updates.

  • RES replaces deterministic gradients with stochastic gradients in both the descent step and curvature approximation update.The algorithm uses stochastic gradients to compute descent directions and update the Hessian approximation.
  • The bias term ΓI is added to the inverse curvature approximation to hedge against random variations and ensure convergence.Relative to SGD, RES preconditions stochastic gradients with the regularized curvature matrix plus ΓI.
  • The curvature update enforces a stochastic secant condition and selects the closest admissible approximation subject to regularization.The update uses the modified stochastic gradient variation and requires a positive inner product condition.
  • Each RES iteration acquires L independent samples, computes stochastic gradients and variations, performs descent, and updates the Hessian approximation.The two core iteration steps are descent and Hessian-approximation updating.
  • Using the same samples at wt and wt+1 for the curvature update costs more gradient evaluations but guarantees the positivity condition needed by the update.The alternative uses fewer evaluations but cannot guarantee the condition required for the regularized update.

III. CONVERGENCE

RES convergence is established under bounded instantaneous Hessian eigenvalues, bounded stochastic-gradient second moments, and a regularization constant smaller than the minimum Hessian eigenvalue.

  • Assumptions: The convergence analysis assumes twice-differentiable instantaneous objectives with Hessian eigenvalues bounded between positive constants ˜m and ˜M.These bounds apply uniformly across instantaneous functions and induce corresponding bounds for the average objective.
  • Assumptions: The stochastic-gradient second moment is bounded by a constant S2, limiting random variation in the descent estimates.This is the stochastic-gradient assumption used in the convergence proof.
  • Curvature condition: Choosing δ < ˜m ensures the modified gradient variation satisfies (ˆrt −δvt)^Tvt ≥ (˜m −δ)∥vt∥2 > 0.This positivity condition makes the regularized curvature update well-defined.
  • Curvature condition: Regularization keeps the curvature approximation uniformly positive definite, thereby upper-bounding the eigenvalues of its inverse.Initializing ˆB0 ≻δI and applying the update recursively yields ˆBt ≻δI for all t ≥ 0.
  • Convergence guarantee: Under the assumptions and the prescribed step-size conditions, the iterates approach optimality in the limit-infimum sense with probability 1.The proof uses a supermartingale argument and establishes lim inf_t→∞∥wt −w∗∥2 = 0 almost surely.

A. Rate of Convergence

The paper characterizes RES’s expected convergence rate under its assumptions and shows that its objective error decays at order O(1/t), while practical convergence-time improvements remain possible.

  • O(1/t) is the order of RES’s expected objective-value error after t iterations under the stated assumptions.The result applies to step sizes of the form ϵt = ϵ0T0/(T0 + t) with suitable parameters.
  • RES has at least a linear convergence rate in expectation, comparable in rate to conventional stochastic optimization algorithms.The paper distinguishes this rate statement from improvements in convergence time observed numerically.

IV. NUMERICAL ANALYSIS

The numerical analysis compares RES and SGD on stochastic quadratic objectives while varying conditioning and dimensionality, measuring the number of processed stochastic functions needed to reach a target relative error.

  • The test problems use positive-definite diagonal quadratic objectives whose average condition number is controlled by the matrix A.The random perturbation changes instantaneous functions while the average objective remains quadratic with matrix A.
  • In Fig. 1, RES reaches a given relative accuracy in fewer iterations than SGD for the tested stochastic quadratic function.The figure plots relative distance to optimality against the number of processed stochastic functions.
  • The convergence-time metric counts stochastic functions processed until ∥wt −w∗∥/∥w∗∥ ≤ ρ.This metric is used to compare computational effort across algorithms.

A. Effect of problem’s condition number

RES is compared with SGD across quadratic problems with different condition numbers. Its advantage is modest for well-conditioned objectives but becomes substantially larger for ill-conditioned ones.

  • A. Effect of problem’s condition number: At equal relative accuracy, RES reaches 3.8 × 10^-2 after 190 function evaluations, whereas SGD requires 1,200.The comparison uses n = 50 and an ill-conditioned problem with ξ = 2.
  • A. Effect of problem’s condition number: With sample sizes L = 1, 2, 5, 10, and 20, RES convergence time first improves and then worsens as L increases.The average convergence time decreases from small to moderate L and increases from moderate to large L.
  • A. Effect of problem’s condition number: For well-conditioned problems, RES reduces the average processed functions from 601 for SGD to 144.The corresponding condition number is 10^0, and the improvement is described as nondramatic.

B. Choice of stochastic gradient average

The stochastic-gradient sample size L trades off curvature-estimation quality against function-evaluation cost. Increasing L reduces variability, but the mean convergence time is best at small-to-moderate values.

  • B. Choice of stochastic gradient average: The reported distributions compare RES sample sizes L = 1, 2, 5, 10, and 20, treating τ > 10^4 as convergence failure.The experiments use n = 50, ξ = 2, and J realizations for each L.
  • B. Choice of stochastic gradient average: Increasing L monotonically decreases the variance of RES convergence times.The empirical standard deviation falls from 2.8 × 10^3 at L = 1 to 22.7 at L = 20.
  • B. Choice of stochastic gradient average: The empirical mean convergence time decreases from 3.5 × 10^3 at L = 1 to 3.3 × 10^2 at L = 5, then increases to 1.2 × 10^3 at L = 20.The intermediate value at L = 2 is 6.3 × 10^2, while L = 10 gives 5.8 × 10^2.
  • B. Choice of stochastic gradient average: Larger samples produce curvature estimates closer to the Hessian, but beyond moderate L the additional evaluations provide no comparable curvature benefit.For L = 5, 10, and 20, actual convergence times τ/L have similar distributions.

C. Effect of problem’s dimension

As dimension increases, RES degrades more smoothly than SGD. RES has comparable or better median convergence times at larger dimensions and fewer extreme convergence failures.

  • C. Effect of problem’s dimension: For n = 5, SGD has a lower median convergence time than RES: 265 versus 400 processed functions.RES convergence times are more concentrated, and all RES realizations lie between 70 and 1,095.
  • C. Effect of problem’s dimension: For n = 50, RES has median convergence time 950 versus 7,942 for SGD.At this dimension, SGD is described as unworkable.
  • C. Effect of problem’s dimension: At n = 50, SGD fails within 5 × 10^5 iterations with probability 0.07, whereas RES does so with probability 3 × 10^-3.SGD exceeds 10^4 iterations with probability 0.45, while RES converges in fewer than 10^4 iterations in all other cases.
  • C. Effect of problem’s dimension: RES convergence time increases smoothly with dimension, while SGD convergence time increases faster.The experiments use dimensions n = 5, 10, 20, and 50 across 1,000 problem instances.

V. SUPPORT VECTOR MACHINES

The paper adapts RES to support vector machines by treating training points as random samples in a regularized classification objective. The resulting stochastic formulation supports minibatch gradient updates.

  • V. SUPPORT VECTOR MACHINES: An SVM seeks a vector w defining a hyperplane that separates training points according to their binary classes.The desired signs are w^T x_i > 0 for positive examples and w^T x_i < 0 for negative examples.
  • V. SUPPORT VECTOR MACHINES: The SVM objective combines a loss function with the regularization term λ∥w∥^2/2, where λ > 0.The paper lists hinge, squared hinge, and log loss as possible choices.
  • V. SUPPORT VECTOR MACHINES: Each training point θ_i = (x_i, y_i) is assigned a uniform probability distribution, converting the SVM objective into a stochastic optimization problem.The random functions are sampled with probability 1/N from the training set.
  • V. SUPPORT VECTOR MACHINES: At each RES iteration, L training points are sampled uniformly to form the stochastic gradient input.The sampled feature vectors and class values are assembled into minibatch vectors before evaluating the instantaneous-function gradient.

A. Numerical Analysis

Numerical experiments show that RES reduces convergence time relative to SGD, especially for larger dimensions, and improves SVM classification accuracy. Regularization also stabilizes stochastic BFGS when small curvature eigenvalues occur.

  • Experimental setup: The experiments use squared hinge loss with N = 104 training vectors and stochastic-gradient sample size L = 5 for RES.
  • Convergence: RES reduces convergence time relative to SGD, with larger advantages as feature dimension increases.For n = 40, RES remains practicable while SGD becomes too slow for practical use.
  • Convergence: For n = 4, RES reaches F(wt) = 6.5 × 10−2 after processing 315 vectors, whereas SGD requires 1.74 × 103 vectors.
  • Support vector machines: RES achieves a mean SVM classification accuracy of 82.2%, compared with at most 65% for SGD and 98% for a clairvoyant classifier.RES exceeds the SGD accuracy with probability 0.98 but fails to produce a working classifier with probability 0.02.
  • Regularization: Regularization limits jumps caused by small curvature eigenvalues and allows RES to recover a reasonable curvature estimate.Non-regularized stochastic BFGS eventually suffers catastrophic deviation and behaves no better than SGD.

APPENDIX A: PROOF OF PROPOSITION 1

The appendix derives the regularized BFGS update by solving a convex matrix optimization problem through Lagrangian duality. The derivation uses the optimal dual variable and matrix identities to obtain the explicit update and establish its positive-definiteness property.

  • Optimization formulation: The regularized BFGS update is obtained by solving a convex optimization problem in the Hessian approximation matrix Z.
  • Dual formulation: Lagrangian duality introduces a multiplier for the secant constraint Zvt = rt and defines the dual function by minimizing the Lagrangian over Z ⪰ 0.
  • Explicit update: Setting the dual-function gradient to zero yields the optimal multiplier, which is substituted into the Lagrangian minimizer to derive the update for Bt+1.The derivation applies the Sherman-Morrison formula to invert the resulting matrix expression.
  • Positive definiteness: The update includes δI, and the remaining terms are shown to be positive semidefinite, establishing the required lower eigenvalue bound.

APPENDIX B: PROOF OF THEOREM 2

The proof establishes Theorem 2 by showing that the expected optimality gap satisfies a recursive inequality and then applying an induction lemma to obtain an O(1/t) convergence rate.

  • Proof strategy: Theorem 2 bounds the expected optimality gap E[F(w_t)] − F(w∗) by a quantity that decays as Q/(t + t_0).The proof identifies the sequence of expected optimality gaps with the sequence controlled by the induction argument.
  • Conclusion: The induction step preserves the bound for every t ≥ 0, completing the proof of the theorem's expected convergence result.The base case and the implication from t = s to t = s + 1 establish validity for all times.
  • Proof strategy: Lemma 3 shows that a nonnegative sequence satisfying the required recursion has the linear convergence rate specified by the theorem.The lemma is proved by induction, first establishing the bound at t = 0 and then propagating it from s to s + 1.
  • Deriving the recursion: The RES optimality-gap recursion is derived by subtracting F(w∗), taking expectations, and using the Hessian lower bound to relate gradient norms to objective-value errors.The Hessian eigenvalues are assumed bounded between 0 < m and M < ∞, enabling the gradient-norm bound used in the recursion.
  • Deriving the recursion: With stepsizes ϵ_t = ϵ_0T_0/(T_0 + t) and 2ϵ_0T_0Γ > 1, the recursion satisfies Lemma 3's conditions.The constants are identified as c = 2ϵ_0T_0Γ, b = ϵ_0^2T_0^2K, and t_0 = T_0.
Loading 1401.7625v1…