PaperlayerView exact revision on arXiv

Source-linked AI summary

Sub-sampled Cubic Regularization for Non-convex Optimization

Jonas Moritz Kohler, Aurelien Lucchi

arXiv:1705.05933v3cs.LGmath.OCstat.ML

TL;DR

The paper addresses the high cost of applying cubic regularization to large-scale non-convex finite-sum objectives. It uses sub-sampled gradient and Hessian approximations with concentration-based sampling, and reports preserved convergence properties and experimental speed-ups.

  • Problem

    Cubic regularization has strong convergence properties for non-convex optimization, but exact model minimization and full Hessian access are costly for large-scale learning.

  • Method

    The method uses sub-sampling to estimate gradients and Hessians, with a high-probability Hessian sampling scheme and support for inexact gradients.

  • Results

    The proposed method exhibits the same convergence properties as its deterministic counterpart and experiments demonstrate speed-ups against deterministic and classical optimization methods.

  • Takeaways & Limitations

    Sub-sampled cubic regularization is especially relevant when n ≫ d, where reducing samples can lower the per-iteration cost of non-convex optimization.

  • Takeaways & Limitations

    Exact global minimization of the cubic model can require factorizing B_k + λ_kI for multiple λ_k values, which is prohibitively expensive for large d.

Abstract

from arXiv · show

We consider the minimization of non-convex functions that typically arise in machine learning. Specifically, we focus our attention on a variant of trust region methods known as cubic regularization. This approach is particularly attractive because it escapes strict saddle points and it provides stronger convergence guarantees than first- and second-order as well as classical trust region methods. However, it suffers from a high computational complexity that makes it impractical for large-scale learning. Here, we propose a novel method that uses sub-sampling to lower this computational cost. By the use of concentration inequalities we provide a sampling scheme that gives sufficiently accurate gradient and Hessian approximations to retain the strong global and local convergence guarantees of cubically regularized methods. To the best of our knowledge this is the first work that gives global convergence guarantees for a sub-sampled variant of cubic regularization on non-convex functions. Furthermore, we provide experimental results supporting our theory.

1. Introduction

The paper targets non-convex finite-sum objectives, where saddle points and costly exact Hessian computations make optimization difficult at scale. It introduces sub-sampled cubic regularization with sampling guarantees intended to preserve cubic-regularization convergence while reducing iteration cost.

  • Non-convex objectives are difficult to optimize because they contain saddle points, non-global local minima, and can be NP-hard even for degree-four polynomials.
  • Exact cubic-model minimization is impractical for machine learning because it requires access to the full Hessian matrix.
  • ARC reduces this burden with an approximate Hessian and Hessian-free Lanczos products, but its Lanczos cost still grows linearly with n and lacks a guaranteed sampling alternative.
  • The proposed method exploits the finite-sum structure through sub-sampling to reduce computational cost while targeting machine-learning guarantees.
  • The paper provides a high-probability Hessian sampling scheme, extends convergence analysis to inexact gradients, and reports speed-ups against first- and second-order methods.

2. Related work

Related work addresses computational costs in first- and second-order optimization and develops approximate cubic-model solvers. The paper positions its sampling scheme as reducing costs while retaining stronger local convergence behavior and allowing inexact gradients.

  • Sampling techniques for first-order methods: Sub-sampling can produce unbiased gradient estimates whose convergence does not depend on n, although stochastic variance can slow convergence.
  • Second-order methods: Traditional second-order methods require O(nd^2) Hessian computation and O(d^3) inversion, while L-BFGS reduces per-iteration cost to O(nd + d^2).
  • Second-order methods: NewSamp reduces Hessian-related complexity to O(nd + |S|d^2), but its convergence is quadratic initially and only linear near the minimizer.
  • Second-order methods: The proposed sampling scheme yields a locally quadratic convergence rate and does not require exact gradients, potentially reducing per-iteration complexity further.
  • Cubic regularization and trust region methods: Cubic regularization improves trust-region methods by using a cubic over-estimator, while ARC permits approximate model minimization instead of exact minimization.
  • Cubic regularization and trust region methods: Other methods accelerate cubic-model minimization or propose stochastic trust regions, but these approaches are described as complementary or lacking the same analysis.

