AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning
Authors: Ioannis Tsingalis
Constantine Kotropoulos
Corentin Briat
Venue: Accepted by TMLR ()

Abstract: A novel regularization technique, AdaCubic, is proposed that adapts the weight of the cubic term. The heart of AdaCubic is an auxiliary optimization problem with cubic constraints that dynamically adjusts the weight of the cubic term in Newton’s cubic regularized method. We use Hutchinson’s method to approximate the Hessian matrix, thereby reducing computational cost. We demonstrate that AdaCubic inherits the cubically regularized Newton method’s local convergence guarantees. Our experiments in Computer Vision, Natural Language Processing, and Signal Processing tasks demonstrate that AdaCubic outperforms or competes with several widely used optimizers. Unlike other adaptive algorithms that require hyperparameter fine-tuning, AdaCubic is evaluated with a fixed set of hyperparameters, rendering it a highly attractive optimizer in settings where fine-tuning is infeasible. This makes AdaCubic an attractive option for researchers and practitioners alike. To our knowledge, AdaCubic is the first optimizer to leverage cubic regularization in scalable deep learning applications.

Published in Transactions on Machine Learning Research (02/2026)
AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning
Toannis Tsingalis
tsingolis Resd. outh.gr
Department of Informatics
Aristolle University of Thessaloniki, Greece
Constantine Kotropoulos
costas@icdd auth.gr
Departmend of Informatics Aristolle University of Thessaloniki, Greece
Corentin Briat
corentin @briat. info
School Life Sciences
University of Applied Sciences Northwestern Switzerland, Muttenz, Switzerland
Reviewed on OpenReview: https: openreviewwww.. net/ formmf (etrrmmmid=pBpB0P00 pd=22BQ1J371
Abstract
novel regularization technique, ADACUBIC, is proposed that adapts the weight of the cubic term. The heart ADACUBIC is an auxiliary optimization problem with cubic con- straints that dynamically adjusts the weight of the cubic term in Newton's cubic regularized method. We use Hutchinson's method to approximate the Hessian matrix, thereby reduc- ing computational cost. We demonstrate that ADACUBIC inherits the cubically regular- ized Newton method's local convergence guarantees. Our experiments in Computer Vision, Natural Language Processing, and Signal Processing tasks demonstrate that ADACUBIC outperforms or competes with several widely used optimizers. Unlike other adaptive algo- rithms that require hyperparameter fine-tuning, ADACUBIC evaluated with a fixed of hyperparameters, rendering it highly attractive optimizer in settings where fine-tuning is infcasible. This makes ADACUBIC an attractive option for rescarchers and practitioners alike. To our knowledge, AuBiiC is the first optimizer to leverage cubic regularization in scalable deep learning applications.
1 Introduction
Deep Neural Networks (DNNs) have demonstrated strong performance on variely of machine learning
tasks (Pouyanfar et al.] 2018 Dargan et al., 2020). DNN models are non-convex (Jin al., [022 Daniloval et al. 2022 Pooladzandi et al. 2022b). Accordingly, saddle points may arise during the optimization 2021 In Dauphin et al. (2014), it is shown that the saddle points affect the efficiency of DNN. Therefore, methods that avoid saddle points are necessary, as discussed next.
procedure (Bedi et al.
The Cubic Regularized (CR) Newton's method was introduced in (Nesterov & Polyak 2006 This mothod effectively circumvents saddle points non-convex selting. The first research direction locuses on carefully selecting the regularization parameter for the cubic term. In Cartis et al. (201 20), an Adaptive Regularized Cubic (ARC) method presented where the cubic regularization term is adapted dynamically, similarly to the radius in the Trust Region methods (Conn al.) 2000). To mitigate the computational burden of deriving the Hessian matrix and the gradient in ARC, Carmon & Duchi (2019) solves the CR sub-problem using gradient descent. Alternatively, one solves the cubic sub-problem using a subsampled gradient and

---

Published in Transactions on Machine Learning Research (02/2026)
a Hessian-vector product (Tripuraneni et al. 2018). In Kohler & Lucchi (2017) a subsampled scheme for the gradient and the Hessian matrix is exploited, achieving the same convergence rate as ARC. In Wang
ie al. (2020b), momentum information utilized to improve the convergence rale of CR. Inspired by Fang le al. (2018), a recursive stochastic variance reduced CR method is proposed in Zhou & Gu (2020), yielding better convergence rate than that reported in (Tripuraneni et al.] 2018). In Huang et al. (2022 the CR
method was applied to solve unconstrained convex-concave saddle point problems.
In a second research direction, it has been demonstrated that injecting a random perturbation whenever a saddle point is encountered can facilitato escape from saddle points. In|Ge et al. (2015); Jin et al. (2017), both negative curvature and random perturbation are applied to Stochastic Gradient Descent (SGD) to escape saddle points. Within the same scope, in Allen-Zhu (2018); Royer & Wright (2018), it is shown that negative curvature and random perturbation can be used find an (Gg:c:))stationna) point faster than the first-order methods. A drawback of these methods is the need to compute the smallest eigenvalue of the Hessian matrix and the corresponding eigenvector. Several methods have been proposed to address this limitation. In Li (2019), it is shown that a perturbed version of Stochastic Recursive Gradient Descent, without using the Hessian matrix information, also converges to an (eg. = point. In MnAllen-Zhin & Li (2018) ;); Zhang & Li 2021], a robust Hessian matrix power method is proposed to compute the negative curvature near saddle points, yielding faster convergence than the standard perturbed gradient descent methods. In Chen jet al. 2002)), to achieve better convergence rate, the average movement of the iterates is controlled by a
step-size shrinkage scheme [Li 2019
In third research direction, escaping saddle points relies on momentum information (Wang et al. 2021b). First-order methods with random initialization and momentum information are shown to be able to escape saddle points in (Sun et al., 2019)- A greater momentum in SGD enlarges the projection to an escape direction, leading to a fast saddle point escape (Wang et al, 2020a).. In Levy et al. (2021), a parameter free recursive momentum method is proposod for non-convex optimization. In Wang et al. (2020a), ; it is shown that acceleration can be achieved for non-quadratic functions under Polyak-L.ojasievin condition and non- convexity. In Wang et al. (2021a), it is presented that the momentum term accelerates the training of onde ReLU network.
A fourth research direction employs variance reduction to escape saddle points. In Allen-Zhu & Hazan (2016), the minimization of the sum of smooth functions is studied, where variance reduction is applied to speed up convergence in both the stochastic and the deterministic case. A general variance-reduution estimation method is introduced that is not restricted to gradients only (Fang et al.) 2018). This method has been applied to numerous problems and has achieved convergence rates superior to those reported in (Allen- Zhu & Hazan 2016). In Nguyen et al.] (2017a); a recursive gradient estimator for convex optimization is introdueed. The latter estimator is then extended to non-convex problems in (Nguyen et al. 2017b). In Ge et al.] (2019), the first variance reduction technique not based on a separate negative curvature search subroutine is proposed.
Last but not least, second-order optimizer, called ADAHESSIAN, has been introduced Yao el al. 2021 ADAHESSIAN is based on the Adaptive Moments Estimation (ADAM) optimizer (Kingma & Baj 2015 and leverages Hutchinson's 's method to approximate the curvature information with low computational cost (Bekas et al. 2007). The convergence rate of ADAHESSIAN for strongly convex and smooth loss function can be found in Yao et al., 2021 Pooladzandi et al.) 2022a). Based on the Hessian power, the convergence rate of AEAHESSIAN for a strongly convex and smooth loss function matches that of either gradient descent or Newton's 's method (Jahani et al. 2021 Sadiev et al. 2022).
In this paper, we focus on the CR Newton method (Nesterov & Polyak 2006) and propose novel algorithm that dynamically adapts the weight of the cubic term in the cubic subproblem. The adaptation of the cubie term is achieved by utilizing an auxiliary cubically cointr optimization problem. The proposed algorithm, ADACUBIC, leverages the advantages of CR theory and Hutchinson's estimation technique. In more detail, the contributions of this paper are:
A novel method is proposed that automatically adapts the regularization parameter M in the cubic sub-problem and avoids saddle points. The primary theoretical contributions concerning the adap- tation of M are encapsulated in Lemma 2 Theorems and 2 as well as the methodologies detailed

---

