PaperlayerView exact revision on arXiv

Source-linked AI summary

A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization

Clément W. Royer, Michael O'Neill, Stephen J. Wright

arXiv:1803.02924v4math.OC

TL;DR

The paper addresses the limited attention to complexity bounds for inexact Newton-CG methods while aiming to retain the traditional approach. It combines damped Newton-CG with negative-curvature safeguards, and reports high-probability complexity guarantees for approximate second-order conditions. The method also requires high accuracy in its step computation, which the authors say is tighter than typically used in practice.

  • Problem

    Complexity bounds that explicitly account for inexact Newton-CG techniques have received less attention, despite existing analyses of stationarity and other global guarantees.

    Source: §1 · p. 2

  • Method

    The method applies CG to damped Newton equations, monitors for negative curvature, and uses either a Newton-type step or a negative-curvature step.

    Source: §1 · p. 2, §5 · p. 21

  • Results

    With high probability, the method reaches approximate second-order conditions with ˜O(ǫ_g^-7/4) complexity for sufficiently large n, matching accelerated gradient-type bounds.

    Source: §4.3 · pp. 19, 21

  • Takeaways & Limitations

    The paper shows that a Newton-CG approach close to traditional variants can have guaranteed complexity for convergence to approximate second-order conditions.

    Source: §5 · p. 21

    The complexity analysis requires high accuracy in the damped Newton step, with tighter residual restrictions than typically used in practical algorithms.

    Source: §5 · pp. 21–22

Abstract

from arXiv · show

We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton's method and the linear conjugate gradient algorithm, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate first-order and second-order optimality conditions. The complexity results match the best known results in the literature for second-order methods.

1 Introduction

The paper addresses complexity guarantees for Newton-CG methods that retain the familiar approach while targeting approximate first- and second-order optimality. It adds safeguards for negative-curvature handling and assumes efficient Hessian-vector products rather than full Hessian evaluation.

1 Introduction

  • The problem is smooth, generally nonconvex unconstrained minimization, with the objective bounded below and full Hessian evaluation considered computationally undesirable.The analysis assumes twice uniformly Lipschitz continuous differentiability on a neighborhood containing the algorithm’s trial points; Hessian-vector products are assumed reasonably efficient.Source: §1 · pp. 2–3
  • Existing Newton-CG analyses often establish stationarity, but complexity bounds accounting explicitly for inexact Newton-CG procedures have received less attention.The paper also notes that newer complexity-focused methods often depart from traditional optimization practice.Source: §1 · p. 2
  • The method applies CG to slightly damped Newton equations, monitoring the iterations for evidence of Hessian indefiniteness.It uses backtracking along an approximate Newton step, or steps along a negative-curvature direction found in CG or auxiliary computation.Source: §1 · pp. 2–3
  • Negative-curvature steps or approximate Newton steps can yield significant objective decrease at reasonable gradient-evaluation or Hessian-vector-product cost.These safeguards support worst-case complexity guarantees.Source: §1 · p. 3

2 Complexity in Nonconvex Optimization

The section places the method among algorithms with global complexity guarantees for nonconvex optimization. It contrasts established second-order iteration bounds and computational-complexity approaches with the paper’s Newton-CG design.

2 Complexity in Nonconvex Optimization

  • Second-order methods have a best-known iteration bound of O(max{ǫ_g^-3/2, ǫ_H^-3}) in the cited literature, first established for cubic regularization.Other algorithms subsequently matched this bound.Source: §2 · p. 4
  • Two approaches based on accelerated gradient and approximately solving a cubic subproblem require ˜O(ǫ^-7/4) operations with high probability.The cited bounds depend only on ǫ.Source: §2 · p. 4
  • A related accelerated-gradient method with a nonconvexity monitor has a high-probability ˜O(ǫ^-7/4) iteration bound and a deterministic bound for the gradient condition alone.The cited discussion contrasts the latter with O(ǫ^-2) for steepest descent and classical Newton’s method.Source: §2 · p. 4
  • The paper’s Newton-based approach modifies CG for inexact damped Newton systems, avoiding a prior positive-definiteness check and an estimate of the Hessian’s smallest eigenvalue.The authors state that this permits a deterministic first-order result; they also cite CG’s adaptivity and ability to detect nonconvexity efficiently.Source: §2 · p. 5
  • The paper frames its contribution as showing that suitably enhanced CG methods can combine practical relevance in large-scale optimization with good complexity properties.Source: §2 · p. 5

3 Damped-Newton / Capped-CG Method with Negative Curvature Steps

