Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
Authors: El Mahdi Chayti
Martin Jaggi
Nikita Doikov
Venue: Accepted by TMLR ()

Abstract: We study stochastic Cubic Newton methods for solving general, possibly non-convex minimization problems. We propose a new framework, 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 stochastic Cubic Newton methods, allowing arbitrary size batches and using 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.

Published in Transactions on Machine Learning Research (09/2024)
Unified Convergence Theory of Stochastic and Variance- Reduced Cubic Newton Methods
El Mahdi Chayti
Machine Leorning and Optimization Laboratory (MLO), EPFL
Martin Jaggi
marlin.jaggi@epf.
Machine Learning and Optimization Laborstory (MIO),, EPFL
Nikita Doikov
nikita, deikooopp.o
Machine Learning and Optimization Laboratory (MLO), EPFL
Reviewed OpenReview: https: openrevieww net/ forum? id= FCs
https:://pperreviea
Abstract
We study stochastic Cubic Newton methods for solving general, possibly non-convex mini- mization problems. We propose new framework, the helper framework, that provides 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 stochastic Cubic Newton methods, allowing arbitrary size batches and using noisy and possibly biased estimates 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 consoquence of our theory is the new lazy stochastic sccond-order method, which significantly improves the arithmetic complexity for large dimension problems. We also establish complexity bounds for the classes of gradient-dominated objectives, including 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.
1 Introduction
In many fields of machine learning, it is common to optimize a function f(x) that can be expressed finite sum
min #ERd
{ f(x) = 1 3 fxx)
(1)
or, more generally, as an expectation over some given probability distribution: f(x)= = [f([f( When f is non-convex, this problem especially difficult since finding global minimum NP-hard in general (Hillar & Lim 2013). Hence, the reasonable goal to look for approximate solutions. The most prominent family of algorithms for solving large-scale problems of the form (1) are the first-order methods, such as the Stochastic
Gradient Descent (SGD) (Robbins & Monro 1951 Kiefer & Wolfowitz 1952). They employ only stochastic
gradient information about the objective f(x) and guarantee the convergence to stationary point, which is
point with a small gradient norm.
Nevertheless, when the objective function is non-convex, a stationary point may be a saddle point or even a local maximum, which might not be desirable. Another common issuc that first-order methods typically have a slow convergence rate, especially when the problem is illcondiitooned. Therefore, they may not be suitable when high precision for the solution is required.

---

Published in Transactions on Machine Learning Research (09/2024)
To address these challenges, we can take into account second-order information (the Hessian matrix) and apply Newton's 's method (see, e.g., (Nesterov) 2018)). Among the many versions of this algorithm, the Cubic Newton method (Nesterov & Polyak] 2006p is one of the most theoretically established. With the Cubic Newton method, we can guarantee global converyence to an approximate second-order stationary point (in contrast, the pure Newton method without regularization can even diverge when starts far from a neighborhood of the solution). For a comprehensive historical overview of the different variants of Newton's method, see Polyak (2007). Additionally, the convergence rate of the Cubie Newton is provably better than those for the first-order methods.
Recent developments in the theory of sccond-order optimization methods include the framework of gradi-
ent regularization ( (Mishchenko 2023; Doikov & Nesterov 2023), adaptive, universal and super-universal
methods |Cartis et al. 2011a| by Grapiglia & Nesterov] 2017 Doikov et al. 2024), the accelerated Newton
methods (Nesterov] 2018), modern analysis of the damped Newton iterations (Hanzely et al.) 2022 Hanzely
2023), and spocial sodond-order schemes for self-concordant and quasi-self--onnorddaa functions (Dvurechensky
& Nesterov 2018: Karimireddy et. al.) 2018 Doikov 2023). Despite some of the advantageous properties most of these developments assume that the objective is convex, allowing the use of different regularization techniques and justifying improved convergence rates. In contrast, the cubic regularization technique is applicable to a wide range of problem classes, including non-convex optimization.
Therefore, the theoretical guarantees of the Cubic Newton method seem very appealing for practical applications. However, the basic version of the Cubie Newton requires the exact gradient and Hessian information in each step, which can be very expensive to compute in a large-scale setting; to overcome this issue, several techniques have been proposed:
One popular approach is to use inexact stochastic gradient and Hessian estimates with subsampling
[Xu et al. 2016 Kohler & Lucchi 2017 Xu et al., 2017 Nilesh et al., 2018 Ghadimi et al.] 2017 Cartis & Scheinberg] 2018 Agafonov et al.] 2020). This technique avoids using the full oracle information, but it typically has slower convergence rate compared to the exact Cubic Newton. Variance reduction techniques (Zhou et al.
2019 Wang et al.) 2019) combine the advantages of stochastic and exact methods, achieving an improved rate by recomputing the full gradient and Hessian information al some iterations.
Lazy Hessian updates (Shamanskii] 1967 Doikoy et al. 2022 utilize a simple idea of reusing an old Hessian for several iterations of a second-order scheme. Indeed, since the cost of computing one Hessian is usually much more expensive than one gradient, it can improve the arithmotic complexity of our methods.
In addition, exploiting the special structure of the function f (if known) can also be helpful. For instance, gradient dominated objectives (Nesterov & Polyak 2006), a subclass of non-convex functions that have improved convergence rates and can even be shown to converge to the global minimun. Examples of such objectives include convex and star-convex functions, uniformly convex functions, and functions satisfying the PL condition (Polyak) 1963) as a special case. Stochastic algorithms with variance reduction for radient-dominate
functions were studied previously for the first-order methods (see, e.g., Fatkhullin et al. (0022) and for the second-order methods with cubic regularization in Masiha al. 2022
In this work, we revise the current state-of-the-art convergence theory for the stochastic Cubic Newton mothod and proposc a unified and improved complexity guarantocs for different versions of the method, which combine the advanced techniques listed above.
Our developments are based the new helper framework for second-order optimization that we present in Scction 3 For first-order optimization, a similar in-spirit technique called learning with auniliary information was developed recently in (Chayli & Karimireddy 2022 Woodworth et al. 2023). Thus, our results can also be seen as a generalization of the Auxiliary Learning paradigm to second-order optimization. However, note that in our socond-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 lany Hessian updates.
2

---

Published in Transactions on Machine Learning Research (09/2024)
Our new helper framework provides us with unified view of the stochastic and variance-reduced methods and can be used by algorithm designed to construct new methods. Thus, we show how to recover already known versions of the stochastic Cubic Newton with some of the best convergence rates, as well as present the new Lazy Stochastic Second- Method, which significantly improves the total arithmetic complexity for large-dimension problems.
Contributions.
We introduce the helper framework, which argue encompasses multiple methods in unified way. Such methods include stochastic methods, variance reduction, Lazy methods, core sets, and semi-supervised learning.
This framework covers previous versions of the variance-reduced stochastic Cubic Newton hods with known rates. Moreover, it provides us with new algorithms that employ Lazy Hessian updates and significantly improves the arithmetic complexity (for high dimensions), by using the same Hessian snapshot for several steps of the method.
In the case of Auxiliary learning, we provably show benefit from using auxiliary tasks as helpers in our framework. In particular, we can replace the smoothness constant with similarity constant, which might be smaller.
Moreover, our analysis works both for the general class of non-convex functions, as well as for the classes of gradient-dominatee problems, which include convez and uniformly conver functions. Hence, in particular, we justify new improved complexity bounds for the deterministic Cubic Newton method with Lazy Hessian updates (Doikov et al. (2022)); as well as for the stochastic Cubic Newton algorithms with variance reduction that take into account the total arithmetic cost of the operations (see Table D.
In the following table, we provide comparison of the total complexities (in terms of the number of stoch. gradient calls) for finding a point with small gradient norm [ S e (non-convex case), or a global solution terms of the functional residual [zf()) - f S & (convex case, gradient dominated functions of degree a = 1), by different. first-order and second-order optimization algorithms. We take into account. that the cost of one stochastic Hessian is proportional d times the cost of the stochastic gradient, where d the problem dimension, which holds for general dense problems.
Non-convex. c- c-loral solution
Convex (a = 1), e-global solution
Ref.
Gradient Descent (GD)
n/
///
Nesterov
2018
Stochastic Gradient Descent (SGD)
1/
1/e²
Ghadimi & Lau
2013
Stochastic Variance Reduced Grad. (SVRG)
n2/a e²
2/2 /
Johnson & Zhang 2013
Cuble Newton (CN)
nd 22/2
1//
Nesterov & Polyak
2006
Stochastic Cubie Newton (SCN)
1/ + 2/
Kohler & Lucehi
Nilesh al
2018
Variance Reduced Stoch. Newton (VRCN)
(nd))/6 A (n12/3
(nd)*/5 (n3/3d + n) e//2 (new)
Zhou 2019
Wang
2019
(new) Variance Reduend CN with Lazy Hesslans (VRCN-Lazy)
(nd)5/o A nvd /avd//"0 2/2 (new) (nd)5/0 A nn/d / (new)
This work
Table The total number of stochastic gradient computations for solving the problem with & accuracy. n is the number of functions (the data size), and d is the dimension of the problem. We use A to denote min(x, ().
We see that for d 2 n/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. This means that, in case of the exact steps, an expensive matrix factorization neods to be computed every iteration for these algorithms. 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.
3

---

Published in Transactions on Machine Learning Research (09/2024)
2 Notation and Assumptions
We consider the finite-sum optimization problem 1 and we assume that our objective f is bounded from below, denoting f* :- inf ((),, and use the following notation: Fo := -(xo)) -f", for some initial 2o E Rd. x
We denote by || := (ar, 1/, 1/2,
Rd, the standard Euclidean norm for vectors, and the spectral symmetric matrices by |H] == max (Xmax (H), -mmin where H = HH T E gdxd, We will also use A
for
to denote min(r,y..
Throughout this work, we make the following smoothness assumption on the objective f:
Assumption 2.1 (Lipschitz Hessian). The Hessian of f is Lipschitz continuous, for some L > 0:
[x) v s L| yll, Va. E Rdd
Our goal is to explore the potential using the Cubically regularized Newton methods to solve problem ([ At each iteration, being a point æ E Idd we compute the next point xt by solving the subproblem of the form
M ly 6
x² E arg mink S...g. = (g.y y xx) (H (olyyx),11 x))
x:
(2)
yERe
Here, 9 and H are estimates of the gradient V (a)) and the Hessian 2² respectively. Note that solving
(2 can be done efficiently even for non-convex problems (see Conn et al. (2000); Nesterov & Polyak (2006);
Cartis et al. (2011a)). Generally, the cost of computing x+ is O(d)) arithmetic operations, which are needed
for evaluating an appropriate factorization of H. Hence, it is of a similar order as the cost of the classical
Newton's s step. Inexact first-order solvers for the cubic subproblem were studied in Carmon & Duchi (020
Nesterov 2022).
We will be interested to find second-order stationary point to local minimum point that satisfies:
We call (s.cc-approzimmae recond-order
[V)(()] s E and Amin f2)()) 2
-oVE,
where E, C > are given tolerance parameters. Let us define the following accuracy measure (see Nesterov Polyak (2006)):
pe(z) == max [Z) =Amin (V (V² (())))))))
0322
Note that this definition implies that if (x( S 3/2 then appoo-apeo local minimum.
Computing gradients and Hessians. It is clear that computing the Hessian matrix can be much more expensive than computing the gradient vector. We denote the corresponding arithmetic complexities of computing one Hessian and gradient of fi(x), 1 i n by HessCost and GradCost. We will make and follow the convention that HessCost = d GradCost, where d is the dimension the problem. For example, this is known to hold for neural networks using the backpropagation algorithm (Kelley 1960). However, the Hessian has a sparse structure, the cost of computing the Hessian can be cheaper Nocedal & Wright (2006).
Then, we can replace with the effective dimension deff GrudCost
HessCost. I d.
3 Second- Optimization with Helper Functions
In this section, extend the helper framework previously introduced in (Chayti & Karimireddy 2022 for first-order optimization methods to second-order optimization.
General principle. The general idea is the following: imagine that, besides the objective function f, we have access to a helper function that we think is similar in some sense (that we will define later) to f and thus it should help to minimize it.
Note that many optimization algorithms can be framed the following sequential way. For a current state x, compute the next state a
4

---

Published in Transactions on Machine Learning Research (09/2024)
xt
E
arg min fa())) + Mr }.
VER
where (-) is an approximation of around current point æ, and (y) is a regularizer that encodes how accurate the approximation is, and M > 0 is a regularization parameter. this work, we are interested cubically regularized second-order models of the form (2) and we use rw b =||
Now, let us look al how we can use a helper h to construct the approximation f. We notice that we can write
f(y)
h(y)
f(y) -hy)
cheap
expensive
We discuss the actual practical choices of the helper function below. We assume now that we can afford the socond-order approximation for the cheap part h around the current point z. However, approximating the part f-h h can be expensive (as for example when the number of elements in finite sum [1) huge), or even impossible (due to lack of data). Thus, would prefer to approximate the expensive part less frequently. For this reason, let us introduce it to approximate f f- h. Another question we still need to ask is what order should we use to approzimate f - h? We will see that order (i.e., a constant) leads us to the basic stochastic methods, while for orders and 2, our methods are akin to classical variance reduction techniques.
extra snapshot point & that is updated less often than Then, use
Combining the two approximations for and we get the following model of our objective f:
(v) C(x, x) + (g(h, x, x), x) + (H(h,, x, () x). xx),
33)
where C(x, æ)) a constant, G(h, æz .) is a linear term, and H(h, 2. .) matrix. Note that æ, then the best second-order model of the form (3) is the Taylor polynomial of degree two for f around æ, and that would yield the exact Newton-type method. However, when the points and æ are different, we obtain much more freedom in constructing
models.
For using this model in our cubically regularized method we only need to define the gradient G(h, æ, a) and the Hessian estimates H = H(h, x, 2),, and we can also treat them differently (using two different helpers, h and f2, correspondingly). Thus, we come to the following general second-order (meta) (egeta)algoithm.. We perform S rounds, the length each round m 1, which our key parameter:
Algorithm Cubic Newton with helper functions
Require: Zo E Rd S, m 2 1, M > 0.
1: for 0 0. Sm - do
2:
if modd m = 0 then
3: Update ã, (using previous states vişt)
elsc
== #:
6:
Form helper functions h1,
7:
Compute the gradient = Ghi, 2t, i.),, and the Hessian H. H(h2, (0, Z..) Compute the cubic step x1+1 E arg min Se S.M... x,,
8:
return Fout using the history (m:)osissm
In Algorithm
1 we update the snapshot स regularly every m iterations. The two possible options
= mod m
(use the last iterate)
(4)
or
3 arg miin,g((-mmm....)/(.(
(use the best iterate).
(5)
Clearly, option (5] is available only case we can efficiently estimate the function values. However, we will see that it serves us with better global convergence guarantces for the gradient-domintedd functions. It remains to specify how we choose the helpers hy and hgg We need to assume that they are somehow similar to f. Let present several efficient choices that lead to implementable second-order schemes.
5

---

Published in Transactions on Machine Learning Research (09/2024)
3.1 Basic Stochastic Methods
If the objective function J' is very "expensive" (for example of the form 1 with - x)), one option is to ignore the part f - h i.e. to approximate it by zeroth-order approximation: f(y) - h(y) = f()) h(@). Since it a constant, we do not need to update æ. In this case, we have:
g(h x, x) = (h) H(gh, a) = v2h2(x).
(6)
To treat this choice of the helpers, we assume the following similarity assumptions, which motivated by the form of the errors for one cubic step (see Theorem C.I]:
Assumption 3.1 (Bounded similarity). For 9, H defined in 6 holds, Vz, Rd:
there erists òi, 82 2 0 such that it
Ex, [I][(1 x, x) vf(x) [3/2]
<
01
3/2
k/ |1 x. Φ) (>)()))
83.
Remark 3.2. Introducing the random variable := G(h .) can be rewritten as a bound for its 3/2-moment:
V fx),, the first condition in the assumption
En, 3/2
3/2
(7)
Note that the standard assumption in the literature on first-order methods (e.g. Lan 2020 is the boundedness of the second moment (or the bounded variance):
E. [|]l
S 0².
(8)
which is stronger than 7 Indeed, using Jensen's incquality for the expectation as applied to a concave function g(l) = /3/1 2 0, we obtain that
E, [|/] = Es, [2,(((111))/444) < (E,, [lmm]]]])] 3/4
0//2
Thus, 7
holds with 6, == a. At the same time, for the Hessian approximation, we assume a stronger guarantee of the boundedness of the thind moment. Note that if both f and h2 have B-Lipschitz continuous gradient, we immediately obtain the deterministie upper bound: 82 < 28.
Under Assumption 3.1 we prove the following theorem:
Theorem 3.3. Under Assumptions 2.1 and 3.1 and M 2 L, for output of Algorithm 1 Dout chosen
uniformly at rwndom from (ai)osigsms we have:
Eluur(
MMF Sm
82 M3/2 + +50/
3/2)
We see that according to this result, we can get (xooe)) S 3/22 only for ε > 8). In other words, we can converge only to certain neighborhood around a stationary point, determined by the error ε1 of the stochastic gradients.
However, we will show next, this seemingly pessimistic dependence leads to the same rate of classical subsampled Cubic Newton methods discovered in Kohler & Lucchi (0117 Xu et al. (0177 2016
At this point, let us discuss the specific case of stochastic optimization, where f has the form of 1 with n potentially being very large. In this case, it is customary to sample batches at random and assumee the noise to be bounded in expectation. Precisely speaking, if we assume the standard assumption that for one index sampled uniformly at random, we have EE, [V((x) (2) < oz and E, V² 22 (x oi Va, then it possible to show that for
h by EieB, fr and h = by EiEB, fi.
where batches B, BA C [n]] sampled uniformly at random and of sizes by and by respectively, Assumption 3.1 is satisfied with (see, e.g., Tropp el al. (2015)): 8n au and 82 0( Note that according to this Vb,
result, can the same random subsets of indices By Br for all iterations of the method.
6

---

Published in Transactions on Machine Learning Research (09/2024)
Corollary 3.4. In Algorithm 1 let choose M L and = 1, with basic helpers 9 Then, according to Theorem 3.3 for any >> 0, to reach on (e, a.pppprooiee second-order local minimum, we need al most
S = LLFo SVVLoo 2312
ilerations with bg = (-²) and bn
oi_ 6 Therefore, the lotal complerity of the method in lerms of
the gradient oracle calls
o² o ह
+
- ( GradCost.
(10)
Recall that detf S Bound 10 improves upon the complexity ((+)) x GradCost of the first-order SGD for non-convex optimization Ghadimi & Lan (2013), unless deff > 2372 (high cost of computing the Hessians).
3.2 Let the Objective Guide Us
If the objective f is such that we can afford to access its gradients and Hessians from time to time (functions of the form [T] with n < oe being "reasonable"), then we can do better than the previous chapter. In this case, we can use a better approximation of the term f - h(y). From a theoretical point of view, we can treat the case when f is only differentiable once, and thus, we can only use first-order approximation of f- h; in this case, will only be using the Hessian of the helper h but only gradients of f. However, in our case, if we assume we have access to gradients, then we can also have access to the Hessians of f as well (from time to time); for this reason, we consider a second-order approximation of the term - h. If we follow the procedure that we described above, we find:
2(,,,,,)) : Vhi( Vh, V (V² (i)1 =),, H(h2, v. .)- = (22((x) - + (()).
(11)
(12)
We see that there is an explicit dependence on the snapshot R. and thus, we need to address the question of how we should update this snapshot point in Algorithm [ In general, we can update it with a certain probability ~ m or we can use more advanced combinations of past iterates (e.g., a moving average). However, for simplicity, we study option 4 (i.e., using the last iterate for updating the snapshot æ); thus, it is updated only once every m itcrations.
We also need to address the question of measuring the similarity in this case. Since employ a second-order approximation of f f h, it seems natural to compare the function f and its helpers hı and h2 by using the difference between their third derivatives or, equivalently, the Hcssian Lipschitz constant of their difference. Precisely, we make the following similarity assumption:
Assumption 3.5 (Lipschitz similarity). For G, H. defined in 11 and that it holds, Væ, x E Rd;
12
there ezists 61 82 2 such
En, [1) x. .) - (1)))
8 a
|
E,, ||| H((2, x, .) V2 f(x)
<
x x
In particular, if f h and f h2 have Lipschitz Hessians (with constants and 6g respectively) then h and ha satisfy Assumption 3.5
Under this assumption, we show that the errors resulting from the use of the snapshot can be successfully balanced by choosing M satisfying:
4 ( 3/2
73 52)3 S
(13)
2m
And we have the following theorem:

---

Published in Transactions on Machine Learning Research (09/2024)
Theorem 3.6. Let f, h2 verify Assumptions 2.1 3.5, and let the regularization porameter M is chosen such that M 2 I. and (13) is salisfied. Then, for the output Dout of Algorithm chosen uniformly al random from (#:)0gisSm=T)) we have:
(x
O
VM
Si
In particular, can choose M = ma 320mmmmm 166gm) which gives
E El (Fout)) 0
/LFo 5m
Vo Sym
vo.Fo
(14)
Based on the choices of the helpers h1 and h2, we can have many algorithms. implementations the following sections.
We discuss particular
We start by presenting the voriance reduction combined with the Lasy Hessian updates, which rely on sampling batches randomly. Our new method will significantly improve complexity bound (10) obtained for the basic helpers, and achieve the best overall performance among all known variants of stochastic second-order methods (see Table D
Then we discuss other applications: the core sets, which try to intelligently find a weighted representative batch describing the whole dataset; semi-superoised learning, engineering the helpers using unlabeled data; and, more generally, auziliaryy learning, which tries to leverage auxiliary tasks in training given main task. We show that. the auxiliary tasks can naturally be treated as helpers.
3.3 Variance Reduction and Lazy Hessians
First, note that choosing h1 h2 f gives the classical Cubic Newton method (Nesterov & Polyak| 2006), whereas choosing hn and ha gives the Lazy Cubic Newton (Doikov et al.] 2022). In both cases, recuperate the known rates of convergence. However, these choices requires to compute the full gradients, that can be expensive for solving problem
[1 with large number n of components.
The following lemma demonstrates that we can create helper functions h with lower similarity to the main function f by employing sampling and averaging.
Lemma 3.7. Let f - Si such that all fa buice differentiable and have L-Lipschill Hessians. Let B c (1, n) be of size b and sampled with replacement uniformly at rondom, and define hB t Eien fi, then by satisfies Assumption 3.5 with 8 = Jt and ó2 = O Slog(diL
vb
Choice of the parameter m in Algorithm 1
Minimizing the total arithmetic cost, we will set
argmin Grad(m, + d Hess(m,
(15)
where Grad(m,s) and Hess(m, s) denote the number of gradients and Hessians required to find an stationary point. Now, we are ready to discuss several particular cases that are direct consequences from Theorem 3.6 and Lemma 3.7
General variance reduction. If we sample batches B, and B,, of sizes by and by, consecutively at random and choose, as Scction 3.1
h1
1
EveB, fs and
h2 by EieB, f..
(16)
11 12 we obtain the Variance Reduced Cubic Newton algorithm (Zhou et al. 2019 Wang et al. 2019). According to Lemma 3.7 this choice corresponds to 8, L/ bb and 8n OLL bb). For by m² n, by m² and M L, we obtain the non-convex convergence rate of the order: E[μz (2oot) o (T.FF.. This the same rate of the full Cubic Newton. However, our cost per iteration is much smaller due to using stochastic oracles. Minimizing the total
and use these helpers along with the estimates
(m)
8

---

Published in Transactions on Machine Learning Research (09/2024)
arithmetic cost, we choose according to 156, as to minimize the following expression: (
min { dn+tdlm" +mm) Anm)] }. Then we reach an (s, Lapproxiimte second-order local minimum in at most
O ( 3/2
x GradCost
(17)
gradient oracle calls.
Variance reduction with Lazy Hessians. We can also use lazy updates for Hessians combined with variance-reduced gradients; this corresponds to choosing
h1 = by Eies, S. and h2 = O,
(18)
which implics (according to Lemma 3.7 that L/ bbg and 82 In this case, we need by m²
obtain convergence rate: Elpz O VLFu
Sy/m ), which matches the convergence rate of the full version of the Lazy Cubic Newton method (Doikov et al. (2022) ), while in our method we use stochastic gradients. In
this case, the choice of m minimizes the following expression: glasy (n, d) == min ad+ (mm"mm) }. Then we
vm
m
guarantee to reach an (e, (..m)-appooriiimal second-order local minimum most
O(
(n.d) g3/2
x GradCost
(19)
gradient oracle calls.
To be lazy or not to be? We can show that gLazy(n, d) (nd)3//An/// and g (m, d)
In particular, for d 2 2/3 we have gleey(n, d) S g (n, d) and thus for 2 2/3 it beller to use Lazy Hessians along with the variance reduction, obtaining complexity We also note that for the Lazy approach, we can keep a factorization the Hessian (this factorization induces most of the cost. of solving the cubic subproblem); thus, as if we only need to solve the subproblem once every m itcrations, so the Lazy approach has big advantage compared the general approach, and the advantage becomes even bigger for the case of large dimensions.
199 than becomes strictly better than [7
Note that according to our theory, could use the same random batches B,, Br [n] generated once for all iterations. However, using the resampled batches can lead to more stable convergence.
3.4 Other Applications
The result in [1]] is general enough to include many other applications that are limited only by our imagination; there are, to cite a few such applications:
Core sets. (Bachem et al. 2017) The idea of core sets is simple: can we summarize a potentially large data set using only a lew (potentially weighted) important examples? Many reasons, such as redundancy, make the answer yes. Devising approaches to find such core sets is outside of the scope of this work. Formally, for the objective function f(x) of the finite-sum structure (1), the core set helper can be given by the following form:
h(x) = 1 Σ (x)
(20)
where each f,,15 S is a core representative (or cluster) for a given dataset. Example 3.8. Let core representatives fi....,fm be fixed, and assume that each function from our target problem be given by
f((x) = (x) tz(()), isisn,
where ji E (l......m m the inder of the corresponding core representative and eạ(x) is some noise. Then,
function of from (20 with weights wy = Ei = jl will be a helper function according to our framework.
Assuming that each E, has Lipschitz Hessian with constant Le will imply Assumption 3.0 for h h h with 8n 82 Tec.

---

Published in Transactions on Machine Learning Research (09/2024)
Reusing batches during training. In general, can see from [1] that if we have batches Bg. Bb such that they are d1 and ó2 similar to f respectively, then we can keep reusing the same batch Bg for at least V of times, and B₁ for b all the while guaranteeing an improved rate. So then, if we can design such small batches with small 6n and 62, we can keep reusing them and enjoy the improved rate without needing large
batches.
Auxiliary learning. (Baieeng al. Aviv et al. Xingyu et al.) study how a given task f can be trained in the presence of auxiliary (related) lasks; our approach
indeed be used for auxiliary learning by treating the auxiliaries as helpers; if we compare [14 to the rate that we obtained without the use of the helpers:
O (V ) we see that we have a better rate using the helpers/auxiliary tasks when 1 + y
vmL
+ VI
vo S
Semi-supervised learning. YYang et al. 2021 Semi-supervised learning is a machine learning approach that uses both labeled and unlabeled data during training. In general, we can use the unlabeled data to construct the helpers; we can start, for example, by using random labels for the helpers and improving the labels with training. There are at least two special cases where our theory implies improvement by only assigning random labels the unlabeled data. In fact, for both regularized least. squares and logistic regression, we notice that the Hessian is independent of the labels (only depends on inputs).
Indeed, let us consider the classical logistic regression model (e.g., Murphy (2012) for the set of labeled data b;),) where b, = +1. Then fitting the model can be formulated as the following optimization problem:
min ((x)) = 1 Σ (--viaa mi)
(21)
=ERd
where ((t) == In(1+e'), Note that (t() = a()) T and (t) o(t) (ott)-o(( (-t)). Hence, the second derivative of the logistic loss is an even function. Computing the Hessian of f directly, we obtain
vaf(x) 1 (-bb-
Σ x))xa)aaa
Thus, we see that the last expression does not depend on the input labels b,. Therefore, if the unlabeled data comes from the same distribution as the labeled data, then we can use it construct helpers which, at least theoretically, have 51 52 O. Because the Hessian is independent of the labels, the unlabeled data with random labels. Theorem 3.6 will imply in this case (xure() = 0 ( where S is the number of times we use labeled data and S(m - 1) is the number of unlabeled data.
technically endow
Example 3.9. Consider the following helper,
h(x) = 1 m
(22)
where labels ūj = +1 are randomly generated, while data {b,} has the same distribution as the torget
data {a.} from 21. Then, taking into account that the Hessian of each f((x) = E0,y,,,,,,300 x) is Lipschitz with constant I max; |la.13//(6/// 3),, we obtain that using helper 22) as hn = lb = h provides us with the
guarantees required by Assumption 3.5 with 8, = L/ ym and 82 = (L/ vm) (see also Lemma 3. 7)
See Figure 2 for the empirical validation of this approach.
4 Gradient Dominated Functions
In this section, we consider the class of gradient-dominated functions defined below.
Assumption 4.1. (r, -gradient dominated. A function f is called gradient dominated on sel if it holds, for some 2 1 and 7 > 0:
f(x:) {
Va E Rd..
(23)
10

---

Published in Transactions on Machine Learning Research (09/2024)
Examples of functions satisfying this assumption are convex functions (a 1) and strongly convex functions (a = 2); see Appendix F.1 For such functions, we can guarantee convergence (in expectation) to global minimum, ie., we can find a point æ such that f())-f S.
The gradient dominance property is interesting because many non-convex functions have been shown to satisfy it (uanzhi & Yang 2017 Hardt Ma 2016; Masiha et al. 2022). Furthermore, besides convergence to global minimum, we get improved rates of convergence.
We note that for > 3/2 (and only for this case), we also need to assume the following (stronger) inequality:
Ef(x:)) -
-E [V((((()))
(24)
where the expectation is taken with respect to the iterates (xt) of our algorithms; this is stronger assumption than 23). To avoid using (24 we can assume that the iterates belong to some compact set Q C Rd and
that the gradient norm is uniformly bounded: Va E Q // (xx)] < G. Then, a (r,a)-gradient dominated on set Q function is also a (rGa-3/2 3 dominated on this set for any a > 3/2.
In the following theorem, we extend the results of Theorem 3.3 to gradient-domnnated functions, for the basic stochastic helpers:
Theorem 4.2. Under Assumptions 2.1 3.1
for M 2 L and T == Sm, we have
Poor < a < 3/2:
[[((T)) 0(avVMr2/00 (3-2a)1
82 + T89
+ M7
(25)
For a = 3322
([f(wT)|-S- = OFFoxxy (+VM))
+
62 M
+ +T01
3/2)
(26)
Foor 3/2 < <a 22 let ho O(Fo/ (V.Po//MMTTB M sit
20
Then for T T240 La 000 2x log(ho)) we have:
Bif(zT)--F = o((VMr
20
(2)) T0
+
62u
+ T89
(27)
Ma
Theorem 4.2 shows (up to the noise level) the global sublinear rate for 1 1 a < 3/2, the global linear rate for a = 3/2 (which can also be seen by taking the limit a + 3/2 in (25 and the superlinear rate for a > 3/2, after the initial phase of to iterations.
We would like to point that instead of Assumption 3.1 we only need to assume E,, Vz) vf(=))] 8f and ()))(())))) {=)(2)] s 62 which might be weaker depending the value of We also prove the following theorem, which extends the results in Theorem 3.6 to the gradient-dominated functions, for the advanced helpers. In this case, we set the snapshot line 3 in Algorithm I as in (5) i.e., the snapshot corresponds to the state with the smallest value of f during the last m iterations.
Theorem 4.3. Under Assumplions 2.1 3.5 4.
for M max m4 1182m), we have:
For 1 1 a < 3/2:
o((
Eff(zsm)]
(3-2a)Sm
For = =3/2:
[[f(mmm)] - O(Fo
-s)
/Mr
2a ). Then for S2 80 Oh 2a-3
For 3/2 < a S 2, let ho O
log(ho)) we have:
M m
r 2a
[[s(ssm)) - (1 (( ( 1ー
11

---

Published in Transactions on Machine Learning Research (09/2024)
Again, the same behavior is observed for Theorem 4.2 but this time without noise (variance reduction is working). To the best of our knowledge, this is the first time such an analysis has been made. As a direct consequence of our results, we obtain new global complexities for the variance-reduced and lazy variance-roduced Cubic Newton methods on the classes of gradient- dondient-dominted functions. Note that in the simplest case of the deterministic Lany Cubie Newton (hą = f and h 0), we enhance the complexity results from (Doikov et al. 2022 to the classes of convex and strongly convex functions, establishing faster rates of convergence.
Let compare the statements of Theorems 4.2 and 1.3 for convex functions (a 1). Theorem 4.2 d guarantees convergence to e-global minimum in at most O 25/2 + 23/2 xx GradCost gradient computations, while Theorem 4.3 only needs O (( )x GradCost, where g(n, d) is either gloey(n, (n.d) d) = (nd)6/o A nn/d or gVR((, d) = (nd) A (n2/3d + n). See Appendix F.3 for more details.
5
Experiments
5.1 To Be Lazy Not to Be
To verify our findings from Subsection 3.3 consider a logistic regression problem (21 with 62-regularization on the "a9a" data set Chang & Lin 2011 We consider the variance-reduced cubic Newton method from (hoou et al. 2019) (referred to as "full VR"), its lazy version where we do not update the snapshot Hessian ("Lazy VR ) the stochastic Cubic Newton method ("SCN"), the Cubic Newton algorithm ("CN"), Gradient Descent with line search ("GD") and Stochastic Gradient Descent ("SGD"). We report the results terms of time and gradient arithmetic computations needed to arrive at a given level of convergence.
Figure I shows that the lazy version saves both time and arithmetic computations without sacrificing the convergence precision. In these graphs, Gradcost is computed using the convention that computing one hessian is d times as expensive as computing one gradient.
Logistic regression: 123, 32561, L2-regularization
10-1
10-1
10
Very
talV
10-
LN
SCN
10
SGD
comput.. (Gradcost)
Time,
Figure Comparison of the convergence of different algorithms. We see that "Lazy VR" has the same convergence speed as its full version "full VR" and the cubic Newton method "ON", while it needs less time and fewer arithmetic computations.
5.2 Auxiliary Learning
Our goal is to show that the helper framework is very general and that it goes beyond the variance reduction and lazy Hessian computations. For the previously considered problem of training the logistic regression (using the same "a9a" data set), we suppose that we also have access unlabeled data (in this sense, this becomes semi-supervised lcarning). Specifically, we have labeled dataset D; {(a; b,)) and an unlabeled N. data set D., J=+++ we suppose that both data sets are sampled from the same distribution P(a. Our goal is to minimize
f(x) = (((a,))>Paa.) [og(1 + exp(- ba Ta))].
A simple computation (see Section 3.4 shows that the Hessian of f only depends on Pa: and, for this reason, unlabeled data to construct good approximation of the true Hessian (if we can sample from P..
12

---

Published in Transactions on Machine Learning Research (09/2024)
Logistic regrossion
10
m: 530
10-+
10-1
10-13
100
200
300
Labelee data access, (Calls of
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 the plot, the percentage of labeled data used during training. We can clearly see that using approach, we benefit lot from the helper function h.
construct the exact Hessian and thus have a helper with o1 = 82 = 0). Let
h()=)) ba
bw Rand + exp( ba: a))];
where ] is any distribution on labels. In experiments, use uniform distribution. Figure 2 shows that, indeed, we can benefit a lot from using this helper function. We note that this observed benefit comes at the cost of performing more steps using gradients and Hessians of the helper function h.
5.3 Non-convex experiments
We go back to comparing the algorithms in 5.1 We consider, now, non-convex problems. First consider the logistic regression with a non-convex regularizer Reg(x) = E i+s? minimize
[Kohler Lucchi 2017). Thus, we
f(x) = 1 Σ log(1 + eepp-xbba a,)) + AReg(æ)
Figure 3 shows the results in this case. Again, we see that "lazy VR" reduces both time and gradient. equivalent computations without sacrificing the convergence speed.
Logistic regression: a9a, 32561,
10a
10
Lazy SJI
10-
SON IN
10
Arith. comput. (Gradcost)
Figure Comparison of convergence different algorithms. We see that using our approach, we benefit. a from the helper function h.
Second, we consider a simple diagonal neural network with L. loss with data generated from a normal distribution. specifically, we want minimize
((x:=(u, = n
Σ
a u o
6 1
1=1
where is the element-wise vector product.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Diagonal Network: n=200000
10
107
10a
10"h
Lacy MIVVA
15
IN
SON
10'*
10
10-1
Arith. comput., (Gradcost)
Diagonal Network: d=400, n=10000
10
109
4
Lacy VII
fall VR
10
Adam
10
10"
10
Arith. comput. (Gradcost)
Time, 5
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.
L2 loss, Diagonal Neural Network: d=100, n=10000
10
102
10
10
10-2
CN
10-7
SCN
S60
Adam
10"
10a
comput., (Gradcost)
Figure Comparison of the convergence the different algorithms. Except for gradient descent ("GD"), which performs very well in this case, again, the same conclusions in Figure with respect to "Lazy VR" can be said.
Figure shows that compared other second-order methods, *Lazy VR" has considerable time and computation savings. It also performs closely to gradient descent with line search, which performs very well in this case. Figure 5 shows the same experiment for larger dimensions, most importantly see that the gap between our 'Lazy VR" and the 'full VR" method grows with d, this is in accord with our theory which predicts an increased advantage of 'lazy VR" as the dimension grows.
5.4 Hessian Cost vs Gradient Cost
We consider again a diagonal neural network and estimate the time costs needed for computing its gradient, Hessian, decomposing the Hessian, and solving the cubic subproblem. Figure 0 shows that the average cost of computing the Hessian is significantly higher than the cost computing one gradient, and the quotient grows approximately lincarly with d (the dimension of the problem). Figure a
also shows that the cost of decomposing the Hessian dominates that of solving the cubic subproblem which explains how our lazy VR method saves time compared to other methods.
5.5 Additional experiments
We consider, in this section, other datasets from the LibSVM library Chang
Lin 2011
14

---

Published in Transactions on Machine Learning Research (09/2024)
Grodient
Pesson/ Grasiene 67332
304
Gread
2016
Hosatan Resemooution Sutoroblem
Demersion
Figure (left) times needed compute gradient, the Hessian, decompose the Hessian and solve the cubic subproblem for diagonal neural network with 10000 and differrnt values of the dimension d. (right) average time computing the Hessian divided by the average time needed to compute the gradient. we notice that the Hessian computation cost is almost proportional to dx the gradient cost. We also see that the time needed to decompose the Hessian dominates the time needed to solve the cubic subproblem.
Mushrooms, con-convex
wés, Non-convex
Auxiliary Learning, w8a
10"
10a vt
10-
10
Aux-CN
ON
10
<
[
10
10"4
10
400 Labeled data access
200
Figure 7: Experiments on Mushrooms (n 8124, 112), Covtype (n 581012, 51), w8a (n 19749, d =000))
datasets.
Figure clearly shows how our method outperforms the baselines by saving time (or calls to the main function in the case of auxiliary learning) without sacrificing performance.
6 Limitations and possible extensions
Estimating similarity between the helpers and the main function. While we show in this work that we can have an improvement over training alone, this supposes that we know the similarity constants 81, 5z; hence, it will be interesting to have approaches that can adapt to such constants.
Engincering helper functions. Building helper task with small similaritics also an interesting idea. Besides the examples in supervised learning and core-sets that we provide, is not evident how to do in generalized way.
Using the helper to regularize the cubic subproblem. We note that while we proposed to approximate the "cheap" part as well Section 3 one other theoretically viable approach to keep intact and approximately solve a "proximal type" problem involving h; this will lead to replacing L by 6, but the subproblem even more difficult to solve. However, our theory suggests that we don't need to solve this subproblem exactly; we only need m > J: we do not treat this case here.
7 Conclusion
In this work, we proposed general theory for using stochastic and auxiliary information in the context of the Cubically regularized Newton method, Our theory encapsulates the classical stochastic methods, as well Variance Reduction and the methods with the Lazy Hessian updates.
15

---

Published in Transactions on Machine Learning Research (09/2024)
Our new methods posses the best-known global complexity bounds for stochastic second-order optimization in the non-convex case, and significantly benefit in terms of total arithmetic computations, by reducing the number of computed Hessians and the required number of matrix factorizations.
For auxiliary learning, we demonstrate a provable benefit of using auxiliary data compared to training alone. Besides investigating general non-convex functions for which we proved global convergence rates to a second-order stationary point, we also studied the classes of gradient-dominated functions with improved rates of convergence to the global minima.
Acknowledgements
This work was supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number 22.00133.
References
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, Alexander Gasnikov, and Martin Takáč. Inexact tensor methods and their application to stochastic convex optimization, arXiv preprint vrXiv:2012.16366 2020.
Navon Aviv, Achituve Idan, Maron Haggai, Chochik Gal, and Fctay Ethan. Auxiliary learning by implicit differentiation. ICLR 2021. URL
026.3. .dff.
Olivier Bachem, Mario Lucic, and Krause Andreas. Practical coreset constructions for machine learning. arXiv:1703 100:10600646 Statt.M.hhttps.. //ar/va.../////////////a//aat org/ htgggb/////////////g////////e/// 1703. 06476 2017.
Shi Baifeng, Hoffman Judy, Saenko Kate, Darrell Trevor, and Xu Huijuan. Auxiliary task reweighting for minimum-data learning. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. URL httt::://axxiv.orr/ppf//////// /2010 /tt///2111..2.....2222 08244. pdf
Yair Carmon and John C Duchi. First-order methods for nonconvex quadratic minimization. SIAM Review, 62(2):395 436, 2020.
Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of unconstrained optimization methods based probabilistic models. Matheralical Programming, 169:337-377 2018.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for uncon- strained optimization. Part I: motivation, convergence and numerical results. Mathematical Progromming, 127(2):245 295, 2011a.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evallatioon complexity. Mathematical programming, 130(2):295-33) 319, 2011b.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1 2011.
El Mahdi Chayti and Sai Praneeth Karimireddy. Optimization with access to auxiliary information.
arXiv:2206.003: 00395 LCs. 2022.
Andrew R Conn, Nicholas IM Gould, and Philippe Toint. Trust region methods. STAM, 2000.
Nikita Doikov. Minimizing quasi-self-concordant functions by gradient regularization of Newton method. arXiv preprint arXi:22008.4774 14742, 2023.
Nikita Doikov and Yurii Nesterov. Minimizing uniformly convex functions by cubic regularization of newton method. Journal of Oplimization Theory and Applications 189:317-339 2021.
16

---

Published in Transactions on Machine Learning Research (09/2024)
Nikita Doikov and Yurii Nesterov. Gradient regularization of Newton method with Bregman distances. Mathemalical Programming, pp. 1-25, 2023.
Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy hessians.
arXi::2212.0078 [math. OC/, 2022.
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized Newton method.
STAM Journal on Optimization, 34(1):27-56, 2024.
Pavel Dvurechensky and Yurii Nesterov. Global performance guarantees of second-order methods for unconstrained convex minimization. Technical report, CORE Discussion Paper, 2018.
llyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimization inequality. Aduances in Neural Information Processing Systems, 35:
under global
2022.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Oplimization, 23(4):2341-23606 2013.
Saced Ghadimi, Han Liu, and Tong Zhang. Second-order methods with cubic regularization under inexact information. arXiv preprint arXiv:1710.05782 2017.
Geovani N Grapiglia and Yurii Nesterov. Regularized Newton methods for minimizing functions with Hölder continuous Hessians. STAM Journal on Optimization, 27(1):478-35) 47)-566,, 2017.
Slavomír Hanzely. Sketch-and-prost meets Newton method: Global ((1kk22) convergence with low-rank updates. XrXiv preprint arXi::2305.1130 13082, 2023.
Slavomír Hanzely, Dmiiry Kamzolov, Dmitry Pasechnyuk, Alexander Gasnikov, Peter Richtárik, and Martin Takáč. A damped Newton method achieves global (11/k²) and local quadratic convergence rate. arXiv preprint arXie:2211.0011 2022.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv:6611.04333 2016.
C. J. Hillar and L.-H. Lim. Most tensor problems are np-hard. Journal of the ACM (JACM) 60 45., 2013.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp. 315-323, 2013.
Sai Pranceth Karimireddy, Scbastian U Stich, and Martin Jaggi. Global linear convergence of Newton's method without strong-convexitt Lipschitz gradients. arXie preprint arXiv:1806. 004 2018.
Henry Kelley. Gradient thcory of optimal flight paths. Ars Journal, 30(10):947-554, 1960.
J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function. Ann. Math. Statist. Volume 23, Number 3, 462-466, 1952.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. In International Conference on Machine Learning, pp. 1895-1904. PMLR, 2017.
Guanghui Lan. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochas- tic second-order methods improve best-known sample complexity of sgd for dradient-dominated functions. In NeurIPS 2022 Advances in Neural Information Processing Systems, volume 35, pp. 10862-10875, 2022. URL http::///rooedddnggg..errrrp.ppp http://////.rrooo.aaaaiooa.aaaaa
Konstantin Mishchenko. Regularized Newton method with global 0(1kk2 convergence. SIAM Journal on Oplimization, (3(3):144001468) 2023.
17

---

Published in Transactions on Machine Learning Research (09/2024)
Kevin P Murphy. Machine learning: probabilistic perspective. MIT press, 2012.
Yurii Nesterov. Lectures on conver optimization, volume 137. Springer, 2018.
Yurii Nesterov. Incxact basic tensor methods for some classes of convex optimization problems. Optimization Melhods and Software, 37(3):878 906, 2022.
Yurii Nesterov and Boris Polyak. Cubic regularization of Newton's method and its global performance. Mathematical Programméng, 108(1):177-205 2006.
Tripuraneni Nilesh, Stern Mitchell, Jin Chi, Regier Jeffrey, and Jordan Michael I. Stochastic cubic regular- ization for fast nonconvex optimization. Part of Advances in Neural Information Processing Systems 31, 2018.
Jorge Nocedal and Stephen Wright. Numerical oplimization. Springer Science & Business Media, 2006.
Boris T Polyak. Newton's method and its use in optimization. European Journal of Operational Research, 13):111 1096, 2007.
Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 3(4):643 653,, 1963.
Herbert Robbins and Sutton Monro. A stochastic approximation method the annals of mathematical statistics. Vol. 22, No. 8. pp. 400-407, 1951.
VE Shamanskii. A modification of Newton's method. Ukrainian Mathematioal Journal, 19(1):118 122, 1967.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trendso in Machine Learning, 8(1-2):1-230, 2015.
Li uanzhi and Yuan Yang. Convergence analysis of two-layer neural networks with relu activation. Advances in neural information processing systems, 30, 2017.
Zhe Wang, Zhou Yi, Liang Yingbin, and Lan Guanghui. Stochastic variance-reduced cubic regularization for nonconvex optimization. ATSTATS, 2019.
Blake Woodworth, Konstantin Mishchenko, and Francis Bach. Two losses are better than one: Faster optimization using cheaper proxy. arXiv preprint arXiv:2302.055/2, 2023.
Lin Xingyu, Singh Baweja Harjatin, Kantor George, and Held David. Adaptive auxiliary task weighting for reinforcement learning. 33rd Conference on Neural Information Processing Systems (NewrIPS 2019), Vancouver, Canada. URL
P. Xu, J. Yang. F. Koorsa-Kiorasnni, and M. W. Mahoney. Sub-sampled newton methods with non-uniform sampling. 2016.
P. Xu, F. Roosta-RRit Roosta-KKorasani Khorasani, and M. W. Mahoney. Newton-type methods for non-convex optimization under inexact Hessian information. ar Xin preprint arXiv: 708. 700.07164 , 2017.
Xiangli Yang, Zixing Song, Irwin King, and Zenglin Xu. A survey on deep semi-supervised learning. Technical report, 2021.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularization methods. Journal of Machine Learning Research 20 1-47, 2019.
18

---

Published in Transactions on Machine Learning Research (09/2024)
A
Reproducibility
Our code is available with all the details necessary for reproducing results in https://githubb.com elmahdichaye http::///w.....ocoooo//////////p
B
Additional Experiments
Logistic regression Mnist
10
15a
10
Lasy SIVVA
10
10
IN
SON
10-3
10
10'1
10
Arith. comput. (Gradcost)
Figure Logistic regression on 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.
Logistic regression an d-3072)
10a
10-3
10-3
Lazy
NIVVRR
10-#
CN
10-9
SCN
10:21
19'
18
500
1500 Time,
3000
2000
Arith. comput. (Gradrost)
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 Lazy VR has big advantage in terms of time compared to all other methods.
A9A, 2-layer MLP
10
10
10-1
2 10
SD VIl
10
19.5
SIV
10:5
10
10"1
16f
101 (Gradcost)
1044
20
40
50
80
100
Arith. comput., Arith.comptt.
Time,
Figure 10: A two-layer NN trained on the A9A dataset. We notice that GD (with line search) outperforms all the algorithms gets stuck at an error of 8 Lazy VR the second fastest and even ends up beating GD smaller error, suggesting that it escaped the local minimum GD was stuck at. Again Lazy VR saves more time compared to full VR.
19

---

Published in Transactions on Machine Learning Research (09/2024)
C
Theoretical Preliminaries
We consider the general problem
min f(z) mcRd
Where f is twice diffcrentiable with L-Lipschitz Hessian i.c.:
f(x) V2 fw))l - - y/l,
Va, y 12
(28)
As direct consequence of 28 (see Nesterov & Polyak 2006
Nesterov 2018 we have for all æ, y E R
I.
[Vf(y) Vf(x)) v2 f(x) x)ll S
2 x y11?
(29)
(f(y) - f(x) (Vf(z) / [v2 - =), y x) 1 y =1|"
(30)
For and at defined as in Equation 22 i.e.
x arg SM.g. (U, = (g. - x) + (H - z),
x) + o/ 1 - 1 }
(31)
The optimality condition of 31 ensures that
g x) + HHC + x) x)) + M 3 0,
(32)
where we denoted r || z||. It also known that the solution verifies:
M H P #+212
r
(33)
We start by proving the following Theorem
Theorem C.I. For any a E Rdd, let axt be defined by Then, for M 2 T, we have:
f(x) f(x*)
1008 MM M (x++ + MI m 1s
[((() 9/1
73
f(m)) H
VM
M
Using 30 with y + and x and for M > L we have:
30
f(x
+ (Vf()(V(())..) x- x)) + (z)) -x), -x) 4
32
f(x)
-M-1 (Vf(x) 9. x))
24
( f()) Hx + - x),xx x))
M2L <
f(x:) , + (V)(z) - + - -x)
+ ( f(x) H H (x+ x), x).
Using Young's inequality xy
v" Vz,yER 4p. 1 s. p
+ 1 ==1 we have:
M 3
12
(VS(x) g. xx)
V V 3//2
36
3vM M
and
} ((V2((x) - H² (x)(* - x)
x) <
M
3
+
72
f(x) - 3
36
M
Mixing all these ingredients, we get
20

---

Published in Transactions on Machine Learning Research (09/2024)
Lemma C.2. For any M L, it holds
3
f(x) f(x=) 2
r
22 [(x)
H
(34)
36
M
M
Using (99
we have:
L
[V[(x]) - H(x xx) + g Vf(x) + (H -V2((=)((==
- x)1l
applying the triangular inequality we get for M 2 I:
[V((tt)
v 2 g H x
x)|| + | (2) - glو f()) H|r
1-2M + V (a:) gl
+ 2M V f(x) HI
3M
( gl
2M V f() HI
2
By the convexity of + 3/2 we have for any (a:) 2 0: E, a,1;)) S E, a.))i 2/2 applying this the above incquality we get
Lemma C.3. For any M 2 L, it holds
1
2
V (1 3/33 < 3Mr3
[V/(x) -9 3/2
[
H
(35)
VM
VM
M
We can also bound the smallest eigenvalue of the Hessian. Using the smoothness of the Hessian we have:
(2f(xx))
f()())) L| _
H + (2x - H -rll
H - V f(x) H I LrI
33
Mr - ( HI LrI.
Which means for M 2 we have:
Amin (V2f(x
<
3Mr
+ + H|I
2
Then the convexity of x + 3 leads to the following lemma:
Lemma C.4. For any M 2 L, it holds
Aman f2 ))3
S 14Mr + M
f2) 3
(36)
M
Now the quantity (M) = max V [f(x))]3//
AAiin (V2 f(an which we can be bounded using Lemmas
C.3
M3/2
and
2
4
< 1
[
3/22
[²)
H|
(37)
M
VM
M
Combining Lemma
C.2 and
37
we get the inequality given in Theorem C.I
M
73
f(x) - f(x
w (x)))
Vs(())
g//3/2
fx)( -113.
1008 / M
72
VM
M
21

---

Published in Transactions on Machine Learning Research (09/2024)
D More on Section 3.1
D.1 Better Similarity using Sampling
One common approach for constructing gradient and Hessian estimates is sub-sampling, The idea behind sub-sampling simple: for an objective of the form in (1) we randomly sample two batches By and B, of sizes by and by consecutively from the distribution D and define:
gr.,, bg iEB,
1
Σ Vi(s)))) and H by Σ (.r) EEB,
(38)
In this particular scenario, the "elementary' estimates Vf(x,, () and v f(a,, 5) are unbiased, and we will assume that they satisfy E,][V[(x) - Vf((=)] & of and E, E f(x) f())ll s so
Lemma D.l. For the eslimalors defined in 38 we have
o H. <1(os(())07
B ((xs) 91.,5,
and E B
3/2
Lemma D.1 demonstrates how the utilization of batching decrease the noise. To simplify things, keep in mind this straightforward rule:
we employ batch of size ba, then we need modify da by de for E hg vb.
Lemma D.1 is based on the following two Lemmas:
Lemma D.2. (Lyapunov's inequality) For any random variable X and any 0 < < t we have
E|x s B(|x)1
and
Lemma D.3. Suppose that q 2 2, p 2, and fir r max (g. 2 log(p)). Consider i.i.d. random self-adjoint matrices "., YN with dimension p p, E[(;) = 0. It. holds that:
N 1/4 22ver
Σ
YI
E [V2) 1/2 l|2 + 4erR[max [4]
Lemma D.3 can be found in (Zoou et al.
2019
Now if we have XI...-, Xa E Rd i..dd vector- valued random variables such that E[X,] = and [[]]|X;-+4]])
o² then by applying Lemma D.2 we get:
3/2
X. Xx E|| 5 Σ
l113/21 < Elll Σ x; 11/33//4
13/4
When we have b i..id matrix-valued random variables r.,... Yo E daxd such that E|y, μ. B[JlY; - 4| -1 and E[Il,, /1|33] < og (by Jensen's 's inequality 02 I da), then by applying Lemma D.3
S <a²
we get:
3
E|| E. -
2
2e log(d)
+ log(d) 03
O
1/g(d))//2 1972
These last two inequalities are identical to the statement of Lerna
D.I
Here and everywhere (6-) hides absolute numerical constant.
22

---

Published in Transactions on Machine Learning Research (09/2024)
D.2 Proof of Theorem 3.3
We use here d1 og and ò2 Oh Combining both Theorem C.1 Assumption 3.1
and Lemma D.2 we get:
Ef(z,) Ef(x++)
Ejt (1++1)
VM f - 9//1
1008
73 E V2 (xx)
H: 1
Lemma D2
1008 Ept (I(+1)
VTT n
3/2
M2
73
o
By summing the above inequality from t = 0 to = T and rearranging we get:
1008T Σ Ex))( -
VM -M(o))))BB(CC) + +40g
3/2
73
M372
All is left is to use the fact that (f(w)) - Bs(xT) S f(wo) - fr = Fo, and by the definition of Doat
(Fo(( $ Σو= (aur(a,), thus:
1008 (Xout)
MM
M572 h + 40
73 3
3/2
E Proofs of Section 3.2
E.1
Proof of Lemma 3.7
We have
f(x)
1 Σ f((z)
and we suppose that each fú, 15 i n have the L-Lipschitz Hessians. Therefore, ʃ also has the L-Lipschitz Hessian. Thus, Ji has the 2I-Tipschiz Hessian.
Applying 2.1 and 29 f: ff we get
2) ff(x)] S L 2
and
x, - 2L =||
We note also the if i is chosen at random then E,G(f, x. .) vf(x) and E,H(Ji, (2f(m)) By using the properties of variance we have
E, 1 x))
22
L
Es 2, f[(x)|
<
b
Applying Lemmas D.2 and D.3 we get
[B]G(ff, x) V
13/2 |0 213
and
Es EsI x, {>)(3)13
2 2e logid)
8e log(d)
Ty (J,, {x)(1)]
2e log(d)
Se le
s
2
I.3 =113.
b
O(( ((rladdd)aa ya/2)
23

---

Published in Transactions on Machine Learning Research (09/2024)
E.2 Proof of Theorem 3.6
We use Theorem C.1 and denote ri+1 = | 2zll- and f, we have:
Then by the definition of the similarity between h1, h2
(f(s))+ - (f simm+i+1)
216 M RaM (Ism+i++)
p E
46
734 M
||
smm+i Dsm 113)
sm+i+1
VM
Summing it for 0 m we obtain
Ef(rem) - -fff(((()+))
Epa (Te-+itt)tt)))
216VM
1=0
E
M 72
155/22
+
7382 MF
)[ 2mmml²)
smati-
VM
We note that |m Jsml ||
- j= Tsm+j- Therefore.
Ef Ef(xam) - (x((((+11mm)
E 216VM Eps (2
E p
46
736
j=1 +3
sm-i41
VM
M
We apply now the following inoquality (from Doikov et al.
2022
3
m
Ti
m
3
which is true for any positive numbers fre and any m 2 1. Hence,
M
//
73 M
7am++ + )3]
72
sm
i+1
VM
M
m
482/2
736
Σ
3
VT
M
+sm+i+1
The above quantity is thus positive if M Equivalently, for M satisfying
m
2/2
7368 M
2 0.
72
3
vM
4 4(51 3/2
+ 73 3
(39)
we have
Ef Ef(x)m - Bf (I((+1)m)
m
Eu( Ey(0am+it1).
216 M
Summing it up for 0 0 s s gives
(M(((xa)-(")
8-1 m-1
Σ
Ef (1)mm+)))))
Sm
2168m
And thus by the definition of Bont we have:
Ex(Tottt
5 216 [M({(=))-11)
Sm
24

---

Published in Transactions on Machine Learning Research (09/2024)
F Gradient dominated functions
F.1 Examples of gradient dominated functions
Let us provide several main examples of functions satisfying
23
Example F.1. Let f be convex on a bounded convez set Q of diameter D, and let solution x" to belong to Q. Then, we have:
f(x) & (Vf(z). x-0)) x²) I (=)ll
Vz E Q.
Therefore, f (D, 1) -gradient dominated.
Example F.2. Let f be uniformly conver of degree 2 with some constant > 0:
f(y) 2 [(x) + (VI(x) x) fll æ=l": Var, y IRd
Then, I is (1) ) -grudient dominaled (see, e.g. Doikov & Neslerov (2021)).
The statement of Example F.2 is easily proven by minimizing both sides of the inequality defining uniformly convex functions.
In particular, uniformly convex functions of degree: & = 2 are known as strongly convex, and we see that they satisfy condition (23) with 2/ and 2. However, the function class (23) much wider and it includes
also some problems with non- convez objectives Nesterov & Polyak (2006).
F.2 Special cases of Theorem 4.2
For convex functions (the case a 1) Theorem 4.2
implies that for M max &T) we have the rate
LD3
D2D2
[[f(or)))) f o
T + 5ID)
(40)
T
Equation (40) has been obtained by (Agafonov et al.
2020
using an assumption that the noise is bounded
almost surely. Using the gradient and Hessian estimates minimum, we need at most
(88. for & > 0 and M = L,, reach an e-global
T = T= LDa
iterations of the method, with the batches of size by = 0 0 D2 Hessians, respectively. Therefore, the total number of arithmetic operations needed to find an e-global minimum
and b, = ( for the gradients and
1/2222
of Da/2 11i2ga72)
x GradCost.
2072
For p-uniformly convex functions of degree s = 3 (the case = 3/2 and ~ )) using stochastic estimates (38) and setting M L, we reach an e-global minimum for any in most
T = =0( log( Eu)
iterations of the method with the batches of sizes b, = O (2155173) and by O (773))77)) Therefore, the total number of arithmetic operations is bounded as
d2VI म:ा
+ d / x GrudCost.
25

---

Published in Transactions on Machine Learning Research (09/2024)
psstrongly convex functions (a 2 and 5 ).). For this class of functions, setting M L, for any get [[ - f < we need perform most
T o(to + log log log( t
and by O o and, where with batches of size by ( ( pe
O
V.F
to Ō
4374
Therefore, the total number arithmetic operations needed to find an e-global minimum, in this case, is
①
1uo Me
+ cl
foo (.v/ie)
GradCost.
F.3 A special case of Theorem 4.3
Let us consider the special case a = 1, which corresponds to minimizing conver functions. Theorem 4.3 implies the following global convergence rate:
[[f(#oo)] - =f= 61
(O
61 S
D2D
LD3
S
S2m²
We have the following special cases based on the choice of the helper functions.
Basic Cubic Newton (Nestrrvv & Polyak 2006) corresponds to 61 = 82 = 0. Thus, we get
its known rate the convex case. We reach an e-global minimum using the following number of arithmetic operations:
0 nd GradCost.
(41)
Cubic Newton with Lazy Hessian updates (Dokov al. 2022) corresponds to 6, 0, 82 L. It gives f(oow) - O following number of arithmotic operations:
LD 52m
By choosing d, we reach e-global minimum using the
nyd VV
GradCost.
(42)
To the best of our knowledge, this complexity estimate of the Lazy Cubic Newton for convex functions new, and improves the complexity the basic Cubic Newton (41) by factor Vd.
Stochasic Cubic Newton with Variance Reduction (houu al. 2019 Wang et al. 2019 corrosponds to sampling random batches By, Br of sizes by. by respectively at each itcration, and setling hn by LieB, Jú, h2 = J Eies, Ja in our helper framework. According to Lemma 3.7 we have 51 = Vo and 82 = (() Therefore, for by m².b, ~ m² and M = L, we get
B[f(#out)] - 0( LD*)) By choosing
(nd))/11, asnn/ 1 1/3 1222//, reach an s-global minimum using the following number of arithmetic operalions:
o( minn((md)/i [1/4
x GradCost.
(3
In Masiha al. (2022), the global complexity estimate for the stochastic Cubic Newton with Variance Reduction established for the gradient dominated functions of degree 1. However, their result is different from ours, assuming only stochastic samples of the gradients and Hessians, while in
our work, we allow recomputing the full gradient and Hessian once per m iterations, similar in spirit to (Zhou et al. 2019 Wang et al.) 2019). In our analysis, we take into account the total arithmetic cost of the operations. Hence, to the best of our knowledge, our complexity estimate 43 is new.
26

---

Published in Transactions on Machine Learning Research (09/2024)
Stochastic Cubic Newton with Variance Reduction and Lazy Hessian updates. In this case, by using sampling, we have ó1 = = and 82 L. If we take m (nd) as dl d2va then we reach e-global minimum using the following number of arithmetic operations:
/hg
min((nd)%/ nvdt GradCost.
Ve
This further improves the total complexity of both the method with Variance Reduction the Lazy Cubic Newton 42
443 and
F.4
Proof of Theorem 4.2
From Theorem C.1 have
Ef(x;) - Ef(x++1)
1008/MM M
E V V
1///2
VM
4
0g
3/2 73
M
h
By the definition of (rradetta dominated functions we have
f(xi) - z T|[[{(>;)11
which leads to
E V (+
[ 20
If a 3/2, then by Jensen's inequality have
E [ 3/2
Bf(
(44)
For a > 3/2 we need to assume that Ef(x;)) - f S [f This gives us [44
We consider the sequence F; = E.(())) - f* and denote
2a
3
C 1008
and
/M 0g
3/2
182
25
Then sequence (Fr) satisfies:
F. F++1
CF2
(45)
We assume that CF2 200ee F1t1 2 (7) we will prove that when this is the case, the sequence (Fr) converges to (g) 1/7 otherwise, stop.
Case 7 1. Then
F <
Fete C+1
From the recurrence, we have:
P. < (1+ (1+ I+C (1+C)-'A++ g
We note that (1+C)-* < exp(
-Ct 1+c). Therefore,
F S exp
-Ct [+0
Fo + 2-
Case 1 << Then let F. ov(-1)
F and à 01/0-5) for which we have
-
F.- Frt1
F ā.
Now let =,7 and & Fr Then
8, 8,41
(8e41 + x)7 xx 2 67
27

---

Published in Transactions on Machine Learning Research (09/2024)
where used in the last inequality the fact that (a +) 2 x² y for y 2 1 and y 2 0. Here, assume that de 2 O. Otherwise, we have F; S (0)
Therefore, 8, F (2) and C4/0--0)
8, - 6c+1
2 0/+11
We have
57 57-1-677
(r- 1)6441
(2- 1)67
( 1767 6241
The concavity of x x²-1 (since 7 S 2) implies that for all x. y 2 0 we have x7 17-1-1-11 2 (x- Hence,
11)-1x>>--- 2 (x-x)(x))) 1).
6 6
6441 81
(1-1)6271
(x-1)67-
8,6751
If de+1 2 6./2 then
2 21/2,
(7 - 1)0
(r 1)67-1
otherwise, 8i+1 S 6,/2, and in this case we have
(27-1-1) -
27 27-1-1
h7- 1) (7-1)67
(7-1)67
(7-1)66
where we used that (4))22 is decreasing. Thus, in all cases we have:
min(1/2, ---1--1)
D.
( 1362 (1-1)67-
(5-1)88
By summing from t == 0 to t -= T 1, we get:
2 DT.
(7-1)87-1
In other words
8T s
(1--I
- Case 3/4<g < 1. Then we have
Fe41 S (ii-entta 1/7
By convexity of ++ 1//7 get
F11 I (F-F-i(Fe- + 21/7-1 1/7
Let & F/22//7 1(2) 21/1010011)
Then have
de+1 5 8
The sequence (6:) is decreasing, thus:
8,+1 < 8//7.
This is a superlinear rate, starting from the moment 5, < 1 We can show that from the very beginning (6))2 will decrease at least at a linear rate, and thus at some point we reach the region of superlinear convergence.
Indeed, we have 8 2 +
8 81-8111
2
1
8- Therefore, 5c (1
2
11
6.41
6141
8111
8,41 <
(1 +
1
1
1 - )o, S exp(- 1-66 -
8/ 81-77
1+
We reach 6, 5 1/2 after 12 40
(1 + 6/ 37) log(26g) ilerations. After that (1 2 40), we enjoy superlinear
convergence rate: o, < (1) (1)
(5)) to
This finishes the proof.
28

---

Published in Transactions on Machine Learning Research (09/2024)
F.5 Proof of Theorem 4.3
In Theorem
we made the choice of updaling the snapshot in the following way Øst1 Barg min (mmmm which means that f(0++1) S f()mm+t) for all e {0,-.., m 1}.
For 1...... S 1 and i E {0, m 1} We have the following inequality
(f Ef (f 216V
V
+ E M smi
462/2 VM
736 M
Øam+i
Iemll
(B((er+1)>-"" 3
By the definition of gradient dominated functions we have E|] Vf(x+)))))
26
So
2
Ef(xem+t) (2m+itt))))
216vM
+ sm++i+1
E
M p3
/46//2
+
7382 M2 Øsmti Zeml
VM
[f(b441)
3
216
+
72
M 3
sm
+i+1
482//2 V
+
7383 Mr2
@sm+i
2mm
Summing the above incquality for 0SiS and remarking that H, Esn, get
Ef(().)) (2)+())))
-(("++1)-f"
2
M
+
72
3 sm+i+1
182/2 VM
+
7383 X7
|
@mm++i
Fsm
By the definition of 2.+1 we have f(#x+1) S f 1 am for all é E {0..... m 1} which leads to
Ef(ā.) - (f((.)1)
216VM
E
M 3
(45//2 VMM
7353
Mr aam++i 2mm 1mm
sm+iit1
For M satisfying 39 we have
2i=0
m- M
72 sm+++1
468/2
VM
+
736
M
Wem+i xam | 2 0 thus we have
-B(())-Ef((tt)
Bf(
216 M
Let us define F. = =Ef(ix)) - f Then
F- - F 2
CF
which is special case of inequality 45 with = 0. Thus we can apply our findings from before and replace a with 0.
29


Reviews:
[{"review_id": "uc6JePCJmP", "reviewer": "Reviewer_Jadv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe theoretical development is sound and the mathematical formulations are rigorously presented.\n\nWeakness:\n\n1. The current experimental validation primarily uses datasets from the LIBSVM library, which are relatively simplistic and might not fully demonstrate the scalability and efficacy of the proposed methods in challenging scenarios.\n2. The first-order baselines are too weak. Consider comparing with those empirically better ones, like Adam and AdamW. Also, I think it would be better to show the detailed profiling, like the time for computing the gradient and hessian respectively.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel framework that unifies stochastic and variance-reduced second-order algorithms with global complexity guarantees, applying to both general non-convex problems and specific machine learning tasks. The introduction of the helper framework is innovative, potentially impacting the design and analysis of stochastic Cubic Newton methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Experiments on more convincing datasets. \n2. Comparasion with more advanced first-order methods.", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "g1blAK1RgV", "reviewer": "Reviewer_eFK5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper provides a unified framework that encompasses multiple methods, offering a comprehensive view of stochastic and variance-reduced second-order algorithms.\n2) The paper introduces new algorithms, such as the lazy stochastic second-order method, that improve upon existing methods in terms of arithmetic complexity.\n3) The paper establishes complexity bounds for both general non-convex functions and gradient-dominated functions, providing a thorough analysis of the proposed methods.\n4) Overall, the text is well-written, and the main points are well-expressed.\n\nWeaknesses:\n1) It should be noted that there are several closely related papers in the area of cubic Newton methods (even in a convex regime), which unfortunately are overlooked. See \"Requested Change 1)\".\n2) In some places, the paper lacks clarity. For example, at the end of the fourth page, the authors introduce a general principle involving a computationally cheap function h and an expensive function f - h. Then they suddenly mention the need for two helpers h\\_1 and h\\_2. This leads to a slight loss of intuition and a certain misalignment with what is written in the general principle. Could the authors please clarify this point?\n3) According to the text, the \"unified property\" of the analysis is given through auxiliary helper functions h\\_1 and h\\_2. However, in section 3.4, the discussion of these functions is mostly hand-waving and lacks a rigorous definition of h\\_1 and h\\_2 (for each particular example), as well as a rigorous proof stating the conditions under which delta\\_1 and delta\\_2 satisfy the assumptions. However, it is important to point out that these assumptions are satisfied for the subsampling of functions f\\_i. Nonetheless, similarly to what I mentioned earlier, it is unclear whether this framework is useful outside this special case.\n4) Regarding real-time comparison, I should note that this comparison in real-time is hardware implementation dependent. Without reviewing the source code, which is not disclosed, it is difficult to determine how well the algorithms are implemented.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary of the main arguments:\n\nThis paper presents a unified framework called the \"helper framework\" that provides a unified view of stochastic and variance-reduced second-order algorithms equipped with global complexity guarantees. The helper framework offers flexibility for constructing and analyzing stochastic Cubic Newton methods, allowing arbitrary batch sizes and the use of noisy and possibly biased estimates of gradients and Hessians.\n\nThe authors claim that the paper recovers the best-known complexities for stochastic and variance-reduced Cubic Newton methods under weak assumptions on the noise.\n\nIt also introduces a new lazy stochastic second-order method that significantly improves the arithmetic complexity for large-dimensional problems. The paper establishes complexity bounds for gradient-dominated objectives, including convex and strongly convex problems. For auxiliary learning, the authors show that using a helper function can outperform training alone if a given similarity measure is small.\n\nAssumptions used by the authors:\n\n1\\. The Hessian of the objective function f is Lipschitz continuous (Assumption 1).\n\n2\\. There is bounded similarity between the gradient and Hessian estimates and the true values (Assumption 2).\n\n3\\. There is Lipschitz similarity between the gradient and Hessian estimates and the true values (Assumption 3).\n\n4\\. The objective function exhibits gradient dominance (Assumption 4).\n\nContributions of the paper:\n\n1\\. Introducing the helper framework that unifies multiple methods, including stochastic methods, variance reduction, lazy methods, core sets, and semi-supervised learning.\n\n2\\. Recovering previous versions of the variance-reduced stochastic Cubic Newton methods with known rates and providing new algorithms that employ lazy Hessian updates, improving the arithmetic complexity for high-dimensional problems.\n\n3\\. Proving a benefit from using auxiliary tasks as helpers in the framework, potentially replacing the smoothness constant with a smaller similarity constant.\n\n4\\. Analyzing both general non-convex functions and gradient-dominated functions, including convex and uniformly convex functions.\n\n5\\. Justifying new improved complexity bounds for the deterministic Cubic Newton method with lazy Hessian updates and for the stochastic Cubic Newton algorithms with variance reduction, taking into account the total arithmetic cost of the operations.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) Could you please specify the difference between this work and several other recent advancements in this field?\n(1) Hanzely, Slavomír. \"Sketch-and-Project Meets Newton Method: Global $\\mathcal O (k^{-2}) $ Convergence with Low-Rank Updates.\" arXiv preprint arXiv:2305.13082 (2023).\n(2) Mishchenko, Konstantin. \"Regularized Newton Method with Global Convergence.\" SIAM Journal on Optimization 33.3 (2023): 1440-1462.\n(3) Hanzely, Slavomír, et al. \"A Damped Newton Method Achieves Global $\\mathcal O\\left (\\frac {1}{k^ 2}\\right) $ and Local Quadratic Convergence Rate.\" Advances in Neural Information Processing Systems 35 (2022): 25320-25334.\n\n2) \"while it can be also possible to generalize our results to functions represented as expectation over an arbitrary probability distribution.\"\nI think it is better to remove this phrase as these results are not presented in the work.\n\n3)Considering the experiments, could the authors please comment on why in Figure 1 and Figure 3 the stochastic cubic Newton method has almost zero arithmetic computations?", "broader_impact_concerns": "This work is primarily theoretical in nature. Hence, there is no identifiable potential for negative societal impact arising from this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "U7DqYPuYP6", "reviewer": "Reviewer_jpd1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) This paper offers rigorous theoretical guarantees with clear complexity bounds and improvements over existing methods.\n\n2) This paper is clearly written and well organized. The authors discuss the related work properly.\n\n3) The helper framework is a novel approach that may influence future research in stochastic optimization strategies.\n\nWeaknesses:\n\n1) The authors mainly validate their methods via logistic regression problems. More results on more complicated tasks and datasets are expected, since the theoretical improvements need more empirical results to validate their effectiveness.\n\n2) Although a helper framework can enhance performance, how to devise a good helper may be a problem in practice. It would be better if the authors could discuss more about this.\n\n3) The effectiveness of the approach heavily relies on the assumptions about noise and data similarity, which might not always hold in practical scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a helper framework for stochastic Cubic Newton methods in optimization, specifically addressing non-convex minimization problems. The primary contributions include:\n\n1) This paper introduces a new framework for stochastic and variance-reduced second-order algorithms. This framework allows for flexibility in batch sizes and incorporates noisy, potentially biased estimates of gradients and Hessians.\n\n2) It provides global complexity guarantees and recovers the best-known complexities for stochastic and variance-reduced Cubic Newton methods under weak assumptions on the noise.\n\n3) The authors develop new algorithms using lazy stochastic second-order methods that improve arithmetic complexity, particularly in large dimension scenarios.\n\n4) The authors also demonstrate that auxiliary tasks can improve learning outcomes if a particular similarity measure is small.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) Additional empirical results are expected, especially on more complicated tasks, which would strengthen the claims about the framework's effectiveness and practicality.\n\n2) More discussion about how to design or find a good helper. Also, it's better to give more discussion about the assumption used, as the current assumptions seem somewhat strong.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors effectively demonstrated the usefulness of the helper framework by recovering the best-known complexity of variance-reduced cubic Newton methods and proposing a new method. The introduction of this framework has the potential to impact the design and analysis of stochastic cubic Newton methods.

All concerns raised by reviewers have been well addressed. Considering the above contributions, this paper meets the acceptance criteria of TMLR.
Decision: Accept (poster)