Primal Acceleration of Newton's Method: Cubic Rate from One Linear Solve

Paper: 2608.21359 Authors: Nikita Doikov Categories: cs.AI, cs.LG, math.OC

The Gap

For convex minimization with a Lipschitz continuous Hessian, second-order methods have long been caught in a trade. You can have the fast global rate, or you can have an iteration that is cheap and simple — but historically not both at once.

The fast rates in this class came bundled with machinery. Cubic regularization solves an auxiliary nonlinear regularized subproblem each step, which means an inner optimization loop inside the outer one. Other approaches perform nonlinear parameter searches, or add dual extragradient corrections. Each of these buys the rate by making the iteration harder to implement and harder to reason about.

The simpler alternative — a plain damped Newton step — does one linear solve per iteration and is straightforward. But its global rate is slower. So the practical question has been: is the extra machinery genuinely necessary to get the fast rate, or is it an artifact of how the existing methods were derived?

   THE TRADE IN SECOND-ORDER CONVEX OPTIMIZATION

   Want the fast global rate O(1/k^3)?
        |
        +-- cubic regularization
        |     -> solve a nonlinear regularized SUBPROBLEM each step
        |     -> inner optimization loop inside the outer loop
        |
        +-- nonlinear parameter search
        |     -> line search over a nonlinear criterion
        |
        +-- dual extragradient corrections
        |     -> extra dual machinery and tuning
        |
   Want a simple iteration (one linear solve)?
        |
        +-- plain damped Newton
              -> but SLOWER global rate
        |
        v
   [GAP] fast rate and simple iteration were believed
         to be mutually exclusive for this problem class

The Increment

One sentence: Before this paper, the fast global rate for this problem class came attached to an auxiliary nonlinear subproblem, a parameter search, or a dual correction; after it, one linear solve per iteration on primal variables alone is enough to reach a cubic rate — and the construction still works with an inexact solver.

Core Mechanism

The method is a direct accelerated Newton scheme with three properties that, taken together, are what the abstract claims are new.

Primal only. The algorithm uses only primal variables. There is no dual variable, no dual correction step, no extragradient machinery. For anyone implementing this, that is the difference between a method you can write in a few lines against an existing linear algebra backend and a method that needs a second, parallel state to be maintained and tuned.

One linear solve per iteration. This is the load-bearing economy. Competing approaches for the same rate each spend something extra per step: an inner nonlinear solve, a parameter search, a dual update. This method spends exactly one linear system solve, which is the same per-iteration cost as the plain Newton step it improves on. The fast rate therefore arrives nearly free in iteration complexity terms.

A predetermined parameter choice. The rate is achieved with a simple predetermined choice of parameters, meaning it is not the result of a delicate tuning procedure that has to be reproduced per problem. This matters for a theoretical claim, because a rate that depends on a well-chosen search procedure is a weaker guarantee than one that holds under a fixed schedule.

The result is a global rate of O(1/k^3) in terms of the functional residual. Stated plainly: the function value’s suboptimality shrinks with the cube of the iteration count, which is the accelerated regime, achieved without the auxiliary subproblems that historically accompanied it.

The most practically consequential part comes last. The method can be implemented Hessian-free, using an inexact linear system solver, while preserving the fast global rate. This is what moves the result from a theoretical curiosity to something usable at scale. If the cubic rate required exact Hessian solves, it would be inapplicable to any problem large enough to need it. Requiring only an inexact solve opens the door to the standard toolkit — matrix-free products, iterative solvers, truncated inner loops. The construction is then extended to arbitrary geometry via Bregman divergence, and to composite objectives.

   ALGORITHM SHAPE (per iteration)
   +--------------------------------------------------------+
   | 1. form / approximate the Hessian at current point     |
   |      (inexact solver is FINE, rate preserved)          |
   +----------------------------+---------------------------+
                                v
   | 2. ONE linear system solve  ->  step direction         |
   +----------------------------+---------------------------+
                                v
   | 3. predetermined damping / parameter schedule          |
   |      (no nonlinear search)                             |
   +----------------------------+---------------------------+
                                v
   | 4. update primal variables only                        |
   |      (no dual state to maintain)                       |
   +----------------------------+---------------------------+
                                v
   GLOBAL RATE: functional residual = O(1/k^3)

   EXTENSIONS: Bregman divergence (arbitrary geometry),
               composite objectives