The method combines capped CG for damped Newton equations with a minimum-eigenvalue oracle for negative-curvature detection. Its line-search algorithm uses Newton-type or negative-curvature steps to pursue approximate second-order optimality with global complexity guarantees.

3.1 Capped Conjugate Gradient

  • Capped CG solves the damped system (H + 2ǫI)y = −g when appropriate, while detecting directions d with d⊤Hd < −ǫ∥d∥² when the shifted matrix is not sufficiently positive definite.It checks for negative curvature directly in CG iterates and search directions, and indirectly through unusually slow residual decrease.Source: §3.1 · p. 6
  • Capped CG limits its iterations to J(M, ǫ, ζ), shown to be ˜O(ǫ^-1/2), and the stated matrix-vector-product bound increases if iterates must be regenerated.Storing the iterates gives the bound described in Lemma 1; regenerating them incurs additional work.Source: §3.1 · pp. 6, 8

3.2 Minimum Eigenvalue Oracle

  • The minimum eigenvalue oracle returns a sufficiently negative-curvature direction or a certificate that the matrix’s minimum eigenvalue is at least −ǫ.The certificate can be false with probability δ.Source: §3.2 · p. 9
  • With a random unit-sphere right-hand side, CG detects a direction of negative curvature when λmin(H) < −ǫ, or certifies λmin(H) ≥ −ǫ, with probability at least 1 − δ.The theorem bounds the iterations by (9) and gives the same probability guarantee for the certificate when no such direction is encountered.Source: §3.2 · p. 10

3.3 Damped Newton-CG

  • Algorithm 3 uses negative-curvature directions found during Capped CG or by an oracle, or an inexact damped Newton step, with backtracking line search for sufficient decrease.The decrease condition depends on the cubic norm of the step.Source: §3.3 · p. 11
  • The method’s scope is global complexity analysis; the authors leave rapid local convergence near a strict local minimum unproved.They describe such a proof as probably possible but complicated and less enlightening than the complexity guarantees.Source: §3.3 · p. 11

4 Complexity Analysis

The complexity analysis establishes that Capped CG produces an inexact Newton step or negative-curvature direction suitable for backtracking and bounds the work to reach approximate first- and second-order points. It combines iteration and per-iteration workload bounds, with a probabilistic second-order guarantee based on a minimum-eigenvalue oracle.

4.1 Properties of Capped CG

  • Capped CG returns either an inexact Newton step or a negative-curvature direction, and both support a successful backtracking line search.The method uses these properties to establish first-order complexity and, with the minimum-eigenvalue oracle, second-order complexity.Source: §4 · p. 12, §4.1 · p. 13

4.2 First-Order Complexity Analysis

  • For sufficiently large n, the first-order computational bound is Õ(ǫ_g^-7/4), matching the deterministic guarantee in and improving on the O(ǫ_g^-2) complexity of gradient-based methods.The operation count is bounded by (2 min {n, J(UH, ǫH, ζ)} + 2)(K̄1 + 1) Hessian-vector products and/or gradient evaluations.Source: §4.2 · p. 17

4.3 Second-Order Complexity Results

  • With probability at least (1 − δ)^K̄2, Algorithm 3 reaches a point satisfying the approximate second-order conditions within K̄2 iterations, under Assumptions 1–3.The minimum-eigenvalue oracle must, with probability 1 − δ, certify the curvature threshold or find curvature below −ǫH/2 within its stated Hessian-vector-product budget; failure can cause incorrect termination.Source: §4.3 · pp. 18–19
  • When δ < 1/K̄2, the second-order success probability can be stated as at least 1 − δK̄2, and the analysis also bounds the Hessian-vector products and gradient evaluations needed to reach such a point.The operation bound is given in Corollary 2, but its formula is not visible in the supplied passages.Source: §4.3 · pp. 20–21
  • The bound applies for sufficiently large n and under the condition δ < 1/ K̄2.Source: §4.3 · p. 21
  • The proof combines Theorem 4's iteration bound with Lemma 1 and Assumption 3, which bound workload per iteration.Source: §4.3 · p. 21
  • O~(ε_g^-7/4) is recovered with high probability for sufficiently large n, matching bounds for accelerated gradient-type methods [1,6,19].Source: §4.3 · p. 21

5 Discussion

The approach combines Newton-type CG steps with curvature checks and safeguards to obtain guaranteed approximate second-order convergence at best-known complexity bounds. A simpler capped-CG alternative preserves essentially the same high-probability guarantees but lacks the deterministic approximate first-order guarantee; the main procedure requires high step accuracy.

