PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact and Inexact Subsampled Newton Methods for Optimization

Raghu Bollapragada, Richard Byrd, Jorge Nocedal

arXiv:1609.08502v1math.OCstat.ML

TL;DR

The paper addresses how stochastic optimization can use subsampled gradients and Hessians without losing useful Newton convergence or scalability. It analyzes exact and inexact subsampled Newton methods, including CG-based solves and SGI comparisons, and establishes sampling conditions for superlinear convergence in expectation alongside complexity results for inexact Newton-CG.

  • Problem

    Subsampled Newton methods need convergence and complexity analyses that explain how gradient and Hessian sampling, and approximate linear solves, should be coordinated in stochastic optimization.

  • Method

    The paper analyzes exact Newton methods with sampled gradients and Hessians, then studies inexact Newton-CG methods that sample only the Hessian and compares them with Newton-SGI.

  • Results

    The paper establishes conditions for superlinear convergence in expectation and provides complexity analysis for inexact subsampled Newton-CG methods.

  • Takeaways & Limitations

    Gradient sample sizes must increase faster than geometrically for the analyzed superlinear rate, while Hessian sample sizes can increase at any rate.

  • Takeaways & Limitations

    The theory can require sample sizes of κ2 and may implicitly assume n > κ2, although practice often succeeds with fewer samples or sketch dimensions.

Abstract

from arXiv · show

The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear rate of convergence in expectation. The second part of the paper analyzes an inexact Newton method that solves linear systems approximately using the conjugate gradient (CG) method, and that samples the Hessian and not the gradient (the gradient is assumed to be exact). We provide a complexity analysis for this method based on the properties of the CG iteration and the quality of the Hessian approximation, and compare it with a method that employs a stochastic gradient iteration instead of the CG method. We report preliminary numerical results that illustrate the performance of inexact subsampled Newton methods on machine learning applications based on logistic regression.

1 Introduction

The paper develops subsampled Newton methods for stochastic optimization, using sampled gradients and Hessians to improve scalability while preserving convergence guarantees. It analyzes exact and inexact variants, including CG and SGI linear solvers, and compares their computational requirements.

  • 1 Introduction: Subsampled Newton methods approximate gradients and Hessians through sampling to improve efficiency and scalability in stochastic optimization.The paper also considers inexact linear solves for additional computational savings.
  • 1 Introduction: The exact-solve analysis identifies sampling conditions that yield linear or superlinear convergence, while exact Newton methods are most practical when d is not too large.Direct Hessian factorization can remain practical when problem structure permits linear-time factorization in d.
  • 1 Introduction: For large-scale problems, the paper studies inexact Hessian-free Newton methods that use Hessian-vector products and balance solver accuracy against Hessian sampling.The analysis focuses on conjugate gradient and stochastic gradient iteration solvers.
  • 1 Introduction: Newton-CG requires fixing the Hessian sample throughout CG, whereas Newton-SGI can change the sample at every iteration.This sampling flexibility motivates comparing the two solvers in subsampled Newton methods.
  • 1 Introduction: The paper measures solver efficiency by the Hessian-vector products required to achieve a local linear rate with convergence constant 1/2.The comparison is framed around computational effort needed to reach a specified local convergence rate.
  • 1.1 Related Work: Prior work had not provided convergence analysis for subsampled Newton methods, while related studies differed in whether progress was established in probability or expectation.The paper positions its analysis relative to sampling-rate, Newton-sketch, inverse-Hessian, and related subsampled methods.

2 Subsampled Newton Methods