Published in Transactions on Machine Learning Research (02/2020)
in Algorithms and 2
Figure D in Appendix A depicts how the key lemmata, theorems, and
corollaries are logically connected throughout Sections to and Appendices B.1 to B.13
The proposed optimizer does not need the computation of Krylov sub-space Wang et al. (2020b):
Zhou & Gu (2020); Kohler & Lucchi (2017) or the calculation of the smallest eigenvalue Allen- Zhu & Li (2018): Allen- (2018): Park et al. (2020) obtaín an optimal solution. The optimal solu- lion is obtained by leveraging Hutchinson's 's method that approximates the diagonal of the Hessian matrix (Bekas et al. 2007). In this way, the proposed method exhibits low memory complexity.
The convergence rate of ADACUBiC is established by exploiting the diagonal structure of the ap- proximate Hessian matrix, which is computed using data batches. This property makes ADACUBIC particularly appealing for deep learning applications.
ADACUBIC is tested on Computer Vision, Natural Language Processing, and Signal Processing tasks, demonstrating a competitive or better performance when compared to SGD Robbins & Monro [951], ADAM Kingma & Ba (2015), and ADAHESSIAN (Yao et al. 2021 optimizers. It should be noted that the parametrization of ADACUBIC performed by employing a well-known set of parameters used Trust Region algorithms (Conn et al.) 20000, Scction 17.1). These parameters are used universally in the experimental evaluation, casting ADACUBIC as an attractive optimizer when fine-tuning is prohibitive.
The paper is organized as follows. Section 2 details the proposed optimization framework. The convergence
analysis of the proposed optimization framework is demonstrated in Section g Section 4 rithms that compute the optimal solution of the proposed optimization framework in Section 2 Experimental
presents the algo-
results, computational complexity, and conclusions are presented in Scctions and respectively.
2 Proposed Optimization Framework
Outline. Scction 2.1 introduces the fundamental definitions used throughout the paper, including the basic formulation of the CR method, which serves as a core building block of the proposed framework. Section 2.2 then introduces an auxiliary constrained optimization problem that forms the foundation of the ADACUBIC. The key intuition to reformulate the classical CR method as a constrained problem in which the cubic regularization term appears explicitly as a constraint. By leveraging Lagrange multiplier theory, this reformulation yields an adaptive update mechanism in which the strength of the cubic regularization term of the CR method is automatically adjusted during optimization. To derive this update mechanism Corollary
Lemmata I Theorem I
D and Theorem 2 are introduced.
Lemma establishes that the auxiliary constrained problem admits global minimizer and ensures that each optimization step is well defined. Lemma 2 is used to establish Theorem [ which in turn is used to derive Corollary [I] Corollary [ shows that the auxiliary optimization problem is characterized by strong duality Boyd & Vandenberghe 2004 Section 5.4). The latter theoretical results are then combined to derive Theorem 2 which provides the basis to replace the fixed cubic regularization parameter of the CR method with an adaptive one and finally derive the ADACuBiC optimizer presented in Section 4
2.1 Preliminaries
To simplify notation, the iteration index ls in X RRd will be explicitly denoted when necessary. Otherwise, it will be suppressed. Let (zf(x)) and vxf(x;) be the Hessian matrix and the gradient of the function (xx) with respect to (w.r.t)) x. In the following, the subscript x in V and Vx is omitted for simplicity, resulting in fxx( and V (x(xx), respectively. The spectrum of the symmetric d x d matrix V f(x() is denoted by A(V2J(xx)) = (V* Suppose that the eigenvalues are sorted in descending order, i.e.
\x(x(((x)) 2 {d(V2f(xx)) Amin (V2f(x))
(1)
If fxxx is indefinite, i.e.
Aa {v(v2 <0 and {(V2f(x+)) > >0, i< d,
(2)

---

Published in Transactions on Machine Learning Research (02/2020)
then f(x is non-convex. The notations f² 2 0 or fxf())) > 0 indicate that the Hessian matrix is positive semi-defiitte or positive definite, respectively. Let 0, be the partial derivative of a function F - w.r.t. the real-valued variable т. Moreover, let @ and ② denole the element-wise product and division, respectively. In addition, let diag(V² = [[V] [xx))... ".............. fxx))aaa vector containing the diagonal elements of the Hessian matrix and Diag(V² (iaa((>((xx))) = v² @ I a x d stand for a diagonal matrix retaining the diagonal elements the Hessian matrix, where I is the identity matrix. |1-1|2 refers the vector lg norm or the spectral norm of matrix. The d-dimensional vector of ones is denoted by Ld-
Rd be a column
A non-convex optimization problem is defined by
f(x) Σ f((x).
min xER
(3)
where f: _d + R and fe: Rd + R are non-convex functions. Solving 3 is generally NP-Hard (Murty & Kabadi 1987 Hillar & Lim 2013). As result, reasonable goal to find an c-stationary point, i.., an approximale local minimum, by checking [VV[())]l e, where V.((x) IRd is treated column vector. However, e-stationary points can be non-degenerate saddle points (i.e., the Hessian matrix at all saddle points has negative eigenvalues) even local extrema in non-convex optimization. To avoid saddle points, second-order methods are used to find an ( e.).sstttoonaryy point by checking
|V/(x)]l <g
and Amin V [x)(
-E11,
where Eg. EH > 0, and Amin ( fx)) denotes the minimal eigenvalue of the Hessian matrix. CR technique is designed to avoid saddle points Nesterov & Polyak 2006). Starting from an arbitrary point Xg, the update rule of CR that solves 33 is written as
Sk+1 = arg min mM (s)
(5)
SERd
where
1 ST (x]((x) S+ M ms( - fxxx) (xxx)) s
||s||
(6)
Xk+1 X + Sk+1, and M > 0 is the regularization parameter that can be fixed or adaptive (Nesterov & 2006; Cartis et al. 2011a) In the following sections, the problem formulation and its solution are
Polyak
presented.
2.2 Problem Formulation
Auxiliary Problem. We are interested in developing adaptive method for selecting M in 5 To do so, introduce the auxiliary constrained optimization problem
(s)) A f(xx) + V s 2 s" (²)(xx)
arg min SERe
(7)
1 subject to ge(s) 1 (1s|)²² - 00
for & 2 0. The Lagrangian function of is
Le(s, - + (xx) T 8
T 42 (xx()))
+ 1 (1s11² E). -
(8)
2
where is the Lagrange multiplier. Let Ω {s (s)s) 0}. The minimizer are seeking in
lies
either within the interior of Ω (i.e., (8) < 0) or lies on the boundary of Ω (i.e., (e(s) = 0). Lemma immediate result of the previous discussion.
is an

---

Published in Transactions on Machine Learning Research (02/2026)
Lemma 1. A vector s" is a minimizer of mi(s) subject to ||s*112 S & if and only if sotisfies
((x(( + 1¹
2 1ss112 1) s = --V =VV fx(x),,
(9)
{²5(xx) + ||s ll I O,
(10)
and v" (1|s~112 - [) = O, where 1- 2 f(xx) + 2/2 ||s ll2 I> 0, then the minimizer s* is unique.
3 {) = 0 in Lemma of Lemma | can be found in Appendix B.1 Definition For some 2 0, denote
The condition v² (I|s*
is called Complementary Slackness (CS) condition. The proof
vr I> 0, r>0} D, A { f(xx)
(11)
2
Next, it is proven that problem is characterized by strong duality. To do so, Lemma 2 and Theorem
1
are introduced. Lemma 2 is used as a preliminary result to prove Theorem Corollary establishes the strong duality of problem as an immediate outcome of Theorem Lemma 2 (Proof in Appendix B.2 For r E DD, we have Le(s(u,r),u,r), rED,
min Le(s, max SERd
(12)
where
2((s(u.)),u))= = (xxx) (xx)) (x²x))((((((x)) + vr
2 =111 1)
Vf(xx)
5
1/
V
3
(13)
6
12
For r E Dr the direction
s(ur) = -vV2f(xx) + ~ 1) vf(x)),
(14)
satisfies
(e(s(v,r),)) L,(s( v.)) 4 (++ (0nE((s(u.))))))
(15)
3v
(++1|s(,,))1)
For r" E Du that marimizes maxrEd, Le(s(u,T),
V [|s(,,)")l2 1)= vs(xx) (V(((())))) s(u,r")= = (2)(xx) -
(16)
is the minimizer of min Le(s, v) in 12
Theorem (Proof in Appendix B.3
We have
min max Cg(s, ()s
max v20, rED. Le(s(1,r),,,T)
(17)
SER 220
where L,(s(v,)). is defined in 13 For E Dv, the direction
s(v,r) = =- 100==-(v0 ---2(((xx)) + vr 4r 1) Vf(x)).
(18)
salisfies
(r + [|(())))]22 (0.L6(((e)))))))))) (19)
Ce(s(v,r),)) Le(s(v, v,)) For the optimal values v² and r* E Dr that marimize max.20, rED. Le (s(()))),,,T)
O, (s(v, (((,(,,)),,,r)
3r (r ||s(U, 1)2)
s' s' r*) (v=2((x))) +
2 ||(("", rr))l2 1) vf(x))
(20)
is the minimizer of min max,20 Lg(s v) in 17 i.e., the optimal s* in Lemma

---

Published in Transactions on Machine Learning Research (02/2020)
Corollary 1. The construined oplimization problem 7 is characterized by strong duality, i.e.,
min max Cs v)) = max min Cg(s,1) v/). SER #20
(21)
v20 SER
Proof. See the proof of Theorem
Given Corollary | the equivalence ween problems (5) and 7 is established Theorem The equivalence implies that both problems have the same optimum.
Theorem (Proof Appendix B.4]. Let v² be the optimal dual variable of the constrained optimization problem 7 The following optimization problems
min (s) and min m(s) subject to gę(s) SER
(22)
BERd
are equivalent w.r.t. the optimal solution s", when M v² and { ||s 1
3 Local Convergence Analysis
Outline. This section provides the local convergence analysis of Algorithm [ begins with Assumption which defines the Lipschitz continuity constants for fx(x,, fx()), and fi().. Subsequently, Theorem 3
establishes the local convergence of Algorithm | when using the exact gradient and Hessian matrix.
Adequate agreement between the exact gradient Vx(x)) and the approximate gradient gk is established
in Assumption _
This assumption is grounded on Wang et al. (2019 Assumption 2) and facilitates the
approximation the gradient using a sampling scheme Lemma 5 akin to the one outlined in (Kohler
Lucchi 2017 Theorem 7).
A sufficient agreement between the exact diagonal Hessian matrix Diag( ( (xx;,) and the approximate
diagonal Hessian matrix B, in (30), is established in Assumption Assumption B is direct application
of (Wang et al. 2019 Assumption 2). Additionally, Assumption supports Lemma while Lemma is and Corollary Lemmata 5 and 0
pivotal for establishing Lemmn g Lemina | is used in Lemmata
provide the deviation bounds for the gradient and Hessian matrix, along with the corresponding conditions required for these bounds to hold. These conditions are consolidated in Corollary [ which ensures the validity of both deviation bounds.
The analysis concludes by discussing the local convergence of the sub-sampled case, where the exact gradient V (xx) and diagonal Hessian matrix Diag( 2 f(xx)) are replaced with their sub-sampled approximations ga and B₁, respectively.
Convergence Analysis. Next, we begin with the main results of the analysis. Assumption is commonly used in previous works (Nesterov Polyak 2006 Cartis et al., 2011a Kohler & Lucchi 2017 and is applied here in combination with Remark
Let F C Rdd be closed convex set with non-empty interior. Let xo int F be starting point of the iterative optimization scheme in the interior of F.
Assumption (Contimuity). The convergence analysis is based on the following assumptions:
The functions fi(x) are tuice-contiiuuoust differentiable and bounded from below by flow
The functions fi(x), (x)),, and f1 are Lipschitz continuous in with Lipschitz constants Ly, bg and LH, vespectively.
Remark 1. Due to the triangle inequality, it follows that the Lipschitz continuity also holds for f(x), V Vx(x). and 2 fxx), with Lipschitz constants Ttf, T.g, and Lu, respectively. In addition, given Assumption f(x) is also lower bounded by some flow.

---

Published in Transactions on Machine Learning Research (02/2020)
By leveraging Theorem 2 the iteration complexity of Algorithm is equivalent to that performed by the cubic regularization method (Nesterov Polyak 2006). Theorem analyses the iteration complexity of Algorithm 1 by adapting the analysis from Nesterov & Polyak (2006 Theorem 1), when Diag( (x)) replaces V f(x())
Theorem (Proof in Appendix B.12 Suppose Assumption 1 holds. Also, let the sequence x,, with 2 0, be generated by Algorithm when Diag( V f(x:)) is used. Then, after iterations, the sequence (x
satisfies
[Vf(x))] 50 ssikk
min
(23)
12/3
If we want to find the iteration & that satisfies minigisa [V S e, we upper bound 23 by and we conclude that
k O
(24)
3/2
Deviation Bounds. Rather than utilizing deterministic gradient and Hessian information, employ estimates of the gradient, the Hessian matrix, and the loss function, which are derived from an independent set of points BR, i.c.,
1
gi:
V[((xa);
(25)
B&
iEB
f((x),
(26)
Byl
SEB
and
F(xx)
Σ f((x)).
(27)
B&
iEB
Assumption 2 (Sufficient agreement ge and fx())). There constant C, > 0 such that the inexact gradient g& satisfies, for all & 0,
gg V/(xx)]lz S Cg |sx12
(28)
For some Xk, the computation of the Hessian matrix Hę dddd in (66) is expensive due to the large size d of Xt. Only the Ressian-voctor. product can be calculated at reasonable computational complexity (Pearl-
mutter 1994). Let H4: Rd + d be function such that H&(v) _ H&V, where H₃ is not accossible. Given the Hessian-vector product operator Hk. the diagonal of H3, i.e., h diag(H;), is approximated by the Hutchinson's method as Bekas et al. (2077)
b; Helvs) ov.
Σ v. V.
E
Ha(v.)ov.en
(29)
where V, Rademacher(0.55 and S is the number of random vectors used in the approximation. Thus, the diagonal approximate Hessian matrix B, E Raxd is given by
B A Diag(ba)
1 S
Diag (H+(v))
(30)
==1
The approximate Hessian matrix 300 is used in the description of Algorithms and in Section It is worth ioting that in the code implementation of Algorithms and oonly the diagonal of Bg is computed, which reduces the memory cost from d x d to d.

---

Published in Transactions on Machine Learning Research (02/2026)
Assumption 3. There is constant CB > 0 such that the ineract Hessian By satisfies, for all 2 0,
[B - Diag (V)x()))())))] S CB 1|su|22
(31)
By replacing Vx(x)) and (xx( with ge and By we get
1 s² mar(s) A F(xx) gf s + 2
M |ss|
S
(32)
Note that the conditions under which Vx(x)) and (x5(xx) can be substituted with gx and Bg are detailed
in Lemmata and respectively.
Let (SK+1, M be the output of Algorithm for B B g = gk, and on. Algorithm 2 is called in line 3
of Algorithm] [ Then, recall that (Sk+1, Mk++) is minimizer of ( and according to Theorem is also minimizer of problem (5) for M Mk41- The first- and second-order optimality conditions
sk+1 V.MM=n+ (SL+1) =0
(33)
and
T
V2ma=ua (Sk+1) 8K+1 2 20,
V (S
(34)
k++
get us to Lemma Corollary 2
Lemma
3
exploited to prove Lemma
Lemma used by Lemmata 5 and
Lemma 3 (Approximate model minimizer). Let
S4+1 arg min ms)s). SERd
(35)
Then, the following statements hold
M
8k + B₁ Sk41
||8++1l|884+ 8:+1 = 0,
(36)
2
M
B& +
|| I 0,
(37)
2
and
+ M
M
g sk41 + S B& sk+
|
|
(38)
2
6
12
Recall that Xt+1 X3. St+1 and from Theorem 2 M
Vk+1
Proof. The reader is referred to Wang et al. 2019 Lemma 3).
Lemma 4. Let {F(x)) be bounded from below by Flow Also, let 8t+1 satisfy the first two conditions in Lemma and let be bounded from below by some Mlow Then
|| + 0, as + 0o.
(39)
Proof. First, note that by Assumption 1 F(x) is also bounded from below by some Flow, Additionally, since M bounded from below and M Vk+1, as indicated in Theorem 2 Vx+1 is also bounded from below. The lower bound of M further discussod in Lemma
in Appendix B.11
Following similar lines to Cartis et al. (201aa) Lemma 5.1), focus the sub-sequence of successful
iterations, in (Cartis et al. 2011a Conn et al. 2000 Thus, from the successful iteration in Algorithm i.., when Pk: T2), we have
F(xx) F(x411) 2 (F(()) MM= (8k+1))

---

Published in Transactions on Machine Learning Research (02/2020)
71
gi
T
Sk+1
1 T
sk+1
B₁ 8k+1
M
||
(40)
2
which by applying 38 yields
MMlow
F(xx) - F(xx+1) 2 7h
|sk+1112
(41)
12
Summing over all iterates from 0 to k - in 41
we obtain
F(xo) F(xx-1) 2
71 M low
ss l12
(42)
which taking into account that (F(xt)) is bounded below yields
12
Mlow (F(xo) - FFlo))
(43)
Thus, the series Ek=0 ||s2l|2 is convergent and 39 holds.
The same conclusion is also derived in CCrtis
ct al.
2011a Lemma 5.1).
Lemma 5. Let the approcimate gradient gx be computed on a set of points B with cardinality [B For
1+
2 4
we have with high probubility 1 - that
B
Igg vf(xx)ll2 Se.
(44)
In addition, is
In _ + 02 || 1
[ 2 321,
(45)
and Lemma 4 holds, ge satisfies Assumption
Proof. The proof can be found in Appendix B.5
Lemma 6. Let the approoimale diagonal Hessian matria By be compuled on a set of points B with In cardinalily |B |. For 2 vdlggggA we have with high probabilily 1-6 8 that
BB - Diag 2 [(xx))]12 Se.
(46)
In addition, if
In
|B 2 v dT. g s Ss l1 CB
(47)
and Lemma 4 holds, By satisfies Assumption
Proof. The proof can be found in Appendix B.6 Corollary 2. If
In 2d o
B& 2 max 32L
vol, S | 1l2 CB
(48)
C2 1|
then and Bg satisfy Assumptions
2 and with probability 1 - 6, for E (0.

---

Published in Transactions on Machine Learning Research (02/2026)
Proof. We combine the results of Lemma 5 and Note that ||sk-1l| is used instead of ||s&||- Due to Lemma 4
| I ||sk=lll2 + || 2 ||:-1 This modification is useful for the practical application of the sampling schemes. However, this poses a challenge since Cg. Cи, Ly, and Lg are not easily accessible.
& imply that the sample size eventually equal to the entire sample size n as Algorithm converges. Thus we have
Remark Lemma and Corollary
VX(x)) and Bg + ((ag(()((xx)) as k + co.
(49)
This allows us to invoke the deterministic local convergence guarantees k in Theorem 3 stochastic first- and second-order information from gi and B, is used.
However,
4 Algorithmic Solution
In Theorem it was shown that the optimal (=",r") solving max,20, rED, Le(v,r) is used in 18 to compute the minimizer of 77 To solve 7 and compute (v","*) Algorithm and are utilized, respectively. In particular, Lemma employed in Algorithm which essential for calculating the values of v and y*
Let VSI, SI, and UI stand for the Very Successful, Successful, and Unsuccessful Iteration, respectively, in Algorithm (Conn et al. 2000 Section 6.1). Denote \ (Bx) as the minimal non-negative diagonal shift that makes B₃ sufficiently positive definite to allow a stable computation of the TR step. Details on the selection x (Bx) in Algorithm can found in Conn et al. (2000) Section 7.3.11) and (Gould et al. 1999).
Lemma 7 (Proof in Appendix B.7 7
The optimal values v² and r" achieving
220, rED, Lz(urr)
(50)
are given by r" = V/E and by solving
1
p(v" ,(v",r*)= ||s("* r
0,
(51)
V
w.r.t. v", respectively.
Next, we clarify the role and physical interpretation of the ADACUBIC hyperparameters as they appear in Algorithms and
(acceptance threshold). 7n E 1) is the minimum ratio between the actual loss reduction and the predicted reduction of the cubic model required to accept a step. If Ps 2 Th the step is considered successful and the parameters are updated. This parameter 7) controls how cautiously the algorithm accepts update steps. Smaller values make acceptance easier, while larger values enforce stricter agreement between the cubic model my (Sx+1) and the objective function F(x; + 8k+1).
Ti2 (very successful threshold). n2 2 7 identifies very successful iterations. When Pk 2 172 the effective trust-region boundary is expanded, allowing larger steps in subsequent iterations. This mechanism accelerates convergence when the cubic model m (Sk-1) is highly accurate.
an (expansion factor). an 2 1 controls the increase of the trust-region parameter & after very successful iterations, thereby expanding the effective trust-region boundary.
02 (shrinkage factor). 02 10 decreases the trust-region boundary after unsuccessful iterations (Pk S m) By shrinking the trust-region boundary, more conservative updates are obtained, thereby improving robustness in regions where the cubic model m (s) is less accurate.

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm AuBiiIC algorithm
1: Set Ek 4- 1, Keeas E (0, 0 < 02 < - 01, and < m S m2 <
2: repeat
Dr k-th itcration, 0, 1....
The function P, BR, and gi are evaluated on the same batch.
b ROOTFINDER is Algorithm 2
Sk+1, Me+1 RooTF INDER B k. gK, Ek, Heass)
Compute Pk using
F(Xx) F(x: + Sk+1)
Pk F(xx) my44s (Sk+1)
if Pk 2 7 then
X X₁. + B/+1
7: else
8:
Xb+1 t X end if
9:
10:
Update &N using
max an [|8 12 Eej
if ph 122
VSI
Ek+1
keep the same Ek max Oz ||s Cm
pv (m,
S1
px - m
A UU
where 6n x 10-6
11: until execution stops (e.g,, afler a specific number of training epochs)
Algorithm 2 Find model minimizer
procedure RoorFINDER(BB g, Kieasy)
(,
Set V
3: if B is positive definite then
4:
0+0
5:
else
>
For some X (B) barely smaller than AB(
6:
v - 2 (B)
7:
end if
Compute s = -B +
g
if [ss|l² S then
10:
if B is positive definite or |s|| = then return s,
11:
12:
else
13:
Compute the eigenvector ua that corresponds to the eigenvalue Aa(B). Then find the root a of the equation ||s + a uall2 el/s which makes the model m. + ua) the smallest. return s + un //
14:
15:
end if
16:
end if
The following, produces and 1²* in Lemma !
while ||i||| c1/3 & Reasy gl/3 do
17:
By Remark 3 increases.
18:
/ ( (/)r 0,
19:
== - (B v
20: end while
21: return s, V
22: end procedure

---

Published in Transactions on Machine Learning Research (02/2026)
Heasy (root-finding tolerance). Rieasy E (0, 1) specifies the error tolerance to terminate the Newton iterations when solving the cubic subproblem in Algorithm Keasy determines how close the norm of the computed slep should be to the trust-region boundary before the termination of the dual variable calculation. Smaller values enforee higher accuracy in solving the subproblem, while larger values favor computational efficiency.
Overall, ?i and 72 govern step acceptance, ai and a2 regulate updates of the trust-region boundary, and Keasy balances accuracy and efficiency in the inner solver of Algorithm 2 ADACUBIC adaptively computes the dual parameter Mk+1; which determines the step Sk+1, the acceptance ratio Pk; and consequently the evolution of the trust-region parameter &x- The dual variable Me+1 encodes local curvature information through the Hessian approximation and acts as an adaptive term in the cubic subproblem. This relationship enables an automatic adjustment of Ex: allowing ADACUBIC to respond effectively to the local geometry of the non-convex loss landscape and to achieve competitive performance across the benchmarks Section 3
5 Experimental Evaluation
Experiments are conducted on computer vision, natural language processing, and signal processing tasks, where the results obtained with the proposed AdACudiC optimizer are compared with those obtained with the SGD, ADAM, and ADAHESSIAN optimizers. The natural language processing experiments are conducted using the Hugging Face Transformers library (Wolf et al. 2020). For SGD, ADAM, and ADAHESSIAN, the Learning Rate (LR) is fine-tuned. For ADACUBIC, the parameters
0.05, = 0.75, 2.5, a2 = 0.25, and Keasy = 0.01 are chosen universally in the experimental evaluation. These parameters are chosen based on the analysis in (Conn et al. 2000 Section 17.1). Table summarizes the universal hyperparameter values used by ADACUBIC across all benchmarks.
Table 1: Universal ADACUBIC hyperparameter settings. All hyperparameters in Algorithm 2 are fixed across benchmarks. cm denotes numerical safeguard used in Algorithm
AUBIUBIC Hyperparameters
Hy Hyperparameter
1/2
0:2
Keass
Assigned Value
0.05
0.75
2.5
0.25
0.01
10-6
Tables 2 and 3 summarize the experimental configurations for each benchmark, including datasets, model architectures, optimizers, and LR settings.
Table 2: Summary of model architectures, training settings, and optimizers used in all experiments.
Task
Dataset
Model
Batch
Epochs
Optimizers
CIFAR-10
Resllet20/ ReaNett3
256
500
SGD, ADAM, ADAHESSIAN, ADACUBIC
CV
CIFAR-100
Reslett1
256
200
SGD, ADAM, ADAHESSIAN, ADACUBIC
SST-2, QNLI, RTE, WHLI MRPC, QQP
SqueezeBERT
32
15
SGD, ADAHESSIAN, ADACUBIC
NLU
SqueezeBERT
32
15
SGD, ADAHESSIAN, ADACUBIC
STS-B, MNLI
SqueezeBERT
32
15
SGD, ADAHESSIAN, ADACUBIC
WikiText-2 PTB
RoBERTs
BERT
DistilBERT
SGD, ADAHRSSIAN, ADACuRic
LM
RoBERTa
BERT / DistilBERT
SGD, ADAHESSIAN, ADACUBiC
CMI
VISION
ResNet18
256
100
ADAM, ADACUBIC
Computer Vision (CV). To prove the elfectiveness of ADACUBIC, experiments are conducted using CIFAR-10 and CIFAR-100 datasets (Krizhevsky] (209).. The experimental results are summarized Ta- ble 4 In all experiments, a batch size of 256 used. The mean accuracy and standard deviation (std) over five runs reported for each experiment. The number of epochs used to train the models on CIFAR-10 and CIFAR-100 is 500 and 200, respectively. In addition, the optimizers are fine-tuned w.r.t. the initial LR and the decaying LR scheme. For SGD, ADAM, and ADAHESSIAN, the initial learning rates are 0.1, 0.001, and
12

---

Published in Transactions on Machine Learning Research (02/2026)
Table 3: Summary of LRs used in all experiments. For the CV benchmark, LRs are decayed by a factor of 10 at epochs 80 and 120 on CIFAR-10, and by factor of 20 at epochs 60, 120, and 160 on CIFAR-100. For NLU, LM, and CMI benchmarks, no LR decay is applicd. For CMI, LR is decayed by a factor of 10 at epochs 80 and 120. ADACUBiC is used with a fixed universal parameter set and does not require LR tuning,
Optimizer
Task
(ataset(s)
Initial LR
LR Schedule / Tuning
SGD
CV
CIFAR-10 / CIFAR-100
0.1
Step decay (tuned) Step decay (tuned)
ADAM
CV
CIFAR-10
CIFAR-100
10-3
ADAHESSIAN
CV
CIFAR-10
CIFAR-100
0.15
Step decay (tuned)
ADACUBIC
CV
CIFAR-10 / CIFAR-100
no LR.
Universal parameters
SGD
NLU
SST-2, QNLI, RTE, WNLI
2x10-2
Tuned
SGD
NLU
STS-B
2x10-3
Tuned
ADAHESSIAN
NLU
SST-2, QNLI, STS-B, MNLI
2x10-3
Tuned
ADAHRSSIAN
NLU MRPC, RTE
2x10-1
Tuned
ADAHESSIAN
NLU
WNLI
2x10-2
Tuned
ADACUBIC
NLU
All GLUE tasks
no LR
Universal parameters
SGD
LM
WikiText-22 2, PTB
5x10-3
Tuned
ADASISSIAN
LM
WikiText-2 2 (all models)
5x10-1
Tuned
ADAHESSIAN
LM
PTB (RoBERTa)
5x10
Tuned
ADAHESSIAN
LM
PTB (BERT, DistilBERT)
5x10
Tuned
ADACUBIC
LM
WikiText-2 2, PTB
no LR.
Universal parameters
ADAM
CMI
VISION VISION
10-4
Tuned
ADACUBIC
CMI
no LR.
Universal parameters
0.15. Furthermore, for ADAHESSIAN, 31 and B2 are set to 0.9 and 0.999, respectively. On CIFAR-10, the LR is decayed by factor of 10 at epochs 80 and 120, while on CIFAR-100, the LR is decayed by factor of 20 at epochs 60, 120, and 160. In addition, spatial averaging Yao al.) 2021) is used for ADACUBIC and ADAHESSIAN CIFAR-100. The entries corresponding to the best accuracy are marked in bold. A reports the accuracy differences between ADACUBIC and the strongest competing optimizer in cach setting. When spatial averaging is used, the accuracy is shown in gray.
On the CIFAR-10 dataset, both ADAHESSIAN and ADACUBIC demonstrate higher accuracy than conven- tional optimization methods like SGD and ADAM. It is worth noting that, while both methods excel, ADaHessIAN achieves a slight edge in accuracy over ADACUBiC for ResNet220 and ResNet33 by 0. 15% and 0.5%, respectively. This performance distinction underscores the effectiveness of ADACUBIC and positions it formidable competitor to ADAHESSIAN in enhancing model accuracy on the CIFAR-10 dataset.
On the CIFAR-100 dataset without spatial averaging, ADACUBIC falls behind SGD, ADAM, and ADAHESSIAN by margins of 0.81%, 0.23%, and 0.64%, respectively. However, with spatial averaging, both ADAHESSIAN and ADACUBIC achieve improved accuracy. This comparative analysis highlights ADACUBIC' distinct per- formance characteristics, demonstrating its unique capabilities relative to other optimizers in challenging scenarios, such as the CIFAR-100 dataset.
Figure depicts the training loss of ResNet20 (lop) and ResNet32 (bottom) on CIFAR-10 for ADAM, ADA- HESSIAN, and ADACUBIC optimizers. As can be seen, the losses of ADAM and ADAHESSIAN decrease dramatically at epoch 80, when the LR has decayed by factor of 10. As can be seen, only by using an adaptive LR can the training loss reduction of ADAM and ADAHESSIAN match that of ADACUBIC. In the last epochs, the loss of ADACURIC is lower than that of ADAM and higher than that of ADA It should be noted that, in all experiments, ADACUBIC is used with the same set of parameters and achieves competitive performance compared to the remaining fine-tuned optimizers.
On CIFAR-10, ADACUBIC consistently outperforms first-order methods (SGD, ADAM) and ranks second to ADAHESSIAN, with very small gaps of 0.15% and 0.5% for ResNet220 and ResNet32, respectively, as

---

Published in Transactions on Machine Learning Research (02/2020)
Table 4: Accuracy (%) and std of the accuracy measures for ResNet18820032 models on CIFAR-10 and CIFAR-100 datasets. A reports the gap between the strongest competing optimizer and ADACUBIC.
CIFAR-10
CIFAR-100
ResNet20
ResNet332
ResNet18
SGD
88.52 + 0.24
89.02 + 0.20
72.62 0.002
ADAM
90.26 + 0.19
91.24 + 0.20
72.04 0.13
91.64 + 0.46
93.15 + 0.12
72.45 + 0.16
ADAHESSIAN
72.59 + 0.271
91.49 + 0.46
92.65 + 0.19
71.81 + 0.003
ADACUBIC
72 + 0.337
0.15 0.36
0.5 + 0.07
0.81 + 0.001
A
0.59 + 0.066
Table 5: Figures of merit on GLUE benchmark using SGD, ADAHESSIAN, and ADACUBIC optimizers on natural language understanding tasks. A reports the gap between the strongest. competing optimizer and ADACUBIC
SGD
ADAHESSIAN
ADACUBIC
A
Datasct
Accuracy (%)
S
91.62
90.71
90.71
0.91
QNLI
90.37
89.47
90.01
0.36
RTE
70.39
64.98
70.39
0.00
WNLI
56.33
56.33
56.33
0.00
Fi / Accuracy (%)
MRPC
0.9094
/ 87.25
0.8562 / 78.18
0.9042
86.76
0.0052/0.49
QQP
0.8775
/ 90.89
0.8742 / 90.82
0.8723 90.40
0.0052/0.49
Pearson
Spearman Corr.
STS-B
0.8863 / 0.8845
0.8786 / 0.8735
0.8832
0.8814
0.0031/0.0031
Matched Mismatched Accuracy (%)
MNLI
82.45 / 82.05
81.65 / 81.57
81.88
81.89 0.57/0.16
summarized in Table 4. On CIFAR-100 without spatial averaging, ADACUBIC trails the best-performing optimizer by al most 0.81% %. Due to its larger number of classes and increased classification difficulty, CIFAR- 100 will possibly lead optimization regimes with stronger parameter interactions. Since ADACUBIC, like ADAHESSIAN, relies
diagonal approximation of the Hessian, it does not explicitly capture such off-diagonal curvature elfects, which may partially explain the observed gap. Importantly, when spatial averaging is applied, the performance of ADACUBIC improves and becomes closer to that of ADAHESSIAN and SGD, confirming that part of the gap is related to high-variance curvature estimation.
Natural Language Understanding (NLU). Table summarizes the results on the natural language understanding task. The GLUE benchmark (Wang et al. 2018) used to train the SqueezeBERT (Tandola et al. 2020) model for 15 epochs. For SGD and ADAHESSIAN, the initial LR fine-tuned in all datasets. For SGD, the initial LR is set to 2 10 for all datasets except from STS-B where it is set to 2 10 For ADAHISSNN,, the initial LR is set to 2 10-3 for SST-2, STS-B, MNLI, and QNLI, to 2 10-1 for MRPC and RTE, and to 2 10-2 for WNLI.

---

Published in Transactions on Machine Learning Research (02/202))
Adam
AdaHessian
AdaCubic
0.25
Loss
0.15
0.10
0.05
300
325
350
375
400
425
450
475
500
56
111
167
222
278
333
389
444
500
Epochs
(a)
Adam AdaHessian
2.00
AdaCubic
1.75
1.50
1.25
Loss
1.00
0.05
0.00
0.75
300
325
350
375
400
425
450
475
500
0.50
0.25
0.00
111
167
222
278
333
389
444
500
Epochs
(b)
Figure 1: Training loss curve of ResNet20 (top) and ResNet33 (bottom) on CIFAR-10 ADAM, ADAHES- SIAN, and ADACUBIC optimizers.
The default parameters of the SqueezeBERT model can be found the official Hugging Face library H The dataset acronyms in the Hugging Face library are SST-2, QNLI, RTE, WNLI, MRPC, QQP, STS-B, and MNLI, while the model acronym is equezaaeer/gguuzzzeeee--m-a
To simplify the experimental evaluation, the experiments are divided into four groups, each corresponding to different performance measure. Group consists of the SST-2, QNLI, RTE, and WNLI datascts. Group

---

Published in Transactions on Machine Learning Research (02/2026)
consists the MRPC and QQP datasets, while groups 3 and consist of the SST-B and MNLI datasets, respectively. The entries corresponding to the best metrics are marked bold. A reports the accuracy differences between ADACUBIC and the strongest compeling optimizer in each setting.
Group 1. Concerning accuracy measure, ADACUBIC and ADAHESSIAN demonstrate the same per- formance SST-2, while SGD performs better by 0.91%. On QNLI, SGD outperforms ADACUBIC by 0.36%, while ADACUBIC outperforms ADAHESSIAN by 0.54%. On RTE, ADACUBIC and SGD achieve the same performance, while ADAHESSIAN is outperformed by 5.41%. On WNLI, all optimiz- ers achieve the same performance. Overall, the mean accuracies achieved by SGD, ADaHesSIAN, and AdACubic are 77.17%, 75.37%, and 76.86%, respectively. can observed that, on average, SGD outperforms ADACUBIC by 0.31%, while ADACUBIC outperforms ADAHESSIAN by 1.5%.
Group 2. Concerning F1 mcasure on MRPC, SGD outperforms ADACUBIC by 0.0052, while ADACU- BIC outperforms A HESSIAN by 0.048. On the same dataset, SGD achieves higher accuracy than ADACUBic by 0.49%, whereas ADACUBIC outperforms ADAHESSIAN by 8.58%. Concerning Fi measure on QQP, SGD outperforms ADAHESSIAN by 0.0052, while ADAHESSIAN outperforms ADACCUBIC by 0.0019. On the same dataset, SGD achieves higher accuracy than ADAHESSIAN by 0.07%, while HEAHESSIAN outperforms ADACUBiC by 0.42%. Overall, the mean F1 values achieved by SGD, ADAHESSIAN, and ADACUBIC are 0.89345, 0.8652, and 0.88825, respectively, while the mean accuracies are 89.07%, 84.5%, and 88. 38.58%. respectively. This way, on average, SGD outper- forms ADACUBIC by 0.0052 and 0.49% on Fi and accuracy measures, respectively, while ADACUBIC outperforms ADAHESSIAN by 0.02305 and 4.08%, respectively.
Group 3. Concerning Pearson correlation index, SGD outperforms ADACUBIC by 0.0031, while ADACUBIC outperforms ADAHESSIAN by 0.0046. Regarding the Spearman correlation index, SGD outperforms ADACUBic by 0.0031, while ADACUBIC outperforms ADAHRSSIAN by 0.0079.
Group 4. Concerning matched accuracy (Wang al. 2018), SGD outperforms ADACuBic by 0.57%, while ADACUBIC outperforms ADAHESSIAN by 0.23%. Concerning mismatched accuracy (Wang ct al. 2018), SGD outperforms ADACUBIC by 0.16%, while ADACUBiC outperforms ADAHESSIAN by 0.32%.
It is worth noting that ADACUBIC exhibits the second-best performance with a pre-fixed universal set of parameters, while SGD and ADAHESSIAN are fine-tuned w.r.t. the initial LR.
Language Modeling (LM). Tables and summarize the results on the language modeling, where perplex- ity (Jelinek al. 1977 is used as an evaluation metric. PTB (Marcus al. 1994] and wikitext-2 (Mer- ity et al. 2017 7 datasets used to train RoBERTa (Liu et al. 2019), BERT (Devlin et al. 2018 and
DistilBERT (Sanh el al. 2019 models with SGD, ADAHESSIAN, and ADACUBIC optimizers.
Table 6: Perplexity achieved by SGD, ADAHESSIAN, and ADACUBiC on wikitext-2 dataset.
Optimizer
RoBERTa
BERT
DistilBERT
SGD
3.547
13.380
6.118
ADACUBIC
3.756
5.759
6.565
ADAHESSIAN
4.374
16.151
6.822
Table 7: Perplexity using SGD, ADAHESSIAN, and ADACUBiC on the PTB datasct.
Optimizer
RoBERTa
BERT
DistilBERT
SGD
4.345
17.344
8.299
ADACUBIC
5.145
14.170
7.334
ADAHESSIAN
7.582
20.851
10.182

---

Published in Transactions on Machine Learning Research (02/2026)
The initial LR of SGD is fine-tuned to 5 10-3 for all models and both datasets. For ADAHESSIAN, the initial LR is fine-tuned to 5- 10 4 for all models on wikitext-2 dataset. On PTB dataset, the initial LR of ADA HESSIAN optimizer is set to 5-- to train RoBERTa model, while the remaining models are trained with initial LR 5-10-4, The remaining parameters for the trained models can be found in the official Hugging Face library The dataset acronyms in the Hugging Face library pcb_teet_____ only and wikitext-2-rav-1 In contrast, the model acronyms are roberta-base bert-base-casen and bistilbert-bas--neee
4.6
18
7.75
AdaHlsssian
SGD
4.4
16
7.50
AdaCubic
SCD
Deslinsty
14
7.25
7.00
AdaCubic
10
3.8
6.50
AdaHessian
3.6
AdaCubic
6.25
4
5
Epochs RoBERTs
Epechs
Epocts
(b) BERT
(c) DistilBERT
Figure 2: Perplexity vs. epochs for RoBERTa, BERT, and DistilBERT models on wikitext-2 dalaset.
22
20
AdeCubic
Adah
24
AdaHessian AdaCubie
13
AdaHessian
AdaCubie
12
Nepiisity
9-
Perplesly
22
Purplasity
31
8
20
10
2.
6-
5-
14
Epochs
Epechs
(a) RoBERTs
(b) BERT
(c) DistilBERT
Figure 3: Perplexity vs. epochs for RoBERTa, BERT, and DistilBERT models on PTB dataset.
First, the perplexity measurements gathered for the wikitext-2 2 dataset in Table b are discussed. When RoBERTa is used, SGD outperforms ADACUBIC and ADAHESSIAN by 0.209 and 0.827, respectively. Next, when BERT is used, ADACUBIC outperforms SGD and ADAHESSIAN by 7.621 and 10.392, respectivcly. For the DistilBERT model, SGD outperforms ADACUBIC and ADAHESSIAN by 0.447 and 0.704, respectively. We observe that in all models, ADACubiC outperforms ADAHESSIAN and performs better or competitively when compared to SGD. Figure depicts the perplexity metric vs. epochs for all models and optimizers the wikitext-2 dataset.
Table 7 gathers perplexity measures on the PTB dataset. When RoBERTa is used, SGD outperforms ADACU- BIC and ADAHESSIAN by 0.8 and 3.237, respectively. For the BERT model, ADACUBIC outperforms SGD and AeaHeSSIAN by 3.174 and 6.681, respectively. For the DistilBERT model, AdACUBiC outperforms SGD and AESSESIIAN by 0.965 and 2.848, respectively. Figure depicts the perplexity metrie vs. epochs for all models and optimizers on the PTB dataset.
On the NLU benchmark, Table 5 ADACUBIC consistently achieves either the best the second-best perfor- mance across all tasks, with the performance gaps reported in the A column remaining small. The second-best performance of ADACUBIC on certain GLUE tasks can be understood in light of recent Hessian-based anal- yscs of Transformers (Zhang et al. 2024 In particular, Zhang et al. 2024) shows that Transformer models
https://github.coo

---

Published in Transactions on Machine Learning Research (02/2026)
exhibit block-wise heterogeneity in their Hessian structure, with strong curvature differences and interactions across parameter groups. While ADACuBIC explicitly leverages second-order information through diagonal Hessian approximations, such approximations may be insufficient. to capture cross- paramerr or block-level curvature interactions fully. This likely explains why ADACUBIC remains highly competitive but does not consistently outperform finely tuned baselines on Transformer-bases tasks. Similar conclusions hold for the LM benchmark, where ADACUBIC consistently achieves either the best or second-best, performance across all datasets.
Overall, it should be noted that ADACUBIC exhibits the best or second-best performance with a pro-fixed universal set of parameters, while SGD and ADAHESSIAN are fine-tuned w.r.t. the initial LR.
Camera Model Identification (CMI). The publicly available VISION dataset (Shullani al. 2017 is utilized for camera model identification. VISION includes 648 Native vidcos, which remain unaltered post- capture by the camera. These Native videos were disseminated via social media platforms such YouTube and WhatsApp, with corresponding versions included in the dataset. Of the 684 Native videos, 644 were shared via YouTube and 622 via WhatsApp. Additional details on VISION can be found in (Shullani et al. 2017). Taking into account the VISION dataset naming conventions outlined in Shullani et al. (2017). videos captured by devices D04, D12, D17, and D22 are excluded due to issues encountered during frame extraction or audio track retricval.
Table 8: CMI accuracy (%) using ResNet18.
ADACUBIC
ADAM
Native
WhatsApp
YouTube
Native
WhatsApp
YouTube
Fold 0
97.40
96.10
94.59
96.10
93.50
91.9
Fold 1
93.51
93.51
93.24
94.80
90.90
93.24
Fold 2
94.81
92.22
94.59
90.90
88.31
95.94
Fold 3
93.42
93.43
91.89
93.42
94.73
82.43
Fold 4
94.73
88.16
93.24
94.73
88.15
95.94
Mean
94.77
93.68
93.51
93.99
91.11
91.89
+ std
1.43
+ 2.59
1.01
+ 1.76
+ 2.66
+ 4.98
The videos are partitioned into training, testing, and validation sets to conduct a typical five-fold strati- fied cross-validation. The audio content from each video is extracted, and the log-Mel spectrogram of each extracted audio is computed using three distinct windows and hop sizes. This results in 3-channel log-Mel spectrograms that capture various frequency details of the audio content. The 3-channel log-Mel spectro- grams are then fed into ResNet18 to perform CMI. Furthermore, for ADAM, An and f2 are set to 0.9 and 0.999, respectively. The LR is decayed by a factor of 10 at epochs S0 and 120 with an initial value 10-4
Table summariize the results when ADACUBIC and ADAM optimizers are used. The mean accuracy achieved using ADACUBIC in the Native, WhatsApp, and YouTube benchmarks is 94.77%, 93.68%, and 93.51%, re- spectively. In comparison, the mean accuracy with ADAM is 93.99% for Native, 91.11% 11% for WhatsApp, and 91.89% for YouTube. This indicates that ADACUBIC is more accurate than ADAM by 0.78%, 2.57%, and 1.62% in the Native, WhatsApp, and YouTube benchmarks, respectively. In terms of std, ADACUDIC demon- strates greater consistency than ADAM by achieving lower std values 0.33, 0.07, and 3.97 in the Native, WhatsApp, and YouTube benchmarks, respectively. Implementation details for the audio CMT task can be found in (Tiingalis al.] 2024).
6 Computational Complexity and Discussion
The performance and time complexity of the second-order methods depend on the approximation of the second-order information captured by the Hessian matrix. Similarly to ADAHESSIAN, ADACUBIC leverages the Hutchinson method (Bekas et. al. 2007| to approximate the diagonal of the Hessian matrix. Figure depicts the time complexity of SGD, ADAHESSIAN, and ADACUBIC when they are used to train ResNet20

---

Published in Transactions on Machine Learning Research (02/2026)
200
SGD
AdaHessian
Cumulative Time (min)
AdaCubic
150
100
50
23
45
67
89
111 Epochs
133
155
177
200
Figure 4: Cumulative time vs. epochs for SGD, ADAHESSIAN, and ADACUBIC for ReaNet20 on CIFAR-10.
SGD
SGD
AdaHessian
AdaHessian
3.0
AdaCubic
3.0
AdaCubic
Target loss
0.15
Training Loss
2.5
Training Loss
2.5
1.5
1.5
1.0
1.0
0.5
0.5
10
40
60
70
20
60
100
Cumulative Time (min)
Epochs
(a) Cumulative time vs, loss
(b) Training loss vs. epochs
Figure Comparison of SGD, ADAHESSIAN, and ADACUBIC on ResNet20 and CIFAR-10. Training loss vs. cumulative time over epochs (Left). Training loss vs. epochs (Right).
CIFAR-10. As be scen, the time complexity of the first-order optimizer SGD is smaller than that of the two second-order optimizers, with ADACUBIC having less time complexity than ADAHESSIAN
Figure 5a shows the training loss vs. cumulative time for SGD, ADAHESSIAN, and ADACUBIC. Figure 5b shows the training loss vs. epochs for SGD, ADAHESSIAN, and ADACUBIA The training loss in Figure 5b corresponds to that in Figure 5a The horizontal dashed line Figure 5a marks the targel loss threshold of 0.15. ADACUBIC reaches this threshold after epochs and 42.40 minutes. In comparison, SGD and ADAHESSIAN require 83 and 81 epochs, corresponding to 35. 36.16 and 61.85 minutes. Table 9 summarizes the latter results. Although ADACUBIC needs more time than SGD due to computation of the second-order information, ADA CUBIC reaches the desired loss in fewer epochs without any LRR tuning. This highlights DUACUIIC as an efficient trade-off between computational cost and convergence quality.

---

Published in Transactions on Machine Learning Research (02/2026)
Table 9: Execution time in minutes required to reach a larget loss threshold when ResNet20 is trained on CIFAR-10.
SGD
ADAHESSIAN
AdACubiC
Epoch
Time
Epoch
Time
Epoch
Time
Result
83
35.16
81
61.85
55
42.40
Additionally, storing the Hessian matrix increases the memory consumption of any second-order optimizer. Using Hutchinson's 's method for approximating the diagonal of the Hessian, the second-order information is represented by the diagonal approximation of the Hessian matrix, which leads to ( memory com- plexity (Bekas et al. 2007). This additional memory cost is incurred by ADACUBIC relative to first-order methods such as SGD.
Furthermore, when utilizing Bekas et al. 2007), the approximation of the diagonal of the Hessian demands an additional gradient back-propagation. The additional gradient back-propagation step also needed HESSIANI.N. When comparing ADACUBIC with ADAM, the latter shares similar memory consumption due the requirement of the gradient momentum term, but it does not necessitate additional gradient brok-prro.g.tion.
Table 10: Comparison of optimization methods used in the experimental evaluation. Recall that d denotes the number of model parameters and S the number of random vectors used in the diagonal Hessian approx- imation.
Optimizer
Order
Sensitivity
Extra Backward Pass
Time Cost
Memory Footprint
SGD
First
High
No
d
ADAM
First
High
No
3d
ADAHESSIAN
Second
Medium
Yes
S d
4d
ADACUBIC
Second
Low
Yes
Sd
2d
Table 10 summarizes the optimization methods used in the experimental evaluation, highlighting their opti- mization order, sensitivity to hyperparameters, and computational overhead. The "Order" column indicates whether an optimizer relies on first- or second-order information. The sensitivity of the optimizers w.r.t. the LR is summarized in the "Sensitivity" column. The sensitivity of SGD, ADAM, and ADAHESSIAN w.r.t. the LR discussed thoroughly in (Yao et al. 2021]. ADACUBIC has low sensitivity, as it achieves competitive performance with a universal set of hyperparameterss. The "Extra Backward Pass" column indicates whether additional back propaaatoogtn steps are required per optimization iteration, which directly relates to the use of second-order information. The reported time cost is dominated by the back-propagation procedure and is expressed as a function of the number of model parameters d. Recall that S is the number of random vectors used in the approximation of the diagonal Hessian matrix. Using S random vectors requires S backpropagation steps, increasing the time cost linearly. The "Memory Footprint" refers to the memory needed to store the gradient, the moment lerms, and the approximated diagonal Hessian. As can be seen, the memory footprint of ADAM and ADAHESSIAN is 3d and 4d, respectively, as the gradient and moments need memory relative to the number of parameters d. ADA needs an additional memory footprint of d for the storage of the approxinale diagonal Hessian. ADACUBiC shows 2d memory overhead relative to SGD, since the gradient must be retained to compute the Hutchinson-base approsimation of the diagonal Hessian, which is subsequently used by Algorithum 2
However, according to Algorithun 2 ADACUBIC requires only the approximated diagonal Hessian for its updates, yielding a theoretical memory footprint of (d). The gap between practical and theoretical memory costs comes from the design of modern deep-learning frameworks, such PyTorch, which are optimized for first-order optimization methods. Thus, computing the diagonal Hessian approximation requires retaining intermediate gradient information. Developing custom implementation that directly computes the diagonal Hessian without storing such intermediates is beyond the scope of this work.

---

Published in Transactions on Machine Learning Research (02/2020)
7 Conclusions
ADACUBIC, a novel adaptive cubic regularized second-order optimizer, has been proposed. ADACUBIC leverages an approximate Hessian diagonal reduce the computational cost induced by estimating curvature information. Although many cubically regularized methods have been proposed in the literature, none have been extensively tested in practical deep-learning applications. The effectiveness of the proposed optimizer has been retonstrated through experiments computer vision, natural language processing, and signal processing tasks that utilize deep neural networks trained on various datasets. With a pre-fixed universal selection of parameters, ADACUBIC exhibits better or competitive performance when compared to other state-of the- fine-tuned optimizers. This fact makes ADACUBIC an attractive solution for optimizing deep neural networks.
Acknowledgments
This work was supported by the Hellenic Foundation for Research and Innovation (HFRI) under the HFRI PhD Fellowship grant (Fellowship Number: 1376) and the "2nd Call for HFRI Research Projects to support Faculty Members & Researchers" (Project Number: 3888). The results were obtained using the High- Performance Computing Infrastructure and Resources of Aristotle University of Thessaloniki (AUTh). The authors would like to acknowledge the support provided by the IT Center of AUTh throughout the progress of this research work.
References
Z. Allen-Zhe and Y. Li. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, volume 31, 2018.
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than SGD. In Advances in Neural Information Processing Systems, volume 31, 2018
Zeyuan Allen-Zhu and Flad Hazan. Variance reduction for faster non-convex optimization. In Proc. Int. Conf. on Machine Learning, pp. 699 707, 2016.
Amrit Singh Bedi, Ketan Rajawat, Vancet Aggarwal, and Alec Koppel. Escaping saddle points for successive convex approximation. IEEE Transactions on Signal Processing, 70:307 321, 2021.
Costas Bekas, Effrosyni Kokiopoulou, and Yousef Saad. An estimator for the diagonal of a matrix. Applied Numerical Mathematics, 57(11-12):1214 1229, 2007.
Dimitri P Bertsekas. Nonlinear Programming, 3rd. Athena Scientific Belmont, 2017.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic
Theory of Independence. Oxford University Press, 2013.
Stephen Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2004.
Yair Carmon and John Duchi. Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM Journal on Optimization, 29(3):1446 2178, 2019.
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 Programming, 127()):245-22)) 295, 2011a.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for un- constrained optimization. Part II: worst-case function-ane derivative-evaluation complexity. Mathematical Programming, 130(2):295-3144 2011b.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Faster perturbed stochastic gradient methods for finding local minima. In Proc. Int. Conf. on Algorithmic Learning Theory, pp. 176 204, 2022.
21

---

Published in Transactions on Machine Learning Research (02/2026)
Andrew R Comn, Nicholas IM Gould, and Philippe Toint. Trust Region Methods. STAM, 2000.
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Innokentiy Shibaev. Recent theoretical advances in non-convex optimization. In Highh- Dimensional Optimization and Probability, pp. 79-163. Springer, 2022.
Shaveta Dargan, Munish Kumar, Maruthi Rohit Ayyagari, and Gulshan Kumar. A survey of deep learn- ing and its applications: A new paradigm to machine learning. Archives of Computational Methods in Engineering, 27(4)1001--192, 2020.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcchre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non- convex optimization. In Advances in Newral Information Processing Systems, pp.
2014.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirec- tional transformers for language understanding. CoRR, 2018.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimiza- tion via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, volume 31, 2018.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Proc. Conf. on Learning Theory, pp- 797-842. PMLR, 2015.
Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang. Stabilized SVRG: Simple variance reduction for nonconvex optimization. In Proc. Int. Conf. on Learning Theory, pp. 1394-1448, 2019.
Gene H. Golub and Charles F Van Loan. Matris Compulations. Johns Hopkins Press Baltimore, 2012.
Nicholas IM Gould, Stefano Lucidi, Massimo Roma, and Philippe L Toint. Solving the trust-region subprob- lem using the Lanczos method. SIAM Journal on Optimization, 0(2):504-522) 1999.
David Gross, Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):1548 1566, 2011.
Christopher J Hillar and Lek-Heng Lim. Most tensor problems are NP-Hard. Journal of the ACM, 60(6): 1-39, 2013.
Kevin Huang, Junyu Zhang, and Shuzhong Zhang. Cubic regularized newton method for the saddle point models: A global and local convergence analysis. Journal of Scientific Compuling, 91(2):1-31 2022.
Forrest N. Tandola, Albert F. Shaw, Ravi Krishna, and Kurt W. Keutzer. Bque What computer vision teach NLP about efficient neural networks? arXiv preprint arXiv:2006.11314 11316 2020.
Majid Jahani, Sergey Rusakov, Zheng Shi, Peter Richtárik, Michael W Mahoney, and Martin Takáč. Doubly adaptive scaled algorithm for machine learning using second-order information. In Proc. Int. Conf. on Learning Represenlations, 2021.
Fred Jelinek, Robert L Mercer, Talit R Bahl, and James K Baker. Perplexity- measure of the difficulty of speech recognition tasks. The Journal of the Acoustical Society of America, 62(S1):S63 S63, 1977.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proc. Int. Conf. on Machine Learning, pp. 1724-1732, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM, 68(2):1 22, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. Int. Conf. Learning Representations, 2015.
22

---

Published in Transactions on Machine Learning Research (02/2026)
Marius Kloft, Ulf Brefeld, Pavel Laskov, Klaus-Robert. Müller, Alexander Zien, and Sören Sonnenburg. Efficient and accurate 4y-norm multiple kernel learning. Advances in Neural Information Processing Systems, pp. 997 1005, 2009.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. In Proc. Int. Conf. on Machine Learning, pp. 1895-1904, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Kfrr Levy, Ali Kavis, and Volkan Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. In Advances in Newral Information Processing Systems, volume 34, pp. 20571 20582, 2021.
Zhize Li. SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. In Aduances in Newral Information Processing Systems, volume 32, pp. 5956-5965, 2019.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized bert pretraining approach. arXiv preprint vrXtc:1977.1699. 2019.
Mitch Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Trecbank. Using Large Corpora, 273, 1994.
Stephen Mcrity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In Proc. Int. Conf. on Learning Representations, 2017.
Katta G Murty and Santosh Kabadi. Some No-copleete problems in quadratic and nonlinear program- ming. Mathemalical Programming, 39(2):117-12g) 1987.
Yurii Nesterov. Leclures on Conves Oplimization, volume 137. Springer, 2018.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, (08(1):177-2088 2006.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: novel method for machine learning problems using stochastic recursive gradient. In Proc. Int. Conf. on Machine Learning, pp. 2613 1621, 2017a.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprinl arxiv:1 072607 2017b.
Seonho Park, Seung Hyun Jung, and Panos M Pardalos. Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization. Journal of Optimization Theory and Applications, 184(3):953-9) 2020.
Barak Pearlmutter. Fast exact multiplication by the Hessian. Neural Computation, 6(1):147-160, 1994.
Omead Pooladzandi, David Davini, and Baharan Mirzasoleiman. Adaptive second order coresets for data- efficient machine learning. In Proc. Int. Conf. on Machine Learning, pp. 17848-17869, 2022a.
Omead Pooladzandi, David Davini, and Baharan Mirzasolciman. Adaptive second order coresets for data- efficient machine learning. In Proc. Inf. Conf. on Machine Learning, pp. 17848 17869, 2022b.
Samira Pouyanfar, Saad Sadiq, Yilin Yan, Haiman Tian, Yudong Tao, Maria Presa Reyes, Mei-Ling Shyu, Shu-Ching Chen, and Sundaraja Iyengar. A survey on deep learning: Algorithms, techniques, and applications. ACM Computing Surveys, 51 (5):11333, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400 407, 1951.
23

---

Published in Transactions on Machine Learning Research (02/2026)
Clément W Royer and Stephen J Wright. Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM Journal on Optimization, 28(2):1448 1477, 2018.
Abdurakhmon Sadiev, Alcksandr Beznosikov, Abdulla Jasem Almansoori, Dmitry Kamzolov, Rachaol Tap- penden, and Martin Takáč. Stochastic gradient methods with preconditioned updates. arXiv preprinl arXiv:2206.0082 002885 2022.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. ArXiv, abs Abs/1910.01108, 2019.
Dasara Shullani, Mareo Fontani, Massimo Iuliani, Omar Al Shaya, and Alessandro Piva. Vision: A video and image dataset for source identification. EURASIP Journal on Information Security, 2017:1-16, 2017.
Tao Sun, Dongsheng Li, Zhe Quan, Hao Jiang, Shengguo Li, and Yong Dou. Heavy-ball algorithms always escape saddle points. In Proc. Int. Joint Conf. on Artificial Intelligence, pp. 3520 3526, 2019.
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochastic cubic regulariza- tion for fast nonconvex oplimization. In Advances in Neural Information Processing Systems, volume 31, 2018.
Toannis Tsingalis, Christos Korgialas, and Constantine Kotropoulos. Camera model identification using audio and visual content from videos. arXiv preprint arXiv:2206. 179166406.11916,, 2024.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science, vol- une 47. Cambridge University Press, 2018.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proc. of Empirical Methods in Natural Language Processing Workshop, pp. 353-355, 2018.
Jun-Kun Wang, Chi-Heng Lin, and Jacob Abernethy. Escaping saddle points faster with stochastic momen- tum. In Proc. Int. Conf. on Learning Representations, 2020a.
Jun-Kun Wang, Chi-Heng Lin, and Jacob Abernethy. A modular analysis of provable acceleration via Polyak's momentum: Training wide ReLU network and a deep linear network. In Proc. Int. Conf. on Machine Learning, pp. 10816-10827, 2021a.
Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan. A note on inexact gradient and hessian conditions for cubic regularized newton's method. Operations Research Letters, 47(2):146-133 2019.
Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan. Cubic regularization with momentum for non-convex optimization. Proc. Uncertainty in Artificial Intelligence, pp. 313 322, 2020b.
Zhiguo Wang, Jiawei Zhang, Tsung- Hui Chang, Jian Li, and Zhi-Quan Luo. Distributed stochastic con- sensus optimization with momentum for nonconvex nonsmooth problems. IEEE Transactions on Signal Processing, 69:4486-4501, 2021b.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, et al. Transformers: -hate-of-the-Art Natural Language Processing. In Proc. Conf. on Empérical Methods in Natural Language Processing: System Demonstrations, pp. 38 45, Association for Computational Linguistics, 2020.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney. Ada- Hessian: An adaptive second order optimizer for machine learning. In Proc. AAAI Conf. on Artificial Intelligence, pp.
2021.
Chenyi Zhang and Tongyang Li. Escape saddle points by simple gradient-descent based algorithm. Tn Advances in Newral Information Processing Systems, volume 34, pp. 8545 8556, 2021.
24

---

Published in Transactions on Machine Learning Research (02/2026)
Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhiquan Luo. Why transformers need ADAM: Hessian perspective. Advances in Neural Information Processing Systems, 37:131786 131823, 2024.
Dongruo Zhou and Quanquan Gu. Stochastic recursive variance-roduced cubic regularization methods. In Proc. Inl. Conf. on Arlificial Intelligence and Stalislics, pp. 3980 3990, 2020.

---

Published in Transactions on Machine Learning Research (02/2026)
A Summary of Dependencies
Corollar
Lenuataa
Lemmata
Lammnn 1
Algorihuu P
Theocen 1
Lemna x
Lemma !td
Lecama t
Leuamnta
Conillrry
Lamno
Conollary
Tamma B
Tamms S
Theeemn
Lamnn
Loman i
Theeeun g
Lemmnn
Leunnn g
Leamns
Leunun
Caroilury
Lecura 28
Leanna
Lemmata
Thanren
Lennat: 1
Aempptin
Chcollas
Figure 6: Logical connection between key lemmata, theorems, and corollaries throughout Sections to and Appendices B.1 to B.13
B Supporting Proofs
B.1 Proof of Lemma 1
Here, we follow the guidelines in (Conn et al. 2000 Theorem 7.2.1). Let us assume that s* is a minimizer of mss) subject to ||s*112 < Then, there is Lagrange multiplier v* such that
0, |s 11 E, active constraint.
inactive constraint
v² (I|s 11 - 0
(52)
52 is the unfolded Complementary Slackness (CS) condition Bertsekas (017)) for the constrained optimiza- tion problem ( The active case occurs when s* lies the boundary of Q i.c., (s(s)) 0 || E
and the inactive case occurs when s* lies in the interior Ω i.e. (e())) < 0 + ||s") 11 <
Active constraint case. We assume that s* is minimizer of ms(s) subject to 11 = E. From the first-order optimality conditions Bertsekas (2177). there exists Lagrange multiplier v", such that
VeLg(s", v²) Vañ(s*) 1/" V
v f((x)) + vs(x))
=0
Vam(sr)
22 fxxx) + 4² || 1) 8" --==(((x)). (53)
2

---

Published in Transactions on Machine Learning Research (02/2026)
where the identity Vs |||||| = 3 ||s||æ s was used for some s. Let s be a feasible point on the boundary of Ω, i.c., [|s|| ç. The Taylor expansion of mh(s) around the minimizer s* is
ml(s = mm(s))))) + (s - s* Vam(ss) + 2 (s - --)""" V)m(s")) (s ss).
(54)
From the second line in 53 we also have
Vam(s') - - ||s0|| s'.
(55)
Given 55 and the fact that and s" are feasible points on the boundary of Q i.e., || = ||s|| 2 we have
= V¹
||8'|12 (s 15-8") S* 1¹
(s - " Vxm((*)=
2 ||s||2 (l|s* 12 s" s*)
v2
||
1
2//3 + 52/5)
5² ss
v²*
||51||
[Is* 11 + +[s|12) - s²'s (56)
=
2
2
2
2
which implies
(s - --) v= = 4²
- ||s'|l2 (s - ss) s)).
(57)
Combining
54h
57
and m)((s) V2 f(x+) gives
mnss = rm(s") v" ||s (s - s²)" s*) (s
-5)
=m(s)) + (s 5T (2)((x))) + V2 |ss 1) (s (s-s)). (58)
2
The second-order optimality condition
Bertsekas
2017 Proposition 4.3.1) for z E Rd yields
zZ ((22(s)) + +v" váge(s")
(59)
where
+ /² m) +o" (=ge(s))= (F')(xE))
1²* ('()"
2 |s I)
(60)
|| ll2
42 (x((xx)
such that z (s*
||s1||| =='s" =0 + zT's 0. Since s* # 0, we have
f(f(()) + 1¹
42 sx
(s*)
1s=1|2
+
2 0 +
2
2
||s 2
(61)
+ 2
(z s )
z" V2 ((x))
|| I
+
2 0.
2
2
S 1
Using x²'s- 0 in 61
we get
zT (v2f(x))=
V¹
||s' 1)
2 0.
(62)
This indicates that (x](xx) + 5 ||s*|| ll I positive semi-definite for vectors in the direction of the mull-space of (sge(s"), i.e., perpendicular to Vage(s").
It remains to consider vectors w E Rd that do not belong to the null-space of V (s*), i.e., wT' & (s*) # 0, and prove that V2 fxx)) + D² ||s*||2 I is also positive semi-dcfinite. To this end, define the line 2
s* +a w as a function of a. Because we are interested in w, such that w V"V o O, the line intersects
the constraint (s)) = 0 + ||||| E in two values of a. For a = O we have s = s* and the aforementioned

---

Published in Transactions on Machine Learning Research (02/2026)
discussion holds. For a o 0, satisfies || = &. In the latter case, we may write s s-s" = 0 w. From 58 we arrive at
a² w" (v')(x))) + 2 ||s 1) 2
rns) = m(ss)
(63)
with a # O. Given the assumption that s' is minimizer, L.c., mmss) - m(s), 63 implics that fxx()x) +
T || I is positive semi-definite. So far, we have shown that if s* is minimizer subject to ||s*
then f²f(x & ||s*|| is positive semi-definite either the direction of the null-space of Vage (s*)
not. Conversely, if V (xxx) + / ||s" I is positive semi-definite, from 58 and 63 we arrive at fn(s") S r)((s) i.e., s* minimizer subject to ||s*||== 5
Regarding the uniqueness of the solution, when f2((x)) 2/2 ||s* I is positive definite, from
58
and 63 we have that mns*) < miss, which indicates that s" is unique minimizer subject to ||s*
Inactive constraint case.
this case, we assume that s* is a minimizer of mn(s) subject to ||s < < when v' = 0. From 53 we
obtain
-V((x)))
(64)
From the sccond-order optimality condition Bertsckas 20017 Proposition 4.3.1), it is implied that Ve ,"") is positive semi-definite. Using the latter fact, along with the fact that VagCe (s* w*)
f(x( when s¹ 0, we get that (xf(x;) is positive semi-definite. This, in turn, implies that are dealing with convex problem.
Conversely, when fxx(x) positive semi-definite and Va O, can use the Taylor expansion of m)()) in (44 along with the fact that
VoLg(s", = + Vañ(s") + v2 Vsge(s =
(65)
+ Vur((")= =0
show that rh(st) S mss). This implies that is minimizer subject to || Regarding the uniqueness of the solution, when v²f(x;) positive definite and v² 0, can solve (58) w.r.t.
s" = =-= (xx)
which indicates that s* unique minimizer subject ||s* 1l <
Given that assumption has been made on the structure of V fx),, we can repeat the aforementioned proof using ((xg(( instead of fx(x) to arrive at Corollary 3 Corollary 3. A vector s* is a minimizer of mss) subject to |s 1| < & if and only if satisfies
(Dag( f(xx)) +
|s 1) s* = -- f
(66)
2
+ xス js I 1 0,
2 f(xx))
(67)
and v² ([|s*] -) = 0, where 1² 2 0. // V
f(xx)
+ - ||s* ||
I > 0, then the minimizer 8* is unique.
Corollary 3 will be used in the proof of Theorem 3
B.2 Proof of Lemma
Starting from the primal optimization problem
min Le v))
V (xxx) Ts
1s 1/
-E). -))
(68)
sER
6

---

Published in Transactions on Machine Learning Research (02/2026)
where v is the Lagrange multiplier, the optimal value the primal problem can be expressed as
min L) SER"
1 s" f(xs) (xxx)) J + SER" 200ED,
min
V (10/2 - 5) (151 (1512-7) }
rv
(69)
where is the Lagrange multiplier associated to the constraint || - r (Boyd & Vandenberghe 2004 Section 5.4). It is essential to highlight that the optimality conditions outlined in Bertsekas (2017 Proposition 4.2.1)
explicitly require to belong to R. However, r is restricted to D, for reasons that become apparent as the proof unfolds. If the weak duality property is applied to the right-hand side (RHS) of (99 we arrive at
(1sIB - }
rED, RER +20 Vf(x))* s Ss f(x(()) s+ N' (1312 4 6
min Lg(s, 2 max min SER"
(70)
From the first-order optimality condition Bertsekas 2017 the optimal value in the Left Hand Side (THS) of 68 w.r.t. s is attained by s that satisfies VaLe v) = 0, i.e.
('
(x*x
1/ ||s||2 + +
1) s - (xx)), 2
(71)
At this point; we note that 71 differs from Denote the RHS of (70) as
9 because the stationarity of L v) is studied w.r.t. only.
Le(s, vf(x)* s + s" v2f(x)) s+ V (13/2 (1Is|B -T)
TV
4
vf(x)) + ST (xx + vr
2 1) s 6
(73/2
-5)
TV
(72)
4
We start with the case v > 0. Solving U, = 0 w.r.t. T, we get
(73)
where r E D,, Restricting in D., implics that > 0, which in turn implics T" > 0, as |s|| = If = 0.
we have ||||| = 0, which leads to the trivial solution, i.e. the zero vector. Solving (,,,(,,, = w.r.t. s, we arrive at
vx(x)) - (-2
1)ss
(74)
For r E Dr, we get from
74
s(v,r) (22
+
vr
I)
vf(x)), リ> 0,
(75)
2
which implics the dependence of s on the variables v and r. Restricting r in Des we achieve the invertibility
in 75 when v > 0. Substituting (73 and 74
72 we get
r),,
s(v,r)" (v2f(x)) + VT I) s(v, 2
5
v 6 12 v
(76)
2
Combining 770 and 76 we get for v > 0
min Ls( 2 max L((s(v,)),,,r)) sERd
(77)
rED,
The derivative of 76 w.r.t. is
0 0.
V (
(78)
Thus, for any v > 0, the optimal value the RHS
77 is attained for r" E Dr that solves
0.L d.Le r).
0.
(79)
Dr
29

---

Published in Transactions on Machine Learning Research (02/2020)
Using 78 in 79
we have
r" (ss(,rr)1 for any v > 0.
(80)
Restricting r" in Dr. we avoid the trivial solution s(v, r") = 0 for any > 0. This restriction on in 69 is precisely due to its inclusion in Dz.
Using 74 in we attain
(g(s(u, u) ss(,r) (V2S(x)) + pr
1 1) s(u,r) 1 r(( + [|s( 5 (81)
Adding and subtracting the terms 1 and " ||s(U,, 1) we gel
(e(s(v,r),)) -(surr) (v2
vr
1)
r(v,r) s(v,r)
1
V f(xx) s(v,r) (s(,)))]
2
1/ p
||S(,, r)
yr
||s(v, ||((,,))] (82)
12
12
Next, using 76 with appropriate rearrangements we arrive at
Ce(s(u,r),v) 2e(s(v,)),,,r) + 1/2 - r|(( - - [|s(v,
yr
= r), + 12
u,
ر + ||s(,,))] 3r [s(v,))]1)
(e(,, ur) + 12 (1s(2,))12 +)² (r+2 [(s(U,)))l))
(83)
Then, using
78 for r E DD and > 0 we obtain
4 + ( (2.06((((es)))er)))
(84)
3v (r + |S((,, r) r)11 22
When 79 is satisfied for some 0, Le r), (T) given by 84 is maximized w.r.t. E Dy. From we have
84
Ce(s(p,r)), = max L,(s(1,T),,,T). rED,
(85)
In order to obtain
12 we need to show
Ce(s(v,r*);u) min Ce v), <> 0. SERd
(86)
When r* E DD in 75 and using r" = ||s(v, r²) I|2 for some v > 0 in 80 we get
(V [()( 1) s(v,r*) = V fxx)
(87)
which implics that s(v, r*) minimizes v).
We conclude with the case v 0. In this case, we observe that 12 is easily attained by applying 70 when equality holds, which concludes the proof.
B.3 Proof of Theorem i
From the weak duality in and 12 we have
min max (s,
max min Le (s,
12
max max L((((,r)),,,)) = max Le(s(u,r),,,r)
(88)
SERA 220
#20 SE
D20 TED,
rED..u20
where the last term in
88
refers to a joint optimization problem. We start with the case 0. The
derivative of 776 w.r.t.
V is
5
3
(s(e, [|s(v,)))
(89)
6
12'

---

Published in Transactions on Machine Learning Research (02/2020)
where r E D..
To prove that (88) holds with equality and subsequently prove (17)
we study the optimality conditions that
maximize the RHS of (88). The optimal value in the RHS of 88 that solves
w.r.t v > is achieved by some v² >
0.2 (s(v,))) du
0,
(90)
w.r.t E DD, is achieved if (9 or equiva- lently 180 holds. Given that (80 holds for any v > O, without loss of generality, we assume that 80 also holds for 0, i.e,
for E Dy. In addition, the optimal value in the RHS of (88)
= ||s(U* r' l|2 for any v² O.
(91)
When 91 holds, from
90
get
3r* ||s(U* rr)) 1*3
(92)
Solving 144 w.r.t. fx(x) and substituting in we get
=)(s(v,)),)) = s((,r)' (v2f(x)) + 2/
1) s(v,r)+
2
2 (((x))"((((x))s((() -1s (93)
Then, applying (92 for Des we have
v) -((,r) (V2S(xx) vr 1) s(u,r) / s((,r) V2 fxxx) s(ur))
1
v 6
|s(v, rs(
vr
||((,,)) +
vr
(94)
4
12
Adding and subtracting of rls we obtain
vr Le(s(u,r),v) = - 1 - s(ur)) (v'S(xx) + -/r 1) s(u,r)
||s(1; 1
||((,,))]
4
6
vr
|s((,,))1
vr
(95)
4
12
Similarly adding and subtracting
of and
v T2
reveals the term Le(s(u, r), v,r) yielding
13 (e(s(v,r)
Le(s(V,T) -
3
+
6
_ [|s(e, m)1 + 12
(,3 + + ( 3r [|s(e, r))3)
12
(96)
The terms inside the first bracket of 966 are identified
-0 (s(1,, r), u,,,, yielding
=
L v,,)
(l|s(1, r)1l r)² (r+22 [|s(v,))]lz)
12
4 (r + [s(
Le(s(v,))),rr)
(0.(((((())),)))) - 0, (97)
3v (r ll2
and by rearranging terms, we arrive at
(r 2 ||s(U. (((2)))l2)) (0..2((((e))))))))))
Cg(s(v,r),)) {(()))
(s +
( (98)
3v (r + [|((,, 1)
When 79
and 90 hold, Le(s(1, u)) is maximized and from 98
we have
(",(""""),,""""""" v20,rED,
max
L((s(1,)),,,))
(99)
31

---

Published in Transactions on Machine Learning Research (02/2026)
where r" and v² optimize the RHS
S8
Given r", V", and 99 to show 17 we need to prove
(s(v) r r",,"" 1 r5) min max V)(
(100)
#20
To do so, we need to show that the optimal in the RHS of (100) equals s(v", r*) ) in the LHS of 100 The
optimal s in the RHS (100) satisfies Lemma I Thus, by Lemma if s(v", r*) satisfies the CS condition
V² (1|s(V" rl E) =0
(101)
and the system of equations
1/¹ |s(V rz)] 1) s(v",r")= -VV((x)) v2 (xxx)
(102)
then (100) holds. [011 implies ||s("", r* r1 = & for /¹ 0, which is true because of 91 To prove 102
we apply 87 where without loss of generality we replace > 0 with v" > O, and the proof is complete.
Corollary in the paper's main body, summarizes this proof's main result.
B.4 Proof of Theorem 2
The proof has two parts. The first part deals with the RHS of (22). while the second part deals with the LHS of (22 similar procedure is followed to that in Kloft et al. (2009) Proposition 1) to prove Theorem
D First part.
Let s* be the minimizer of 7 which satisfies the feasibility condition gę(s*) I 0. We want to show
that when M = v², s* is also minimizer of 5 From Lemma 1 we recall that 2n (IIs*11 [ E) = 0. Consequently,
min max L) = fe(s", v²) = mmss)) + 6 (110211 - 1 m((s) sER 220
(103)
from condition
From Corollary we have
min max (s, = max min Le(ss)) = max (Vv) = vi(²),
(104)
sEld =00
#20 SERd
220
where (V)) is the dual function of the constrained optimization problem have
From
103
and
(044 we
50, by feasibility
fn(s)= ((0")= min sER
Le(8, min SERd
(s)s V'
(1s11 E) }
< min ml(s) = mm(s) + v2 (1s2112 11)2--))-- (1)=))-()=m(6 ms(s)) (105)
seg
0 from CS condition
Since the first and the last term in [105 are equal, due to the CS condition, the in- in-between inequalities hold with equality, i.e.,
(ss) + 1 (1s1 [1)] m(ss)
1² (Is5112 -t).
min sCRd
(106)
Removing the constant term
v² from both sides of 106 we obtain 6
1²
min my- (s) vi(ss) SEad
|s
s(xx) + + (xxx)) ) s S
[x](x=
|| m (s"), (107)
6
which implies that s* is also minimizer of 5 with M = v² and the first part of the proof is complete.

---

Published in Transactions on Machine Learning Research (02/2020)
> Second part.
Let. s" be a minimizer of (5). We should prove that 8" is also a minimizer of when & = ||s =| For such ç: 9e(s*) = O. We prove the second part by contradiction. Suppose, s" is not optimal in 77 i.c., there a feasible point such that ri(s) S fi(s)). For this feasible point we also have ge (s) and ge (s) S (s()). Then, we get,
fn(s) I m(s") + mss) gę(s) S Em(ss)) + gc(s")
+ m(ss) + (|s) - -E) - mm(s)))))
(1s0112 - -)) (108)
Adding 55 in both sides of the last inequality in 108 using the definition of mnd (s) with M = V. and applying the definition isss) 7 we get
ms (s) (s).
(109)
This is a contradiction, because S" is a minimizer of 55 Hence, s* also a minimizer 0g (
7 when
0 +
1| which concludes the second part of the proof.
B.5 Proof of Lemma 5
We follow similar lines to the proof of Kohler & Lucchi 2017 is used instead of BN to emphasize that the deviation bound in 44 and the sampling scheme in 45 are specifically derived using information associated with gi-
Lemma 6 and Theorem 7). Note that B%
The proof resorts to Vector Bernstein's inequality in Lemma 19 the centered gradient
(discussed in Appendix B.13 Let us define
2/, (x(()))
V fxx),
(110)
where 1....., n = [1 First, we show
2 12 S [x+((x))|| + [xx
s 2
(111)
which implies [xtal12
12 S 4L3. Accordingly, 02 - Ab3 in Lemma 19 In 111
we have used
[Vx(x)]l2 - V 112 <
Ly Ly,
(112)
where the triangle incquality and Assumption I have been applicd. Then, we have
Z₁
2 gk vx(x)).
(113)
13 i=1
Using 113
Lemma 19 for n = |B3] and 0² =L3 yields
2 (-18g)
Pr(lgg: - (x(x))ll2 2 e) < exp
(114)
3213 4
Next, require that the probability of the gradient deviation Pr(llg 8 E (0, 1], i.e.,
vf(xx))l2 c) is less than some
2
1
In 3 +
exp
-B%
s 8 $88
(115)
32L? 4
To derive
44
we use
1155 in lg
vs(xx)llz 26, along with Assumption
to get
g:
vf(x+)ll2 2 C. || + 4
< C || 2
(116)
B

---

Published in Transactions on Machine Learning Research (02/2026)
which yields
45
Using the complementary probability
with 8 E (0, 1]. it is implied that
g+ vf(x))l22 6
is fulfilled with high probability 1- 8 when 115
holds. The latter derives
44 and the proof is complete.
B.6 Proof of Lemma 6
Following similar lines to Kohler & Lucchi [0017] Lemma 8 and Theorem 9) and using B instead of B₁ to emphasize that the deviation bound in (46) and the sampling scheme in (47 are obtained using information related to Bg, we get
((D))
B
1
Diag HAV. O
1 Σ Diag
Σ iEB
V
f((xx)
Vs V
S
S
|3%
Σ
Σ
Diag (v.))), (117)
S ==1
1B%
1EB%
Let
B = Diag ( fi(xx)) Vvv.)
(118)
For A E Ixddd it is known that ||A||2 - ||||| Golub & Van Loan 2012).
Accordingly, for B we obtain
B = Diag Vifi(E) ① v.))
Diag (V2s(xx=vv ① ov.)ll
d
(V*[((x))v))))), (119)
where [v.li = +1, yielding
| [/ S I|val2-
(120)
For v, E Rd |/al22 S Vd valll Gould et al. 1999h, where Ivvello = maxigisallv.ld = 1. This allows us to rewrile 120 as
B B S vd V fx 11 Ivelloo S {(x))>
(121)
As result
| vdLg.
(122)
because [(x)()))) 1| S Ly due to Assumption
To apply the Matrix Bernstein's 's inequality in Lemma 22 define the centred Hessian matrix
Z B Diag ( (xx)))
(123)
where T...., B-
Let n' |B From Lemma using Assumption 1 and applying the triangle inequality have
(D S V fx))()) <
V fi()
s n Σ Lg S Lg,
(124)
Using 122
124
and applying triangle inequality yields
z B Diag( Diag(V?f(x)) f(x)) < B +||iia(VV S <VVd+ 1)4g.
(125)

