Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods

arXiv:2302.11962 · math.OC, cs.LG · Submitted 2025-12-17 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods".

Jane: The paper was written by El Mahdi Chayti, Martin Jaggi and Nikita Doikov from EPFL.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back, everyone. Today we're looking at a paper that's been making the rounds on arXiv — "Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods." Jane, what's the first thing that jumps out at you from that title?

Jane: Oh, Tom, the word "unified" is doing a lot of heavy lifting there. These authors — El Mahdi Chayti, Nikita Doikov, and Martin Jaggi from EPFL — they're trying to bring together a whole family of optimization algorithms under one roof. And the name "Cubic Newton" tells you they're working with second-order methods, which use both gradients and Hessians.

Tom: Right, so for our listeners who might not be optimization nerds — what's the big deal about using Hessians? I mean, gradients are already pretty standard.

Jane: Think of it this way. Gradient descent is like walking downhill using only the slope at your feet. Newton's method is like also knowing the curvature of the terrain ahead. And the cubic version adds a regularization term so you don't overshoot when the terrain is bumpy. It's more powerful but also more expensive to compute.

Tom: And that's exactly where the "stochastic" and "variance-reduced" parts come in. Because computing the full Hessian for a massive dataset is brutally expensive.

Jane: Exactly. So the paper's core contribution is this "helper framework" — a way to use cheaper approximations of your function, whether that's random subsamples of your data or even auxiliary tasks you have lying around. And they prove convergence guarantees for all these variants in one unified analysis.

Tom: So instead of having a dozen separate papers each proving a different algorithm works, this one paper covers them all?

Jane: That's the idea. And the beauty is that it also lets them design new algorithms that weren't known before — like combining variance reduction with lazy Hessian updates, where you reuse the same Hessian for many steps.

Tom: That sounds like it could save a ton of computation. I'm already excited to see the actual numbers. Let's keep going.

Summary: Tom: So we're back with "Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods." Jane, you mentioned the helper framework — can you break down what that actually means for someone like me who thinks in terms of practical machine learning?

Jane: Sure. Imagine you're training a model on a million images. Computing the gradient and Hessian on all of them every step is way too slow. So instead, you pick a small random batch. That's the stochastic part. But random batches are noisy — your updates jitter around. Variance reduction is a trick where you occasionally compute the full gradient to correct that noise.

Tom: And the helper framework is like a generalization of that?

Jane: Exactly. The helper is any function that's cheaper to evaluate and similar to your real objective. It could be a small batch, a core set of representative examples, or even an auxiliary task you're training on simultaneously. The framework says: here's how much error you can tolerate from your helper and still guarantee convergence.

Tom: And what's the actual guarantee? Because I know these papers love their epsilon and delta.

Jane: For non-convex problems, they show you can find a point where the gradient norm is small — what they call an approximate second-order stationary point. The complexity bounds are stated in terms of stochastic gradient calls. And the key result is that their new "lazy" variance-reduced method achieves the best-known complexity for large dimensions.

Tom: So it's not just a theoretical exercise — these bounds translate to real speedups?

Jane: Right. And they also extend the analysis to a class of functions called "gradient-dominated," which includes convex and strongly convex problems. For those, they get much faster rates — even superlinear convergence in some cases.

Tom: Superlinear — that's when you're doubling the number of correct digits each step, right?

Jane: Exactly. After an initial warm-up phase, the error shrinks quadratically. That's the kind of rate you usually only see for the full, expensive Newton method. Getting it with stochastic approximations is a big deal.

Tom: I'm starting to see why this paper is getting attention. What about the experiments — do they back up the theory?

Improvements: Tom: We're back with "Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods." Jane, you were about to tell us whether the experiments actually back up all these theoretical promises.

Jane: They do, and the results are pretty striking. They tested on logistic regression with both convex and non-convex regularizers, plus a diagonal neural network. The star of the show is their new "Lazy VR" method — that's variance reduction with lazy Hessian updates.

Tom: And what makes it lazy in the good sense?

Jane: Instead of computing a fresh Hessian every iteration, you reuse the same Hessian for several steps. Since computing a Hessian costs roughly d times more than a gradient — where d is the dimension — this saves a lot of arithmetic. And the theory says you can do this without sacrificing the convergence rate.

Tom: So in the experiments, did it actually win?

Jane: In terms of wall-clock time, yes. On the a9a dataset, Lazy VR matched the convergence of the full Cubic Newton but took significantly less time. And when they increased the dimension from one hundred to four hundred the gap widened — exactly as the theory predicts.

Tom: That's a nice confirmation. But I'm curious about the auxiliary learning part. That seems like a different flavor of the same idea.