3. Formulation

SCR uses independently sampled gradient and Hessian estimates to build and approximately minimize cubic models, while adapting regularization across iterations. Its formulation combines Krylov-subspace model solving with termination and minimization conditions intended to preserve cubic-regularization guarantees at lower cost.

  • 3. Formulation: SCR targets large-scale problems where exact cubic-model minimization is prohibitive, using a sampling scheme intended to retain deterministic convergence results.The stated retained results include quadratic local convergence, global second-order convergence, and worst-case complexity bounds.
  • 3.1. Objective function: The method independently samples Sg and SB to form unbiased gradient and Hessian estimates for each local cubic model.The estimates are defined as sample averages of component gradients and Hessians.
  • 3.1. Objective function: The model derivative combines the sampled gradient, sampled Hessian, and cubic regularization through ∇mk(sk) = gk + Bksk + λsk, with λ = σk∥sk∥.This derivative defines the stationarity condition used when minimizing the local model.
  • 3.2. Algorithm: At each iteration, SCR samples data, approximately solves the cubic model, evaluates the objective, and updates σk according to the step's success.Very successful, successful, and unsuccessful iterations use distinct regularization updates.
  • 3.3. Exact model minimization: Exact global model minimization requires finding a root in a λk range ensuring Bk + λkI is positive semidefinite, but repeated factorizations are prohibitively expensive in high dimensions.The lower bound is λk ≥ max{−λ1(Bk), 0}.
  • 3.4. Approximate model minimization: An inexact model minimizer can preserve cubic-regularization properties when it satisfies the two requirements stated in Assumption 1.The paper notes that these requirements include the displayed first-order and curvature-related conditions.
  • 3.4. Approximate model minimization: A Krylov-subspace minimizer satisfies the inexactness assumption independently of subspace dimension, reducing model factorization to a tridiagonal matrix at O(d) cost.Building the subspace still requires Lanczos matrix-vector products, with cost increasing with dataset size n.
  • 3.4. Approximate model minimization: SCR terminates Lanczos before the Krylov subspace reaches dimension d to keep per-iteration cost low, motivated by the linear growth of Lanczos cost in n.The stopping rule is formalized as Assumption 2.

4. Theoretical analysis

The analysis shows that concentration-based sampling can provide sufficiently accurate gradient and Hessian approximations for SCR, allowing it to retain global and local convergence properties with slightly worse constants. Under the stated assumptions, SCR achieves high-probability sampling guarantees, quadratic local convergence, global first- and second-order convergence, and a worst-case first-order complexity bound.

  • Assumptions: The analysis assumes Lipschitz-continuous Hessians, while global first-order and superlinear local convergence can also be obtained without that assumption.The continuity assumptions require Lipschitz conditions on the component functions, gradients, and Hessians.
  • Assumptions: SCR requires sufficient agreement between sampled and exact gradients and between sampled and exact Hessians.The Hessian agreement condition is stronger than the Dennis–Moré condition, which lacks a theoretical guarantee for quasi-Newton approximations.
  • Sampling guarantees: Bernstein concentration inequalities bound gradient and Hessian approximation errors in ℓ2 and spectral norms as functions of sample size.The resulting gradient and Hessian sampling conditions satisfy the required agreement assumptions with probability 1 − δ.
  • Sampling guarantees: Required sample sizes grow with dimensionality and the Lipschitz constants, while eventually reaching the full sample size n as SCR converges.The gradient deviation bound is non-asymptotic, holds with high probability, and becomes more accurate as the sample size increases.
  • Global convergence analysis: The penalty parameter remains in a bounded positive range, and successful iterations achieve objective decrease linked to model decrease and step size.A sufficiently large penalty parameter guarantees a successful step; termination conditions also prevent steps from becoming too small relative to the gradient norm.
  • Local convergence: With a positive-definite Hessian at the limit point and nondecreasing sample sizes on unsuccessful iterations, SCR converges q-quadratically with high probability.The result applies when the sampled quantities satisfy the gradient and Hessian sampling conditions and the stopping criterion is used.
  • Global convergence: SCR provides deterministic global convergence to first-order critical points using stochastic first-order information under the stated agreement and bounded-objective assumptions.The function-decrease lemmas connect successful-step progress to the full gradient.

