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

El Mahdi Chayti; Martin Jaggi; Nikita Doikov

math.OCFeb 23, 2023

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

Authors: El Mahdi Chayti, Martin Jaggi, Nikita Doikov

Organizations: Machine Learning and Optimization Laboratory (MLO), EPFL

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.

Figures & tables

	Non-convex , $\varepsilon$ -local solution	Convex ( $\alpha=1$ ), $\varepsilon$ -global solution	Ref.
Gradient Descent (GD)	$n\,/\,\varepsilon^{2}$	$n\,/\,\varepsilon$	Nesterov (2018)
Stochastic Gradient Descent (SGD)	$1\,/\,\varepsilon^{4}$	$1\,/\,\varepsilon^{2}$	Ghadimi and Lan (2013)
Stochastic Variance Reduced Grad. (SVRG)	$n^{2/3}\,/\,\varepsilon^{2}$	$n^{2/3}\,/\,\varepsilon$	Johnson and Zhang (2013)
Cubic Newton (CN)	$nd\,/\,\varepsilon^{3/2}$	$nd\,/\,\varepsilon^{1/2}$	Nesterov and Polyak (2006)
Stochastic Cubic Newton (SCN)	$1\,/\,\varepsilon^{7/2}+d\,/\,\varepsilon^{5/2}$	$1\,/\,\varepsilon^{5/2}+d\,/\,\varepsilon^{3/2}$	Kohler and Lucchi (2017) Nilesh et al. (2018)
Variance Reduced Stoch. Cubic Newton (VRCN)	$(nd)^{4/5}\wedge(n^{2/3}d+n)\,/\,\varepsilon^{3/2}$	${(nd)^{4/5}\wedge(n^{2/3}d+n)\,/\,\varepsilon^{1/2}}$ (new)	Zhou et al. (2019) Wang et al. (2019)

Table 1: The total number of stochastic gradient computations for solving the problem with

\varepsilon

accuracy.

n

is the number of functions (the data size), and

d

is the dimension of the problem. We use

x\wedge y

to denote

\min(x,y)

Figure 1: Comparison of the convergence of different algorithms. We see that “Lazy VR”

Figure 2: Cubic Newton method with and without using the helper function

h

. For

m=1

, this is simply the classic Cubic Newton method. To give an intuitive meaning to the plot,

\frac{1}{m}

is the percentage of labeled data used during training. We can clearly see that using our approach, we benefit a lot from the helper function

h

Figure 3: Comparison of the convergence of different algorithms. We see that using our approach, we benefit a lot from the helper function

h

Figure 4: Comparison of the convergence of the different algorithms. Except for gradient descent (“GD"), which performs very well in this case, again, the same conclusions as in Figure 2 with respect to “Lazy VR" can be said.

Figure 5: Effect of increasing the dimension on the convergence of the different optimization algorithms we consider. We notice that with increased dimension, the gap between our method "Lazy VR" and "full VR" widens meaning "lazy VR" saves more time as the dimension of the problem grows.

Figure 6: (left) times needed to compute the gradient, the Hessian, decompose the Hessian and solve the cubic subproblem for a diagonal neural network with

n=10000

and different values of the dimension

d

. (right) average time for computing the Hessian divided by the average time needed to compute the gradient. we notice that the Hessian computation cost is almost proportional to

d\times

the gradient cost. We also see that the time needed to decompose the Hessian dominates the time needed to solve the cubic subproblem.

Figure 7: Experiments on Mushrooms (

n=8124,d=112

), Covtype (

n=581012,d=54

), w8a (

n=49749,d=300

) datasets.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Logistic regression on the MNIST dataset for different algorithms. We notice that second-order methods clearly outperform first-order methods. We also note how cubic Newton (CN) starts as the fastest but our Lazy VR method catches up to it.

Figure 9: Logistic regression on the CIFAR10 dataset for different algorithms. We notice that second-order methods clearly outperform first-order methods. We also note that our Lazy VR has a big advantage in terms of time compared to all other methods.

Figure 10: A two-layer NN trained on the A9A dataset. We notice that GD (with line search) outperforms all the algorithms but gets stuck at an error of

10^{-6}

. Lazy VR is the second fastest and even ends up beating GD to a smaller error, suggesting that it escaped the local minimum GD was stuck at. Again Lazy VR saves more time compared to full VR.

Second-Order Optimization

Second-order optimization uses curvature information, such as Hessians or their approximations, to choose efficient steps toward better solutions.

See all 90 papers

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
Oct 1, 2026Jiayi Song, Zi XuMin-Max Optimization
Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China
Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization
Mar 6, 2026Ganzhao YuanNonconvex Stochastic Optimization Stochastic Optimization
Shenzhen University of Advanced Technology (SUAT), China
Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum
Jun 18, 2024Haoyuan Cai, Sulaiman A. Alghunaim, Ali H. SayedMomentum Methods Nonconvex Stochastic Optimization
Ecole Polytechnique Fédérale de Lausanne, Switzerland · Kuwait University, Kuwait

Oct 1, 2026J/K move · Enter open · S save

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Jiayi Song, Zi Xu

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Min-Max Optimization

Open paper AskPDF arXiv

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an

L

-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most

D_Y

, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most

Δ

. The target accuracy

\varepsilon

is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter

1/(2L)

. Under an unbiased stochastic first-order oracle with variance at most

σ^2

and mean-square smoothness, we prove the lower bound

Ω\!\left(L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right)

. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter

μ>0

and condition number

κ:=L/μ

, we obtain

Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right)

under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant

\bar L

, we obtain

Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right)

. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.

Abstract

Second-Order Optimization

Explore similar work

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum