Source-linked AI summary
A Stochastic Quasi-Newton Method for Large-Scale Optimization
R. H. Byrd, S. L. Hansen, J. Nocedal, Y. Singer
TL;DR
Large-scale stochastic learning needs curvature information, but noisy gradient differences can make quasi-Newton updates unstable. The paper proposes limited-memory BFGS with periodically averaged, sub-sampled Hessian-vector products; experiments indicate improved effectiveness and robustness, including performance exceeding SGD in one study.
Problem
Constructing stable, efficient Hessian approximations for scalable stochastic optimization is difficult, while stochastic gradient descent is adversely affected by Hessian ill conditioning.
Method
The method uses limited-memory BFGS and collects average curvature estimates at regular intervals through sub-sampled Hessian-vector products instead of differencing noisy gradients.
Results
Numerical results indicate that the algorithm is more effective than oLBFGS and, on a synthetic-data experiment, SQN with bH = 300 and 600 outperformed SGD.
Takeaways & Limitations
The approach provides a robust and efficient stochastic quasi-Newton method for large-scale machine-learning optimization, with Hessian-vector-product costs amortized through update spacing.
Takeaways & Limitations
Very small Hessian batch sizes can produce harmful BFGS updates, requiring monitoring of sTy and possibly increasing bH or skipping updates.
Abstract
from arXiv · showhide
The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at regular intervals, through (sub-sampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise.
1 Introduction
Large-scale machine learning requires stochastic approximation because full-batch optimization can be computationally and memory intensive. The paper proposes a limited-memory stochastic quasi-Newton method that obtains curvature from periodically averaged Hessian-vector products rather than noisy gradient differences.
- Motivation: Large-scale learning often requires stochastic updates because models and training datasets create high computational and memory demands.Small data subsets also support perpetually streamed learning settings.
- Method: The proposed method uses limited-memory BFGS correction pairs and periodically averaged, sub-sampled Hessian-vector products to obtain reliable curvature information.Regular intervals promote sample uniformity and avoid differencing noisy gradients.
- Stochastic approximation: Mini-batch stochastic gradients are computed from randomly selected subsets, making them substantially faster than gradients based on the entire training set.The batch size is chosen sufficiently small for the stochastic approximation regime.
- Method requirements: The central design challenge is constructing a stable, efficient Hessian approximation while updating its inverse directly with O(n) per-step work.These requirements target scalable limited-memory quasi-Newton implementation.
- Motivation: Stochastic gradient descent is adversely affected by Hessian ill conditioning, while an ideal inverse Hessian could remove this dependency from complexity.The ideal inverse Hessian is not viable in practice but motivates improving the stochastic scaling matrix.
- Paper scope: The paper presents the algorithm, analyzes convergence, reports machine-learning experiments, surveys related methods, and concludes with remarks on its contributions.The discussion uses Robbins-Monro, stochastic approximation, and stochastic gradient descent as essentially equivalent names for the same algorithm.
2 A stochastic quasi-Newton method
The method combines limited-memory BFGS with curvature estimates collected at regular intervals from sub-sampled Hessian-vector products rather than noisy gradient differences. It targets stochastic optimization with scalable steps and competitive computational cost.
- Classical stochastic quasi-Newton updates can produce unreliable curvature because differencing small-sample stochastic gradients does not reflect the Hessian of the full objective.
- The method decouples stochastic-gradient calculations from curvature estimation, allowing different samples and a separate regular update schedule.
- SQN uses limited-memory BFGS correction pairs, with displacement vectors formed from average iterates and curvature vectors computed through sub-sampled Hessian-vector products.
- The method computes correction pairs every L iterations and uses the resulting matrix after an initial stochastic-gradient phase.
- The quasi-Newton matrix is applied through two-loop recursion rather than formed explicitly, using the correction pairs and stochastic gradient.
- For the reported settings M = 5, b = 50, 100, . . . , L = 10 or 20, and bH ≥300, the additional SQN iteration cost is small relative to SGD.
3 Convergence Analysis
The convergence analysis assumes a twice continuously differentiable, strongly convex objective and controlled stochastic gradients. Under these conditions, the SQN Hessian approximations remain uniformly well-conditioned and the algorithm inherits a convergence guarantee.
- The analysis assumes that F is twice continuously differentiable and strongly convex, with Hessian bounds controlled by positive constants.
- Under the stated assumptions, the objective has a unique minimizer; ℓ2 regularization can ensure the required Hessian lower bound when component Hessians are nonnegative definite and uniformly bounded.
- Lemma 3.1 establishes uniform spectral bounds µ1I ≺ Ht ≺ µ2I for all SQN Hessian approximations.
- The proof shows that the eigenvalues of the initial matrices and subsequent BFGS approximations are bounded above and bounded away from zero.
- The global convergence result covers SQN as a special case when Hk remains constant for L iterations, assuming unbiased stochastic gradients and uniformly bounded, positive-definite Hk.
- With αk = β/k and β > 1/(2µ1λ), Theorem 3.2 supplies the step-size condition used for the convergence guarantee.
- Corollary 3.3 applies the general result to Algorithm 1 because Lemma 3.1 verifies the required Hessian-approximation condition.
4 Numerical Experiments
Experiments on synthetic, RCV1, and SPEECH problems compare SQN with SGD and examine batch-size, memory, and curvature-update choices. SQN generally outperforms SGD, while useful curvature can be obtained from relatively small Hessian subsamples, subject to safeguards against overly small batches.
- Synthetic Dataset: Increasing memory M improves synthetic-data performance during both the first few epochs and runs exceeding 70 epochs.The later-stage benefit is especially pronounced for large memory sizes.
- RCV1 Dataset: SQN outperforms SGD for every tested RCV1 batch size, while b = 300 decreases the objective fastest initially and b = 1000 eventually overtakes it.The relative outcome depends on whether performance is measured by iterations or accessed data points.
- RCV1 Dataset: For RCV1, increasing bH helps until computational cost offsets accuracy gains at b = 300, whereas bH = 10000 remains effective when b = 1000.The experiments also indicate that bH = 100 can provide useful curvature benefits.
- RCV1 Dataset: Very small Hessian batches can produce harmful updates: at bH = 10, s and y approached 90°, causing a large step through the s^Ty denominator.Monitoring s^Ty relative to s^TBs can indicate when to increase bH or skip an update.
5 Related Work
The paper situates its method among stochastic second-order approaches, contrasting gradient-difference BFGS variants and diagonal or covariance-based methods with its stochastic Hessian-vector-product strategy.
- Stochastic quasi-Newton methods: Earlier stochastic BFGS methods enforce sample uniformity by resampling data for consecutive gradients, requiring an extra gradient evaluation per iteration.These methods use gradient differencing within the BFGS framework.
- Online Newton methods: A two-stage online Newton method uses averaged SGD followed by quadratic-model minimization with stochastic Hessian-vector products, unlike this quasi-Newton approach.Its second stage effectively takes one Newton step with a constant step size.
- Adaptive and natural-gradient methods: AdaGrad uses a diagonal matrix based on uncentered gradient covariance, whereas this paper uses a full, non-diagonal Hessian approximation.The distinction is between covariance-based diagonal rescaling and full-matrix curvature modeling.
- Adaptive and natural-gradient methods: Natural gradient methods seek steepest descent in feature space using the Fisher information matrix but require knowledge of the training-point distribution.TONGA instead uses a weighted online covariance update and a low-rank approximation with O(n) step cost.
- Hessian-vector-product methods: Although related work also uses Hessian-vector products, those methods are batch or sample-average methods rather than stochastic-approximation algorithms.The paper explicitly distinguishes its stochastic regime from the batch setting of Byrd et al.
6 Final Remarks
The final remarks emphasize stable, regularly spaced Hessian-vector products as the method’s curvature mechanism, while identifying batch-size choices and nonconvex curvature conditions as important boundaries.
- Contribution: The method gathers curvature from sub-sampled Hessian-vector products at regular intervals instead of computing gradient differences at every iteration.This design is presented as a stable alternative for stochastic quasi-Newton updating.
- Results: Numerical results suggest that improved performance over Robbins-Monro SGD comes from incorporating curvature through a full matrix, not merely rescaling gradients.The claim concerns the form of the curvature information used by SQN.
- Practical considerations: Choosing a sufficiently large Hessian batch and a sufficiently spaced update interval can make Hessian-vector products affordable.The paper gives L = 20 as an example of spacing that amortizes their cost.
- Alternative curvature estimates: Gradient differences remain a possible alternative, but they require shared samples and protection against round-off noise from close differences.Hessian-vector products handle these issues automatically but require code for their computation.
- Scope and convergence: Global convergence is established for strongly convex objectives, while nonconvex application requires enforcing s^T y > 0.The latter condition is stated as necessary for extending the approach beyond the analyzed convex setting.