5 Discussion

  • The safeguarded Newton-CG framework matches the best known complexity bounds for second-order methods in nonconvex optimization.It monitors CG for negative curvature and combines CG and Lanczos-based curvature detection with complexity guarantees.Source: §5 · p. 21
  • An alternative explicit CG iteration cap retains essentially the same high-probability complexity results as Theorem 4 and Corollary 2, but loses Theorem 3’s deterministic approximate first-order guarantee.The capped variant is more elementary to specify and analyze.Source: §5 · p. 21
  • The complexity analysis requires high accuracy in the damped Newton-system step, allowing only a small residual at the approximate solution.Practical algorithms typically use looser restrictions; the paper says tighter bounds appear necessary for its complexity analysis, and differences from practical procedures remain under investigation.Source: §5 · pp. 21–22

A Linear Conjugate Gradient: Relevant Properties

The appendix reviews classical CG operations and properties used in the paper’s analysis. It also shows how to evaluate the negative-curvature test with essentially no additional cost by storing two scalars per CG iteration.

A Linear Conjugate Gradient: Relevant Properties

  • Classical CG updates the iterate, residual, and search direction through successive matrix-vector products and scalar recurrences.The appendix presents the standard CG algorithm and views it as solving the quadratic problem associated with the matrix and vector inputs.Source: A Linear Conjugate Gradient: Relevant… · pp. 23–24
  • During CG, residuals are orthogonal, search directions are mutually conjugate with respect to the matrix, and iterates lie in the generated search-direction span.These standard properties support the later analysis of the modified CG procedure.Source: A Linear Conjugate Gradient: Relevant… · p. 24
  • The negative-curvature test can be evaluated at essentially no cost by storing α_k and ∥r_k∥² at each CG iteration.This avoids storing or regenerating earlier iterates and avoids additional matrix-vector products.Source: A Linear Conjugate Gradient: Relevant… · pp. 24–25

B Implementing Procedure 2 via Lanczos and Conjugate Gradient

The appendix relates randomized Lanczos and CG as minimum-eigenvalue oracles for detecting negative curvature. With a random start, CG inherits Lanczos’s high-probability guarantees, and a Lanczos variant can estimate the matrix-norm bound when it is not known in advance.

B Implementing Procedure 2 via Lanczos and Conjugate Gradient

  • CG detects nonpositive curvature at the same iteration that Lanczos first finds such a direction in the corresponding Krylov subspace.The equivalence holds when CG is applied to the quadratic with right-hand side set to the negative of the Lanczos starting vector.Source: B Implementing Procedure 2 via Lanczos… · pp. 25–27
  • With a uniformly random start, CG inherits a high-probability curvature guarantee: if λ_min(H) < −ε, it finds a direction with curvature at most −ε/2 within the stated iteration limit.The corollary also states that running for that limit without termination certifies with probability at least 1−δ that λ_min(H) ≥ −ε.Source: B Implementing Procedure 2 via Lanczos… · p. 28
  • Randomized Lanczos estimates an upper bound M on ∥H∥ satisfying ∥H∥ ≤ M ≤ 2∥H∥ with high probability, so the oracle need not be given a bound in advance.The resulting procedure terminates correctly with probability at least 1−δ; each Lanczos iteration requires one matrix-vector multiplication.Source: B Implementing Procedure 2 via Lanczos… · pp. 28, 30
  • The norm-estimating Lanczos variant has complexity within a modest constant multiple of the version using a known norm bound.The paper states this comparison assuming an available upper bound on ∥H∥.Source: B Implementing Procedure 2 via Lanczos… · p. 30

C Proof of Theorem 2

The proof of Theorem 2 uses an auxiliary sequence of strongly convex quadratic functions and induction to bound the CG quadratic objective. It then translates those bounds into residual-norm relations to derive the required result by contradiction.

C Proof of Theorem 2

  • The proof assumes the step remains sufficiently far from earlier CG iterates, then reformulates this condition using strong convexity of the quadratic model.The distance condition is stated for each earlier iterate and the later CG iterate.Source: C Proof of Theorem 2 · pp. 30–31
  • An auxiliary sequence Φ_j of quadratics with Hessian εI is introduced, and induction bounds Φ_j at the final CG iterate by the model q plus a shrinking error term.The induction follows from the recurrence defining Φ_j and the stated relation between successive terms.Source: C Proof of Theorem 2 · p. 31
  • The proof inductively relates q(y_j) to the minimum Φ*_j, using CG properties and residual bounds to obtain a contradiction with the assumed distance condition.The final contradiction establishes the theorem’s required conclusion.Source: C Proof of Theorem 2 · pp. 31–34
Loading 1803.02924v4…