---

Published in Transactions on Machine Learning Research (02/2020)
which implies
Zi S Vdly:
(126)
d > 1. Let
8
Z
A
Σ
123 Z
B
Diag V2 V2 f(x))).
(127)
S ==
118
SEB
Let also
s
a²
E
2
E
2
Σ
E
2
iE
iEB
iE
2
Σ
E
S S B
(128)
= 1 iEBR
which implies 0² S sd |
Also let K Vd Tng Using the latter Lemma
22
implies
s Σ
2dexp
t
t vdl,g
2t v
(129)
2d exp 2 val.
a² VdL.
s=l
LEB
Using 127 in 129) for 1 S
o² VdL,
and setting e = To yields
Bs - Diag f(xx))) 2 S edx
e Valle
(130)
For some E (0, 1], we are interested in the upper bound
Pr( Bx Diag ((xx)) 2))
(131)
which implies
2d exp (-
2 2 /gg
In 2d
S
H dL2
x SIB
(132)
Similarly, using 127 in (129) for
o² and setting Vdlg
Is yields
3 S
Pr( Bg Diag( (xx((x))] 2
S 2dexp
(133)
vdl.
Again, we are interested in the probability Pr[[ B. - Diag( (2))(()((x)))l)) 2 <) less than some 8 E (0, 1]. i.c.,
3 SI
In 24
2d 2dc
200c2 Vdl.g 9 S S 1
(134)
8
VdL,
We have that for < that - 5 -22 Thus, for d > have Vol, and the lightest upper bound
of Pr[[ - Diag fxx))) 2 t) 133 134 indicates how large e must be for the probability of a deviation in [13 be at most depending on the number of Hutchinson samples S, the mini-batch size 1 the parameter dimension d, and the smoothness constant Lg- Next, using (34] in Assumption get
In 2d
In 2d 8
< BB Diag( (2x S CB ||sx||2 $ vdl. S
CB [|sell + >B 2 vdL. s || CB (135)

---

Published in Transactions on Machine Learning Research (02/2020)
which yields 47
Using the complementary bound
Pr( B₁ Diag Diag(V2[(Xe)))) 2 2 -
it is implicd that
B₁ ( 12xx)) <
is fulfilled with high probability 1- 1- 8 when 134 holds. The latter is
46 and the proof is complete.
B.7 Proof of Lemma 7
In the following, gt and B₃ are utilized instead of (x+)) and fxt)) This substitution is performed because Sk and B₃ are diroctly used Algorithms 1 and 2 both of which operate on data batches. In this manner, r(u,r) is now defined in terms of Bş and gk: rather than
and [x(x),, respectively.
To obtain the minimizer r) in 20 we need to solve w.r.t. v and r the system of equations
0, Lev, =0 and r() =0
(136)
The solution (v,r) in 136
can also be computed sequentially. We start with the case 0. In this case, we can first solve (v,r) = 0 w.r.t. r E D,, Then, the optimal can be used to solve (,, = 0 w.r.t. V to obtain the optimal v >> O. Solving (z,,r) = 0 w.r.t. r, yields
T Bk
B
1)
[
Bg
1)
gk
v
([|s(1,+)112 - 0. (137)
(2)
For r), # 0, r D2, and v > Fom 137 we obtain the root
(138)
13 Then, the optimal can be computed by solving (v,
w.r.t. i..,
gk
B + ur I) -1
-1
-
B
1)
g
3
0,
(139)
4
2
6
12
which is rewritten as
c
3
[| r)
(140)
4
12
for some 5 0. Substituting 138 in 140
the optimal given by
VVE.
(141)
Using
141
in 140
the optimal y can be computed by solving
w(v, r) = ||s(u, - VE = 0,
(142)
w.r.t. for fixed. It is shown in Conn et al. 2000 Scction 7.3.3) that instead of solving 142 it is more
preferable to solve
6(v,r)
0.
(143)
|s(
1
VE
We conclude with the case 0. Tn this case, the minimizer s(u,r) in concludes the proof.
20 is handled by Algorithm 2 which

---

Published in Transactions on Machine Learning Research (02/2020)
B.8 Preliminaries for Lemmata and 9
Lemma 8. For M E Rddd and Diag(M) we have
| 2 [DDag((M)
(144)
Proof- First, prove
[M)lg(M)l2 max Diag(M)xxl
(145)
Let d² = maxx (M)K- Then, from the definition of the spectral norm, we have
[M)lg max |x]|2=1
MM)l( S max
Σ
(DDaa((M S |d'1
max |x|||=
Σ x
(146)
|x]| =1
which leads
[iag(MM)ll S dd
(147)
Let be the vector of all zeros except 1 in the mit position, where m arg max, Diag(M)a. Then,
[Daag(M)]22 ||x|]_=
max [M)xg 2 |Diag (M)em
(148)
which leads to
[Miag(MM]l2 2 ld").
(149)
L47
and
149
imply
145).
From the definition of the spectral norm, we have
xTMrMx
|Mx max x.y0
My
[M||
max |
max xx|1==
2 lee Me = MMyl-
(150)
|x|||
||x 12 llyl|
Restricting 150 in the diagonal elements of M gives
| 2 max Diag(M)al.
(151)
which using
145 leads to
M 2 [Diag(M)]lz
(152)
which is 144 This inequality becomes an equality when M diagonal matrix. Therefore, 144 provides the tightest possible bound in this case.
B.9
Lemmata 9 and 10
Given the Lipschitz continuity assumption of / (2](x) Lemma introduces the Lipschitz continuity of
Diag( 2 fx)). Lemma g is used in Lemmata 10 and 17 Lemma 10 is adaptation of Nesterov & Polyak
2006 Lemma 1) tailored to fit the context of this analysis. Lemma 10 is used in Lemmata 14
15
and 16
Lemma 9. 1f (xx) is Lipschilz continuous in F, Diag(V²/(x)) is also Lipschilz continuous, i.e.,
(eigg((2((x)) Diag v f(y)) < Lu |
(153)
Proof. The proof of the lemma is casily obtained by combining the Lipschitz contimuity the Hessian matrix in Assumption I (see also Remark I with Lemina g in Appendix B.8 In Lemma we use 2 f2)(x) fly).

---

Published in Transactions on Machine Learning Research (02/2020)
Lemma 10. For any x and y in F, we have
I lyy x112
[Vf(y) vx(() Diag(V x)]12 -
(154)
and
[(y) -(x) V 5(x x)) Diag( (()g))) xx) s LH lly x x
(155)
Proof. Nesterov & Polyak 2006 Lemma 1) does not make any assumption on the structure of V2 The only assumption to derive Nesterov & Polyak 2006 Lemma 1) is the Lipschitz continuity of V f(x). Thus.
given Lemma and following the proof guidelines in Nesterov & Polyak (0006) Lemma 1), (154 and 155 are easily derived, which concludes the proof.
B.10 Details for Algorithm
Here, Algorithm 2 is discussed when B₃ and g are utilized instcad of fx(x)) and V fxx),, respectively. This is done because BŞ and gx are directly involved in the application of Algorithm which operates on data batches. In this manner, s(v,r) and r(v,r) are now defined with respect Bş and gk, rather than Diag( 2 f(x)) and fxxs), respectively.
Lemma 11 provides some useful properties of o(u, r) exploited in line 18 of Algorithm 2 Lemma is used in
Lemma 12 which shows that for some r E Dr, Newton-Raphson updates in line 18 Algorithm 2 converge to the roots @(u,r) = w.r.t. v 0. However, the Newton-Raphson method may diverge on its own, and appropriate safeguards are necessary prevent this. These safeguards are adopted from (Conn al., 2000 Algorithm 7.3.6) in Algorithm 2 Lemma 13 stems from Conn al. (2000) Lemma. 7.3.5) adapted to
the analysis here. Lemma 13 provides the termination rule used in Algorithm
Lemma 11. Let
Ha - B
vr 2
(156)
Suppose Bx + O and vr > ma 2 Aa (B&) } for some v > and r > O. Then, the function Φ(v. r) is strictly increasing and concave w.r.t. and fixed r. The first- and second-order partial derivatives of ((u, r) w.r.t. are
0ub(u,r) 0,s(urr)² s(u,r)
(157)
[s((r))
and
0e((rr) =3 (d,s(u, TTT s(v,r))² |0,s(M, r) 11 [|s( |s(1r))
S0,
(158)
||(
respectively, with
0,s(ur))=55 r' H ( (U,r)s(u,r)
(159)
Proof. Following similar lines to Conn al. 2000 Lemma 7.3.1), the first-order partial derivative of d(v,r)
51
w.r.t. is
a.b(urT) On (s(u,)))((urr))) s( 0
VE
1 [(s(u,)) 1)
a (s) a.s(u,r)² s(,,))(()))
-
Σ
(160)
||s(v, r)1l
E=1
which is 157
The second-order partial derivative of G(v, r) w.r.l. v reads

---

Published in Transactions on Machine Learning Research (02/2020)
Lo(v.r) - (stem)) s(v,r)) (s(u)))=s(u,))) (0,s(u,)) ( s(u.r))
(Q,((,,))* s(x,r)) R)((,r)² ((,,)((rrrrr))))))))) + (10,s(e,,)))
||s(u, f (161)
[(s(1)))
The first-order partial derivative of
s(u,r)
18
k (u, gh
(162)
w.r.t. V is
0,s(u,r) - H (v, BA
H ((,))
(163)
which is (159. From (163) and the assumptions about v and r, i.e,, vr max -2 (Ba)] with v >
0
and 0, obtain
a,s(u, r)" s(v,r) = - s(v,r)" H. (v, s(y,r) <
(164)
Using [64) in 160 we infer that r(ur)) strictly increasing w.r.t. u. The second derivative of 162 w.r.t.
is given by
(s((ur)= r²
((rr)))
(165)
From 162 and
165
we get
(,, s(vrr) 2 10,s(v, r1)
(166)
The substitution of 166 in 161
yields
Lolur) = 3{ =3{ (d,s(v,))"s(a
|0,s(1, r) 12 (
(167)
[|((ur)]]
(s(u,r)
which is 158 The concavity of 6(V, r), w.r.t. v, i.e. 03((u r) <0, follows by applying the Schwartz inequality, i... (O.s(v,) rMT s(v, r)) s [10,s(v, r)1 (s(v,)) in 1167) which completes the proof.
Suppose that for some > 0 and r > 0 we have r max (2.-2 -2 do (Bx)) and ((vr)) < 0. Then for a fixed r, the Newton iterates
Lemma 12. Let (b(ur) satisfy Lemma
11
H(urr) ut + doglu,r)
(168)
will still satisfy g(v+,r) < O and comvergence monotonieally toward the root v² of Φ(v,r) 0 w.r.t. The convergence of the Newton iterations w.r.t. is at least linear and ultimately quadratic.
Proof. Following similar lines to Conn et al. 2000 Lemma 7.3.2), we study the convergence of the Newton iterations in 168 w.r.t. v when r is fixed. Suppose that Φ(v, r) satisfics Lemma which implics 0, r) > 0. Then, from the Newton iteration w.r.t. v in (168), we have
6(v,r) + (vt - v) a, = ((u,)) r) is concave, i.c. S. r) S Combining the concavity of ddv, r) with (169
(169)
According to Lemma we get
< olv ,r p(v,r) (u+ - v) dob(urr) 0
which proves that ((v,r) < 0 is inherited by all Newton iterations w.r.t. v. Let (v",r) be the root of ((,r). In addition, let (u', r) be an intermediate point between points (n,r) and (u*,r), i.e, (v',r) =
a (v, r) + (1 (1-a) (v", with a E 10, Then, the Taylor expansion about 2², r reads as
1 blu,r) مiu :f foooo aoow'' ,r)(u (r)o(u v²) ( 22 -0 0(v -v)))-
(170)

---

Published in Transactions on Machine Learning Research (02/2020)
We assume that ru, is close to rr).. This proximity implies that the last term in equation 170 becomes even closer to zero, and consequently, it is omitted from the subsequent analysis. The assumption that (v, r) is proximity to (v",r) ensures the convergence of the Newlon method (Bertsekas) 2017). This proximily is achieved by utilizing the safeguarded Newton Algorithm A comprehensive analysis of the safeguarded
Newton methodology be found in (Conn et al. 2000
Subtracting '" from both sides of 168 Lee,
v+ v = (v--v")) p(u,r)
(171)
0,p(ur))
and substituting 170 in 171 arrive at
v² v0 (1 Ovō(v',r))
1 180(p' ,r) 0,b(u,)) (v v²)²
ood(urr) (V-v")
(172)
We examine the following cases:
If
a.o(v'.r .r) Bud(Mrr)
1, 172 diverges.
Buolu' .)) (,0()
2. If
1, we have at least linear convergence in (172).
3. If avolv'.r .r) D.l(P.)
0, we have quadratic convergence as the lincar term vanishes in 172).
From the concavity ((,, r) w.r.t. v, we have that 0,6(v, r) is decreasing, which implies that a .x) O.d(())))
1. Thus, the Newton iterations w.r.t. convergence in 168) at least linear and ultimately quadratic, which completes the proof.
Remark 3. Lemma implies that 0rb(U,T) > O. Suppose that for some and we have d(u,r) < 0, i.e., Lemma 12 holds. Then, by (168) we have that vt V. Given v >> and the initial volues of and in lines and ④ of Algorithm the optimal and always satisfy B5 + Pr 0.
Lemma 13. For some and > O, suppose u max (0, 2 (Bx)) and
||s((T)))12 - Keasy g
(173)
with Kensy (0, 1). Then
m))(u,r)) S Keass)) ) m((s)t
(174)
where st is the minimizer of that satisfies Lemma and
nn(s) - F(xx) + 5 s
+ 2
8 B s.
(175)
Proof. A similar proof to that in Conn et al. (2000 Lemma 7.3.5) can be devised for the constraint ||s|
g.
B.11
Preliminaries for Theorem
Here, Nesterov & Polyak
20066
Lemma 1), Nesterov & Polyak
20066] Lemma 2),
Nesterov & Polyak (2006)
Lemma 3), Nesterov & Polyak (2006) Lemma 4), and Nesterov & Polyak (2006 Lemma 5), correspond to
Lemmata
10
14
15
16
and 18
respectively, proven for Diag V fx)) in place of V fxx). In addition,
Lemma
17 is proven providing details not included in Nesterov & Polyak 2006 Section 2).