5. Experimental results

Experiments on real-world datasets evaluate SCR against first- and second-order methods for convex and non-convex logistic regression. The results indicate that SCR reduces ARC computation time while retaining global convergence behavior.

  • Experimental setup: Experiments use A9A, COVTYPE, and HIGGS datasets with n much larger than d, comparing SCR against SGD, SAGA, Newton, BFGS, L-BFGS, and ARC.The models use standard ℓ2 and non-convex regularizers.
  • Results: SCR reduces ARC’s computation time without losing its global convergence property.The experiments compare SCR with the deterministic ARC method and classical optimization approaches.
  • Results: Newton’s method is closest in performance, but its performance degrades as d increases.Newton’s method also cannot optimize non-convex COVTYPE because of a singular Hessian.
  • Results: BFGS terminates early on non-convex HIGGS because of a local saddle point.The result illustrates a failure mode observed for one competing method and dataset.
  • Results: The high condition number of COVTYPE substantially affects SGD, SAGA, and L-BFGS performance.SCR’s sampling schemes use constants C and M to scale sample sizes and offset expensive quantities κ_g and κ_f.

6. Conclusion

The paper concludes that sub-sampled gradient and Hessian estimates can construct a cubic trust-region analogue with deterministic-like convergence properties. Experiments on real and synthetic data support the algorithm’s performance, while neural-network training remains future work.

  • Contribution: SCR estimates the gradient and Hessian by sub-sampling to construct a cubic model analogous to trust-region methods.This is the paper’s central algorithmic proposal.
  • Theory: SCR exhibits the same convergence properties as its deterministic counterpart, including the best known worst-case guarantees for non-convex functions.The conclusion states this comparison at the level of convergence properties.
  • Empirical evaluation: Numerical experiments on real and synthetic datasets demonstrate the performance of the proposed algorithm.The algorithm was compared with its deterministic variant and more classical optimization methods.
  • Future work: Training neural networks is identified as future work because saddle points make them difficult to optimize.The paper does not report neural-network experiments here.

A.1. Concentration Inequalities and Sampling Schemes

This appendix section simplifies notation before presenting its concentration-inequality and sampling-scheme results. The iteration subscript is omitted in the subsequent results for brevity.

  • Notation: The appendix drops the iteration subscript k in the following results.This is explicitly done for notational simplicity.
  • Notation: The notation simplification applies to the results that follow in this section.The passage scopes the convention to the subsequent results.
  • Notation: The omitted subscript is an expository convention rather than a change to the algorithm.The stated purpose is brevity and simplicity of presentation.

A.1.1. GRADIENT SAMPLING

The gradient-sampling analysis extends Vector Bernstein concentration to averages of centered random vectors. It then applies the bound to sub-sampled gradients to derive probabilistic accuracy conditions and corresponding sample-size requirements.

  • Concentration bound: The appendix extends Vector Bernstein’s inequality to averages of independent, zero-mean vector-valued random variables.The variables are assumed centered, uniformly bounded, and variance-bounded.
  • Concentration bound: Averaging independent centered vectors reduces the variance bound to at most 1/n times the individual variance bound.The derivation uses independence, zero mean, and the averaging term.
  • Gradient sampling: For gradient sampling, each centered vector is defined as x_i = g_i(x) − ∇f(x), enabling the concentration inequality to bound deviation from the full gradient.The resulting probability statement controls deviations at a specified tolerance and failure probability.
  • Gradient sampling: Choosing the sampling bound to be at most M times the squared step size satisfies the gradient-agreement condition and yields a sample-size theorem.The sample size follows by substituting the concentration bound into the sufficient condition and rearranging.

