Source-linked AI summary
Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
Xiao Wang, Shiqian Ma, Donald Goldfarb, Wei Liu
TL;DR
The paper studies stochastic quasi-Newton methods for nonconvex stochastic optimization with noisy gradient information. It proposes a general convergence framework and a stochastic damped L-BFGS method, proving an O(ε^-2) SFO-call guarantee for a randomly selected iterate.
Problem
Stochastic quasi-Newton methods had been designed for convex or strongly convex problems, while nonconvexity makes preserving positive definiteness difficult and prevents line-search approaches from remaining feasible.
Method
The paper proposes a general stochastic quasi-Newton framework and a stochastic damped L-BFGS method that avoids explicitly generating H_k.
Results
O(ε^-2) SFO calls suffice to achieve E[∥∇f(x_R)∥^2] ≤ ε when a randomly chosen iterate is returned.
Takeaways & Limitations
The framework provides almost sure convergence to stationary points for the studied nonconvex stochastic optimization setting.
Takeaways & Limitations
The analysis is scoped to assumptions including the stated stochastic-gradient and smoothness conditions, and addresses feasibility challenges specific to nonconvex stochastic optimization.
Abstract
from arXiv · showhide
In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle (SFO). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case iteration complexity. When a randomly chosen iterate is returned as the output of such an algorithm, we prove that in the worst-case, the SFO-calls complexity is $O(ε^{-2})$ to ensure that the expectation of the squared norm of the gradient is smaller than the given accuracy tolerance $ε$. We also propose a specific algorithm, namely a stochastic damped L-BFGS (SdLBFGS) method, that falls under the proposed framework. {Moreover, we incorporate the SVRG variance reduction technique into the proposed SdLBFGS method, and analyze its SFO-calls complexity. Numerical results on a nonconvex binary classification problem using SVM, and a multiclass classification problem using neural networks are reported.
1. Introduction.
The paper addresses stochastic quasi-Newton methods for nonconvex optimization with noisy gradient information, developing convergence guarantees, complexity bounds, and specific damped L-BFGS variants.
- Research setting: The paper studies stochastic quasi-Newton methods for nonconvex stochastic optimization using noisy gradients obtained through a stochastic first-order oracle.The setting includes a continuously differentiable, possibly nonconvex objective and potentially extremely large random sample data.
- Motivation and gap: Existing stochastic quasi-Newton methods were designed for convex or strongly convex problems, leaving the nonconvex setting insufficiently addressed.The paper identifies nonconvex stochastic optimization as a newer focus and contrasts it with prior convex-oriented methods.
- Motivation and gap: Preserving positive-definiteness without line search is a central challenge because nonconvexity and gradient noise complicate curvature conditions.Line search can satisfy the curvature condition for nonconvex problems, but is not feasible in the stochastic setting considered.
- Contributions: The proposed SQN framework proves almost sure convergence to stationary points for diminishing step sizes and establishes iteration-complexity guarantees.For α_k proportional to k^-β, the required iteration count is reported as N = O(ε^(-1/(1−β))).
- Contributions: When a randomly selected iterate is returned, the framework provides a worst-case SFO-calls bound for achieving a small expected squared gradient norm.The introduction identifies this randomized-output result as a main complexity contribution, while the supplied abstract states the bound as O(ε^-2).
- Contributions: The paper proposes stochastic damped L-BFGS, including an SVRG-based reduced variant, and reports numerical results for nonconvex classification tasks.The applications include binary SVM classification and multiclass neural-network classification.
2. A general framework for stochastic quasi-Newton methods for nonconvex optimization.
The paper develops a stochastic quasi-Newton framework for nonconvex optimization with noisy SFO gradients, establishing convergence and complexity guarantees under stated assumptions.
- The SQN framework targets nonconvex stochastic optimization and proves almost sure convergence to stationary points.
- The analysis assumes a lower-bounded, continuously differentiable objective with globally Lipschitz gradient and unbiased noisy gradient estimates.
- SQN uses mini-batch stochastic gradients and positive definite inverse-Hessian approximations generated from historical gradient information.
- Theorem 2.2 shows that every limit point of the SQN iterates is stationary with probability 1 under the stronger bounded-noisy-gradient assumption.
- With a suitable diminishing stepsize, the iteration bound required to control the average squared gradient norm is O(ε^(-1/(1−β))) for β in (0.5, 1).
- For random output and constant stepsize, SQN achieves E[∥∇f(xR)∥2] ≤ ε with O(ε^-2) SFO calls under the corollary’s conditions.
3. Stochastic damped L-BFGS method.
The paper develops a stochastic damped L-BFGS method for nonconvex stochastic optimization that preserves positive definiteness while reducing the cost of quasi-Newton direction computation. Its analysis establishes boundedness properties and an O(ε^-2) SFO-call guarantee.
- Method construction: Damping preserves positive definiteness of both B_k and H_k under the update.The positive-definiteness result is established for the damped BFGS updates and carried into the L-BFGS construction.
- Efficient direction computation: (4p + 6)n multiplications are required to compute the step direction with the stochastic damped L-BFGS procedure.The cost depends linearly on the dimension n and memory size p.
- Efficient direction computation: The method uses stored pairs (s_j, ȳ_j) and a memory size p to construct H_k recursively without explicitly generating the full matrix.The resulting search direction is computed through the L-BFGS two-loop recursion.
- Method construction: The stochastic damped L-BFGS method generates inverse-Hessian approximations for the proposed stochastic quasi-Newton framework in nonconvex problems.The method is designed to satisfy the framework’s assumptions and uses damping to address nonconvexity.
- Theoretical properties: Under AS.5, the eigenvalues and operator norm of H_k are bounded away from zero and above, respectively.These bounds support the framework assumptions needed for the convergence analysis.
- Complexity: N_sfo = O(ε^-2) suffices to achieve E[∥∇f(x_R)∥^2] ≤ ε for the stochastic damped L-BFGS method.The total SFO-call count includes the batch sizes used in consecutive iterations.
4. SdLBFGS with a Variance Reduction Technique.
The section introduces SdLBFGS-VR, combining stochastic damped L-BFGS with variance reduction, and analyzes its convergence and SFO-call complexity.
- SdLBFGS-VR incorporates variance reduction into a stochastic damped L-BFGS method for nonconvex empirical risk minimization.The method uses mini-batch stochastic gradients and is designed to permit a constant step size.
- SdLBFGS-VR allows a constant step size and can accelerate the convergence speed of SdLBFGS.The method is summarized as Algorithm 4.1 for solving the empirical risk minimization problem.
- The proposed variance-reduced method is analyzed through convergence-rate results under assumptions AS.1, AS.2, and AS.5.The analysis follows a sequence of lemmas and a theorem establishing the method's rate under specified parameter choices.
- The parameter choices use βt = β = Lκ̄T^1/3, α = μ0m/(Lκ̄T^2/3), and q = ⌊T/(3μ0m)⌋.These choices are made under positive constants ν and μ0 in (0, 1).
- O(T^2/3/ε) component gradient evaluations are sufficient to achieve E[∥∇f(x)∥^2] ≤ ε.The complexity follows because the outer iteration count is O(T^2/3/ε) and each outer loop requires T + qm evaluations.
5. Numerical Experiments.
The experiments evaluate SdLBFGS and SdLBFGS-VR on synthetic and real classification problems, examining memory size, batch size, damping, and step size.
- Experimental setup: The experiments compare SdLBFGS with SGD on nonconvex sigmoid-loss SVM problems and compare SdLBFGS-VR with SVRG using constant step sizes.The evaluations include synthetic data and the RCV1 dataset.
- Synthetic data: Larger memory sizes generally improve SdLBFGS performance, while p = 5, 10, 20 oscillate less and perform similarly on synthetic data.The p = 5, 10, 20 variants significantly outperform p = 0 and p = 1.
- Damping: Small damping parameters δ = 0.01, 0.1, and 1 produce the best SdLBFGS performance in the reported tests.This pattern is also reported for the RCV1 experiments.
- Batch size: With fixed total SFO-calls, m = 100 slightly outperforms m = 500, despite m = 500 performing best by iteration count on synthetic data.The reported trade-off reflects fewer iterations with larger batches.
- Classification performance: Lower squared gradient norms generally correspond to higher correct-classification percentages in the reported tests.This relationship is reported for both synthetic and RCV1 evaluations.
- RCV1: SdLBFGS outperforms SGD on RCV1, while larger batch sizes improve SNG and m = 1 exhibits dramatic oscillation.For the tested batch sizes, m = 50 and 75 are slightly better than m = 100 under the fixed-call comparison.
- Variance reduction: For the variance-reduced method, SdLBFGS-VR usually performs better than SdLBFGS and better than SVRG at the same step size.Neither SdLBFGS-VR nor SVRG is stable when α ≥ 1.
6. Conclusions.
The paper concludes that its stochastic quasi-Newton framework supports nonconvex optimization, with SdLBFGS and variance-reduced SdLBFGS providing analyzed algorithms and encouraging classification results.
- The proposed framework provides global convergence, iteration-complexity, and SFO-call-complexity analyses under conditions on step size and algorithm output.The framework targets stochastic quasi-Newton methods for nonconvex stochastic optimization.
- The stochastic damped limited-memory BFGS method falls within the framework and preserves Hk positive definiteness without requiring convexity.The method does not explicitly generate Hk.
- A variance-reduced stochastic L-BFGS method is proposed for empirical risk minimization.The method is the variance-reduced extension analyzed in the preceding section.
- Encouraging numerical results are reported for nonconvex classification problems using SVM and neural networks.These experiments provide empirical evaluation across the two stated classification settings.