A Newton Method That Hits O(1/k³) With One Linear Solve Per Step

TL;DR: “Primal Acceleration of Newton’s Method” on arXiv describes a second-order optimizer that reaches an $O(1/k^3)$ convergence rate while doing just one linear solve per iteration and skipping the expensive machinery (cubic regularization, nonlinear subproblems, dual corrections) that usually comes with that speed.

Most of the AI research I read is about models. This one is about the math underneath the models: how you actually find the bottom of a loss surface, and how fast. The paper is titled “Primal Acceleration of Newton’s Method,” posted to arXiv under both cs.AI and cs.LG. I’ll treat the abstract as the primary source here, because that’s what’s available, and I’ll be honest about where the claims outrun what I can verify from an abstract alone.

What is the paper actually claiming?

Newton’s method is the classic second-order optimizer. Instead of just following the gradient downhill (first-order, like SGD or Adam), it uses the Hessian, the matrix of second derivatives, to account for curvature. That curvature information lets it take much smarter steps near a minimum. The catch is cost. Each Newton step traditionally means forming and solving with the Hessian, which is expensive, and getting a good global convergence rate has historically required extra scaffolding.

The two dominant ways to get that scaffolding are cubic regularization (you add a cubic penalty term and solve a nonlinear subproblem at every step) and dual extragradient corrections (you carry around dual variables and do correction steps). Both work. Both add real per-iteration cost and implementation complexity.

The paper’s claim is that you can get the accelerated rate, $O(1/k^3)$ in the functional residual, for convex functions with Lipschitz continuous Hessian, using only primal variables and one linear solve per iteration. No cubic subproblem. No nonlinear parameter search. No dual extragradient step. The authors say, “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.”

That “to the best of our knowledge” phrasing matters. It’s a novelty claim scoped to a specific problem class, not a claim that this beats everything everywhere. Read it precisely.

Why does “one linear solve per iteration” matter so much?

Here is the practical heart of it. When you compare optimizers, iteration count is a vanity metric on its own. What you care about is total work. An algorithm that converges in fewer iterations but does ten times the work per iteration can easily lose.

Second-order methods have always lived on the wrong side of that trade. They converge in dramatically fewer iterations than gradient descent, but each iteration is heavy. Cubic regularization makes it heavier, because solving that regularized subproblem is itself an iterative process. So the accelerated rate came with a tax.

The claim in this paper is that the tax is gone, or at least much smaller. A linear solve is $Ax = b$. That’s a well-understood operation with mature solvers, and critically, you don’t have to solve it exactly. The abstract says the method “can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate.”

Hessian-free is the phrase to circle. It means you never have to form the full Hessian matrix. You only need Hessian-vector products, which you can get through automatic differentiation at roughly the cost of a gradient. Combine Hessian-free with an inexact solver (think conjugate gradient run for a handful of steps) and you have something that, on paper, could scale to problems where forming a Hessian is impossible.

If that holds in practice, it’s the difference between “second-order methods are a nice theory” and “second-order methods you could actually run.”

Where should I stay skeptical?

I want to be the guy who cuts the hype, so let me. Here is what the abstract does not tell us, and what would decide whether this matters outside a proof.

The rate is for convex functions with Lipschitz continuous Hessian. Neural network training is not convex. Not even close. Loss landscapes are riddled with saddle points and non-convex structure. So the headline rate does not transfer directly to training a transformer. That doesn’t make the work useless for ML: convex subproblems show up all over the place (logistic regression, many classical ML fits, inner loops of larger methods, certain fine-tuning and calibration steps, optimization inside RL and control). But anyone reading “faster Newton” and picturing GPT training runs is getting ahead of the math.

There are no experiments in the abstract. I have no wall-clock numbers, no comparison against L-BFGS or cubic-regularized Newton on real problems, no sense of how the inexact solver’s tolerance interacts with the guaranteed rate in messy conditions. A clean $O(1/k^3)$ theorem is a strong result, but the constants hidden in that big-O and the behavior under inexactness are exactly where nice theory meets ugly reality. I can’t evaluate that from what’s posted.

And “one linear solve per iteration” is honest about count but not about difficulty. The linear system’s conditioning drives how many inner solver steps you need. A well-conditioned system is cheap. An ill-conditioned one can eat your budget even with a great outer method. The abstract says the rate is preserved with an inexact solver, which is encouraging, but the real test is total operations to a target accuracy on problems people care about.

The extensions are the most interesting tell about ambition. The authors say they generalize to arbitrary geometry via Bregman divergence and to composite optimization. Composite problems (smooth part plus a simple nonsmooth regularizer, like an L1 penalty) are where a lot of real applied optimization lives. If the primal acceleration genuinely carries over there without losing the rate, the reach is wider than a single clean theorem.

Practitioner’s Take

If you train neural nets for a living, this is a paper to file, not to act on today. It targets convex problems, and the interesting engineering questions (wall-clock, conditioning, inexact-solver tolerances) are unanswered in the abstract. Watch for a follow-up with experiments before you believe any speedup claim.

If your work touches convex or convex-inner-loop optimization, though, this is worth a real read when the full PDF and any code land. The move to try: take a convex problem where you currently run cubic-regularized Newton or a careful L-BFGS, and once a reference implementation exists, benchmark this method Hessian-free with a truncated conjugate-gradient inner solve. Measure total Hessian-vector products to a fixed accuracy, not iteration count. That number is the whole game.

The catch most readers will miss is in the fine print of the title itself: “primal” and “one linear solve” are the claims, and they’re specific claims about avoiding cubic subproblems and dual corrections, not a general “Newton is now cheap” statement. The value here, if it survives contact with experiments, is dropping a whole layer of algorithmic machinery while keeping the fast rate. Simpler that performs as well as complex is almost always the better engineering bet. But “if it survives contact with experiments” is doing a lot of work in that sentence, and until someone posts the numbers, that’s exactly where I’d keep my expectations parked.