Source-linked AI summary
Primal Acceleration of Newton's Method
Nikita Doikov
TL;DR
The paper addresses accelerated global optimization of convex functions with Lipschitz continuous Hessians without the auxiliary nonlinear subproblems used by earlier methods. It develops a direct primal-space Newton acceleration requiring one linear solve per iteration and obtains an O(1/k^3) global rate, with extensions to inexact, Hessian-free, Bregman, and composite settings.
Problem
Existing accelerated second-order methods for convex functions with Lipschitz Hessians use auxiliary nonlinear subproblems, searches, or extragradient corrections, motivating a simpler approach.
Method
The paper directly incorporates Hessian information into the momentum-form Fast Gradient Method using only primal variables and one linear system solve per iteration.
Results
O(1/k^3) global convergence in functional residual is obtained for convex functions with Lipschitz continuous Hessians, matching accelerated cubic Newton with simpler iterations.
Takeaways & Limitations
The method supports approximate linear or nonlinear subproblem solutions, Hessian-free solvers, arbitrary Bregman geometries, and composite optimization while preserving the stated global rate.
Takeaways & Limitations
Adaptive estimation of the second-order parameters remains an open question, with their product currently treated as a single step-size that must be fine-tuned.
Abstract
from arXiv · showhide
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.
1 Introduction
The paper introduces a direct primal-space acceleration of Newton’s method for convex functions with Lipschitz continuous Hessian, motivated by the cost of existing globally accelerated schemes. With one linear solve per iteration and no auxiliary nonlinear subproblems, searches, or extragradient corrections, it achieves an O(1/k^3) functional-residual rate.
- Method: The method directly generalizes the momentum-form Fast Gradient Method by incorporating Hessian information at the extrapolated point.It uses H_k ≈ ∇^2f(y_k) within the primal accelerated iteration.
- Motivation: Newton-type methods seek global convergence from arbitrary initialization, while existing accelerated approaches often require costly regularized subproblems or corrections.Cubic and accelerated cubic Newton methods use nonlinear subproblems, auxiliary minimizations, or extragradient corrections.
- Method: The algorithm operates solely in primal variables, without aggregating dual gradients or performing extragradient corrections.Setting H_k := 0 recovers the classic Fast Gradient Method.
- Results: O(1/k^3) functional-residual convergence is achieved for convex functions with Lipschitz continuous Hessian using one linear system solve per iteration.The rate matches accelerated cubic Newton while requiring simpler per-iteration work.
- Extensions: The construction extends to Bregman geometries and composite optimization, retaining the O(1/k^3) global rate with approximate subproblem solutions.For the simplest second-order iterate, inexact linear solves are also sufficient, enabling Hessian-free implementations.
2 Algorithm Reparametrization
The method reparameterizes its iterations with cumulative weights and normalized ratios, while tracking primal points and prox centers. A single Newton step approximates the contracted subproblem minimizer and yields the update formulas.
- The analysis fixes Euclidean geometry and uses Bregman divergence later to extend the method to arbitrary norms.
- Positive weights a_k are organized through partial sums A_k and normalized ratios γ_k to simplify the iteration analysis.The reparameterization supports the momentum and step-size formulas.
- The algorithm maintains main iterates x_k and auxiliary prox centers v_k, initialized identically.Prediction points are formed as convex combinations of these sequences.
- The next prox center is defined by approximately minimizing a contracted objective.This connects the construction to contracting-point methods.
- One classical Newton step is sufficient to obtain a sufficiently accurate prox-center update.Controlling γ_k places the current prox center in Newton’s local quadratic-convergence region; the construction also resembles interior-point path-following.
- The prox-center and prediction updates correspond directly to the primal method’s formulas through displacement and momentum identities.The derivation matches the regularization and momentum parameters in method (3).
3 Properties of One Newton’s Step
The analysis applies one Newton step to a strongly convex contracted objective under a Lipschitz-Hessian assumption. Local quadratic convergence controls the approximation error needed for the accelerated method.
- The objective is convex with a Lipschitz continuous Hessian, while the analysis uses the exact Hessian at the prediction point.The matrix norm condition uses the standard spectral norm for symmetric matrices.
- The contracted objective h_k has a unique minimizer because its regularizer makes the objective strongly convex.Its Hessian is bounded below by the identity, and the minimizer satisfies a stationary condition.
- One Newton step produces an approximation whose error is governed by the local quadratic-convergence analysis.The analysis evaluates the step applied to h_k and its Hessian Lipschitz constant.
- Choosing a sufficiently small contraction parameter ensures that the current prox center lies in Newton’s local quadratic-convergence region.This choice determines the convergence rate of the accelerated method.
- The distance and gradient bounds together establish quadratic convergence in terms of the gradient norm.The gradient result follows by combining the distance estimate with an upper bound on the Newton step length.
4 Accelerated Rate Analysis
The accelerated analysis proves a global O(1/k^3) functional-residual rate using a Lyapunov invariant and a predetermined coefficient schedule. The method retains one linear solve per iteration and supports approximate solves and extensions.
- Theorem 1 establishes the central invariant relating the initial distance, weighted optimum value, prox-center distance, and current function value.The invariant is proved by induction over the iterations.
- The invariant immediately gives f(x_k) − f⋆ ≤ R^2/(2A_k), so maximizing A_k determines the convergence rate.The proof uses the contracted objective and convexity bounds to propagate the invariant.
- A predetermined choice of coefficients satisfies the required condition and yields the accelerated O(1/k^3) global rate.The schedule also produces simple momentum-update formulas and preserves the stated invariant.
- The concrete primal accelerated Newton method is the first known second-order method in this class to achieve O(1/k^3) with one linear system solve per iteration.The claim applies to convex functions with Lipschitz continuous Hessian.
- The method can use an approximate linear-system solution while preserving the accelerated framework, and it extends to composite optimization and Bregman geometries.The paper also notes that tuned second-order step sizes may be preferable in practice to the rigid theoretical choice.
5 Bregman Geometry and Composite Problems
The construction extends from Euclidean smooth optimization to arbitrary norms through Bregman divergence and to composite objectives with simple constraints or nonsmooth regularizers. The resulting scheme tolerates inexact subproblem solutions and supports Hessian-free implementation.
- Bregman Geometry and Composite Problems: The generalized scheme uses a 1-strongly convex distance function and its Bregman divergence instead of relying on Euclidean squared distance.The divergence satisfies a lower bound by one-half the squared norm and obeys the key three-point identity.
- Bregman Geometry and Composite Problems: The composite problem includes a differentiable smooth term f and a proper closed convex regularizer ψ that may be nonsmooth and impose simple constraints.The Hessian of f is assumed Lipschitz continuous on the feasible domain.
- Bregman Geometry and Composite Problems: The generalized iteration forms a prediction point, evaluates the Hessian there, and computes the next prox center by approximately minimizing a Bregman-regularized composite subproblem.The subproblem is convex quadratic plus Bregman and composite terms.
- Bregman Geometry and Composite Problems: Inexact solutions are explicitly allowed through a tolerance condition because the generalized subproblem can be complicated for arbitrary geometries and regularizers.The tolerance is designed to be attainable by reasonable numerical solvers.
- Bregman Geometry and Composite Problems: In the Euclidean smooth special case, the generalized method reduces to the earlier method and permits Hessian-free linear solves using only Hessian-vector products.Conjugate gradient is given as an example suitable for large-scale models.
- Bregman Geometry and Composite Problems: The general convergence result preserves an accelerated rate under the chosen parameters, including for the inexact composite scheme.The corollary specifies a coefficient choice for the generalized algorithm and its accelerated rate.
6 Discussion
The method achieves an O(1/k^3) rate for convex functions with Lipschitz continuous Hessian using one linear solve per iteration, while several adaptive and higher-rate extensions remain open.
- 6 Discussion: O(1/k^3) convergence is achieved for convex functions with Lipschitz continuous Hessian using one possibly inexact linear solve per iteration.The method does not require correcting extragradient steps.
- 6 Discussion: Adaptive estimation of parameters such as L2 and R remains an open question for retaining one linear solve per iteration.The current method fine-tunes their product γ ≡ L2R as a single scalar second-order step-size.
- 6 Discussion: An improved O(1/k^7/2) rate with simple per-iteration complexity may require replacing the global parameter R with a local proximal-step estimate, making the subproblem nonlinear.This replacement introduces complications because the subproblem is no longer linear.
- 6 Discussion: Connections between the method and classic quasi-Newton methods remain to be established through non-asymptotic analysis.The authors leave this direction for future research.