The section analyzes subsampled Newton methods using sampled gradients and Hessians, establishing how their sample sizes must grow for linear or superlinear convergence in expectation. It also develops a more precise Hessian-error analysis along the current error direction.

  • Global Linear Convergence: Geometric growth of the gradient sample, |Xk| = ηk with η > 1, suffices for an R-linear convergence rate while a constant Hessian sample can be retained.The result assumes a constant steplength and uniform gradient sampling.
  • Local Superlinear Convergence: Superlinear convergence requires gradient samples to grow faster than geometrically and Hessian samples to satisfy |Sk| →∞.The Hessian sample may increase at any rate meeting the stated monotonicity and divergence conditions.
  • Error Analysis: The Hessian-subsampling error decreases inversely with the square root of |Sk|, and the resulting convergence bound combines gradient, Hessian, and Newton-model error terms.The analysis controls Hessian error along wk − w∗ rather than through a full matrix concentration bound.
  • Assumptions: The superlinear theorem relies on a bounded-moments assumption for iterates that the paper characterizes as potentially restrictive.The theorem also requires increasing gradient and Hessian sample sizes under the stated assumptions.
  • Local Superlinear Convergence: Under Assumptions A1–A4 and B1, unit-step iterations achieve R-superlinear convergence in expectation from a sufficiently close starting point.Specifically, E[∥wk − w∗∥] ≤ τk with τk+1/τk → 0.

3 Inexact Newton-CG Method

The paper analyzes inexact subsampled Newton methods that use exact gradients, sampled Hessians, and approximate linear solves via CG. It derives conditions and complexity bounds for achieving local linear convergence, while noting that worst-case CG bounds may be conservative.

  • Method: The inexact Newton-CG method subsamples only the Hessian, keeps the gradient exact, and approximately solves the Newton system with CG.The section assumes the objective is R because computing its full gradient is considered realistic for finite-sum objectives.
  • CG analysis: CG convergence depends on the Hessian spectrum, so the analysis uses a worst-case bound based on the condition number.Actual CG behavior can vary by iteration and may terminate in at most d steps, or earlier when the matrix has fewer distinct eigenvalues.
  • Complexity target: The analysis selects the Hessian sample size and CG iteration count to guarantee a local linear convergence rate with constant 1/2.The resulting conditions are established under assumptions A1, A3, A4, and B1.
  • Sampling boundary: If the required sampling parameter β exceeds N, sampling with replacement is valid but wasteful; setting β=N makes the Hessian approximation exact without replacement.With β=N, the C2 term becomes zero and the theorem remains valid.
  • Residual termination: A residual-based stopping rule can replace a prescribed CG iteration count, requiring its control parameter ζ to scale inversely with a quantity related to the Hessian condition number.The residual test is calibrated so that the same linear convergence target can be obtained.
  • Limitation: The section’s complexity guarantee may underestimate Newton-CG performance because it relies on worst-case CG behavior rather than its potentially faster per-iteration progress.CG reaches the exact solution in at most d steps, but the bound is designed for general spectral behavior.

4 Comparison with Other Methods

The paper compares Newton-CG with Newton-SGI and summarizes their work complexity alongside other optimization methods. Its analysis favors Newton-CG in condition-number dependence, but the table requires caution because methods use different convergence notions and accuracy definitions.

  • Comparison criterion: The comparison measures efficiency by the total work needed to achieve a linear convergence rate with constant 1/2.For Newton-CG, each outer iteration uses βr Hessian-vector products, where β is the Hessian sample size and r is the CG iteration count.
  • Newton-SGI: The Newton-SGI method replaces CG with a semi-stochastic gradient iteration for solving the sampled Newton system.This approach can change the Hessian sample at every inner iteration, unlike Newton-CG, which requires fixing the sample throughout CG.
  • Newton-CG versus Newton-SGI: Newton-CG complexity depends on the square root of a condition number, whereas Newton-SGI complexity depends on the condition number itself.The Newton-CG analysis also gains a log(d) factor by avoiding matrix concentration bounds.
  • Scope boundary: The theory assumes the sample size or sketch dimension is below n, implying n > κ2 for the compared finite-sum methods.The paper notes that practice often succeeds with far fewer samples or sketch dimensions than the theoretical κ2 requirement.
  • Complexity summary: Table 4.1 compares total gradient and Hessian-vector products needed for an ϵ-accurate solution across Newton-CG, Newton-SGI-related LiSSA, Newton Sketch, and baseline methods.The table reports orders of magnitude rather than a single directly comparable ranking.
  • Interpretation caveat: The complexity table should not be treated as a simple ranking because the listed methods differ in convergence type and in the definition of an ϵ-accurate solution.Convergence may be deterministic, in expectation, or in probability; accuracy may concern function values or iterate distance.