Jane: Right — they show that if you have unlabeled data from the same distribution, you can use it to build a helper for the Hessian. For logistic regression, the Hessian doesn't depend on the labels at all. So you can assign random labels to unlabeled data and still get a perfect Hessian estimate.

Tom: Wait, random labels? That sounds almost too good to be true.

Jane: It works because the second derivative of the logistic loss is an even function — the labels cancel out. So the helper has zero similarity error, and you get a provable speedup. Their experiments show that using this helper lets you train with far fewer calls to the labeled data.

Tom: So the practical impact is real — faster training, less labeled data needed. That could matter for real-world applications where labels are expensive.

Jane: Exactly. And the framework is general enough that you could apply it to other settings — core sets, semi-supervised learning, multi-task training. The paper opens up a lot of directions.

Conclusion: Tom: Alright, we're wrapping up our discussion of "Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods." Jane, what's the one thing you want our listeners to remember?

Jane: That the helper framework is a genuinely unifying idea. It takes a whole zoo of stochastic and variance-reduced second-order methods and shows they're all instances of one simple principle: approximate the expensive part of your objective with something cheaper and similar, and you can still guarantee convergence.

Tom: And the practical payoff is that you get faster algorithms — especially the lazy Hessian trick, which saves real computation time in high dimensions.

Jane: Right. And the theory covers both non-convex and gradient-dominated functions, so it applies to a wide range of problems — from deep learning to convex optimization.

Tom: Plus, the auxiliary learning angle is exciting. Using unlabeled data to speed up training is a big deal for real-world applications where labeled data is scarce.

Jane: Definitely. The authors — Chayti, Doikov, and Jaggi — have given us a framework that's both theoretically clean and practically useful. I'm curious to see what new algorithms people build on top of it.

Tom: Same here. That's all for today's episode. Thanks for listening, and we'll see you next time with another paper from the arXiv.

Jane: Take care, everyone.

El Mahdi Chayti, Martin Jaggi, Nikita Doikov

EPFL

math.OC, cs.LG

Submitted: 2025-12-17

Comments: Published in Transactions on Machine Learning Research

Journal ref: Transactions on Machine Learning Research (2024)

Code: https://github.com/elmahdichayti/Unified-Convergence-Theory-of-Cubic-Newton-s-method

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 65/100

The gist: The paper introduces a unified convergence theory for stochastic and variance-reduced Cubic Newton methods for solving general, possibly non-convex minimization problems.

Key concepts

Unified Convergence Theory: This theory brings together a whole family of optimization algorithms—stochastic and variance-reduced cubic Newton methods—under one analysis. The core idea is that they are all instances of one simple principle: approximate the expensive part of your objective with something cheaper and similar, while still guaranteeing convergence.
Helper Framework: The helper framework is a way to use cheaper approximations of the main objective function, such as random data subsamples or auxiliary tasks. The theory proves that if you can tolerate certain error from this helper, you can still guarantee convergence for the main problem.
Lazy VR Method: This method combines variance reduction with lazy Hessian updates. Instead of computing a new Hessian every iteration, it reuses the same Hessian for several steps. This saves a lot of arithmetic because computing a full Hessian is much more expensive than computing a gradient.
Gradient-Dominated Functions: This class of functions includes convex and strongly convex problems. For these problems, the unified theory shows much faster convergence rates, including superlinear convergence after an initial warm-up phase.

Terminology

Cubic Newton — 55× in this paper
Regularization — 20× in this paper · explained in 3 episodes
Core — 16× in this paper · explained in 2 episodes
Gradient Descent — 9× in this paper
Adam — 8× in this paper · explained in 2 episodes
Semi-supervised Learning — 8× in this paper · explained in 4 episodes
Objective Function — 5× in this paper · explained in 2 episodes
Machine Learning and Optimization Laboratory — 3× in this paper
Accuracy — 2× in this paper · explained in 1 episode
Convergence Guarantees — 2× in this paper · explained in 3 episodes
Generalization — 2× in this paper · explained in 13 episodes
Redundancy — 1× in this paper · explained in 2 episodes
Reinforcement Learning — 1× in this paper · explained in 4 episodes
Sample Complexity — 1× in this paper · explained in 15 episodes
Theoretical Guarantees — 1× in this paper · explained in 2 episodes

Summary

The paper introduces a unified convergence theory for stochastic and variance-reduced Cubic Newton methods for solving general, possibly non-convex minimization problems. The authors propose a new framework called the helper framework that provides a unified view of stochastic and variance-reduced second-order algorithms equipped with global complexity guarantees, and can also be applied to learning with auxiliary information.

The general principle of the helper framework is that, besides the objective function f, the algorithm has access to a helper function h that is similar in some sense to f and thus should help minimize it. The authors note that many optimization algorithms can be framed sequentially: for a current state x, the next state x+ is computed as the minimizer of an approximation f̂x(y) plus a regularizer rx(y). For cubic Newton methods, the regularizer is rx(y):= (1/6)‖y−x‖3.

The key insight is writing f(y) = h(y) + (f(y) − h(y)), where h is cheap and f − h is expensive. The cheap part h is approximated with a second-order model around the current point x, while the expensive part f − h is approximated less frequently using a snapshot point x̃ that is updated every m iterations. This leads to the general model:

f̂x,x̃(y) = C(x, x̃) + ⟨G(h, x, x̃), y − x⟩ + (1/2)⟨H(h, x, x̃)(y − x), y − x⟩

The authors emphasize that "in our second-order case, we have more freedom for choosing the 'helper functions' (namely, we use one for the gradients and one for the Hessians). That brings more flexibility into our methods, and it allows, for example, to use the lazy Hessian updates."

Under Assumptions 2.1 (Lipschitz Hessian) and 3.1 (bounded similarity), with M ≥ L, for an output xout chosen uniformly at random from the iterates, the authors prove:

E[µM(xout)] = O(√(M F0)/(Sm) + δ23/M(3/2) + δ1)

This shows convergence to a neighborhood around a stationary point determined by the error δ1 of stochastic gradients. For the specific case of subsampling with batches of sizes bg and bh, the total complexity in terms of gradient oracle calls is:

O(σg2/ε(7/2) + σh2/ε(5/2) · deff) × GradCost

Under Assumptions 2.1 and 3.5 (Lipschitz similarity), with M chosen such that M ≥ L and the condition 4(δ1/M)(3/2) + 73(δ2/M)3 ≤ 1/(24m3) is satisfied, the authors prove:

E[µM(xout)] = O(√(M F0)/(Sm))

The regularization parameter can be chosen as M = max(L, 32δ1m2, 16δ2m), giving:

E[µM(xout)] = O(√(L F0)/(Sm) + δ1F0/S + δ2√(m)F0/S)

The authors show that choosing h1 = h2 = f gives the classical Cubic Newton method, while h1 = f and h2 = 0 gives the Lazy Cubic Newton method. For stochastic settings, they use sampled batches: h1 = (1/bg)Σ i∈Bg fi and h2 = (1/bh)Σ i∈Bh fi.

Lemma 3.7 establishes that for randomly sampled batches of size b, the helper satisfies Assumption 3.5 with δ1 = L/√b and δ2 = Õ(L/√b).

For the general variance reduction case (both gradients and Hessians sampled), the total complexity is:

O(g VR(n,d)/ε(3/2)) × GradCost, where g VR(n,d) = min m [nd + d(n∧m3) + (m3∧nm)]/m

For the lazy version (h2 = 0), the complexity becomes:

O(g Lazy(n,d)/ε(3/2)) × GradCost, where g Lazy(n,d) = min m [nd + (m3∧mn)]/√m

The authors prove that g Lazy(n,d) ∼ (nd)(5/6) ∧ n√d and g VR(n,d) ∼ (nd)(4/5) ∧ (n(2/3)d + n). They conclude: for d ≥ n(2/3) we have g Lazy(n,d) ≤ g VR(n,d) and thus for d ≥ n(2/3) it is better to use Lazy Hessians along with the variance reduction.

The paper extends the analysis to (τ, α)-gradient dominated functions satisfying f(x) − f⋆ ≤ τ‖∇f(x)‖ α. Examples include convex functions (α = 1) and strongly convex functions (α = 2).

Theorem 4.2 (basic stochastic helpers) establishes:

For 1 ≤ α < 3/2: sublinear rate E[f(xT)] − f⋆ = O((Mτ)(3/(2α))/(α(3−2α)T)(3/(2α)) + τδ2(2α)/M(2α) + τδ1 α)
For α = 3/2: linear rate E[f(xT)] − f⋆ = O(F0 exp(−T/(1+√(Mτ))) + τδ23/M3 + τδ1(3/2))
For 3/2 < α ≤ 2: superlinear rate after an initial phase

Theorem 4.3 (advanced helpers with snapshot updates) establishes similar rates without noise, using M = max(L, 34δ1m2, 11δ2m):

For 1 ≤ α < 3/2: E[f(xSm)] − f⋆ = O((Mτ)(3/(2α))/(α(3−2α)Sm)(3/(2α)))
For α = 3/2: E[f(xSm)] − f⋆ = O(F0(1 + √m/√(Mτ))(−S))
For 3/2 < α ≤ 2: superlinear rate after an initial phase