Think of it as getting a high-speed train without building a second track. Earlier methods in this class reached high speed by adding infrastructure: a passing loop for an inner subproblem (cubic regularization), a signalling search that has to find the right schedule each run (nonlinear parameter search), or a parallel control line (dual extragradient). All of them work, and all of them mean more track to lay, inspect and maintain. This paper shows the same speed is attainable on the single existing track — one linear solve per stop — provided the schedule is decided in advance. And crucially, the track does not need to be perfectly level: an inexact solve, the approximate equivalent of track that is good enough rather than surveyed to the millimetre, does not cost you the speed.

Key Concepts

• Global versus local rate: a local rate holds near a solution, once you are close enough; a global rate holds from any starting point. Global guarantees are much stronger, and the machinery this paper removes — cubic regularization and friends — existed largely to buy global behaviour. Getting it globally from a simple iteration is the notable part.
• Functional residual as the measure: the rate is stated in terms of how far the current function value is from the optimum, not how far the iterates are from the optimal point. Function-value suboptimality is the quantity that usually controls downstream error, and it is the natural unit when the problem has non-unique minimisers.
• Inexactness that does not cost the rate: the property that approximate linear solves preserve the fast global convergence. This is what makes a second-order method viable on large problems, since exact Hessian solves are exactly what becomes impossible first as dimension grows.

Framework Shift

Before (fast rate requires extra machinery):
  iteration = [linear solve] + [one of:]
                 - inner nonlinear subproblem (cubic reg.)
                 - nonlinear parameter search
                 - dual extragradient correction
  -> fast global rate O(1/k^3)
  -> but each iteration is harder to implement and analyse

After (fast rate from the simple iteration):
  iteration = [ONE linear solve] + [predetermined schedule]
              primal variables only
              inexact solver acceptable
  -> same global rate O(1/k^3)
  -> plus Bregman (arbitrary geometry) and composite extensions

From buying the fast rate with an auxiliary nonlinear subproblem, to obtaining it from a predetermined schedule around a single linear solve, the core shift is that the extra machinery was a property of the derivation rather than a requirement of the rate.

Expert Assessment

Problem choice: A classic and still-live question, and the framing is well chosen. In second-order convex optimization, “can the fast rate be had without the auxiliary subproblem” is not a curiosity — it is the question that determines whether a method is implementable in a real solver stack. The extension to inexact solves is the part that makes it matter beyond theory.

Method maturity: This is a clean theoretical contribution rather than an empirical one, and it should be read that way: the deliverable is a rate with a stated set of assumptions, not a benchmark table. The strength is the economy of the construction. The honest limitation is the class of problems — convex objectives with Lipschitz continuous Hessians is a meaningful restriction, and the cubic rate is claimed for that class, not for the non-convex problems where second-order methods are most often reached for in practice.

Experimental integrity: Not applicable in the usual sense; the claims are theorems. The relevant scrutiny is on the assumptions and on what “predetermined choice of parameters” conceals — a rate that requires the right constant embedded in the schedule is weaker than one that is schedule-free, and readers should check the extension to composite and Bregman settings for how much structure is assumed there.

Writing quality: The abstract is unusually well-organised for this genre: it states the rate, then explicitly enumerates the three things the method does not need, which is exactly the information a practitioner wants when deciding whether to try an implementation. The paper would be more useful still with a short note on practical behaviour in the inexact regime — how loose the solve can be before the rate degrades in constant factors, even if not asymptotically.

Verdict: strong accept — the right kind of theoretical result: it removes machinery rather than adding it, and it does so under an inexactness assumption that keeps the method relevant to large problems.

Takeaways

• Before adopting an auxiliary subproblem to obtain a better rate, check whether the rate actually requires it. Here the machine was a property of the derivation, not of the guarantee.
• Prefer constructions with a predetermined parameter schedule over ones that depend on a search procedure. Fixed schedules yield stronger, more reproducible guarantees.
• Requiring only an inexact linear solve is what makes a second-order method usable at scale. When reading a convergence result, check the inexactness assumption before the rate — a rate needing exact solves rarely ships.
• When comparing optimisation methods, count what each iteration spends beyond the linear solve. That per-iteration overhead, not the asymptotic rate, usually decides what gets implemented.