---

Published in Transactions on Machine Learning Research (02/2020)
Let the level set and assume that F _ ((f(x))) Let
S(c) = {x E R2, f(x) S c)
(176)
y( + (y x) + " 5(y-xx x)² Diag( Diag(V2J(x))) (2x(()) x)+ + M
6 1l
x x112
(177)
TM(x) = arg min mig f(x.
(178)
and
fxs(x) min y(x,y).
(179)
That is,
fx(x) (x))).
(180)
To compute (x) in 178 we solve Vy fyf(x,y) y) i.c.,
v (x) + (x)) - x) +
2 lly x112 (y - x) = 0.
(181)
Let (x) = |x - (x) For (x) in 1111) if we multiply both sides of 181 by Tas(x) x we
arrive at
M
(Ts()) - -x) (Tas(x)) - x)" Diag( (Tx) - x) 2 [I(Tx)(x) - xx11 = 0.
(182)
Lemma 14. For any E F with f(x)= S f(xo), we have
fx(x)² - (x)( 2 O.
(183)
Moreover, i 2 L and x E int F, then
TM(x) E 2(f(x))
(184)
Proof. Using Corollary 3 we obtain
M 2
Diag( 2 fxx))
||x yll2 I O,
(185)
which when pre-multiplied by (TM((x) - x)T and post-multiplied by (TM(() - x) yields
M [T((x) -x1 2 0.
(x) x)" Diag 2
x)
(186)
Then, combining 182 with 186
arrive at 183
Assumption and Contradiction. We now show that (x(() E((()). Following the approach of Nes- terov & Polyak (2006 Lemma 2), we proceed by contradiction by assuming Tx((x) & (xf(x)) for M 2 L We then show that this assumption cannot hold, leading to a contradiction. Thus, we conclude that (x) E (x)()))
By assuming (x) & (((()), there exist.
Ya = (1-0) (xx()),
(187)
with a E [0, 1], such that
f(ya) f(x).
(188)
Using the upper bound of 155 with y Ya we obtain
41

---

Published in Transactions on Machine Learning Research (02/2020)
f(ya) S f(x) + VV -x)+ Naa xx) Diag(V - -x)
Lt
l x l2
187
6
f(x) aVx (TT)(x))(((((()) x)+ a²
a LH
(Tar(x) x)" Diag (ing(V x)
Ihs (x) - -x112
(189)
which using
182
implies
a²
a²
.M
aIn
f(ya) f(x) s -
Vf(x) (x-x)" - Tm(x))
[Tas - x112
(190)
2
2
2
20 as ac (0 and 195
For a E 1, we have
M a
M Lи
(191)
2
3
3
which by using our assumption M Lu it is implied that. f(ya) S f() in 190
However, f(y.) S f(x)
contradicts (188 for M 2 HH which in turn leads to 1884, and the proof is complete.
Lemma 15. If (x) E F then
Lu + M
(VS(TM(x))l
1 (x).
(192)
2
Proof.
Sctting y = (x) in 154 and
181
we get
LA [T - x112
[V]((M( - (x() Diag (² -x)122 -
(193)
2
and
M respectively. Then, combining 193 with 194 and the definition of the reverse triangle incquality, we arrive at 192) and the proof complete.
M V + Diag Diag(Daa (x)) - [[TM(x)) 11T(x)))
x||
(x(;,
(194)
Lemma 16. For any F have
(M+La Lu Ily x11 + s(y)
fm(() min y
(195)
and
M
f(x) - fx)(x) 2 12 (x).
3
(196)
Moreover, if M 2 Lu, then (x(x) E F and
f(TM(x)) S far (x).
(197)
Proof. In the following, we have used the relaxed condition M 2 LH M 2 Lu relaxed condition M 2 Lu also satisfies Lemma
> Lg. Note that the
14 From the lower and upper bound of 155 we have
M + Lu Ily - f(x)
f(xxy) <
(198)
6
and
f(y) S f(x,y),
(199)
respectively. Thus, we have
M + LH
f(y) < y(x,))
x11 + f(y).
(200)
42

---

Published in Transactions on Machine Learning Research (02/2020)
Minimizing 2200 all sides w.r.t. y yields
M + (M+ Lu
min f(y) min f(x,y) min y
lly -x112 +1y)
(201)
y
which in turn using y = (x) yields
M + Ls
f(TM(x)) S f(x, (x) S min
ly - x|2 + f(x))
(202)
Additionally, using (80 in 202 we obtain 195).. Note that 195 aligns with the results presented Nes-
terov & Polyak (2006 Lemma 4), with the distinction that Diag(
V2 f(x)) used in place of V2 fxx).
From
the LHS of 202 and 177 we obtain
f(x) (xTM(x)) 2 f(x) - (xx(TTs(x))
M
[T x) - (TM((x) x)" Diag( x)
[T - -x11 (203)
6
In addition, from 182 we have
M
(TM(x)) x) Diag( [(x)) - 2 ([(x)) -x) x)+
| (x) - x112
(204)
4
which combined with 203 and 180 gives
M
fxx far 2
( (T) x) + (x),
12 T (x),
(205)
2
which in turn combined with 183 yields of (200) and using 180) we obtain 197).
196
To conclude the proof, setting y TM)x) in the LHS
Lemma 17. x F then
2 2L + M,
PM. (x++1) max
[Vf(x--)]]2
Amai (Diag( (V2 f(x++1)))
(206)
V LH + M,
Proof. From
192 have
2 La M
[f((x+1)]a S ||x+1 xill2.
(207)
185
implies
Diag( (xx))) Lu ||x - --l2 It M ||x - yl12 I> LL ||x - y112 I
M
Amin (Diag(V?) [(x))) (Diag(??((x))) LH ||x - v1l2 2 - LH |x - 8112,
(208)
which by setting y X and x yields
Amin (Diag 2 f(x,)) LH ||x; x 11: M LH ||x, x1+1
(209)
Combining Nesterov 2018
Corrolary 1.2.3) with Lemma for y x and x = yields
Amin ( 2 Amin
( (o0g())(()))) Lu Ixx x4t1l22
(210)
which when combined with 209 gives
( M + LH ||x: - x441l22
Ami (Diag(V² ( f(x++)))
(211)
43

---

Published in Transactions on Machine Learning Research (02/2020)
and, in turn, implies
2
2L + M Amin (Diag( ( V22 f(x++1))) 1 1|x x(+1l12.
(212)
In order to obtain an (Eg, et -stationayy point, we need ||x, - x 1ll2 S eg and 1|x,- - xc+1lla S en in 207
and 212 respectively, which yields (206), and the proof is complete.
Lemma 18. For any F we have
Pa (M)(Tx(x)) & (x).
(213)
Proof. Adapting Nesterov 2018
Corollary 1.2.2) in our context yiclds
Diag(V? [TTM((())) ž
(x)
(214)
Combining 214 and 185 gives
Diag( V2 (+)(((()))) = (--M Lu (x)(
(215)
which when combined with Lemina
yields 213 and the proof is complete.
B.12 Proof of Theorem 3
Let (54-1. be the output of Algorithm 2 for B Diag(V²((x,)), g Vf(x)). Recall that (8,+1: M(+1)
is a minimizer of (7) and according to Theorem it is also a minimizer of problem 5 where = 1/+1-
Recall also that Xi+1 = x; - 8,41 and let. the sequence {x:)21 be generated by Algorithm
Next, suppose that Assumption holds, i.e., the objective function f(x) bounded from bellow, f(x) 2 flow for all E F. Then, continue with the proof of the main result in Thcorem From 196 have
Mo
f(xo) - fF,, 2
r (Xo)
12
M1
f(xi) - (x1) 2
Mi (x1)
12
(216)
Mx-1
f(xx-1) FM (xx-1) 2
Mr (x6-1);
12
where TM, (x:) ||x; x and
[M,(x) A min mas (s).
(217)
SERa
Summing over 216 we get
k- l
Mr
Σ (f(x:) - FM, FM, (xi))
>
12 1 (xi).
(218)
k=0
1=0
Then applying f(x++1) < FM (x:) (Lemma 16).
we get
M,
Σ ((xx))((x+x)))
TMM (xi).
(219)
which, by applying the telescoping sum, yields
M,
f(xo) f(xx)) 2
12 T.M (xx).
(220)
==

---

Published in Transactions on Machine Learning Research (02/2020)
Next, using the lower bound of (xx)) ie., flow by Assumption and Remark
we obtain
Mi
s(x0) -llow z
12 MM (xi);
(221)
which implies
La
pm, pM, (x++1) F., (x:) 122/33 (f(x)) -loo 1/3
((x0) flow
(x:) 12 Lo
(222)
M,
where Lemma 18 Appendix B.11 is applied to get μ.M. (x++1) I sr. (x:). For Lu = Mr and applying the
trick 12 3 + 122/3
3 (8/2)1/3 + 121/3 (3/2) 81/3 + 12 (3/2) + 12
(3/2) 1/3 8/4 - (3/2) 8/3, we arrive
8 3 fxx) flom
PLg (x++1)
S
(223)
3
Lick
As in Nesterov & Polyak 22006 Theorem 3), here it is assumed that V (xx) is positive definite for some
2 0. The latter assumption implies that Diag(V2 f(x.) is also positive definite. Then for some i 2 0,
from 206), we restrict our study
1 [x(++)))
Pig (X++1)
(224)
V T.
which combined with (223). yields
/3 (xx) flow 2/3
min [V - 1/3
8
(225)
3
which implies (23 The convergence rate in the approximate g, and B, are used instead of V fx;) and 2 fxx)), respectively. The latter argument is strengthened by Corollary and the proof complete.
23
used to establish the local convergence rate when
B.13 Vector and Matrix Bernstein Inequalities
For completeness, we restate Kohler & Lucchi 2017 Lemma 18), incorporating corrections for minor ty- pographical errors. Lemma 19 is utilized by Lemma Next, Lemma 20 is introduced and utilized by Lemma 22 which in turn is utilized by Lemma 6 Lemma 21 is also used by Lemma 22
Lemma 19 (Vector Bernstein Inequality). Let X1, X2........ Xn. be independent random vectors of common dimension d and assume that each one is centered, uniformly bounded, and also the variance is bounded from above, i.e.,
E[x] 0 and ||xil22 S 0 as well as E[||x s o²
(226)
Let z= ER= X.. Then have
(-n
2
Pr([z|12 2 S exp -n 8022
(227)
with 0 < <<c<o>/0+..
Proof. A proof can be found in KKhller & Lucchi 2017 Lemma 18). However, some typographical errors were identified, leading us to reproduce the proof for clarity.
The Vector Bernstein inequality for independent, zero-mean random vectors states
Gross 2011
Theorem 12)
1
a
1 ( [
Pr
-
Σ
x;
exp
(228)
4V

---

Published in Transactions on Machine Learning Research (02/2026)
where V= = E | is the sum of the traces of the covariance matrices of the centered vectors x;
Using E|||x, 22 I o² yields V S no?
Note that in 228], the probability condition is scaled by factor of 1/n to align with the subsequent analysis
involving z. Let E = (t + /V)n + = ne - VV. Using (228 we get
1 1/ nc vV) )))))))))
)
1
- )
Pr (1 20 exp
exp
(229)
4
VV
4
VV
We claim that
( vV
2
1 n22
1
1
S
+
(230)
4 2V
4
Indeed, if 230 holds we arrive at valid inequality
n222
1 n26
ne
2
+1
V
VV
2 V
(231)
2
nc
v2
2 0.
V2V
Using 230 in 229
gives
2 - 802
+ 1)
Pr [[22|1 2 c) exp
(232)
where V S no² is used. According to Gross
2011
Theorem 12), t < V/ max; [xxll2- For V s no² and no² /0, we arrive at n
||xil22 S 0 gives < no² /0. Given V S no² and
no = 1+ VV
Vno ees 0
to,
(233)
where Ve < x with x is used. In addition, can be shown that Var(z) S 0²/n Gross 2011 12) establishing (227), which concluded the proof.
Theorem
Lemma 20. Let u; : Qu, + R" and V; Shy, + RM be independent random vectors for each i,j. Let 9: 9:R² Rm Raxd be function that produces random matrices. Then, for any indices (i.j) + (k, I), the matrices ((u.v,)) and g(ug, vi) are independent, regardless of whether u, and V, come from the same or different distributions.
Proof. Let two threshold matrices M and M' (which are symmetric d d matrices), and consider the probability
P(g(u, vy) & Mn g v1 & M'),
(234)
using the element-wise comparison operator <. Given that u, Qu, - R and v, Dyy R are independent random vectors, and g: R" x Rm + Rdxd is function generating random matrices, rewrite the event as
(g(u, vy) & M) = (w,) E In. x Sly g(uu(wm)) vy((w,))) & M]
=((u;v,5) Ra x Rm g(u, v2) $ M). (235)
Similarly, we have
(g(up, vi) & M') = {(wm (wi) E Iue x Puy (wm)) ). (wi,)) & M'}
{( vI) Rm x RM g(u, vi) M'). (236)
Let
A = {(u Vj) E 12 x R g(,, v,) & M)
(237)
46

---

Published in Transactions on Machine Learning Research (02/2020)
and
B = {U vt) ER" x Rm gu vt) & MM
(238)
Then using 235 and 236 in 234
write
(( vy) & M (o(u,, vi) & M1) P((u, v,) E (n vi) B).
(239)
Recall that the sequences }u,} and {vy} independent families of random variables which implies that the pairs (u, vÿ) are formed by drawing independently from these families. Thus, since u, and Vj are independent for each (i,j), and (ug, vi) are also independent, we have
P((g(u, vy) M) n (g(Ug, vi) M)) = P((u, ((()),,) A)P((ug, vi) E B):
(240)
which implics
P(fglu, v,) & M) n (g(u., vi) & M') P(g(u, vy) & M)P(g(u, vi) & M'),
(241)
where (235 and 236 used. Since the joint probability factorizes, this proves that g(u, v2) and g vi) are independent whenever (i.j) + (k, regardless of whether and V, come from the same or different distributions.
Lemma 21. Let X E Raxd a symmetric mean-zero matric with |X|| S 1 almost surely. Then,
E (exp(AX)) I exp (o())E(X²1),
(242)
where g(A) = = 1.
Proof. We refer the reader to /Vershynin 2018
Lemma 22 (Matrix Bernstein Inequality). Let X,j A g(us; v2) d x zero-mewn random matrices with two independent sources of randomness, u, and Vj. Also, let (Xigh N.M be a set of independent random matrices of common dimension d x d, such that [|xi]lla I almost surely for all i. Then, for every 2 0, we have
M N
(- 12/2
Pr
ΣΣ
X j=1
2t t
s 2dexp
(243)
2
Here, the matria variance given by
M
0²
E
X
(244)
In porticular, we can express this bound a miature of sub- Gaussian and sub- sub-esponential tails, just like in the scalar Bernstein's incquality:
N
M
3
t 0 K })
Pr
ΣΣx,
X
t < 2d
min
(245)
The following analysis is based on /Vershynin 2018 Reduction of MGF. To bound the norm of the sum
Proof.
Theorem 5.4.1).
N
M
s
X
(246)
[m
jml

---

Published in Transactions on Machine Learning Research (02/2026)
we need to control the largest and smallest eigenvalues of S. We can do this separately. To put this formally, consider the largest eigenvalue
Amax (S) A max (S
(247)
and note that and
S|| = max [A((S) = max Amax (S), Amax Amax(-S)}
(248)
Pr([Amax(S)) 1) Pr(Amax (S) 2 1) + (-S)) 2)) - PPr(Amax(S5 2 l and Amax 2 1), (249)
which implies
Pr([Amax (S) 2 t) - Pr(Amax (S) 2) Pr(Amax(-S)) 2t.
(250)
To bound Amax (S), proceed with computing the moment generating function. We fix A 1 0 and use Markov's s inequality to obtain
Pr(Amax (S) 2 t) = Pr( PAr(eAMmax (8) 2 Ed S -M E Ele
(251)
Since by Vershynin [2018 Definition 5.4.2) the eigenvalues of ex are es), we have
E - Me (S) (e (c
(252)
Since the eigenvalues of es are all positive, the maximum eigenvalue of es is bounded by the sum of all eigenvalues, the trace of ee which leads to
E[E
(253)
Application of Lieb's inequality. First note that
N-1M-1
N-1
M-1
s= Σ
ias + Σ
XNy + XNM.
(254)
j=1
To prepare the application Lieb's inequality in Vershynin 2018 term from the sum
Lemma 5.4.9), let us separate the last
--1M-1
N-1
M-1
AXN; + AXNM ))
ET exp
ΣΣ
AX + Σ AX
M
+
Σ
(255)
i=1
j=1
Conditioning on (Xig Ji.==1
- and applying Vershynin 2018
Lemma 5.4.9) for the fixed matrix
N 1-1M-1
N-1 Σ X +
M l
+
XXN;
(256)
j=1
==l
and the random matrix Z A AXNM, obtain
N-1 M-1
N-1
M-1
AXN; + AXNN) ))
E < E
MMM
N.M
Tr exp
Σ
Σ
AX + Σ
XX +
Σ
f=1
1=1
==1
N-1M-1 Σ
N-1
M-1
< E (x.,
EXXx
Tr exp
Σ
XX +
Σ
AX +
Σ
AXN; AXNM NM
1=1
i=1
N-1M-1
N-1
M-1
<E EEix, (Xu))N
--1-M11
Tr exp Σ Σ
XXij + Σ
XXaM
MM
XX NJ
log Ex Ex XXNN NNa
(257)
Ø=1
48

---

Published in Transactions on Machine Learning Research (02/2026)
We continue similarly: separate the next term XX NXN-1,M-1 from the remaining sum and apply Vershynin 2018 Lemma 5.4.9) again for = 11M-1,--1 Repeating this process NM times, we obtain
N M
Pr(Amax (S) 2) S Tr e
e-
exp
ΣΣ
log E exp AX1s
(258)
MGF of the individual terms. It remains to bound the matrix-valued moment generating function E ExAXy for each term Xiy. We now use Lemma 21
Completion of the proof. Using Lemma 21 we obtain
N.M
N.M
E (exp (AX;j/K)) 3 exp (o(A) EXX
IK²)
+
II E exp (AX,;/K)] 3 II
exp (o(A) 1[x
J
N,M
N.M
II 1-
E (AX,(XX,)KK)) exp
exp g(A)
Σ 2
E
(259)
which implies
N,M
N.M
II
E exp (AX,, /K) exp
g(A)
Σ
(260)
k-=1
i-=1
Also, given that Xij are independent, we have
N.M
N.M
E Eex (AX.//3)) )) = exp
N.M
II KJ=1
E eexp (XX,;/K)) exp
log
πI WJ=1
eex
Σ
log E (XX (AX,g/K))
(261)
which combined with (660)
N.M
N.M
exp
Σ
log E exp (AXi;/ x)) 3 exp g(A)
Σ
2
1/12
(262)
1
and applying the trace to both sides yields
N.M log E Eexp (AX.;/K) (K) )) < Tr (exp (exp (o(A) 2/K3)),
Th
exp
Σ
(263)
1/=1
where Ž - E
Since the trace of exp(9 (A)2/(A))))) K22 is sum of d positive eigenvalues, it is bounded by d times the maximum eigenvalue and using Vershynin 20188 Definition 5.4.2), obtain
M Eisl Σ
N
X
Tr (exp (ạ(A) 2/K3)) < d Amax (exp (o(A) 2/K3)) d exp (g(A) Amax (Z/k))
exp (g(A) [|0]|/3) exp (g()) (264)
Combining (258 and 264
we get
log E exp AX,j ))
Pr(Amaxx (S) Kt) s e
M1 Tr
exp Σ>
< d exp (- 9(A) 0² O(A) 02/13))
(265)
which implies
>
9(1) K2 0
Pr(Amax (S) 2 t) < d exp
( x+
(266)

---

Published in Transactions on Machine Learning Research (02/2020)
Minimizing over 0, the minimum occurs at.
Kt 0z
log 1+
t2 O.
(267)
Plugging this into the bound, we get
o² (-22 K2
Kt
)
Pr (Amax (S) d exp
h
(268)
where
h(u) (1 + uu) log(1 1 + u) u, for u > 0.
(269)
We know that Boucheron et al. 2013 Exercise 2.8)
u² h(u) 2 2(1 u/3)²
(270)
with v > 0 and thus
o²
2²
Pr (Amax (S) 2 () < d exp
(271)
K2 2(1 + u/3)
Kt where u o².
Substituting u in 271 we obtain
12/2
Pr (Amax (S) 2 t) S d exp
(272)
0² + K1/3
Following similar steps with - instead of and using 250
yields
exp
31
t
P(Immax (S) 2)
8
(273)
2d exp
3t
t t> O²/K
SK
Intuitively, for small 1, i.c., S 0² KK we have a sub-Gaussian bound, while for large t, i..,, t > 0² 02/K3 we have a sub-exponential bound. Looking for the tightest bound, we may write
P(IAmax (S) 2 t) s 2dexp (-s
3 min
t t # })
(274)
G2 K


Reviews:
[{"review_id": "wJWjDQ0q6l", "reviewer": "Reviewer_1HGb", "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": "", "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": "**Summary:**\n\nThe paper proposes AdaCubic as a new second-order optimization algorithm suited for training deep neural networks. Compared to existing solutions that approximate the full Newton method, such as AdaHessian, the AdaCubic algorithm explicitly addresses the issue of saddle points in non-convex loss landscapes by leveraging cubic regularization. Concretely, the general cubic regularized Newton method is reformulated as a constrained optimization problem, whose batch-wise solutions involve automatically adapting the cubic regularization hyperparameter. Extensive theoretical results demonstrate the equivalence between the original and reformulated optimization problems, while also providing convergence guarantees for AdaCubic.\nFinally, an empirical study across various learning tasks and data modalities demonstrates the effectiveness and robustness of AdaCubic with fixed hyperparameters compared to other optimization algorithms whose learning rates have been tuned.\n\n**Strengths:**\n\n- The theoretical results demonstrate AdaCubic's convergence under reasonable assumptions, taking into account the use of a diagonal Hessian matrix, as well as the noise inherent in the batch-wise computation of the gradient and the diagonal elements of the Hessian.\n- The empirical study follows established benchmarks and demonstrates that AdaCubic can be applied with a single set of hyperparameters across various learning tasks, data modalities, neural network architectures, and other training hyperparameters, including the number of training epochs.\n- The computational and memory complexity of AdaCubic is well-suited for practical large-scale deep learning applications, thanks to the use of Hutchinson's method for approximating the Hessian matrix.\n- The paper provides a structured overview of existing works that target the issue of escaping from saddle points. Moreover, detailing their shortcomings provides a clear motivation for the development of AdaCubic.\n- The paper clearly indicates that the code will be publicly available upon acceptance, reducing the barrier to using AdaCube in practice.\n\n**Weaknesses:**\n- (A) While a main contribution of AdaCubic is its effectiveness under fixed hyperparameter values, providing more details on how these values are selected and how different choices affect its performance would make AdaCubic more accessible for practitioners. Currently, the reader is referred to another paper to understand the physical meanings of the hyperparameters. \n- (B) The presentation of the training hyperparameters and model architectures is difficult to follow. For example, the computer vision experiments clearly note the mini-batch size of 256, whereas this information is missing for the other learning tasks. A condensed and standardized tabular overview could resolve such issues.\n- (C) There is no clear (potential tabular) overview of the differences and commonalities of AdaCubic to other established optimizers, such as SGD, Adagrad, Adam, and AdaHessian. Such an overview would make it easier to understand the advantages, e.g., cubic regularization, and the disadvantages, e.g., higher computational complexity due to the extra backward pass for Hutchinson's method, of AdaCubic.\n- (D) Although the paper notes that the code will be made publicly available upon acceptance, providing it as supplementary material for review would have been insightful.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Overall, the aforementioned strengths **support the paper's major claims**. Primarily, the presentation within the paper can be enhanced to better understand the properties and behavior of AdaCubic, which are essential prerequisites for its practical adoption.", "audience_yn": "Yes", "audience_explanation": "Optimization algorithms with strong robustness for fixed hyperparameter values across diverse deep learning applications are of particular **interest for a large audience**. In addition to the presented empirical study, the theoretical results can also provide further insights into research on second-order optimization and the avoidance of saddle points.", "requested_changes": "Please address the aforementioned weaknesses, answer my questions at the end of this review, and resolve the minor issues also listed at the end of this review. The **critical parts** are the weakness (A) and the questions (I-III).\n\nFinally, I would like to note that the paper writing is quite technical, which is good on the one hand. But on the other hand, more intuitive explanations, added to one place or another, would further ease the understanding for non-experienced readers in the optimization literature. For example, outlining the steps of deriving the proposed framework at the start of Section 2 (as also done in Section 3) would make the general idea clearer from the beginning.", "broader_impact_concerns": "N/A", "additional_comments": "**Questions:**\n\n- (I) In its principal design, the empirical evaluation study seems to be related to the one performed in the AdaHessian paper. For example, both report results for ResNet20 and ResNet32 on $\\\\texttt{CIFAR-10}$ and rely on the $\\\\texttt{GLUE}$ benchmark. However, specific hyperparameter values differ. Concretely, 500 as the number of training epochs for $\\\\texttt{CIFAR-10}$ is quite large compared to 160 training epochs used in the AdaHessian paper. Figure 1 also demonstrates that AdaCubic requires more epochs until convergence. What was the reason to increase the number of training epochs?\n- (II) How are the (initial) learning rates of the optimizers SGD, Adam, and AdaHessian tuned? Most likely, these learning rates stem from the respective benchmark papers. However, making this process more transparent would be beneficial.\n- (III) What are the effects of $\\\\kappa_{\\mathrm{easy}} \\in (0, 1)$ and how is its value defined?\n- (IV) In the sentence above Corollary 3, you state that you repeat the proof with the diagonal Hessian matrix $\\\\mathrm{Diag} (\\\\nabla f(\\\\mathbf{x}))$ instead of the gradient $\\\\nabla f(\\\\mathbf{x})$. Do you rather mean $\\\\mathrm{Diag} (\\\\nabla^2 f(\\\\mathbf{x}))$ instead of the full Hessian matrix $\\\\nabla^2 f(\\\\mathbf{x})$?\n\n**Minor Comments:**\n- The paper uses `\\citet` and `\\citep` inconsistently:\n  - When the citation is grammatically part of the sentence, e.g., \"Authors et al. proposed …\", `\\citet` is often the right choice. \n  - When the citation is only a parenthetical reference, e.g.,  \"... as established previously (Authors et al., 2019) ...\", `\\citep` is typically the correct choice.\n- There is a missing space in \"subjectto\" in Eq. (22).\n- The `itemize` environment would be more suitable to describe the four groups of datasets as part of the $\\\\texttt{GLUE}$ benchmark.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2ohbEoKOVj", "reviewer": "Reviewer_d2MB", "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": "", "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 proposed a new optimizer for neural networks called AdaCubic.  \nThe method relies on a second order method with a cubic regularization term. Unlike previous methods, which require finetuning the hyperparameters, the regularization term is adaptive and thus user friendly.  \nThe paper proved convergence of the optimizer and exhibited strong emprical results on several tasks of wide machine learning domains.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Partly yes.  \nThe motivation and the problem statement is quite clear.  \nThe paper is theorectically strong with rigorous proofs for convergence.  \nThe experiment section of the paper exhibited performance of the proposed optimizer comparing with other optimizers, including experiments on neural network task specific performance, curves of convergence and cummulative timing. However, even though on some tasks the AdaCubic shows slightly better scores, e.g., on CIFAR, the convergence rate and the cummulative timing don't show significant improvement, which hinders the wide application of AdaCubic.  \nThe authors claim other optimizers need finetuning of hyperparameters while AdaCubic does not. However, AdaCubic also have a set of hyperparameters, and it is unclear how these hyperparameters influence the training dynamic.", "audience_yn": "Yes", "audience_explanation": "A study in optimizers is always helpful to machine learning community. With the development of large models and hardware design, a fast, convergent optimizer is always an important topic.", "requested_changes": "Despite the strong mathematical results, I think there should be text narrative part in the paper.  \nFor example, why (3) is a form of non-convex optimization, why such sum decomposition?  \nMaybe add some text before lemma 2 so that it is more clear to reader what is going on there, it is not quite smooth transition.  \nFor the self-containedness, some details e.g. $\\lambda^+_d(\\mathbf{B})$ in algorithm 2 should also be explicitly explained.  \nIn figure 1, why the loss curve of AdaCubic does not drop a lot with the learning rate decay?  \nSince AdaCubic is a second order cubic regularized method, it should be compared with more related cubic regularized methods.  \nIs there a clear application field where AdaCubic dominates all the major optimizers?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tfm0F59Hok", "reviewer": "Reviewer_mfxj", "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": "", "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": "The paper introduces AdaCubic, a second-order optimization method that dynamically adapts the regularization parameter ($M$) of the cubic term in Newton’s cubic regularized method. By solving an auxiliary optimization problem with cubic constraints. the method avoids saddle points and ensures convergence. To maintain efficiency, it employs Hutchinson’s method to approximate the Hessian diagonal, reducing memory complexity to $O(d)$", "claims_and_evidence_yn": "Yes", "claims_explanation": "Theoretical: The paper claims to introduce a novel method that dynamically adapts the cubic regularization parameter ($M$) to avoid saddle points. This is well-supported by the theoretical derivation in Section 2, specifically the formulation of the auxiliary constrained optimization problem and the proofs of strong duality (Theorem 1 and Corollary 1) and equivalence (Theorem 2). The convergence analysis (Theorem 3) accurately establishes the $O(1/\\epsilon^{3/2})$ rate, consistent with standard Cubic Regularization literature.\n\nEfficiency: The claim of low memory complexity ($O(d)$) is accurately supported by the use of Hutchinson’s method to approximate the Hessian diagonal (Eq. 30)\n\nRobustness: The claim that AdaCubic works well with a \"pre-fixed set of hyperparameters\" (sourced from Trust Region literature) without fine-tuning is supported by the experimental setup.\n\nPerformance: The claim that AdaCubic \"outperforms or competes\" is supported by Tables 2 and 5 (GLUE benchmark and Signal Processing tasks).", "audience_yn": "Yes", "audience_explanation": "The paper addresses two major points of second-order methods: computational cost (addressed via diagonal approximation) and hyperparameter sensitivity (addressed via the adaptive cubic mechanism). The promise of a \"tuning-free\" optimizer that performs competitively with Adam/SGD is of high interest to practitioners who spend significant resources on hyperparameter search.", "requested_changes": "Wall-Clock Time Analysis: While Figure 4 mentions \"Cumulative time,\" the text heavily emphasizes per-epoch performance. It will be the best to add a specific Table comparing the wall-clock time required for AdaCubic vs. SGD/Adam to reach a specific validation accuracy or loss threshold. This is critical to assess if the extra computation per step (Hutchinson's estimation) is worth the improved convergence rate.\n\nClarification of \"Large-Scale\": The abstract claims applicability to \"large-scale applications.\" The experiments use ResNet on CIFAR and BERT-base, which are arguably medium-scale by modern standards. Please either qualify this claim (e.g., \"medium-to-large scale\") or include a discussion/experiment on a truly large-scale setting (e.g., a larger LLM) to demonstrate memory scaling.\n\nPerformance Gaps: Explicitly discuss cases where the method did not outperform the baseline (e.g., specific GLUE tasks or CIFAR-100 if applicable). Analyzing why the diagonal Hessian approximation might fail in these specific instances would add valuable insight for the reader.", "broader_impact_concerns": "NA", "additional_comments": "Lower Confidence. I am not an expert in optimization or second-order methods. Reviews are more from the application point of view.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)