A.1.2. HESSIAN SAMPLING

The Hessian sampling analysis uses matrix concentration to control deviations between the sub-sampled and full Hessians. It derives high-probability agreement conditions while noting that the resulting norm bound can be conservative.

  • Concentration analysis: Matrix Bernstein concentration bounds deviations of the sub-sampled Hessian from the full Hessian.The analysis centers independent Hessian matrices and applies operator concentration to obtain the required deviation bound.
  • High-probability guarantee: The sampling condition ensures that the Hessian approximation remains within a chosen deviation ϵ with probability 1 − δ.The deviation probability is controlled by δ ∈ (0, 1].
  • Agreement condition: A spectral-norm error bound proportional to ∥s∥ implies the sufficient Hessian-agreement condition required by the method.The implication uses ∥Av∥ ≤ ∥A∥op∥v∥ for the spectral matrix norm and Euclidean vector norm.
  • Caveat: The sufficient sampling condition may be conservative because the operator-norm bound is tight only when the step aligns with the largest eigenvector.The text explicitly notes that less restrictive sampling conditions may satisfy the same agreement requirement.

A.1.3. ILLUSTRATION

Figure 2 compares suboptimality and sample sizes for cubic-regularization methods on a9a, covtype, and gaussian. SCR’s automatic sampling grows exponentially and can reduce early-stage computation.

  • Figure 2: Figure 2’s top row reports suboptimality and bottom row reports sample sizes across a9a, covtype, and gaussian.The comparison includes SCR, deterministic ARC, and stochastic ARC variants with linear or exponential sampling.
  • Automatic sampling: SCR’s automatic sampling scheme follows an exponential curve, reducing the amount of computation used early in optimization.The caption attributes the early savings to the exponential sample-size schedule.
  • Comparison: The manually tuned linear and exponential sampling schemes do not reach SCR’s performance despite being tuned for their best possible performance.Those schemes were also set to reach the full sample size at the final iteration, unlike SCR’s automatic schedule.

A.2. Convergence Analysis

The convergence analysis establishes step-size, sampling, and success properties for SCR, then uses them to derive global and local convergence guarantees. Under the stated assumptions, sampling eventually becomes exact and local convergence is quadratic with high probability.

  • Local convergence prerequisites: SCR’s sampling assumptions provide lower and upper step-size bounds, eventual full sample size, and eventually very successful iterations.These four properties are identified as prerequisites for the local convergence analysis.
  • Sampling behavior: The sample sizes eventually equal n with high probability, including when unsuccessful iterations occur infinitely often because sample sizes are not decreased then.The analysis treats finite and infinite unsuccessful-iteration cases separately.
  • Local convergence: All iterations are eventually very successful with high probability near a local minimizer whose Hessian is positive definite.The result assumes ∇f(w∗) = 0 and positive definiteness of H(w∗).
  • Convergence implications: The local analysis excludes the possibility of infinitely many unsuccessful steps as a consequence of the eventual-success result.This point is given as a note following the eventual full-sample-size lemma.
  • Local convergence: The gradient norms and iterates converge quadratically with high probability once the sampling error vanishes asymptotically.The argument uses the eventual error limit and a Taylor expansion around the limiting point.
  • Global convergence: Successful-step decrease bounds and the bounded penalty parameter yield a deterministic global convergence guarantee using stochastic first-order information.The analysis concludes that the full gradient norm tends to zero.
Loading 1705.05933v3…