PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Cubic Regularization for Fast Nonconvex Optimization

Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, Michael I. Jordan

arXiv:1711.02838v2cs.LGmath.OCstat.ML

TL;DR

The paper asks how to find approximate local minima efficiently for general smooth, nonconvex stochastic objectives, where first-order methods can reach saddle points. It develops a fully stochastic cubic-regularized Newton method using noisy gradients and Hessian-vector products. The method achieves ˜O(ϵ−3.5) oracle evaluations, improving on SGD’s ˜O(ϵ−4) rate and matching the best-known result without delicate acceleration or variance reduction.

  • Problem

    Stochastic nonconvex optimization needs methods that escape saddle points rather than merely reach first-order stationary points, which may also be maxima or saddles.

  • Method

    The paper develops a fully stochastic cubic-regularized Newton method that uses noisy gradients and Hessian-vector products and an inexact cubic subsolver.

  • Results

    ˜O(ϵ−3.5) oracle evaluations find ϵ-approximate local minima, improving on SGD’s ˜O(ϵ−4) rate and matching the best-known result.

  • Takeaways & Limitations

    Stochastic Hessian-vector products can support faster provable local-minimum finding without delicate acceleration or variance-reduction techniques.

  • Takeaways & Limitations

    The analysis becomes more elaborate for an approximate cubic subsolver, while one stated subsolver condition is only approximately true.

Abstract

from arXiv · show