5 Numerical Experiments

The experiments evaluate inexact subsampled Newton methods for logistic-regression classification, comparing Newton-CG and Newton-SGI across datasets, sampling levels, computational costs, and scaling choices.

  • Experimental setup: The experiments use binary classification with logistic loss and ℓ2 regularization, evaluating training and testing behavior.Training error is measured as R(w)−R(w∗), while testing error omits regularization.
  • Methods: The tested methods include GD, exact Newton, Newton-CG, and Newton-SGI, with full gradients and differing second-order computations.Newton-CG uses conjugate gradients; Newton-SGI computes an inexact step with stochastic gradient iteration.
  • Newton-CG experiments: Newton-CG is evaluated with Hessian sample sizes of 5%, 10%, and 50% of the training data.Comparisons use training error against iterations and effective gradient evaluations, plus testing error against time.
  • Evaluation criteria: The experiments measure computational effort through gradient evaluations, Hessian-vector products, function evaluations, and line-search work.The figures therefore compare both iteration progress and practical time or evaluation costs.
  • Newton-CG versus Newton-SGI: Newton-CG and Newton-SGI are compared on scaled and unscaled synthetic data using training-error, effective-gradient-evaluation, and testing-error plots.For scaled data, the SGI iteration count per Newton-SGI iteration is varied; for unscaled data, αsgi is selected from a tested range.
  • Observed outcomes: Across the reported experiments, both Newton-CG and Newton-SGI are judged worthy of further investigation on a wider range of test problems.The authors describe the numerical results as preliminary but effective in practice.

6 Final Remarks

The paper establishes convergence and work guarantees for subsampled Newton methods, including expected superlinear convergence and complexity bounds for inexact variants. Preliminary experiments support their practical value, while the analysis assumes uniform sampling and adds a condition for expectation-based guarantees.

  • Final remarks: Superlinear convergence in expectation is obtained when gradient sample sizes grow faster than geometrically, while Hessian sample sizes may grow at any rate.These conditions apply to methods that subsample both the gradient and Hessian.
  • Final remarks: The inexact Newton-CG method uses the full gradient, subsamples the Hessian, and receives work bounds for achieving a specified linear convergence rate.Work is counted through individual gradient and Hessian-vector-product evaluations and compared with Newton-SGI bounds.
  • Final remarks: The paper’s expectation-based convergence results are stronger than prior one-iteration probability bounds, but require assumption (2.18).The analysis considers uniform rather than non-uniform sampling.
  • Final remarks: The preliminary numerical results support the value of subsampled Newton methods and motivate broader investigation.The authors leave a more detailed and comprehensive study for future research.

A Additional Numerical Results

The appendix extends the numerical comparisons across additional classification datasets, reporting Newton-CG and Newton-SGI results under scaled and unscaled settings. It also records a nonconvergence case for unscaled Covertype Newton-SGI.

  • Additional datasets: Additional results cover Cina, Mushrooms, MNIST, Gisette, and Covertype datasets.The appendix reports Newton-CG comparisons with GD and Newton, and scaled or unscaled comparisons with Newton-SGI.
  • Reported metrics: The appendix figures plot training error against iterations and effective gradient evaluations, and testing objectives or errors against time.The exact testing metric varies across the scaled and unscaled dataset figures.
  • Dataset detail: MNIST is used for binary classification of digits into even and odd.This dataset-specific setup accompanies the appendix’s numerical comparisons.
  • Observed limitation: Newton-SGI on unscaled Covertype did not converge for any tested steplength αsgi ∈ {2−20, ..., 23}.This is the appendix’s explicitly reported nonconvergence case.
  • Newton-CG versus Newton-SGI: Scaled Covertype results compare Newton-CG with Newton-SGI using training-error, effective-gradient-evaluation, and testing-error plots.The appendix presents analogous scaled and unscaled comparisons for the other datasets.
Loading 1609.08502v1…