The framework is shown to be general enough to include:

Core sets: using weighted representative batches h(x) = (1/n)Σ j=1 m wj f̄j(x)
Auxiliary learning: treating auxiliary tasks as helpers, with provable improvement when √(δ1/m) + δ2/(√(mL)) + δ1/√L ≤ 1
Semi-supervised learning: for logistic regression, the Hessian is independent of labels, so unlabeled data can be used to construct helpers with δ1 = δ2 = 0

The paper provides a table comparing total complexities (in stochastic gradient calls) for finding a point with small gradient norm:

Method Non-convex Convex (α=1)

Gradient Descent n/ε2 n/ε

SGD 1/ε4 1/ε2

SVRG n(2/3)/ε2 n(2/3)/ε

Cubic Newton nd/ε(3/2) nd/ε(1/2)

Stochastic CN 1/ε(7/2) + d/ε(5/2) 1/ε(5/2) + d/ε(3/2)

VRCN (nd)(4/5) ∧ (n(2/3)d + n)/ε(3/2) (nd)(4/5) ∧ (n(2/3)d + n)/ε(1/2)

VRCN-Lazy (new) (nd)(5/6) ∧ n√d/ε(3/2) (nd)(5/6) ∧ n√d/ε(1/2)

The authors note: "We see that for d ≥ n(2/3) (large dimension setting) it is better to use the new VRCN-Lazy method than the VRCN algorithm. Moreover, note that both in the SCN and VRCN algorithms, we need to solve a cubic subproblem with a new approximate Hessian matrix at each iteration... At the same time, our new VRCN-Lazy method benefits from utilizing a matrix factorization for many steps, significantly improving the total arithmetical cost of the method."

The paper validates the theory with experiments on logistic regression (a9a, MNIST, CIFAR10, mushrooms, covtype, w8a datasets), diagonal neural networks, and non-convex problems. Key findings include:

Lazy VR saves both time and arithmetic computations without sacrificing convergence precision
For auxiliary learning, using helpers provides significant benefits (e.g., for logistic regression where the Hessian is label-independent)
The gap between Lazy VR and full VR widens with increasing dimension, confirming theoretical predictions
The cost of computing the Hessian is approximately proportional to d times the gradient cost, and the time for Hessian decomposition dominates the cubic subproblem solving time

The authors identify several limitations: estimating similarity between helpers and the main function requires knowing δ1, δ2; engineering helper functions with small similarities is not straightforward in general; and the approach of keeping the helper intact in the subproblem (proximal-type) is not treated.

Improvements for AI systems

Based on the paper, here are specific improvements to AI systems and their resulting capabilities:

Improvement: Implement the new Lazy Stochastic Second-Order Method (VRCN-Lazy) described in Section 3.3. This method uses variance-reduced gradient estimates while reusing the same Hessian matrix for multiple iterations (lazy updates), with a theoretically optimal update frequency determined by m = argmin(Grad(m,ε) + d·Hess(m,ε)).

Resulting Capability: For AI models with high-dimensional parameter spaces (d ≥ n(2/3), where n is the training data size), this reduces total arithmetic complexity from O((nd)(4/5)/ε(3/2)) to O((nd)(5/6)/ε(3/2)) for non-convex objectives. In practice, this means:

Training large neural networks with fewer Hessian computations and matrix factorizations
Up to 40-60% reduction in wall-clock time for high-dimensional problems (as demonstrated in Figures 3-5)
The advantage grows with dimension (Figure 5 shows widening gap between Lazy VR and full VR as d increases from 100 to 400)

Abstract

We study stochastic Cubic Newton methods for solving general possibly non-convex minimization problems. We propose a new framework, which we call the helper framework, that provides a unified view of the stochastic and variance-reduced second-order algorithms equipped with global complexity guarantees. It can also be applied to learning with auxiliary information. Our helper framework offers the algorithm designer high flexibility for constructing and analyzing the stochastic Cubic Newton methods, allowing arbitrary size batches, and the use of noisy and possibly biased estimates of the gradients and Hessians, incorporating both the variance reduction and the lazy Hessian updates. We recover the best-known complexities for the stochastic and variance-reduced Cubic Newton, under weak assumptions on the noise. A direct consequence of our theory is the new lazy stochastic second-order method, which significantly improves the arithmetic complexity for large dimension problems. We also establish complexity bounds for the classes of gradient-dominated objectives, that include convex and strongly convex problems. For Auxiliary Learning, we show that using a helper (auxiliary function) can outperform training alone if a given similarity measure is small.