This paper proposes a stochastic variant of a classic algorithm---the cubic-regularized Newton method [Nesterov and Polyak 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only $\mathcal{\tilde{O}}(ε^{-3.5})$ stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the $\mathcal{\tilde{O}}(ε^{-4})$ rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.

1 Introduction

The paper addresses stochastic nonconvex optimization beyond first-order stationarity by adapting cubic-regularized Newton to noisy gradients and Hessian-vector products. It targets approximate local minima with a provably faster oracle complexity than SGD.

  • Motivation: Classical nonconvex analyses may converge to saddle points because first-order stationarity permits local minima, local maxima, and saddles.The paper instead targets points with small gradients and nearly positive-semidefinite Hessians.
  • Motivation: SGD requires O(ϵ−4poly(d)) iterations to find an ϵ-approximate local minimum, while full-Hessian methods can be prohibitively expensive for large models.Hessian-vector products offer curvature information and can be computed as efficiently as gradients in many cases.
  • Motivation: The paper asks whether stochastic Hessian-vector products can speed up nonconvex optimization, where prior stochastic progress was limited.This question motivates combining stochastic first- and second-order information.
  • Results: ˜O(ϵ−3.5) oracle evaluations improve on SGD’s ˜O(ϵ−4) rate and match the best-known local-minimum result without delicate acceleration or variance reduction.The complexity counts stochastic gradient and Hessian-vector-product oracle evaluations, with logarithmic factors hidden.
  • Contribution: The proposed method is a fully stochastic cubic-regularized Newton algorithm with noisy gradients and Hessian-vector products, extending a classic non-stochastic method.Cubic regularization incorporates Hessian information by minimizing a local third-order Taylor model.

2 Preliminaries

The preliminaries define the stochastic optimization setting, the approximate local-minimum target, and cubic regularization as a third-order local-model method. They also identify the stochastic and computational obstacles the algorithm must address.

  • Stochastic setting: The stochastic objective is an expectation over random samples and covers both finite-sum offline problems and online settings with sequentially arriving data.The function may be nonconvex.
  • Stochastic setting: The algorithm uses stochastic gradients and Hessian-vector products rather than forming the full Hessian, whose products can be as cheap as gradients for arithmetic-circuit models.This computational property is highlighted for neural networks.
  • Assumptions: The paper assumes a lower-bounded objective together with smoothness conditions limiting local changes in the gradient and Hessian.These assumptions are described as standard in work on escaping saddle points and finding local minima.
  • Target: An ϵ-second-order stationary point, also called an ϵ-approximate local minimum, requires both a small gradient and a Hessian close to positive semidefinite.This strengthens first-order stationarity by controlling curvature.
  • Cubic regularization: Cubic regularization builds a local upper bound from a third-order Taylor expansion and minimizes the resulting cubic submodel to produce the next iterate.The method is described for functions with Lipschitz Hessians.
  • Algorithmic challenges: The stochastic algorithm must handle noisy derivatives, Hessian access restricted to vector products, and inexact cubic-subproblem solutions.These are the three obstacles explicitly identified for transferring cubic regularization to the stochastic setting.

3 Main Results

The paper develops a stochastic cubic-regularization meta-algorithm that uses stochastic gradients and Hessian-vector products through a black-box subsolver to find approximate second-order stationary points.

  • Algorithmic framework: The meta-algorithm samples independent gradient and Hessian minibatches, then optimizes a stochastic cubic submodel with a black-box subsolver.The subsolver receives a gradient vector and Hessian-vector-product oracle, returns an approximate submodel minimizer, and supplies the submodel decrease used by the stopping rule.
  • Algorithmic framework: The subsolver accesses the Hessian only through Hessian-vector products, avoiding explicit formation of the stochastic Hessian matrix.Gradient-based solvers, including gradient descent and accelerated gradient descent, can be used within this interface.
  • Algorithmic framework: The solver may return an inexact update, subject to conditions requiring either sufficient decrease or controlled suboptimality relative to the exact cubic minimizer.Condition 1 bounds the subsolver’s gradient iterations by T(ϵ) and specifies the acceptable output conditions.
  • Main guarantee: With probability at least 1−δ, Algorithm 1 outputs an ϵ-second-order stationary point within the theorem’s stated total number of stochastic gradient and Hessian-vector-product evaluations.The guarantee holds under the assumptions of Theorem 1 and a suitable cubic subsolver.
  • Gradient-descent subsolver: Gradient descent provides a valid cubic subsolver, and under the stochastic cubic-regularization framework it already achieves the optimal asymptotic rate.A faster subsolver cannot improve the overall rate because gradient averaging dominates the subsolver complexity.
  • Implementation: For neural networks, each gradient or Hessian-vector-product evaluation takes O(d) time, so runtime scales with the oracle count times this per-evaluation cost.The method’s practical cost is therefore determined by both the evaluation complexity and the cost of computing each oracle.

4 Proof Sketch

The proof connects stochastic cubic-submodel progress to true-function progress and uses boundedness below to show eventual termination at an approximate second-order stationary point.

  • Stochastic submodel: At each iteration, the stochastic cubic submodel is built from averaged stochastic gradients and Hessians, whose accuracy requires sufficiently large minibatches.The analysis uses concentration so these averages approximate the exact gradient and Hessian uniformly in relevant directions.
  • Claim 1: If the current iterate is not an ϵ-second-order stationary point, the cubic submodel has large descent after its minimization step.The proof lower-bounds the norm of the optimal cubic-submodel step to establish sufficient movement and descent.
  • Claim 2: Large descent in the stochastic cubic submodel implies large descent in the true function, up to a stochastic error term.This transfer requires controlling the discrepancy between the stochastic submodel and the true function.
  • Termination: Because the true function is bounded below, sufficiently large decreases cannot continue indefinitely; an iteration with small submodel descent must eventually occur.Claim 1 then identifies the resulting iterate as an ϵ-second-order stationary point.
  • Stochastic termination: Claim 2 is especially important under stochastic access because the algorithm observes the submodel rather than the true function when deciding whether to terminate.For an approximate subsolver, Claim 1 becomes approximate while Claim 2 remains valid through a more involved argument deferred to the Appendix.

5 Experiments

Experiments on a synthetic saddle-point problem and MNIST autoencoding show that stochastic cubic regularization escapes saddles faster than first-order baselines and reaches favorable optima sooner.

  • Implementation: Hessian-vector products are computed efficiently in TensorFlow using the method of Pearlmutter.
  • Synthetic experiment: The synthetic problem combines a W-shaped piecewise cubic with a scaled quadratic, producing a saddle at the origin with Hessian eigenvalues -0.2 and 20.The negative curvature is much smaller than the positive curvature and comparable in magnitude to the evaluation noise.
  • Synthetic experiment: Stochastic cubic regularization escapes the synthetic saddle and reaches a global minimum faster than SGD.Batch sizes and learning rates were tuned separately for a fair comparison.
  • MNIST autoencoding: On MNIST deep autoencoding, stochastic cubic regularization escapes multiple saddle points most quickly and reaches a local minimum faster than SGD and AdaGrad.The comparison uses training error, with a held-out validation split for hyperparameter selection.
  • MNIST autoencoding: AdaGrad makes slightly faster progress than stochastic cubic regularization after entering a basin around a local optimum.

6 Conclusion

The paper develops and analyzes stochastic cubic regularization through concentration, subsolver, descent, and stationarity arguments. The proof establishes that approximate cubic-model updates lead to approximate second-order stationary points under the stated assumptions.

  • Conclusion: The stochastic method is based on the cubic-regularized Newton framework and uses sampled gradients and Hessians to form cubic subproblems.
  • Subproblem solution: The Cubic-Subsolver either obtains sufficient model decrease or supports a stationarity guarantee for the resulting update.
  • Concentration analysis: The analysis controls stochastic gradients and Hessian-vector products through minibatch concentration conditions.The proof invokes matrix Bernstein bounds for the stochastic quantities.
  • Stationarity argument: If the updated point is not an ϵ-second-order stationary point, the proof separates cases according to large gradient or sufficiently negative curvature.

A.3 Proof of Claim 1

The proof of Claim 1 shows that approximate cubic-subproblem solutions either provide sufficient progress or yield an approximate second-order stationary point after refinement.

  • A.3 Proof of Claim 1: The Cubic-Subsolver handles updates through two cases: sufficient cubic-model decrease or a small-step situation requiring further analysis.
  • A.3 Proof of Claim 1: The final gradient-descent loop refines the approximate cubic step and returns a 4ϵ-second-order stationary point.
  • A.3 Proof of Claim 1: When the update reaches the required stationarity regime, gradient smoothness and concentration bound the true gradient and Hessian errors.
  • A.3 Proof of Claim 1: If the cubic submodel decreases sufficiently, Hessian Lipschitzness and concentration transfer that decrease to the underlying objective.

A.5 Proof of Theorem 1

The proof of Theorem 1 combines probabilistic concentration, progress accounting, and a cubic subsolver to guarantee an ϵ-second-order stationary point with high probability and the claimed oracle complexity.

  • A.5 Proof of Theorem 1: The analysis assumes that f is bounded below and conditions on concentration and subsolver-success events across outer iterations.A union bound controls the total failure probability.
  • A.5 Proof of Theorem 1: Theorem 1 guarantees an ϵ-second-order stationary point with probability at least 1−δ within the stated total stochastic gradient and Hessian-vector product evaluations.
  • A.5 Proof of Theorem 1: Each outer iteration uses minibatches for stochastic gradients and Hessian approximation, while the Cubic-Subsolver recomputes Hessian-vector products during inner iterations.
  • A.5 Proof of Theorem 1: The final gradient-descent loop has subleading complexity relative to the overall gradient and Hessian-vector product costs.
  • A.5 Proof of Theorem 1: The Cauchy-step case guarantees sufficient descent when the stochastic gradient is large, and cubic-submodel gradient descent handles the complementary case.

B.2 Gradient Descent Loop in Algorithm 3

The gradient-descent loop approximately minimizes a perturbed stochastic cubic submodel under step-size and initialization assumptions. Its iterates achieve near-optimal submodel value with high probability after a stated iteration budget.

  • Gradient descent subsolver: The loop minimizes a fixed stochastic cubic submodel using gradient descent with a perturbation replacing g by g + σq.The perturbation avoids the hard case associated with non-convex quadratic problems.
  • Assumptions: The analysis assumes a suitable gradient-descent step size and initialization of the form ∆ = −r g/∥g∥, with 0 ≤ r ≤ R_c.These are labeled Assumptions A and B in the analysis.
  • Perturbation: The perturbation q is uniformly distributed on the unit sphere, and the gradient perturbation magnitude is set using σ = ρε′.The theorem applies the perturbed gradient-descent scheme under Assumptions A and B.
  • Guarantee: With probability at least 1 − δ′, the iterates satisfy ˜m(∆t) ≤ ˜m(∆⋆) + (1 + σ̄)ε′.For sufficiently small constants, the additive error is further bounded by 2ε′ = c3.
  • Iteration complexity: ˜O(ℓ/√(ρε)) iterations suffice for a descent iterate when the cubic subproblem minimizer has norm at least one.This regime corresponds to subproblems whose minimizer is not an ε-second-order stationary point.
  • Failure probability: The eventual choice δ′ ∼ O(1/ε^1.5) contributes only logarithmic dependence on ε to the upper bound.The logarithmic contribution is absorbed by the ˜O notation.

B.3 Proofs of Lemma 2 and Corollary 3

The paper combines two cubic-subproblem procedures to establish the correctness and complexity of Algorithm 3. This yields the claimed high-probability guarantee for Algorithm 1 when using the resulting cubic subsolver.

  • Corollary 3: Instantiating the Cubic-Subsolver with Algorithm 3 makes Algorithm 1 output an ε-second-order stationary point with probability greater than 1 − δ.The conclusion is obtained by applying Theorem 1 to Lemma 2.
  • Lemma 2: Algorithm 3 satisfies the cubic-subsolver condition with probability at least 1 − δ′ under the same assumptions and parameter choices as Theorem 1.The result follows by combining the analyses of the Cauchy step and gradient-descent loop.
  • Algorithm 3 cases: The Cauchy step handles ∥g∥ above the threshold, while gradient descent solves the cubic submodel when ∥g∥ is below it.The Cauchy step has gradient complexity O(1), whereas the gradient-descent loop has complexity ˜O(ℓ/√(ρε)).
  • Oracle complexity: The resulting guarantee is stated in terms of total stochastic gradient and Hessian-vector product evaluations.The supplied passage introduces this total complexity measure, while the displayed bound is fragmented.
  • Descent verification: The two procedures have descent constants K1 = 7/20 and K2 ≤ 1/96, with the required ordering −K1 ≤ −K2.This ordering lets Algorithm 3 meet the descent requirement used in Theorem 1.

C.1 Synthetic Nonconvex Problem

The synthetic experiment uses a piecewise cubic W-shaped objective and compares methods through tuned optimization settings. Computational constraints limit the extent of hyperparameter search in the broader experiments.

  • Synthetic objective: The synthetic objective is a piecewise cubic W-shaped function parameterized by slope ε and length L.The experiment sets ε = 0.01 and L = 5.
  • Stochastic cubic regularization: Stochastic cubic regularization uses ρ = 1, the analytic Hessian Lipschitz constant, and 10 inner iterations per cubic-subsolver invocation.These settings are chosen as a trade-off between progress and accuracy.
  • Hyperparameter search: The synthetic grid search varies batch size over {10, 30, 100, 300} and step size over {c · 10^-i : c ∈ {1, 3}, i ∈ {1, 2, 3, 4, 5}}.Gradient and Hessian batch sizes are tuned separately for the proposed method.
  • Selection criterion: Configurations are selected by fastest convergence to a global optimum while keeping the final objective within 5% of the optimum.For the stated optima, this corresponds to an absolute tolerance of 0.0002666···.
  • Experimental limitation: Full hyperparameter grid searches were not feasible for every method because of computational constraints.The broader experiments fix gradient batch size at 100 and stochastic-cubic Hessian batch size at 10 before tuning remaining parameters.
Loading 1711.02838v2…