A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent
Authors: Shuo Xie
Tianhao Wang
Beining Wu
Zhiyuan Li
Venue: ICLR 2026 Poster (2026)
Keywords: adaptive optimizer
steepest descent
loss geometry
convergence rate
Primary area: optimization

Abstract: Adaptive optimizers can reduce to normalized steepest descent (NSD) when only adapting to the current gradient, suggesting a close connection between the two algorithmic families. 
A key distinction between their analyses, however, lies in the geometries, e.g., smoothness notions, they rely on. 
In the convex setting, adaptive optimizers are governed by a stronger adaptive smoothness condition, while NSD relies on the standard notion of smoothness. 
We extend the theory of adaptive smoothness to the nonconvex setting and show that it precisely characterizes the convergence of adaptive optimizers. 
Moreover, we establish that adaptive smoothness enables acceleration of adaptive optimizers with Nesterov momentum in the convex setting, a guarantee unattainable under standard smoothness for certain non-Euclidean geometry. 
We further develop an analogous comparison for stochastic optimization by introducing adaptive gradient variance, which parallels adaptive smoothness and leads to dimension-free convergence guarantees that cannot be achieved under standard gradient variance for certain non-Euclidean geometry.

Published as a conference paper at ICLR 2026
A TALE OF Two GEOMETRIES: ADAPTIVE OPTIMIZ- ERS AND NON-EUCLIDEAN DESCENT
Shuo Xiel Tianhao Wang?
Beining Wu
Zhiyuan Li'
'Toyota Technological Institute at Chicago
University of California, San Diego
University of Chicago
{shuox, zhi leryyuannnetiiic..o
tlanhaowanguucdd.edu. beiningweuchicago..em edu
ABSTRACT
Adaptive optimizers reduce to normalized steepest descent (NSD) when only adapting to the current gradient, suggesting a close connection between the two algorithmic families. A key distinction between their analyses, however, lies in the geometries, e.g., smoothness notions, they rely on. In the convex setting, adaptive optimizers are governed by a stronger adaptive smoothness condition, while NSD relies on the standard notion of smoothness. We extend the theory of adaptive smoothness the nonconvex setting and show that it precisely character- izes the convergence of udaptive optimizers. Moreover, we establish that adaptive smoothness enables acceleration of adaptive optimizers with Nesterov momentum in the convex setting, guarantee unattainable under standard smoothness for cer- tain non- -un-uuciddan geometry. We further develop an analogous comparison for stochastic optimization by introducing adaptive gradient variance, which paral- lels adaptive smoothness and leads to dimension-free convergence guarantees that cannot be achieved under standard gradient variance for certain -uclldeid geometry.
INTRODUCTION
Adaptive optimizers such as Adam have been indispensable for training large-scale machine learning models (Bi al., 2024; Dubey et al., 2024; Yang et al., 2025; Wen al., 2025). Their dominance in training efficiency, however, has recently been challenged by the surprising effectiveness of simpler Normalized Steepest Descent (NSD)-type methods such as Muon and Lion (Jordan et al., 2024; Chen et al., 2023; Team et al., 2025; Liu et al., 2025; Shah et al., 2025). Behind this competition of two family optimizers, a broader consensus has begun to emerge: their superior performance is critically related to their ability exploit oucludeide geometry of the loss landscape (Balles et al., 2020; Xie & Li, 2024; Zhang et al., 2024; Pethick et al., 2025).
Recent studies have rigorously characterized how adaptive optimizers exploit EunEuucldd geome- try. For example, Maladkar et al. (2024) and Xie et al. (2025a) show that AdaGrad and Adam benefit from exploiting the -gemmeeyy of loss functions, and a one-sided variant of Shampoo has been shown to leverage the geometry induced by the matrix spectral norm (Xie et al., 2025b; An et al., 2025). Notably, Bernstein & Newhouse (2024) proposed striking connection between adaptive op- timizers and NSD: with exponential moving average (EMA) turned off, certain adaptive optimizers reduce exactly to their NSD counterparts. For example, without EMA, Adam coincides with NSD under the foo norm, and Shampoo coincides with NSD under the matrix spectral norm, which is proposed to be an independent algorithm Muon. Yet, beyond these connections, there is no formal result that systematically characterizes the relationship between the two families of algorithms. This naturally motivates the following question:
Q1. Do adaptive methods (like Adam, Shampoo) and their corresponding non-Euclidean descent (like Lion, Muon) exploit the oon-Euclidean geometry of loss landscape in the same way?
To address this question, we adopt theoretical perspective and focus comparing different types of smoothness assumptions that underpin the analysis of these methods. fact, even under the
Equul contribution.

---

Published as a conference paper at ICLR 2026
same geometry, two distinct notions of smoothness arise. The first is the standard smoothness under a general norm (cf. Definition 2.3), which governs the convergence rate of NSD. The second is called the adaptive smoothness (cf. Definition 2.4), introduced by Xie et al. (2025b) and shown to govern the convergence rate of adaptive optimizers in the convex case. Indeed, a main contribution of our work is to show that adaptive smoothness also characterizes the convergence rate of adaptive optimizers in the nonconvex setting. Therefore, while both adaptive optimizers and NSD can exploit non-Euclidean geometry, they rely on fundamentally different smoothness assumptions.
This difference is not merely terminological but quantitative: adaptive smoothness is always no smaller than the standard smoothness under the same geometry. In other words, from the standpoint of technical conditions, the adaptive smoothness represents stronger assumption, which in turn motivates our second question:
Q2 Does the stronger smoothness assumption in adaptive methods offer optimization benefit?
We answer this question affirmatively. In particular, we show that by leveraging Nesterov accel- eration, adaptive optimizers can attain an accelerated O rate under adaptive smoothness in the convex setting. In sharp contrast, has been shown by Guzmán & Nemirovski (2015) that the convergence rate of any optimizer is no better than 1(T-1) under the standard to smoothness as- sumption. This establishes a clear separation: adaptive smoothness enables adaptive optimizers to achieve acceleration under non- Euclidean geometry, while the standard smoothness fails. Therefore, the stronger adaptive smoothness assumption indeed translates into concrete optimization benefits, showing its difference from the standard smoothness.
In fact this difference has a direct and interesting analogy in terms of the noise assumption in the stochastic setting. When gradient noise is present, its variability can be measured in two distinct ways: the standard variance considers gradient variation under a fixed norm, whereas the adaptive variance (ef. Definition 4.1) measures noise in more stringent but also more adaptive way that requires uniform control over the geometry prescribed by each preconditioner under consideration. By construction, adaptive variance is always no smaller than standard variance, directly paralleling the relationship between adaptive and standard smoothness. Analogous to adaptive smoothness that enables acceleration under stronger requirement, adaptive variance can likewise yield benefits despite being larger. We demonstrate this through a careful analysis of NSD under two types of noise assumptions: adaptive variance enables dimension-fres rate, which is not attainable in the worst case under the standard variance condition.
Taken together, our results demonstrate that adaptive smoothness and adaptive variance are different from their standard counterparts as adaptive smoothness enables an acceleration rate and adaptive noise enables a dimension-free rate. These findings reveal an intricate interplay between adaptivity and non non-Enne Euclidenn geometry, deepening our theoretical understanding of adaptivity in optimization.
Below we summarize our main contributions.
In Section 3, we show the convergence rate for adaptive optimizers on nonconvex func- tions (Theorems D.2, D.7 and D.8), which depends on the adaptive smoothness and matches optimal O(T-1/4) rate. It theoretically justifies that adaptive methods and NSD exploit the geometry through different smoothness notions in the nonconvex setting.
In Section 4.2, we identify the benefit of the adaptive smoothness by showing it enables an acceleration rate ((T-2) of adaptive optimizers equipped with Nesterov momentum (The- orem 4.3) in contrast to the convergence rate 11(T"1 the standard foo smoothness.
In Section 4, we extend the benefit of adaptive geometry to noise assumptions by introduc- ing adaptive noise (Definition 4. We show that this stronger notion of noise can provide a new type of convergence rate for NSD with momentum on nonconvex functions which gets rid of dependence on parameter size d (Theorem 4.5). We complement its superiorty by providing a lower bound under the standard noise (Theorem 4.7).
Our analysis of adaptive optimizers is carried out through unified framework that covers a broad class of methods, including AdaGrad, AdaGrad-Nore and one-sided Shampoo. The proof technique developed in this framework may be of independent interest.
2

---

Published as a conference paper at ICLR 2026
1.1 NOTATIONS
Let Md be the set of all d-by-d matrices, S C MM be the subset of all symmetric matrices. We use S4 denote the of positive semi-definite matrices. We denote by Ia M the identity matrix. For matrices A, B, we denote their inner product by (A, B) = Tr(A B).
For E S4, || == V x: Hæ the (semi-)norm of x: E [R: with respect to H. For a convex set H C S4, we define the induced H-norm as
| =
sup H HEN,
|
(1)
Throughout the paper, we reserve f for the loss function and zo for the initialization of an optimiza- tion algorithm. For convenience, we denote the initial suboptimality as Do f(xo) -ine (xx).
FROM ADAM/SIGNGD TO ADAPTIVE SMOOTHNESS
We use the example of Adam and SignGD to motivate the notion of adaptive smoothness in Sec- tion 2.1, and then present the formal definition in Section 2.2, along with some related background.
2.1 ADAM AND SIGNGD CAN EXPLOIT foo GEOMETRY, BUT IN DIFFERENT WAYS
We start by discussing specific pair of algorithms, Adam and SignGD, to illustrate the problem of interest. It is known that SignGD can be viewed as Normalized Steepest Descent (NSD) under the fo norm and its convergence rate for deterministic nonconvex functions admits the following form (Xie et al., 2025a)
S =0 <O(V
AOT-I-I (f) T
min [V(()))ll [VI(a))l EE[T]
the standard smoothness of under the toe norm (see Definition 2.3). Note that SignGD can also be viewed special case of Adam with 31 .2 However, the convergence rate of Adam for general 31, .2 instead depends on a different diagonal adaptive smoothness notion, min Hed H- = Tr( H) in Maladkar
where -1 (f)
(2024); Xie et al. (2025a). In particular, Adam with 31 = 0 (a.k.a. RMSProp) for deterministic nonconvex functions admits the convergence rate min.e(r) [[V = Ó( (f)/T) (Xie et al., 2024). Notably, this diagonal adaptive smoothness is always no smaller than T (f) (Balles al., 2020). This suggests that though both SignGD and Adam admit convergence guarantees for the & norm (the dual norm of || (loo) of the gradients, they achieve so under different smoothness notions. This distinction motivates the following question:
which defined Ldiag
How does the diagonal adaptive smoothness Laing (f) emerge an too geometry?
||æ for To address this question, let consider the convergence of NSD under any norm
H E H D4 (see Theorem 4.5):
min [V](m))) =o( AOLi-II ( E
V
(2)
T
where ||. || H.. is the dual norm of || Minimizing both sides of (2) over e D4 with Tr H) < yields
inf min [V[())))l o diagonal H TTHH)S
Au inf
T diagonal H L (n ) Tr(H)ST
Au T
where the equality can be checked by the definition of (fiag()). Now the right-hand side matches the aforementioned convergence rate of Adam. The adaptivity of Adam is then demonstrated by its ability to automatically identify and adapt to the best diagonal matrix induced norm for any given loss function, without the need of knowing H.
3

---

Published as a conference paper at ICLR 2026
Importantly, the left left-hand side of (3) is closely related to the & norm of the gradients because
sup dingonal H (T
||
loo.
inf diagonal HH))T((H)
|| ||H, 11.11.
(4)
We illustrate this fact in Fig. 1. In words, this means that the foo norm is the pointwise supremum of all weighted 22 norms induced by diagonal matrices with unit trace, whereas its dual, the l norm, is the pointwise infimum of all the corresponding dual norms. Also, the unit &oo ball is the intersection of all unit balls for those &g norms, and the unit & ball is the union of all dual unit balls.
Indeed, the duality between supremum of a class of primal norms and infimum of the corresponding dual norms in (4) is not just coincidence, but rather special property induced by the structure of the preconditioner set H = D4 for Adam. This property holds more generally for any well- structured preconditioner and discuss the corresponding adaptive smoothness in Section 2.2.
2.2 ADAPTIVE SMOOTHNESS ASSOCIATED WITH WELL-STRUCTURED PRECONDITIONER
The following definition of well-structured preconditioner sets is proposed by Xie et al. (2025b) to unify the analysis of a broad family of adaptive optimizers with structured preconditioners.
Definition 2.1 (Well-structured preconditioner set). S S is said to be a well-structured precon- ditioner set if H = 5 n KC for some matrix subalgebra K. C MM with Ia E K.
As will be discussed in Section 3.1, many commonly used adaptive optimizers, including Adam, AdaGrad, and their variants, can be cast into the framework of a meta-algorithm (Algorithm 1) with well-structured preconditioner sets. A specific case H = Dí, the set of all diagonal PSD) matrices, which is the running example in the previous subsection. For any such well-structured pre- conditioner set H. we have the duality between the supremum the primal norms and the infimum of the corresponding dual norms, formalized in the following lemma.
Lemma 2.2. Let H C S be any strl-structured preconditioner set. Recall that its induced norm Then it holds that
defined as || || (H II -ll.-
inf || [HHH, HER(T(H)) 11,,,, HEH,T((HN)
inf -1IH--
Based on this fact, we can generalize the discussion in Section 2.1 to any well-structured precondi- tioner set H. showing that NSD and adaptive optimizers with preconditioner set H. can exploit the geometry induced by || = || |/ via two different smoothness notions, the former being the stan- dard smoothness under || || and the latter being the adaptive smoothness defined in Definition 2.4.
We proceed to introduce the adaptive smoothness associated with any vell-structured preconditioner set H.. We first review the standard smoothness notion under a general norm ||-||-
Definition 2.3. For a loss function denote the smoothness of with respect to I1- iee. the smallest positive constant L such that [[V](z) - v V s(y)ll, & L. || - yll for any x; y.
Rd IR and any norm II-I|, we will use Ln--1 (f) to
When || . = ||- || for some well-structured preconditioner set H. I. 1-11 (f) is then the standard smoothness of under the norm induced by H. In contrast, the adaptive smoothness associated with 7. is defined as the smallest smoothness of ff under all norms || induced by H E H with Tr(H) I 1, as formalized below. This term is introduced as H-smoothness in Xie et al. (2025b). We rename it to highlight this notion adapts to the structure of H. in contrast the standard smoothness.
Definition 2.4 (Adaptive Smoothness, Xie al. 2025b), The adaptive smoothness of a function w.t. a well-structured preconditioner set H. is defined as the smallest smoothness of under all h for H H with Tr(H) < 1, that is.
AH (f) min LIpl1 HEH T(H)S1
min HEH Vz. H<V
Tr(H).
(5)
For set of d-by-d matrices I. C M we that K. is subalgebra if it is closed under scalar mul- tiplication, matrix addition, and matrix multiplication. More concretely, require that for any E R and A, B E K., it holds that A,, A B. A B K.
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 General Adaptive Optimization Algorithm
Hyperparam: 0, total steps T, learning rate 7) convex cone H. S4, decay factor 3 Input: initialization 20. stochastic loss functions (ft)== Rd - IR
M- f 0
for t = , 1:
9: < f((
Mi-1 9
Cumulative variant,
M, +-
B M + (1- 3) 9:9.
EMA variant, Weighted variant.
B M 1 g
Vi arg mim HEH (Mr + cId, 1 (r(H)
2+41 f- D2 11V,-'g
return ZT
In the deterministic convex setting, it has been shown by Xie et al. (2025b) that the conver- gence rate of an adaptive optimizer with any well-structured preconditioner set H is of order (f) | /T). In Section 3, we extend such characterization to the nonconvex setting, demonstrating that the adaptive smoothness (f) governs the convergence behavior of any adap- tive optimizer with well-structured preconditioner set H.
Comparison between two smoothness notions. For any H E H with (r(H) 1, it always V flv)ll,, $ / V V H.. Therefore,
holds || yll
2 | yll and (xx)
[V[(x) ( H.
[V - V [[y)]l 11 (f).
L (f) sup w.y
sup a.
y
x y 1
Minimizing over H E H with Tr(H) then yields Wu (/) L (/) words, condition, the adaptive smoothness arguably stronger than the standard smoothness. But they can differ by at most multiplicative factor of d, as summarized in Proposition 2.5. Proposition 2.5. For any Rd + IR, it always holds that - (f) & An (f) S d L1-1 (f).
41-1 (S). In other
preconditioner set S. St and any loss function f
UNIFIED ANALYSIS IN THE NONCONVEX SETTING
In the nonconvex setting, we establish unified analysis that encompasses broad family of adaptive optimization algorithms. Our result highlights how the convergence behavior of these methods depends critically the notion of adaptive smoothness.
3.1 ADAPTIVE OPTIMIZERS WITH WELL-STRUCTURED PRECONDITIONER SETS
We adopt the framework in Gupta et al. (2017) and Xie et al. (2025b) to describe adaptive optimiz- ers unified way, as displayed Algorithm This meta-algorithm is flexible in two aspects: the way of aggregating past gradients and the choice of preconditioner set H. First, there are three different ways to aggregate the past gradients Algorithm each of which is presented a sep- arate algorithm block in Appendix D.I. The cumulative and EMA variants are the most common ways, and they are indeed equivalent to the weighted variant up to hyperparameter transformations. Therefore, it suffices to study the weighted variant. and the results for the other two variants follow as corollaries. Another flexibility of Algorithm comes from the choice of convex cone H. More specifically, Algorithm recovers several standard optimizers by specifying H. as follows:
H = {all diagonal PSD matrices) recovers AdaGrad and Adam. {c Ia c > 0} recovers AdaGrad-Nome and AdaSGD (Wang Wiens, 2020).
. 7l S recovers full-matrix AdaGrad (Duchi et al., 2011) 1).
H. = shh @ Ian yields one-sided Shampoo/ASGO recently proposed by (Xie et al., 2025a;
An et al., 2025)
5

---

Published as a conference paper at ICLR 2026
In particular, based on the notion of strutsstre preconditioner sets defined in Definition 2.1, Xie et al. (2025b) develops a unified convergence analysis for Algorithm in the convex setting, and the convergence rate depends on the adaptive smoothness with respect to H. defined in Definition 2.4.
Additional notations. We define PH(M) arg ee (M, H + Tr(H)) for any M E + Then in Algorithm I, V2 (M) and Lemma B.4 will show that PH(M) is the projection of MM onto H. Specifically, when H contains all the PSD matrices, V, M,
>
3.2 CONVERGENCE RATE IN THE DETERMINISTIC NONCONVEX SETTING
Here we only present results for the deterministic case to highlight the role of adaptive smoothness, and the complete results for the (stochastic) nonconvex setting and corresponding proofs can be found in Appendix D.2. We first present the convergence guarantee for the weighted variant of Algorithm in the following theorem.
Theorem 3.1. For any Algorithmm I with well-structured preconditioner set H. where the update of Mofollows the weighted version, i.e., M, 3M--1 + +g.g, for all E [T]] Let Au (f) be the adaptive smoothness of the loss f according to Definition 2.4. Then when fi = f, it holds that
0. 3 E (0, > 0, and T E N, let {ax)) be the iterates of
----1
Bi/2
Vde
T
|f(x)l
I
E+
VE. VT
T
where& & 20m + nbH (/) [|STllop and ST = E E V (V, -VV
For general well-structured preconditioner set, || Ô [1o 3)T/3 + log(d))). When the preconditioner set only has diagonal matrices, ||ST lop (1 3)T 3)T
The above result for the weight variant be converted to guarantees for the cumulative and EMA variants. Specifically, the cumulative variant is equivalent to weighted accumulation with = while the EMA variant with learning rate r and stability constant e produces identical iterates as weighted accumulation with v7 = 8/ /VV- 3 and e w = = (1- B). Below we present the result for the cumulative variant Theorem 3.2, and the result for the EMA variant is in Theorem D.8.
Theorem 3.2. For any e 2 0, r > O, and T E N, let {x, IT be the iterates of Algorithum I with well-structured preconditioner set H. where the update of M, follows the cumulative version, i.e.,
M, = M, + 9:9, for all I. E (T). Let Nx (f) be the adaptive smoothness of the loss J according to Definition 2.4. Then when ft = J. holds that
T
1
1 | S /T (E+Vde VE)
T
where & = - Ae +n. 1.7..0 Au (f) a). Moreover, when setting 1) V Axc()) loga it holds that "
E = 1=-(V/2 Ō(VAo An (f) logd).
At high level, Theorem 3.2 shows that, with appropriate hyperparameters, Algorithm with any well-structured preconditioner set H. achieves convergence rate of order Ö(log d / /AoAu()// on deterministic nonconvex functions where Ō(-) hides logarithmic factors in problem parameters other than the dimension d. This result illustrates that the adaptive smoothness Ax (J') governs the convergence rate of adaptive optimizers the nonconvex setting, complementing previous results for the convex setting Xie et al. (2025b). Moreover, we remark that when H contains only diagonal matrices, the log factor disappears, recovering the bounds in Xie et al. (2025a).
It is worth noticing that the convergence guarantees in the above two theorems are concerned with | (mx)ll depending on specific 7 rather than [ )l For the specific case of Adam where H is the set of all diagonal PSD, this becomes a guarantees in terms l norm of the gradicnts, as discussed in Section 2. On the other hand, Pethick al. (2025); Kovalev (2025a) show that
NSD achieves O(( (اميي ) in the deterministic case. Taken together, these two rates suggest that adaptive optimizers and NSD exploit different smoothness notions in the nonconvex setting.

---

Published as a conference paper at ICLR 2026
3.3 TECHNICAL CONTRIBUTION: A NOVEL MATRIX INEQUALITY
Previous theoretical results for one-sided Shampoo/ASGO (Algorithm 7) and other well-structured preconditioners primarily focus on convex objectives (Xie et al., 2025b; Kovalev, 2025a). In the non- convex regime, existing convergence analyses apply essentially when the preconditioner set contains only diagonal matrices' (Xie et al., 2025a). In contrast, we show the first unified convergence anal- ysis that applies to any general well-structured preconditioner set, well beyond the diagonal cases.
central difficulty in our analysis is the extension from diagonal preconditioners to a general pre- conditioner set H. In the diagonal case, the proof basically decomposes entry-wise analyses, and scalar telescoping readily yields the desired bounds. However, for general H. noncommulativity prevents such simplification, and bounding the second-order terms requires handling delicate matrix inequalities. Our resolution of this challenge yields a key technical contribution, formalized below.
Lemma 3.3. Let 2 O and 3 (0. For any T E N, consider any sequence of vec- tors go: .............. -T E Rd. Let M-1 = O, and recursively define M, = 3M- + 9:9: for t 0, T - 1. For any well-structured preconditioner set H. define V₁ arg min Hen MM + ela. H Tr( for each E 11. Then for any H E HnSS it holds
T-1
T-1 Vv. (V, - 3V, V. 1=0
Σ lIVe gella S (H(H || where ST
Moreover, there exists an absolute constant Ci, C2 > 0, independent of d, T, B and H. such that
||TT si (1111000 log (1+22
T
(~ -- T+ + log / + C2.
Σ
19:11
t=
In the special case when H commutative, the above bound can be further improved to
|| lop S (1 -BT + log V
Specializing gt's ss's to be the gradients, Lemma 3.3 provides general upper bound on the sum of second-order terms. It highlights the essential gap between diagonal and general preconditioner sets: noncommutativity introduces an additional log d factor, making the dependence strictly worse than in the diagonal case. Nevertheless, this is the first bound that applies to arbitrary well-structured preconditioner sets, and plays a central role in extending convex analyses to the nonconvex setting.
The proof of Lemma 3.3 can be found in Appendix C. A key step is to establish a novel matrix inequality Lemma C.1 that relates the difference between two positive definite matrices the dif- ference between their logarithms, which may be of independent interest.
4 BENEFIT OF ADAPTIVE GEOMETRY
We have shown Section 3 that the nonconvex convergence rate of adaptive optimizers relies criti- cally on the adaptive smoothness of the loss, and the bound is worse than that of the corresponding NSD. This naturally raises the concern in Question 2: does the stronger adaptive smoothness lead to stronger results? In this section, we address this question from two complementary angles:
1. Under the adaptive smoothness assumption, adaptive optimizers can achieve faster conver- gence rates on convex functions via Nestrov acceleration.
2. The distinction between standard smoothness and adaptive smoothness mirrors a parallel separation in the assumptions gradient noise.
At high level, these two angles share the same underlying mechanism: Under non-Euce non-Eucli geometry, averaging might not be effective in reducing the norm, which we will explain below.
This he generalized to any commutative well-structured preconditioner set.

---

Published as a conference paper at ICLR 2026
Algorithm 2 Accelerated Adaptive Algorithm
Algorithm 3 NSD with momentum
Hyperparam: = 0, total steps T, learning rate
Hyperparam: 2 O, total steps T, learning
convex cone H. - S+
rate norm || ||, averaging parameter a
Input: initial Lo. constants C0....,0y E (0,
Input: initialization æp. initialization mo- stochastic loss functions (ft)
To < 2o. M- t
for t = 0, 1....- T- -
for t = 0, 0,1....,. -
g. - V Ver fa:::: (x,) where St fa is in (8)
g: < (f(()))
M, + M,11 9:91
m, + (1 a aammm11 agg
Vi - arg min (M + eld, H H H
U arg max (m,, u)
HEH
|
L++1 f V,V
1(+1 1
3t41 f- 01 + (1 at.
return æT
return TT
4.1
ADAPTIVE VARIANCE: AN ANALOGUE OF ADAFTIVE SMOOTHINESS
Our main results in this section are concerned about accelerated adaptive algorithms for convex functions and NSD in the nonconvex setting, Before presenting these results, we introduce key technical ingredient: adaptive variance, a quantity that serves as the analogue of adaptive smooth- ness for gradient noise.
Definition 4.1 (Standard and adaptive gradient variance). For an index set T, let ffther be a set of stochastic loss functions where each ft - R.
For any norm || Rd, the gradient variance of {fiher under || is defined as Tn a1-i(())))T)==
sup
E [((r) B[V
The adaptive gradient variance of (fthET w.r.f. any well-structured preconditioon set H. is TH on((feheT)>= HEH, IET IET ZER!
min
sup E - fx))]] [=] =-))
(7)
This adaptive variance is inspired by the noise assumption in Kovalev (2025a), both capturing the overall variation of gradient noise in the geometry induced by H. Compared with the traditional noise assumption that only characterizes & norm variance, adaptive variance provides a more in- formative measure. addition, analogous to the comparison between Az (f) and LI-1ly (f), the adaptive variance is always no smaller than
formalized in Proposition B.11.
Here compare Definition 4.1 with bounded covariance assumption in Xie al. (2025b); An et al. (2025) that there exists Σ 2 0 such that E[V fxx)) (a.))
V (2;)) = Σ. When the covariance matrix upper bounded by Σ, σн S Tr( (P (E) for general H shown in Proposition 10 On the other hand, Definition 4.1 doesn't require the existence of Σ that can upper bound the covariance matrix everywhere. Therefore, Definition 4.1 is weaker assumption than the bounded covariance assumption.
4.2 ACCELERATION ON CONVEX FUNCTIONS
We follow the framework in Kovalev (2025a) to formulate a unified class of adaptive optimizers with well-structured preconditioner sets with Nesterov acceleration in Algorithm 2. Through the perspective introduced by Kovalev & Borodich (2024), the idea is to interpret each step of Nesterov acceleration a single step of standard gradient constant a E (0, and a reference point I, the corresponding modified loss is defined as
modified loss, i.e., fau, tt in Eq. 8. Here for
()) = f(ax + (1 - a)æ).
(8)
For stochastic convex functions satisfying Assumption 4.2, we establish the convergence rate of Algorithm in the following Theorem 4.3, whose proof is in Appendix E. Assumption 4.2. Let f be convex loss function. For all t [T] and any E[V vf(x).
8

---

Published as a conference paper at ICLR 2026
Theorem 4.3. For a well preconditioner set H. let f be a convex loss function whose H-sooothssss constant is Λи (f) E (0, oo) according to Definition 2.4. For > T > O. consider Algorithm 2 with at 2/(t + 2) for t 0, ,.
L. Suppose x² is the global minima and m,. [2 x. b| S D for some D >> O and Assumption 4.2 holds with adaptive gradient
variance (x((ft)T=)) )² I 2 for some oH E 00). Then it holds that
-
2D
E [VT((V=-1+++
(>2
E
4
Eg. t=0
9.
T V,
gt
nTT + 1)2
2n
2
(T
1)2
2n2
(T 1)2 Ar (f) Öllog² d) + T oH Ö(log d).
Moreover, when choosing learning rate 1j D, the convergence rate becomes
[[f(ār) - [(x=) An (J) D2 log" d + dvED
T7 log
+
T
VT
Remark 4.4. A drawback of Algorithm 2 is that the optimal choice of learning rate 1j in Theorem 4.3 depends the unknown parameter D max, ||ar, x² 1/ To circumvent this issue, follow the approach in Kovalev (2025a) to introduce a projected variant (see Algorithm 8 and discussion in Appendix E.2), which ensures that all iterates remain inside a ll-llx-bull of radius D. The removes the requirement for prior knowledge of D, and we establish a same convergence rale in Theorem E.5.
Our convergence guarantee attains a deterministic component of order Ö(AN (f) (f) an accel- erated rate governed by the adaptive smoothness Vh (f)- In comparison, Guzmán & Nemirovski (2015) shows that any first order optimizer can only achieve Oi (111))) for the specific case of lo norm smoothness. Taken together, these results show that the adaptive smoothness is neces- sary to achieve the acceleration, which can't 't be replaced by the weaker -uclideid smoothness, highlighting its algorithmic benefit and answering Question 2 in the affirmative.
The analysis in Kovalev (2025a) yields similar results when H contains only diagonal matrices. However, their Assumption 4, which is critical for their analysis, imposes restrictive conditions on both the loss and the gradient noise for more general H. By contrast, our approach avoids such requirements by leveraging Lemma 3.3.
4.3 NONCONVEX RESULTS FOR NSD UNDER ADAPTIVE NOISE ASSUMPTION
The ineffectiveness of averaging in the dual space also leads to difficulty in reducing gradient vari- ance via averaging. To illustrate this, consider i.i.d. random vectors Ii...., ., In with E[æ;] = 0 and B|[|=: [3] < o², we have E[ll > xil factor in the latter bound can be tight. This causes the dimension-depencee NSD in the nonconvex setting, as shown in recent works (Pethick et al., 2025; Kovalev, 2025b).
o² while > x < d= and the extra convergence rate of
< n
||
In particular, the dimension- factor p supx ||=|| captures the mismatch between w.. and 1|2 For diagonal H., NSD reduces to SignGD with I1-11x,, |l- yielding P = O and vacuous bounds when T < d. We avoid this by using the adaptive variance assumption. We prove the stochastic rate of NSD in Theorem 4.5 and the proof is deferred Appendix F.I.
The concurrent work Kovalev & Borodich (2025) also leveraged the adaptive variance assumption to prove a dimension-free nonconvex convergence rate of NSD. However, they used smoothness metric similar to adaptive smoothness while our Theorem 4.5 uses the standard smoothness. Our rate strictly better because of the relationship between standard smoothness and adaptive smoothness.
Theorem 4.5. Let H be a well-structured preconditioner set. For any 2 0, a E (0,1), n >>>>>>>>> 0, and T E N, let {x be the iterates of Algorithm 3 with || Let Li (f) be the smoothness of the loss If w.r.t. I1-11ze according to Definition 2.3. Suppose Assumption 4.2 holds with adaptive gradient variance ore ( 0z Then it holds that
1| and mg V fo(wo).
Do
2n L
20
E
V f
(f) + aT 2onVa.
nI
Let 0g = -AOII-I1 (f) afao < then

---

Published as a conference paper at ICLR 2026
When T 0g" we choose a 2/3 and 1j V I T 5/12, The rate is O (0xxI11/3).
When 2 00" we choose a = vT" 17 1 17-11 The rate
(Aabit-l 100)
0g
11/2
If au
1. then
When T < ady we choose a 1 and 1 = 11
Ag T 1/2
The rate is O
(v AOLII-1 11 (f)T
47/4 "110
(Ao (4 V
When T 2 añ. we choose a = do and 1 VT
The rate is
717a
Theorem 4.5 shows that, with appropriate choices of the learning rate and averaging parameter a. NSD achieves dimension-free rate depending only the standard smoothness 11I-1 (J) and the adaptive variance Tu, thereby avoiding the unfavorable factor. Next Theorem 4.6 shows that such a dimension free upper bound is unattainable under the standard gradient variance assumption.
Theorem 4.6. For any 2 O, a E (0, > O, and T E N. let {æ:}i=o be the iterates of Algorithm 3 with any norm Il-Il- Suppose Assumption 4.2 holds with the gradient variance TH. (ff.)T 1)² o..1 for some IHI. E [0. oo). Then holds that
T Σ [ax))))
Ao T/
2n
1-11 (n)
2 aT "HI +20H11 -min (1, (1,0"/20b(1 20 ||+;
min
l1a))
a
where
(ill ||=,|| (12) = supx | sup
measures the distortion between the two norms.
Here the norm distortion xb(1] ||., || 112) can grow with the dimension d. Consequently, Theorem 4.6
gives two kinds of upper bound for the convergence rate of NSD:
When is small (e.g. T < d). the constant term IHI. dominates.
For sufficiently large T and small (for which the four terms are balanced), the last term in the upper bound becomes 1-11- (11) ||-, || [|2), which depends on d.
Moreover, such dependence on d is inevitable in the worst case as shown by Theorem 4.7.
Theorem 4.7. For any fixed Do. 02, dd learning rate n,, and any averaging parameter a, there exists a loss function f Rd + R. sequence of stochastic iid loss functions fo. fi, f1.....fr--.... fr-1 and
an initialization Bo satisfying the following conditions:(1) (xxa)-inf f(x) Dg and 4 (f) L; (2) For any x E R.d, it holds that EE[ [(x))] (f(x) and
- (s() $ o².
When running Algorithm 3 with || || bo learning rate n, averaging parameter and initial- ization xn = 0, it holds that
E
min T
[xx)) min (dLAno 2 2
Theorem 4.7 also shows two kinds of lower bound we can achieve on signGD with momentum:
When T is not large enough, we can achieve the lower bound f((o), which shows the hardness induced by the stochasticity and matches the first upper bound in Theorem 4.6.
On the other hand, if want to achieve the error e e 25- to, we require the number of steps 2(e od +), whose dependence on dimension d is ((d+).
conclusion, under the standard gradient variance assumption with || = || and ||- = I1- the d-dependent rate in Theorem 4.6 is unavoidable. In contrast, Theorem 4.5 attains dimension- free rate under the adaptive gradient variance assumption, highlighting a fundamental gap.
CONCLUSION
We extend the unified analysis of adaptive optimizers to nonconvex functions, establishing conver- gence rate depending on the adaptive smoothness. It strengthens the comparison between smooth- nesses that adaptive optimizers and NSD in the convex settings. We further show the benefit of adaptive smoothness by showing the accelerated rate of adaptive optimizers with Nesterov momen- tum. The benefit of adaptive geometry is also justified by comparing two kinds of noise.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint arXiv:140..1537, 2014. 15
Kang An. Yuxing Liu, Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, and Tong Zhang. Asgo:
Adaptive structured gradient optimization. arXiv preprint arXiv:2503.20762, 2025. 1, 5, 8, 15
Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux. The geometry of sign gradient descent. arXiv preprint arXiv:2002.080555 2020. 1, 15
Jeremy Bernstein and Laker Newhouse. Old optimizer, norm: An anthology. arXiv preprint
arXiv:2409.2032. 2024. 1
Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, et al. Deepseek Ilm: Scaling open-source language models with longtermism. arXiv preprint Siti::2000.022544 2024.
Lizhang Chen, Jonathan Li, and Qiang Liu. Muon Optimizes Under Spectral Norm Constraints.
arXiv preprint arXiv:2506. 5504,, 2025. 15
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xu- anyi Dong. Thang Luong, Cho-Jui Hsieh, et al. Symbolic discovery optimization algorithms. arXiv preprint arXiv: arXiv:2302.06675. 2023. 1
Xiang Cheng, Fred Roosta, Stefan Palombo, Peter Bartlett, and Michael Mahoney, FLAG n' n'FLARE:
Fast Linearly-Coupler Adaptive Gradient Methods. In International Conference on Artificial Intelligence and Statistics, pp. 404-414. PMLR, 2018. 15
Sinho Chewi, Sébastien Bubeck, and Adil Salim. On the complexity of finding stationary points of smooth functions in one dimension. In International Conference on Algorithmic Learning Theory, pp. 358-374, PMLR, 2023. 45
Ashok Cutkosky, Anytime online-to-batch, optimism and acceleration. In International conference on machine learning. pp. 1446-1454. PMLR, 2019. 15
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International confer- on machine learning. PMLR, 2020. 15
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama 3 herd of models. arXiv e-prints, pp. arXiv-2407, 2024.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 2011. 5
Alina Ene, Huy L Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021. 15
Kevin Frans, Pieter Abbeel, and Sergey Levine. What Really Matters in Matrix- Seeri--Whiteningg Optimiz- ers? arXiv preprint 20 2025. 15
Vineet Gupta, Tomer Koren, and Yoram Singer. unified approach to adaptive regularization in
online and stochastic optimization. arXiv preprint (cXiv:/706.0656) 2017. 5, 38
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor opti- mization. In International Conference on Machine Learning, 2018. 15
Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1-14, 2015. 2,9
Wei Jiang, Dingzhi Yu, Sifan Yang, Wenhao Yang, and Lijun Zhang. Improved Analysis for Sign- based Methods with Momentum Updates. arXiv preprint a50iv:2507. 220:2957.//091 2025. 15
11

---

Published as a conference paper at ICLR 2026
Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024.
Pooria Joulani, Anant Raj, Andras Gyorgy, and Csaba Szepesvari. A simpler approach to acceler- ated optimization: iterative averaging meets optimism. In International conference on machine learning. PMLR, 2020. 15
Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019. 15
Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An cimost-linner-tiee algo- rithm for approximate max flow undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 217- 226. SIAM, 2014. 15
Dmitry Kovalev. SGD with Adaptive Preconditioning: Unified Analysis and Momentum Accelera- tion. arXiv preprint 2rXiv:2506.23803 2025a. 6, 7, 9, 34
Dmitry Kovalev. Understanding gradient orthogonalization for deep learning via non-euclidean trust-region optimization. arXiv preprint arXiv:2503. 12645, 2025b. 9, 15,
Dmitry Kovalev and Ekaterina Borodich. On linear convergence in smooth convex-concave bilinearly-coupled saddle-point optimization: Lower bounds and optimal algorithms. arXiv
preprint arXiv:2411.14611, 2024. 8
Dmitry Kovalev and Ekaterina Borodich. Non-Fuclidean SGD for Structured Optimization: Unified Analysis and Improved Rates. arXiv preprint arXiv:2511.11166 2025. 9
Tim Tiz-Kit Lau, Qi Long, and Weijie Su. PolarGrad: A Class of Unifying Preconditioning Perspective. arXiv preprint arXiv:2505.11799, 2025. 15
Optimizers from
va Convergence Rate AdamW Mea- Huan Li, Yiming Dong, and Zhouchen Lin. On the O( Kija
sured by & Norm. arXiv preprint arXiv:2505.11840 2025. 32
Elliott H. Lieb. Convex trace functions and the wigner-yanase-dyson conjecture. Advances Math- ematics, 11(3):267- 228- 1973. 17
Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al. Muon is scalable for LLM training. arXiv preprint arXiv:2502.16982, 2025.
Devyani Maladkar, Ruichen Jiang, and Aryan Mokhtari. Convergence Analysis of Adap- tive Gradient Methods under Refined Smoothness and Noise Assumptions. arXiv preprint arXiv:2406.04559 04592, 2024. 3,
Depen Morwani, Itai Shapira, Nikhil Vyas, Eran Malach, Sham Kakade, and Lucas Janson. New Perspective on Shampoo's 's Preconditioner. arXiv preprint 1177422406.17748, 2024. 15
Thomas Pethick, Wanyun Xie, Kimon Antonakopoulos, Zhenyu Zhu, Antonio Silveti-Falls, and Volkan Cevher. Training deep learning models with norm-constrained lmos. arXiv preprint arXiv:2502.07529, 2025. 1, 6, 9, 15
Maria-Eleni Sfyraki and Kun Wang. Lions and muons: Optimization via stochastic folfk-
arXiv preprint arXiv:2506.04199 2025. 15
Ishaan Shah, Anthony M Polloreno, Karl Stratos, Philip Monk, Adarsh Chaluvaraju, Andrew Hojel, Andrew Ma, Anil Thomas, Ashish Tanwer, Darsh Shah, et al. Practical efficiency of muon for pretraining, arXiv preprint Nxiv:25555.0222... 2025.
Chongjie Si, Debing Zhang, and Wei Shen. Adamuon: Adaptive muon optimizer. arXiv preprint arXiv:2507. 1005, 2025. 15
12

---

Published as a conference paper at ICLR 2026
Kimi Team, Yifan Bai, Yiping Bao, Guanduo Chen, Jiahao Chen, Ningxin Chen, Ruijue Chen, Yanru Chen, Yuankun Chen, Yutian Chen, et al. Kimi k2: Open agentic intelligence. arXiv preprint arXiv:2507.20534, 2025. 1
Nikhil Vyas, Depen Morwani, Rosie Zhao, Itai Shapira, David Brandfonbrener, Lucas Janson, and Sham Kakade. Soap: Improving and stabilizing shampoo using adam. arXiv preprint arXiv:2409.1132/ 2024. 15
Jiaxuan Wang and Jenna Wiens. AdaSGD: Bridging the gap between SGD and Adam. arXiv preprint arXiv:2006. 16541, 2020. 5
Kaiyue Wen, David Hall, Tengyu Ma, and Percy Liang. Fantastic Pretraining Optimizers and Where to Find Them. arXiv preprint 2Xiv:2509.020466, 2025.
Shuo Xie and Zhiyuan Li. Implicit Bias of AdamW: too Norm Constrained Optimization. arXiv preprint arXiv:2404.0m 244:22404.04444, 2024.
Shuo Xie, Mohamad Amin Mohamadi, and Zhiyuan Li. Adam Exploits lx -geometry of Loss
Landscape via Coordinate-wise Adaptivity. arXiv preprint arXiv:2410.08/99 2024. 3
Shuo Xie, Mohamad Amin Mohamadi, and Zhiyuan Li. Adam Exploits SleelLk gettemy of
Loss Landscape via Coordinate- wiie Adaptivity. The Thirteenth International Conference on Learning Representations, 2025a. 3, 5, 6, 29,
Shuo Xie, Tianhao Wang. Sashank Reddi, Sanjiv Kumar, and Zhiyuan Li. Structured Precondi- tioners in Adaptive Optimization: A Unified Analysis. In Forty-second International Conference on Machine Learning. 2025b. 2, 4, 5, 6, 7, 8, 15, 17, 29,26
An Yang, Anfeng Li, Baosong Yang. Beichen Zhang. Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025.
Chenyang Zhang, Difan Zou, and Yuan Cao. The implicit bias of adam on separable data, Advances in Neural Information Processing Systems, 37:23988-222 -202,, 2024.
13

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
1.1
Notations
2
From Adam/SignGD to Adaptive Smoothness
2.1
Adam and SignGD can exploit &oe geometry, but different ways
2.2
Adaptive smoothness associated with well-structured preconditioner
3
Unified Analysis in the Nonconvex Setting
3.1
Adaptive optimizers with well-structured preconditioner sets
3.2
Convergence rate in the deterministic nonconvex setting.
3.3
Technical Contribution: Novel Matrix Inequality
4
Benefit of Adaptive Geometry
4.1
Adaptive Variance: An Analogue of Adaptive Smoothness
4.2
Acceleration Convex Functions
4.3
Nonconvex Results for NSD under Adaptive Noise Assumption
5
Conclusion
10
A Related Work
15
Auxiliary Results
15
B.1 Comparison adaptive geometry
18
Proof for the matrix inequality
20
D Unified proof for adaptive algorithms
25
D.1 Relationship between adaptive algorithms
25
D.2 Proof for weighted algorithm
26
D.3 Proof for the cumulative and EMA variants
32
Proof for the accelerated algorithm
34
E.1 Stochastic without projection
34
................................
E.2 Stochastic case with projection
38
F Proof for normalized steepest descent
39
F11
Convergence rate with respect to adaptive gradient variance
41
F2 Convergence rate under general-norm assumption
43
F3 Dimension dependent lower bound for NSD
44
14

---

Published as a conference paper at ICLR 2026
A RELATED WORK
Adaptive optimizers. Matrix-valued preconditioning methods such as Shampoo (Gupta et al., 2018) provide structure-aware updates and growing body of work refines their preconditioners and practice (e.g., improved analyesvimleementtioonss and Adam-Shampor hybrids) (Morwani et al., 2024; Vyas al., 2024; Lau et al., 2025; Si al., 2025). Variants like one-sided Shampoo/ASGO achieve stronger convex rates than earlier methods (Xie et al., 2025b; An et al., 2025), but the nonconvex guarantees are missing which we show in Section 3. The recent work Frans et al. (2025) views adaptive optimizers as a modified matrix whitening technique and points out it can outperform accurate spectral normalization (NSD our context). They highlight the variance adaptation is previously overlooked while we also want to understand the benefit of adaptive optimizers/geomettn
NSD. Cutkosky & Mehta (2020) proves the convergence rate O(1/7%.5) of normalized gradient descent with momentum on nonconvex functions. Pethick et al. (2025); Kovalev (2025b) extend the results to any normalized steepest descent while the smoothness metric becomes smoothness w.r.t. the specific norm NSD uses. Many works analyze popular optimizers by showing the equivalence to NSD under some norm, e.g. Lion NSD under -nom (Sfyraki Wang. 2025) and Muon NSD under spectral norm (Chen et al., 2025), and thus apply the classic optimization results. Jiang et al. (2025) achieves a similar result as our Theorem 4.5 but their noise assumption stronger than ours and only states the result for specific SignGD. The difference between the two kinds of smoothness is also discussed Balles et al. (2020) in the context for SignGD only.
Nesterov acceleration be viewed the linear coupling between gradient de- scent and mirror descent (Kelner et al., 2014; Allen-Zhu Zhu & Orecchia, 2014; Cheng et al., 2018). Through this lens, Cutkosky (2019); Kavis et al. (2019); Joulani al. (2020); Enc et al. (2021) applied it on adaptive optimizers with specific structures like diagonal/coordinate- wise and achieve deterministic ( convergence rate.
Acceleration.
B AUXILIARY RESULTS
Recall that we define (M arg gen H- for any M E S in Section 2. In this section, we will prove several important properties of Px which will be useful in proving the convergence rate for general well-structured H.
will help interpret these results when keeping in mind that Px(M) = 1/ when H is the PSD) matrix cone, i.e., there is constraint the structure.
We will first state Lemma A.2 in Xie et al. (2025b), which will be used a lot in our proof.
Lemma B.1 (Lemma A.2 in Xic et al. (2025b)). For any A,B H. (A, (B, H) holds
for all H E H. then it must be A = B.
Lemma B.2. For any M E S and any H E H. X 2 0, it always holds that (M, H) = (PH(M)? H) and (x + ALa)² (x) + Ala-
Proof. By property (c) in Proposition A.3 in Xie et al. (2025b), we know that for any M > O.
(M PH(MM) (M) HM)x(M)*
Px(
0.
Note that H + Pa (M) H (M) -M is bijection from H. to H. by lemma A.I in Xie et al. (2025b), so we have (M- - (M )2, H - (M 1
= 0 for all H E H. + H PP is also a bijection from 7/ H. So have that (M- Px 2 H) 0 for all H H.
For any À 2 0 and any H E H, we have that
(Px(M XLa)? H) (M + Ala, H)
H) + (AIa, H)
-(Px(M) H) + (Xla H)
= (PH(MM)² AIa, H)
Note that P* + 22,)² and (M) + AI are both in H. We conclude Px (M + AIa) PH(M)² + ALa according Lemma B.1.
15

---

Published as a conference paper at ICLR 2026
Lemma B.3. For any M1, M2 S4+,
For any 2 0,
PH(cM)2 (M)?. For any 0 3 A 3 B, it always holds Px(A) = Px)B))
Proof. For any H E H. we have that
(Px(M + M2) H
-M, + M2, H)
(M,, H) + (M2, H)
= =PPH(Mi)' : (Px()M)) H)
-(PM(Mi) +Px(MM2) H).
Then we have that PH(M) + M2)² PH(M)) + Px( from Lemma B.I. For any c 2 holds that
(Px(cM) H. =CMM H)
=c(M, H)
=c(PH(M) .H) = (cPP((M) H)
So also holds that Px(ccM)==cPx(M (M) from Lemma B.I. Moreover, when 0 A < B, (B (A) PH(B A) Px(A) Then Px(B)
(A(A) because X is monotone function.
Lemma B.4. If we define proju arg min | - H then it holds that proj (M) Px(M)
Proof. We define dm (H) J
H|
Tr((M H)M
(M H)
Then WHdM (H)
2(H M). Because H. is cone, by the optimality of proj [M), it always holds for any H H. that
0 = (
(M)), H proj (M) = 2 (proj z (M) M, H proj (M))
For any H' H. always choose H H' + proj (M). H H because H is closed under matrix addition. Then it always holds that (proj (M) M, H') = 0. On the other hand, Lemma B.2 shows it always holds that (Px) M, H') = 0 for any H' E H. Then we can get proj (M) (2 by Lemma B.1.
Lemma B.5. For any A, B S and any well precondiioereee set H.
[Px - P=(A)llop - B - --Al
Proof. We have that
PB = PA(A+ + B A) (
| Allop I)
(PH(A)² + B A op 1)
3 (H((A) + |B
A
lp
The last step by considering x + + Allon
$ VIIB
A lop for every eigenvalue
A of (A). Similarly we can also show (A) - PH (B) + B A op proof.
which finishes the
Lemma B.6. Tr]PH(X)) is concave function.
16

---

Published as a conference paper at ICLR 2026
Proof. For any psd matrices A and B, we have that
A
+
B
A + B
TT
PHc
min MCH
H
+ (T(HH)
2
2
(A, (A.H--)-
B, H
+ Tr(H)
min HER
2
2
(A, H 1) +Tr(H)
B, H 1) TT(
min HEH
+ min HEH
2
2
[r[P:(A)] + Tr(P:(B)).
Lemma B.7. Let A and æ. y Rd. It holds
[H((A + xx ) - PH(A + yy Olop S v2Il - yll2.
Proof. Set F(X, Y) == tr (vX vY) for x, Y = O. By Lieb's concavity theorem Lieb (1973),
F is jointly concave and positively homogeneous, hence superadditive:
F(Xi+X, +2) > F(X1, Yi) F(X2, Y2).
Define Ix = Px(HH) Then Hl is the pinching onto unital *-subalgebra H.
For any A, P.Q 0,
[pxx(A+)) -(A-) tr(At) - (TPAA((A)))))
Using (2)² = x ()), the cross term equals F(II (A) + HI (P), (1) + (Q)), which by superadditivity is least F(II((A) (A), II ( (A)) + F(II (P), II (Q)) tr
(T(P)(P)Px(Q) Hence
(Px(A+P) Px(A+Q]]I= [P (Q)
Write = ||0112, 8 = || u =x/r, v y/s, and cos 0 u v. For the unstructured square root,
VEE "y |f = 2 + 2rs cos2 0 s 2(r² + 2² 2rs 0) 2|| -
Pinching monotonicity of F yields
[< - 1l Il [xxx Ix( T) S || -Vyy yy 11 x
Apply Eq. with P wa. T Q yy T. [ PH P*(AAty T llop S [P((xx - Px "ll S v2 1 y
Lemma B.S. For any well-structured preconditioner set and any vector Rd, it holds that
|| Tr(Pu(<xT]]
Proof. We have that
(rrP [)]
min x. HeR
1 min
min x H - TcT((H) HEH
min
Vx H-
HCH.T((H)
Xie et al. (2025b) shows that || = minHER.D(HSSI x H-1 in their proof of lemma 3.3, which finishes the proof.
17

---

Published as a conference paper at ICLR 2026
Lemma B.9.
Px(gigt) g: arg min (x. gt)
| x
Proof. First we show that satisfies that ( 9 11 S 1. For any H E H and Tr(H) 1 1, have that
(x(l: gill - Px(9.. H (9ig)
=Tr(PH(9ig: HP (gig) _ )
9:g.
= =Tr(PH(gig. HPi Pu(gig.))
-Tr(H) 1
Then [[ 9:11 (UPrEe,T:(NS)) [P((gg))) ge 1l < 1.
Next, we can employ Lemma B.8 to show that
(Px(9 > gt, 9t) = Tr( Tr(Px(9:9]))* 9:9. Tr(P: ))
19
Because min |ae In (x, 9.) = ll x, and there is only one unique vector achieving this optimal- ity, we finish showing the statement.
Proposition B.10. For any well-structured preconditioner set H. let T (x((fthee) be adaptive gra- dient variance defined in Definition 4.1. It always hold ou(ife I Tr(Px(E)) when we assume f()) Vfi(z)][ Vfx(a))] 3 for any TT.
Proof of Proposition B.10. From Definition 4.1, can have that
ox((sheT))==
min sup E V (=) Vi( HERTTHH) a.!
min sup E [V) - -/()))) " HEH, a.t
min HE),
E
By the definition of Px E), we know that (, PH [ -1 = Tr(Px and
Tr(Px(E)) = min HER
Σ, H. Tr(H)
2
2 min HEH
E HT
min mEи
v E (H (H)
= min
H-H
HEH
2 ox((iteeT)
which finishes the proof.
B. COMPARISON ON ADAPTIVE GEOMETRY
Proposition 2.5. For any well-structured preconditioner set H C 84 and any loss function f Rd + IR, it always holds that L 11 (f) & Ax (f) < d T1 (f).
Proof of Proposition 2.5. For any H H. with Tr(H) S 1, by the definition of |I and |l-b,,. it holds for any Id that | 2 || and | I | Then by the definition of (f) Definition 2.4,
|V)(x) V5(y)
[V ()(g)) -11-11, (f).
LIH (f) = sup xn.
< sup 2.
x y H
18

---

Published as a conference paper at ICLR 2026
1.0
0.5
-1.0
-1.5
X1
91
Here we demonstrate the duality between the supremum of the primal norms and the infinumm the corresponding dual norms for any well-structured preconditioner set H. In particular, we consider 7 (all diagonal PSD matrices]. in which case I1-1lx = II-I and 1- Left figure: the - ball (black square) in the primal space is the intersection of all || || unit ball (colored ellipses) for E H with Tr(H)= S 1, that is, || ol is the supremum of all such primal || Fr norms. Right figure: the || Il-it ball (dashed black square) in the dual space the union of all ||- | balls (dashed ellipses) for H E H with Tr(H) < 1, that is, 1| is the infimum of all such dual || Il norms.
Figure 1:
11-11--
Therefore, further minimizing both sides over H E H with Tr(H) S 1, we obtain the desired result.
On the other hand, va |1- Then we have that Ar (f) S -111111- (f).
choose H' La H and Xie et al. (2025b) shows that ||-1
We can also choose H be all PSD matrices so that we know H S 7t" Then we know ||0|| SUPHEH,T((H)))
sup (UP [æl| ||0|| and ||l| inf (H))) || 2 inf (Tr)ss || Xie et al. (2025b) also shows that ||æl| H-- |0 = ||0||2- So we have that
[Vʃ(x) V
L R (f)
sup
0 3 ll
a.
fV f(
sup
æ 3/12
2.
1
Vd V (æ) v (
sup
d m.
Va x vl2
1
[Vf((x Vf(y))
sup
d a.y
x yll
1
Au (f).
Proposition B.11. For any set of stochastic loss functions (feheT and any well-structured precon- ditioner set H. it always holds 11-1l ((ft)er)² S ) < d Til,, ((ftee))?.
Proof. For any H E H with Tr(H) < 1, it always holds that |/ < ||uli for any E Rd. and thus
sup #ER
E|ll [/)l -[V
H.
sup EET .ERd [[
B[AA())]] H
19

---

Published as a conference paper at ICLR 2026
By minimizing H E H with Tr(H) 1, conclude that 11ll,, (ffiher)? 1 ox((feher)).
Similar with the proof of Proposition 2.5, can show that on((fehET)? s Ed - when choosing H* z We can also show that SUPiET. E ff())) [[Vf(
SUPieT, V [ Then combining them, we have that dsuPteT,aER. E V EIVA 2 ox((fihee)?. O
C PROOF FOR THE MATRIX INEQUALITY
Lemma 3.3. Let 2 0 and 3 E (0. For any T E N, consider any sequence of vec- tors go ................................
.T. 9T-1 E Rd. Let M-1 0, and recursively define M, 3M + 9:9. for = 0 T 1. For any well-structured preconditioner set H. define V₁ = arg min M, +
cl. H Tr( ()) for each E [T --11 1). Then for any H E ENNS it holds
T-1
T-1 Σ V.
Σ II, 9 < Tr(H) S where ST =
(V2 V.
Moreover, there exists an absolute constant C1, C2 > 0, independent of d, T, e, B and H. such that
|STIlop si (1+ log (1+
(
T
Σ 19 dl (11-)))))
( (-- T + log V7- + C2.
1
In the special case when H is commutative, the above bound can be further improved to
| lup $ 5(1 -BTT + log \V--o/elopp
Proof of Lemma 3.3. For each & = 0..... T 1, by the definition {M) we have
V 9: 12 = (V, HV, .9.9.) (V, HV, M,, + cla) - (V, HV, . + ela).
Since V. -HH E H. it follows from Lemma B.2 and the definition of (V:)*= T-11 that
V 9: 2 = (V. HV, D.V,-1,PP(00 PP
- -v, PM +
-V, VVV.
V22)
V. (V,2 -V3-3V2, V1-1)
Then summing over t 0, ..... T --1 gives
T
Σ
V g: H Σ H. V. (V2- V.
T-1
$ Hr)
Σ V. (v? - 3V22) V.
op
This shows the first part of the lemma. We next bound the spectral norm of -T-lv- VV? 8V2,)V
Note that (V22, B +cla)² (B( by Lemma B.3. Since M, M,+cl x (1M,-+elj, we further have V22 2 VV2 > by Lemma B.3. Therefore, since Xmii (V,2) 2
20

---

Published as a conference paper at ICLR 2026
can apply Lemma C.1 get that for any C 2 c2>00 0.
v. -V,- VV 3(og C loge)
12cd
(log V22) (og( +
x²
T262
120-1d
Tr(V?" - -V
π
3log C
loge)
1
3(log C
log c)
log 3
Ia +
(log( (V,2) -oog(
x²
x²
12ed
12C-
d
Tr|M + eld +
T2E2
π²
3log C
loge)
1
3(log C Coog--loooh log (log(V;3) log( log(V22 v(-1)
log
La
3
x²
12ed
12C--d
Trigigt T + Baa Ia)
x²22
where the first equality holds by Lemma B.2. Further summing over O,.... T gives
T-1
3(log C
log c)
1 Ia+
3(log C - log c)
Σ Vi (V2 - -vV =
Toog
(log( (\--)- - -log(V3)) (22))
n²
B
x²
1=
12cd
12C- d
T-1
Trig + B)eIokka
n262
T²
t=0
3(og C - loge)
1
Tlog
Ia + log( V2 V/-1/e)
π²
3
12cd
12C-'d d
T-1
+
d(L ((1-3)eT)
Σ |lge| & La
7262
n2
where the equality holds as V- (eLaa = Vela. Note that (og(1/3) log(1 1 + (1- - 3)/B) s
(1 3 for any 3 E (0. 1). Then by triangle inequality for the spectral norm, we have
T
3log C - log c)
(1-
3 T + log V2- /ellop
Σ V. (V2 - -V, 1=0
n²
op
+
12ed
+
12C-1d)
(a(1 B)TC +
T
Σ
9
x222
x²
t=
(10)
In particular, we choose
(1 -1-33) BYTB/ log /
e²
C max(e /c,cc)
(11)
4d(d(1 - ByT' + 2i
11::112
With this, the second term the right-hand side of (10) satisfies that
12ed
12C-Id)
))
(d(L-)))
ByTe +
S ?
1-
3
T log 12 /
2222
n
B
Plugging this back into (10), we obtain
6 3loglo(C/ C/c) (1-
Vv. -VV
T log /
7²
3
op
Moreover, by the choice of i (11),
C log (og(max(e2/2) 1)) = 2logg
[dd(d(1 - T) + Σr-1 19:
(L1-8)T//311 log V2 / .11 1))
max
21

---

Published as a conference paper at ICLR 2026
For convenience, denote A -1-3))//++og Then combining the above two displays, we get
VV-1//lloop and B 4d(d(1-8))e=
2T=0
T-1
19
11
6
3 n7
B A' 1
Σ
V (V? 1=0
A +
A
log
max
op
When A > 1, we always have max B/A, S +
B, which gives rise to the following bound
Σ
(V,
log(1 + B))
1=0
When A 1, using the fact that (og(1/x)) - 1/e, we have
A Alog
max
A' 1)
< A log(1 (1 + B) - A log & A Alog(1 + B) + 1/e.
In this case, the bound becomes
T-1
-
6
(1 log(1 + B)) + 1/c]
t=0
op
Combining the above two case, we can conclude that there exists universal constants C1, C2 > such that
Σ (V² t=0
logg Cz.
This completes the proof for general well-structured preconditioner set H. In this special case where matrices in H. diagonal, we have that
T-1
T-1
3V2,)v = -1-B3TI+++ 3 Σ V, (v?
Σ
LL V
1=
T-1
(1- + log VVV,3v)
where the inequality follows from the fact that Ia A- 3 log for any A 2 Further note that as V.-1 V. are diagonal matrices, they commute with each other. Then using the fact that log( AB) log log B when A and commute, we obtain
Σ vv -VV 3 (1 ByT + 3 t=
Σ (Vz) - log( V22)]
1=
- -1-3)TTIa log (V2_1/c)
Therefore, in this case it holds that
T-1
Σ V. (V, -V.
< 3)T + log V271///la
This completes the proof.
Lemma C.1. For any positive definite matrices X, Y E Rddd such that Y 3 X, holds for any
0 0 c C that
3(log log
12ed
12C ld
X 1111 1/2
(log X log Y) +
Ti(X
Y) -IX-Y)
x²
72 X2min X
x²
22

---

Published as a conference paper at ICLR 2026
Proof of Lemma C.I. For any 8 E (0, 1), since the matrix logarithm is operator concave, it holds that
1 - 6) + + = (1 - 6) log + d log Y. Reorganizing the above inequality yields that for all á (0, 1),
log((1
log( X + + X)) log
log X - -log Y
6
Taking the limit - 0, we obtain
log X - log Y = Olog x) Y].
The proof is completed by further applying Lemma C.2 with A = X Y.
Lemma C.2. For any positive definite matrix X Rdxd and any positive semi-definite matrix
A E gdxd, o, it holds for any 0 S S C that
3(log C log c)
12ed 12C-'d) R2 Amin ())
X 1/2
AX AX 1/2
2 log X|
+
+
Tr(A) Ia.
2
x²
(12)
Proof of Lemma C.2. We consider the following expansion of the matrix logarithm:
log(X X 5A) log X + //" (x (x+ 5A (X + 0(83).
This implies that
log X + 5A)
llog
0
I
I
i log X)[4|
lim 8-+0
A
dz.
X + =1
X + =1
Let Rdd be arbitrary unit vector. Note that both X 1/2 AA 1/2 and log (X) [A] are linear in A, and thus we first consider A uu for any unit vector Rd. We define the following two quantities
f(u, v) = = (x)g(X)(uuu [uu 110 - r o
f((x (X 2x+2 =Iaaa=uu T (X + =Ia)
(13)
g(u, = = x 1/2 X 1112
(14)
Now suppose that the SVD of X is X Udiag( A1,... A where U Rdd is orthog- A₂ U and (X + =f) = Udiag(1/(A) +
onal matrix. Then X 1/2 = U diag A
2),...,1// 1,(11 + T.) Writing à Uu and i = Uv then f(u, v) becomes
f(u. =
diag
üū diag t
Aι +==
Aa +
du
(uoū ū (1/(A1
1/(ha ( 22))
Similarly, g(u, v) becomes
g(u, v) 8 diag( A 1/2 ...., A -1/2 11/2jūū
yuū" diag( (1 1/2 1/2
,
...., 112360
( (1/2 1/2 1/2,,1/2111 (1/>=1//_...111_11)) 1/2))/
1// 1/22
Now applying the fact that 1122 1 J
-1/22 dz for any > 0, we have
x+s
11
a(u, v)
i i u, 1/2
1/2 (A1 z),..., //1111(1x /(v 2))) dz)
23

---

Published as a conference paper at ICLR 2026
To further bound g(u, v). we split the integral into three parts: [0,c], [c, C], and [C, oo) where 0 and C' >> are constants to be determined later. That is,
2
g(u, v) - π
ú, 1/2 1/2 + +) ,),..,. 1/2 / + =)) )2)))dz) dz)
3
i 8, (= 1//1//12 (A1 + 2/. /Ax + +z))} dz
3//12/(Ae
2
7²
ū i 8 (2 1/2 (A1 + :)...., 1/2 / + +2)) dz
=: 91 (u, v) + 92(2, v) + (u) v)
where we apply the triangle inequality and denote the three terms on the right-hand side by (i v), 92 (u, u), (u, v) respectively. We control cach term separately.
First, for gi (u, v).
3
gi(u, v) =
(ü O ú, (1/(A1+ + +2), ..., 1/(ha + +]]) z -1/2dz
π²
3
PC
| O S112
Σ
d
1/2
2 2/1/2
n²
(A= + z)2
3
| oll
2
x-1/2
n²
min A
12 ū O 0
011 cd
72. minie(d X7
where the first inequality follows from Cauchy-Schward inequality and in the second inequality we apply Xitz S 1 as each A; is positive. Next, for the integral over (c, CJ. we have
x,
3
g2 u, v)
(ū T o, (1/(A) + +2), 1/(Aa + 2))) x 1/2dz
3
(uo 6, (1/(A) + =)..... 1/(Aa + =))}>dz (T. =z
7²
3(log C loge)
(f
(u 3 8, (1/(A1 2),....,//(AA,, =2
7²
3(log C' - log c) f(u,v)
n²2
where the first inequality follows from Cauchy-Schwarz inequality, and in the second inequality we relax the domain of the integral to [0, oo), which exactly gives us f(u, v). Finally, for ga (u, v),
3
ga(u, (u v)
iu O o, (1/(A1 + 2),, 1/(ha + +))) x 1/2 dz
n2
3
1
1/2
| O 0112
Σ
111/2 dz
72
(he + 2)²
3
<
?
12 ū @ 812.60 C-ld
x²
where the first inequality follows from Sauchy-Schwarz inequality and in the second inequality apply x+== < as each A; is positive. Collecting the above bounds, we obtain
g(u, v) 5 3(log C - log c)
f(u, v) + 12 12 ū c 81 cd 12 û O 0 0
C-ld
(15)
n²
n² min of X?
24

---

Published as a conference paper at ICLR 2026
Now for any general positive semi definie matrix A E R with eigendecomposition A E auuuu apply the bound (15) each u, in the eigendecomposition and sum over all i to get
3(log C
log c)
12ed
ogg ong(U ui, v)
0i (ui, v) x² emin, X
x²
i=1
12C
d
d
+
as ü o ج113
π
Note that ú, ② 0 I
both and ö are unit vectors, Therefore, further have
3(log C
log c)
12ed
12C dd
0gg U; 1) $
0u o v) + n² min.ee
Cs +
04
A
π
1=1
1=1
3(log C' log c)
12ed
120 d
oil(u; 1) + n² .mingegg] X3
Tr(A)+
Tr(A).
n²
n
i=1
Recall the definition of f(u, v) and g(u, v) in (13) and (14). Then we have shown that for any unit vector V E Rd
0 x 1/2 AX 1220 3(log C' - log
12ed
12C d TT(A).
Tr(A) + n²2
n2
x² mingeld] X
Therefore, we conclude that
3(lg C - -llo))
12ed
12C-11d
X/1 1 1/2
θ log( (X)(A)
+
+
Tr(A) Ia.
π²
X)2 π²
D UNIFIED PROOF FOR ADAPTIVE ALGORITHMS
D.1 RELATIONSHIP BETWEEN ADAPTIVE ALGORITHMS
Cumulative accumulation (Algorithm 4) maintains the plain sum of past squared gradi- ents, thereby giving equal weight the entire gradient history. A famous example this category is AdaGrad.
EMA accumulation (Algorithm 5) computes an exponential moving average of past gra- dients, which yields a stationary estimate of recent gradient statistics. Notable examples include Adam and R.MSProp.
Weighted accumulation (Algorithm 6) applies geometrically decaying weights to past gra- dients, which differs from EMA accumulation in that it does not normalize the weights to sum one.
Algorithm General Adaptive Cumulative Optimization Algorithm
Hyperparam: 2 0, total steps T, learning rate 7), convex cone H S.,/ 3 Input: initialization 2o. stochastic loss functions (fr) Rdd xdR - R
Mo +
for t 1,2, ... :
g: < (((
M, < M.1 9:9,
V, + arg mill M. + ela, H-1) + (r(H)
æ; < 0t-1 V,V,-1 g:
return FT
25

---

Published as a conference paper at ICLR 2026
Algorithm 5 General Adaptive EMA Optimization Algorithm
Hyperparam: 0, total steps T, learning rate 7), convex cone H C S.,, 3 Input: initialization 20, stochastic loss functions (fr)== aduxdn + R
Mo <- 0
for t = 1,2, ,.2. ;
9, <- V (
M, +- 3M--1 + g:9:
V, + arg min MM + Eld, H- + Tr(H)
3, + xt-1 vVV, 9r
return Ty
Algorithm 6 General Adaptive Weighted Optimization Algorithm
Hyperparam: 0, total steps T, learning rate 7), convex cone H C S.,, 3 Input: initialization Zo, stochastic loss functions {fo)== Rdd. xda + R
Mu < 0
for t = ........... 2.....TT
gr (1(
M, + 3M,-1 + 9:9:
V. arg min [M + eLd, H- + Tr(H)
2, +- x:-1 VVVi gt
return ZT
We also put the definition of one-sided Shampoo (Xie et al., 2025b) in Algorithm 7.
Algorithm 7 One-sided Shampoo
Hyperparam: 2 O, total steps T, learning rate initial Mo. Lo = 0 Input: initialization æo, stochastic loss functions (f+)ī=1 Rddxxd. xdn + R
for = 1........ T
G. - (((,,-)))
L, - L, + G.G.
X, X 1- (Ln + +eld))
return ZT
D.2 PROOF FOR WEIGHTED ALGORITHM
Before presenting the main theorems, first clarify our gradient noise assumption below. As- sumption D.1 is stronger than the conventional noise assumption when it assumes the condition holds almost surely. assume the covariance matrix is bounded.
required in proving Lemma D.3. Lemma D.5 can still hold when we only
Assumption D.1. For any t E [T] and any æ E Rd, [[Vf(=)) = V f(x) where the expectation is taken with respect to the randomness in the loss fo. Moreover, there exists E 0 such that for all t t 0, - = V f(x)
- (.) f((x) 3 Σ.
With Assumption D.I in place, Theorem D.2 presents the general result for weighted adaptive al- gorithms stochastic nonconvex functions, which is then specialized to the cumulative and EMA variants Theorem D.7 and D.8, respectively. When plugging Σ = O in the stochastic rate, we can get the deterministic result in Section 3.2.
In this section, we will define H = arg min (E)) II (f). For all the M, and V in this section except the proof Theorem D.7 and Theorem D.8, they are defined as in Algorithm i.c. M, 3M-1 g.g." We will define gr- f(xx) and
M, 3M 9.9. Σ, V. Px (M. cla)-
(16)
26

---

Published as a conference paper at ICLR 2026
Then it always holds M, M, because of Assumption D.1. By Lemma B.3, it also holds V; = Vi-
Theorem D.2. For any 2 0, 3 (0. n O. and T E N. let {a, ne.)tn be the iterates of Algorithm I with well-structured preconditioner set H. where the update of follows the weighted version, ie., M,- 3M,- 9:9, for all l. E [T]. Let Az (J) be the adaptive smoothness of the loss J according to Definition 2.4. Then under Assumption D. 1, it holds that
84/2
Ir [PM((E T- +
cla)
V Vf
I
0=
E+
V5.
T
T
where & is given by
2Âu
{ "
+ +H (S + /2d 1/2 S| llop
(17)
and ST =
VV
For general well well-structured preconditioner set, ||Srllop Ô /) When the preconditioner set only has diagonal malrices, ||ST lap (1 +
Proof of Theorem D.2. With the shorthand g: Vate), we need to bound
E T
(V)(()))) = g Il
= E Σ Tr(Px(a.0))
(18)
where the second equality holds by Lemma B.8. By employing Lemma D.4 and Lemma D.5, we have that
E
(19)
T
TrVV%
9.9.1)
B \ Tr|v
E
T
IVVV
9.9.))
( Tr
Pt
T-
E
([
T-1
gi/2
E
T
Σ
Tr
g.g.
V.
|1
1=0
1=
t=0
(20)
It then suffices to bound the sum of Tr VV To this end, we apply Lemma D.3 to get
T-1 E
T
Σ t=
TV 9.9. S 2E
Σ Tr 9.9. / op Σ Tv "VV.29g9..))
(21)
Here, the second term on the right-hand side can be controlled by applying Lemma 3.3. For the first term on the right-hand side, need to apply the descent lemma. Specificallyy recall that H = arg EHH L (f), and then by second-order Taylor expansion.
f(x++1) f(xx) + (V f(xx) 0c+1 -x1) + AH (f)
[0 - xz 12
2
=f - (gt. V V.-lg,) 9.) + A (f)
V1 9: H
By taking expectation on both sides and summing over = 0, ,,...,?
1, we get
1 12 (f)
Elf(or) f(xo)) < EE Σ
Tr
E
V gi
2
H
1=0l
t=0
27

---

Published as a conference paper at ICLR 2026
Rearranging the above inequality, have
T
[ - f(TT))
nA (f)
T-1
Σ
Tr
9.g.'
+
E
Σ
Vi
gill H
2
t=0
Ao nAu (f)
T-1
V
9t
H
(22)
"
1=0
where the second inequality holds by the definition Do f( m fax). Therefore, combiningg (21) and (22) yields
T
20o + MAN (E)
E
Tr
9:9.1
9: 1l + 2 1Ellop E V
Tr - 9:g.1
"
1=0
t=
1=0
(23)
Now, we apply Lemma 3.3 both EΣ
V ge geller and EΣ Tr "9
-
V 9: which gives
T-1
V 9 S Tr(HH ||ST|lop = |S
T-1
V 1 gell22 - alIssn S
0m0
where ST = V (V? - BV, V Based on this, we further define
2 ff(o) min f(x) + nAn (f) Srllopp + / 2 lo S|| llop
ç = 17
(24)
Applying these bounds to (23) gives
E
TVV
-999. Sc
(25)
Now we can plug (25) into (20), and hence follows from (18) that
T-1
T-1
E
[2:))))
Tr TT(P((
T
T
t=0
Σ T
8./2
PM T-1 ela
1
1-12111111 Tr PH
(
VT.
remains to provide a concrete bound for [|St|lops which follows from Lemma 3.3 and Lemma D.6. Specifically, we know from Lemma 3.3 that
( (1- ByT
V
|t lop Ci
log
1g.11
d - -YT +1
+ log
+ +C2.
B
lop
(=0
(26)
Moreover, by Lemma D.6, we know that
1lgel12 = poly |
(1/ (f) (f).d. n)
0=0
Vr 1 = poly(T,
/I Ax (f) dd n)e).
28

---

Published as a conference paper at ICLR 2026
Then the first term in Eq. 26 satisfies
d
log
19:12
dl 3)T
+1 1 log [poly(T,
|Ellop [Vf(au)]l : An (f),d n, B, ()
1=
Ölog d)
where O(.) hides logarithm dependence on all problem parameters except d. Similarly, the second term Eq. 26 satisfies
91-
V
(1-BYT
+ log
+ Ö(lgg d)
8
B
op
Plugging these two bounds into Eq. 26 yields that for any well-structured H.
| ollp - Ō logd (1 (1-
B)T - log logd)
(27)
When H. only has diagonal matrices, we can improve Lemma D.6 with results in Xie et al. (2025a). The dependence on d can improved such that log( -i-1//eee = Ó(). Then Lemma 3.3 gives us
Vi=
| llap S (1 33T + log
(1 (L1-3)++00 +
op
This completes the proof.
Lemma D.3. Under the setting of Theorem D.7, let Ve be as defined in Eq. 16. Then it holds that
/
2
T
E. TV 9:
2
Σ E.
TV 9:0.1
op
E.
TV - 9:9.
2
2
t=
t=0
Proof. First we can compute the gap by replacing V. with V. follows
Tr (V, '9 = Tr
V. IV;
V, 9.9..
1 Tr V. 9:g. + Tr (V. - V.) V.VV 9:9, V,-1 (28) where the second inequality follows from the fact that TRAT & 1 THAAT TB
2
with A V. 9e and B VV, V.)V,-'g g:- Note that since V. = V, it holds that
V. V 3 V. Then we can upper bound the second term on the right-hand side of (28) as
Tr (v. v.)V, V. 9:9. V V.-1
s Tr [V. Vi 9.g. V.
TV..VVV
I ||V, - Vellop Tr(V;-2
[Px(M Px (M:)) lop 2
Further applying Lemma B.5 yields Tr (v- V. - (v V)), 9:g. T V.
s | M1 Tr 2 99g. T
- | 1>>|0pp op VV 9
(29)
where the second inequality holds because 0 M, Assumption D.1. Then plugging (29) back into (28), we get
M: g.g. T + + gig. A 2Σ based on
T-1
Tr(V. g:g.
Tv
9:0.
Tr Vi 1--1-v-11 9:0"
0=
t=
2 |
lop
T-1
Tr
9.g.
Tr Tr 9g...) (VVV22.9..)
2
t=0
29

---

Published as a conference paper at ICLR 2026
Lemma D.4. Under the setting of Theorem D.7. let Vi be defined in Eq. 16. Then it holds that
T E
9:9. 1)
T-1
E
Tr
E E
TM
>
E
Tr Tr(PH(0...))
t=
1=0
r=
Proof of Lemma D.4. For convenience, denote A, PH(gig ) and B, = Vi. Then
T-1
T-1
T-1
Σ B A.. B:). T-1
Σ
TH(Px(9.
Σ
TH[A.]
Σ
(A,
Now taking expectation on both sides and applying Cauchy-Schwand inequality, we get
T-1
Tr(P:((..))))
Σ
B
Σ
E B 12
1=
t=0
Applying Cauchy-Sehwand inequality again, we further have
T-1
T-1
1/2
E
Tr.Px(0.0.)1
Σ
E
B,
Arli.)
Σ
B
E
1F
1=
1=0
1/2
T-1 Σ
1/2
E
Tr
Pr P,
E
Tr(
1=0
1/2
T-1
1/2
E3
Tr[V
(
where the second equality follows from Lemma B.2 V, E H. This completes the proof.
Lemma D.5. Under the setting of Theorem D.7, let V, be as defined in Eq. 16. Then it holds that
E
ST. Pu (5 E + im0
+ (Σ
34/2
E
Σ Tr g.g.
V. (30)
t=
Proof of Lemma D.5. Recall that V. PH(M. + eTa) H. Then applying Lemma B.2, get
Tr[ Tr(V Tr( M, + e.)) Tr((M, + ".
(31)
Further plugging in M. = 3M + 9:9. + Σ, we have
Tr V.J Tri T + Σ + BM, + eIa) V.-
=Tr((E 3M + eIa) V. I1 Tr Ir V.
Applying Lemma B.2 again, we further have
Tr[ Tr[Px (E + 3-M,, + ela)² 1 Trigig. V.
Tr PM E 3M, cIa) ) + Tr(g.g. 1.
(32)
where the inequality holds because V. = P ( + - - > P Next, we will further control the right-hand side of the above inequality by recursive expansion.
For notational convenience, for any < < t, denote
A,
3
Σ +
3 M + ela-
i=0
30

---

Published as a conference paper at ICLR 2026
Then for any we have
(T.(PH((.)) = ET
PH Σ
3
Σ +
go+ g + cld)
1=0
ETT
PH
E1-o-1
Σ + g M 3 -e- ela)
1=0
where the inequality holds because Tr[Px [X] is concave X by Lemma B.6. Then since Ege-agi-. 1 - + E by Assumption D.I, we further have
E ET. ET
Pic
E + gets M -.9. -. + tta) 8'
1=0
E Tr [PH
(A. s+1 8r 9t -9-
Applying the same trick in (31) As+1 + 3 - 9 obtain
T (Px(A,)) (A.)] E Tr Pxx A s+1 9 PH s+1 3 9:- 9 9 11
IE Tr (As+1 + 3 99 Px AA++1 + -
E Tr PM(AA+1) PH + / 9t-
+ E Tr -: 9 (A, 3
S &T [Px(A.+1)] + Tr
PH + 3 9: -9- (33)
where the second equality is again by Lemma B.2 and the second inequality follows from the fact that PH(A.41 + 3r -1- = (A((A+)). In addition, note that
Ast1 + 5gg. P:----9- I.. = I2= 8r
E+ ++MM. + +9. +g.
ela 2 3 (M,. +ela).
Thus it follows from Lemma B.3 that
Px(A,+1 9 = PH(B" (M[BBB(MM_)))) (M,, Eld)) 3012 (M, + tld) B./2V.... (34)
Now combining (33) and (34) yields
E Tr P A.)] < ET (H Further telescoping over = 1,.... 1, we obtain
Tr-ht-------- Vo-al.
ETr [Px 33, eI)] = TT [Px A1)
E'
+
3 99..9._ Vi=1
1-1 3r
Tr
PH
Σ + +ela)
Σ 3 IT Vi-!
(35)
Now, plugging (35) back into (32), we obtain
ETrV
<
Tr
PH
Σ 3 E + Ela
+
3 Tr 0t- (9...TT.VV Vil
1-1
Tr
P#
8r Σ + cla
+ela
g 3)
ET 9
V. '].
Finally, summing over & = 0,1,...,
T - 1, we get
T-1
< T-1
T-1
Tr[V.
Σ Tr
PH
3 + +la
+ Σ
Σ
3(1-
Tr(g.g. V.
1=0
T-1
T
-
PH
3r
Σ + ela
+ +(
gi/2
E
Tr 9. V.
1=0
1=0
This completes the proof.
31

---

Published as a conference paper at ICLR 2026
Lemma D.6. Under the setting of Theorem D.2. for any fixed initialization Zo. let go .u and Vo...., Vr-1 be given by Algorithm Then the following hold with probability 1:
T-1
1 - 2(1 + [Vf(z)) + An (f)² d
1=0
V
|
<2((EEllap [Vv A An (f)² dn + ed.
Proof. In this proof, we will define H* - Tr(H).
We first control
Ei=o
119.l12.
According to Assumption D.I, we have
T-1
T-1 Σ I9 1=0
T
Σ 0=
1
llop
|| + +19. llop) - T op
+
19:
(36)
t=
1=0
So suffices to control the sum of [gell By triangle inequality, 1 |l
2
g.
9o lol12-
and thus only need to bound the distance 9r go. To this end, since all æ, we have
H
= V2 f(x)
=
H for
9 g0ll2 [zz) ff(o))l S H llop || æollz S Ax(f)
x 22112. (37)
Moreover, control each ||, T. l follows:
||0++1 - 22112 = 1? V. 90112 Tr(g V, 2gs)
= = Tr( PH ²9.9)
Tr² Tr( PM (M.) (g ))2
where the last equality holds by Lemma B.2. Then since M. 2 9.9. T. we have Px(M.) = PH(g.g.) by Lemma B.3, and it follows that
|x x.112 7²² Tr([s) dip
Plugging this back into Eq. 37, we get || goll2 S ())a so |g S 21 Ar dd. Now applying this Eq. 36, we obtain
2 2 +
Σ 11..11 S
T
T
21 27
up
$ 2( M op
+
11 1 Au (f) dT
(38)
Finally, we can bound ||V llop as follows:
VT- 12
V2 1 PM(M S TT((P((MT
Tr(M
where we apply Lemma B.2 the last equality. Note that Tr(Mr-1) = ETT 1Igr 112 + ed, so follows from (38) that
| llop $ 22([EEllop + 12 + An dn ed.
This completes the proof.
D.3 PROOF FOR THE CUMULATIVE AND EMA VARIANTS
We will derive the convergence rate of cumulative optimizers and EMA optimizers by reduct- ing from Theorem D.2. the stochastic case, the dependence on T of both convergence rate is O(T-1/4) matching previous results on specific examples AdaGrad and Adam (Xie et al., 2025a; Li al., 2025).
32

---

Published as a conference paper at ICLR 2026
Theorem D.7. For any 0, 17 O, and T N, let { (xeYT_o be the iterates of Algorithm I with well-structured preconditioner set H. where the update of M, follows the cumulative version, i.e., M, M, + 9:9; for all t E (T). Let Ag (f) be the adaptive smoothness of the loss f according to Definition 2.4. Then under Assumption D.I, it holds that
T-1 [V(
_ VT T1/4
Tr|P 7 [a)
1=0
where& & given by
8 Ö ( + (m An (f)+
log d)
Moreover, when setting the learning rate n
An Ax(f)) log
it holds that &
O(VAo Au (f) log d + d E
1/2 log" d).
Proof of Theorem D.7. The desired result directly follows from Theorem D.2 with 3 = 1, where we additionally apply the bound Tr Tr(Px(T2 + eIa)) S TH + &Ta) using Lemma B.3. L
Theorem D.8. For any 2 0, 3 E 1), n O, and E N, let {ar,)=- be the iterates of Algorithm 1 with well-structured preconditioner set H. where the update M, follows the EMA version, i.e., M, = BM + (1 of the loss J according to Definition 2.4. Then under Assumption D.I, it holds that
3) for all t E [T]. Let Au (f) be the adaptive smoothness
1 T1/4 Tr|Px elaa)*
E
V [((x)))
<VT"T
t=
where &. is given by
Ao N
n An (f) + ddd B||2
1/2
log d 13
up
log
vT
Moreover, when setting 1 - 3 = 0 -0(lodd)
logd
and 1 = Ax(f) log a' it holds that
K k= ==ō (ó(((V)) An (f) + dl | 10p
1/2 log logd).
When there is no noise, i.e., fo f, it holds that
1
V/e2/4 T1/
E
M [xx (l
S
V
VT
where K is given by
Do
n An (f)
(0)1)) 1
log d
K ò
-T
log d
nVT
T
VT
3
Moreover, when setting 1 - 3 = O logd
and
Ax(ff) log= it holds that
An
k δ (v (vAo Do An logd)
Proof of Theorem D.8. As mentioned in Section 3, Algorithm 5 is equivalent to Algorithm 6 with c/(1 3) in place of e and // /1 3 in place of 77. Therefore, the convergence rate of Algorithm follows from Theorem D.2 with this change of hyperparameters. Specifically,
T-1 VIT
B1/2
Tr(P T-1 B + 1-9 Ia)l
1 T
E
g
n.*
E+
VE
(39)
T
VT
t=
33

---

Published as a conference paper at ICLR 2026
where & satisfies
ç {= Ō A
(v' Au (1) + + +d
(1=21 log d logd)
(40)
8
We can further simplify the result for $ as follows. Note that Σ
B S 1 - () and
T-1
1
vB
v 2
Σ
8
v3
1 3
1- 8
then follows from Lemma B.3 that
1
Th
PH
Ja)
la
STr
PH
E
eTa)
Tr(P*(E+ddl +ela))
1-
vI-B
Applying these to (39), we get
T
V2 &
TT(Px + +lla)
E
E
Dell H. H.. S
T
T -1-3
VT
V1
1=
Denote E BJT. Then we have
V2 K +
TT (E + edail
Dell,.. S
VR.
T
T1/4
By (40), we know that λ satisfies that
Do
nAX (1) + +0>dv1=53 11
1/2 lop
(1) T + log dl
x: Ô
log
T/T
VT
B
This completes the proof.
E PROOF FOR THE ACCELERATED ALGORITHM
In this section, will define H arg T.) 41 (f). Our proof follows the strat- egy developed by Kovalev (2025a). For completeness, we reproduce some of the arguments to make the exposition self-contained.
E.1 STOCHASTIC CASE WITHOUT PROJECTION
Theorem 4.3. For a well-structured preconditioner set H. let f be a convex loss function whose H-smoothness constant is Aς (f) E (0, oo) according Definition 2.4. For
T > 0, consider Suppose xt is the global minima and max [r xxx H < D for some D 0 and Assumption 4.2 holds with adaptive gradient
Algorithm 2 with 0e 2/(1 (1+ + 2) for L = 0, 1,1,,... .T -
variance Tz (f((f )2 < o for some oH [0, oo). Then it holds that
2D
D2
T-1
- - < (T + 1)2
E ETT(VV
+
Σ
V.
2m
2
T
11
t=
2n²
(T+ 1y² Au (f) Ōlogg d) + Tizo
TH Ö(log d)
Moreover, when choosing learning rate 1 D, the convergence rate becomes
((((Tr) f(x))) )] = 0 Au (f) D2 log* d + dveDD
+ on D log
T2
/T
34

---

Published as a conference paper at ICLR 2026
Proof of Theorem 4.3. Combining the results of Lemma E.2 and Lemma E.3, get
T-1
E ff for. (x++1) - far.e. (x"))
D
Tr
DT(V--1)
D
1 2
T
9t
V
9t
27
211
7-1
+ E
(g: - vfnns (xt), V.
9.ll
1=0
Au (f) 17
+
E
V g
(41)
2
remains further bound the last terms.
For the last term on the right-hand side of (41), we apply Lemma 3.3 to get
1 geller. & Tr(H)) Ö(log² d) - d)
(42)
where the second step follows from the definition of H
For the third term on the right-hand side of (41), consider any H E H. with Tr(H) S 1, and then it follows from the Cauchy-Sehh Schwarz inequality that
T
9. v ff (x,), V
9t
S
E
fa 113) 1/2
9
12)
2=
t=0
1/2
T-1
E
9g:
V ai (x: || H--
E
V
9 1
t=0
t=0
Here similarly have E
Ö(log" d) according to Lemma 3.3. Then we further minimize over E H with Tr I to get
E
VVV
9el H Tr|H
Ö(og** d)
min HEH,T(HHSI
E
ge
fai
(x:)
T
T-1
min HE))T(H)
Vi + (1 a()a;) - Vf + (1- a))
T-1
< 2
1=
where the last equation follows from Assumption 4.2 and the condition on dH- Therefore, we obtain
T-1
1/2
Σ gt V ae (xx), V;- gi)
5 OH
Σ
a
ÖOlog* d) S oxx T/2 Öllog² d)
(43)
where we have plugged in the choice of a, = 2/(1 + 2). Finally, combining (41), (42) and (43), we obtain
E
aar Ei (x++1) fe (x)))(x)))))))))))))))))))))(( <
+ ETv
D2
!
T
Σ
gt
V,
g.
2n
2n
2
t=0
7? Au (f) Ölog? d) + T Ö d)
+
2
The proof is then completed by further applying Lemma F.
35

---

Published as a conference paper at ICLR 2026
Lemma E.1. Under the setting of Theorem 4.3, it holds that
4 E ( paine (x*))
BIf(#r)- f(x)))
(44)
(J
Proof of Lemma E.I. Plugging the definition of far.ee in (8), we have
T-1
T
fa,,"((xx))
pa (x++1)]
BIf(axx" + +11 - f(a00111 (1 - ac)x(e)
00 " (1)))))()) (((0(a))-(((---) f(
0i E (z)( - (J( f(x'))
(a, 21 11-aa) an) -a f(x'))
a (1 - an) (i) - f(x))) - -o-- f(x"))
where the inequality follows from the convexity of f. Plugging in the choice of a, 2/(t + 2), we further obtain
T-1
(T' + 1)² B[f(x*) - f(āT))
T
E
E(f(a,) - f(x"))
4
t=
t=
(T 1) B[f(x") f(xr)).
This completes the proof.
Lemma E.2. Under the setting of Theorem 4.3, it holds that
E (o. (0,,3((x)) (x²*
5 E
D3 2m
Th TT(V--1)++
D
1
5 g V. g1
2m
Proof of Lemma E.2. For every = 0, ,,,...,T T 1, by the convexity of fo it follows from the Taylor expansion of far.at at that
for (x,) for (x) & (V fer (xt). xt - xx))==== = (g., :; xx ( for (xx) -t. - xx)
(
Since g: is unbiased estimate of V fa..e (2:), taking expectation both sides yields
E faa (xx,) far (xx) E Egg, x. -x")]
By definition L++11 = x; V2 Dr, so it follows from Lemma E,4 that
(gt: De xx) S
27 | x: 11
2n |
x 11 + 7 11
Define V-1 for convenience. Then combining the above two equations yields
E pa (xx) fa (x=)
< E
1
||, x: x11
1
|
- x 11, + V. 9
2m
2n
1
1
E
||,;
x
"0112
11
||
x x²1lix/
2m
2n
E
1
|| xx
"12
Vi-,
"
2/2
V1 g 11
2m
36

---

Published as a conference paper at ICLR 2026
Summing over t, we obtain
T-
1 T-1
E ( f(
s E
x
+
Σ
|
x Vli
2n
2n
t=
1=
[y T-1
E3
Σ
V
9:
li;
2
1=
Since V. 2 V2-1, we have || 1 x where the second inequality holds because of the assumption that max ||0; x 11 S D. Therefore, we further have
1
V
S 1|
Tr(V, - Vi-1) S Dr.Tr(VV - V1-1),
D
T-1
T-1
E for.:e (xx) far.ee(""
S
E
Tr(V;
7 V(-1)+
Σ
V
g 11
21
2
DD2
T-1
E
Tr(V +
Σ
VV 9 liV
2m
2
1=0
D)2
" T-1
E
(Mr-1 + cla. Vi-11 +
Σ
IV, \V
2m
2 1=0
D2
D2 T-1
1 T-1
E
Trr (Tr(V==1)+ +
Σ
9:
T V
V
1-19
"T V. gt
211
2n 1=0
1=
Since Vi 3 VT-1 for all [T- 1}, have Di TV S 9, Consequently, T-1
V
9. for all
[T 1).
Σ fa (xx) - fai (x*)] [ S
D2c
Tr
(V(V--) +
D2
+
"
T-1
Σ
gt
V
9t
2m
2n 2
1=0
This completes the proof.
Lemma E.3. Under the setting of Theorem 4.3, it holds that
T-1
ga (x).)))))))))))))))))))))))))( - (2=-1)- fu, 2
a R (xx)
fe (xt) )) - 1)
Σ
VV gelli.
1=
t=0
T-1
An (2) 2 T-1
+ 1 Σ -
va (xz)), Vr Vo'gi)
gt) +
Σ 1=
VI, g 2
2
1=
Proof of Lemma E.3. By Definition 2.4, we have that
f(y) S f(x) + (Vf(x), x) + Ar (f)
||0 y1l
2
By the definition of fo in (8),
for. (x141)= S fai.ei (xx) + (V fat x x141 - xz) AH (f)
|
xz 11
= f n V f Rt 2 (x,), V.-ig.) + Ar (f) n²
V 9. H-
2
AN (f)
= n(gt, V gr) + (g: V p (ax). V. g.) +
vV-1gill H-
1
2
where we plug in the update rule for Ø1+1 in Algorithm 2. Summing over yields
T-1
T-1
T-1
Σ a R (x)
fa
S
Σ
par (x=)) - 1 Σ
VV; gt 11
T-1
An n2 T-1
+ n
(g: V Vf V
gt) +
Σ 1=0
VV 1 gg 1
2
1=0
This completes the proof.
37

---

Published as a conference paper at ICLR 2026
The following lemma is standard result for mirror descent. Lemma E.4 (Lemma 5, Gupta et al. 2017). For any To
E X, g E Red and H = 0, let x1
arg min (g, zo) + || Zoll H. Then it holds that
(g. xo x1 -
9
11:0
x1 11
Moreover, for any
X. it holds that
g x) - 200 1
2
||0|| x
H
200 x 11
(g. Fo x) K aro 1
|||
x
+
H
g H
2
E.2 STOCHASTIC CASE WITH PROJECTION
Algorithm 8 Accelerated Adaptive Algorithm with Projection
Hyperparam: 2 0, total steps T, learning rate 7) convex cone H C rradius D? Input: initialization zo = To. a sequence of positive constants , or E (0, 1]
M-1 <- 0
for t = 0, 1,2,.... .......... :
gi < V f (xt) where ft f: is defined in (8)
M, + Mi-1 + 9:9;
V. arg min HEN M, + ela, H H- + (H)
F141/2 + 32 - V, gt
T141 f arg min | <D 1 1/+11/21/2
T+41 + 0g +1/2 + (1 - at)
return TT
Theorem E.5 shows the convergence rate of Algorithm 8, which is the same as Algorithm 2 while removing the dependence on prior knowledge of D.
Theorem E.S. For well well-structured preconditioner set H. let f be a convex loss function whose H-smoothness constant NH (f) E (0, o0) according to Definition 2.4. For c > 0, T > O, consider Algorithm 8 with ae- = 2/(t + 2) for t = 0,1,..,,T 1. Suppose the global minima x² satisfies that |x" 2l S D and Assumption 4.2 holds with adaptive gradient variance (H(((e)E S oz for some O% E [0, o.). Then it holds that
T
(((TT)-((a'"
2D
ETI(V=))+ +
D2
11
4
E
T-1
91 t=
-
V.Vi gt
nT
+1B
2n
2
(T
1)2
2n2
(T+ 1)2 Au (f) Öllog² 2 d) + T1/2 on Ö(log d).
Moreover, when choosing learning rate = D, the convergence rate becomes
E[f(zr) f(==)) 0 Au (f) D2 log² d d/cDD
+ Tx log d
T
VT
Proof of Theorem E.5. Combining the results of Lemma E.7 and Lemma E.8, we get
[ 0r (#x41/2) par, (xx
"o="))((==') ==")}= E
Dd 2n
Th Tv(V=+)++ +
D
"
Σ 1=
91
V.
g:
2n
2
T-1
+ E
17
[g V fe (2))) V. gitl
Nu 72) T-1
+
Σ
V g
2
1=0
The rest of the proof will be the same as the proof of Theorem 4.3.
38

---

Published as a conference paper at ICLR 2026
Lemma E.6. Under the setting of Theorem E.5, it holds that
T-1
[[f(@r) [(x")] (T 1)2
Σ
(20-111)))112))) - faeeee (x*)
(45)
Proof of Lemma E.6. The proof is the same as the proof of Lemma E.I with 2441/2 in place of
Tt+1.
Define V-1 = for convenience.
Lemma E.7. Under the setting of Theorem E.5, it holds that
T
D2e
D 2n
T-1 Σ t=0
E
(an.e((0))) - -ass (xx) S
Tv(VT-1) +
9t V.
gt
2n
2
Proof of Lemma E.7. The proof is the same as the proof of Lemma E.2, except that controlling (gt, x²) requires some extra work. Specifically, by definition F4+1/2 = Et. V gr. so it follows from Lemma E.4 that
1 ggt, Bt -e-> x²) S 21j
1
? VV, || x x01 +
9: l.
21j
2
Since E++1 = arg min #c X, x|I|=//| 1 1/+1/2ll and | IIu S D, it holds that d ax | +
X(x 20+1) x1+1/21| Vi h=0
0, which implies that (x* x1+1) Vi(E++1 - 2c+1/2) 2 0. V/ | - I'1 + 2(x x(+1) Vi(I++1 - x++1/2) +
Then it follows that ||/+1/22 x²
| 21+1/21 2 | x x'
Therefore, applying this to the above inequality yields
(g, Ft. x²) S |x0. x 1
0++1 x 2 2 gell
21
2n
Then the rest of the proof is the same.
Lemma E.S. Under the setting of Theorem E.5, holds that
Σ ( fa (20)-1/2) - fe (xx")
ja (xx)) (pe.,((==")
Σ 1=
V gelli
T
11² T-1
gg. v (.r V, gt)
+
Σ
V
gt 1
2
Proof of Lemma E.8. The proof is the same the proof of Lemma E.3 with 2141/2 in place of 2++1-
F PROOF FOR NORMALIZED STEEPEST DESCENT
Suppose that || is norm IRd and I.-1l, is its dual norm. The following descent lemma charac- terizes the progress one step of steepest descent under || ||- Lemma F.1 (Descent lemma). Let f Rd - R be differentiable function. For any m Rdd let = arg max <1 (m, v). Then for any v > holds that
f(x np) < f(x) f=))), + 2n [Vf(()) mll. + y? 2 (f)
Proof of Lemma F.I. By definition the smoothness in Definition 2.3, we have
|m
f(x - nu) < f(x) (z) (17
L (f)
2
= [(() - (V (xx m, u) (m, u) + 7
2 L (n)
122
S (()))) + (m)) (x) mll. "/ 7|/m||
-/2 - H-1 (J)
39

---

Published as a conference paper at ICLR 2026
where in the last step use ||u||| and (m. u.) |||]|| by the definition of u. Then we further apply the triangle inequality ||m]] 2 [Vf(z)]] [VV ma| to get
1 (-(()))
f(x -j))= S f(x) [V/ + 2 V (=)) mll.
This concludes the proof.
Proposition F.2. For any 2 0, a E (0.1), O, and T E N. let {or) be the iterates
of Algorithm with III Let (f) be the smoothness of the loss f w.r.t 1-IIl according to Definition 2.3. Suppose Assumption 4.2 holds. Then it holds that
Ao n/T
2
2(1 -a)n (f)
E (2 1
+
E
m Vf(xo))l.
T
af
20 T-1
Σ
E
(g
Proposition F.2. Apply Lemma F.1 with ||||| yields that
f( f(x:) - - [V()) + [
+ 21) V (2;) mell.
(46)
2
Rearranging the telescoping sum of Eq. 46 from t t T - 1, we have that
1 - (f(xoo) min f(x)] [1|1(((mn
2 Σ ElIV(( mell.
E E[[f(())
n/
2
(47)
By the update rule of Algorithm 3, we have m, = (1 a (011-)m4-1+000 agt, so m. ff(x)) (1 (m (((a==)))((-_///aa->>>))) -V(a))))))-((())))-)-))))))))))) aag vf(z))).
Unrolling the above recursion, we get that
m4 (ax,) - am v)())))
Σ [u-a)t(a-a/VV/cea)-) Vf(z:)) a(g. -
and
f(;)) mmlle S (1 a)) - vf(0o))l= + i=1
- V(()))
Σ (r= v((aa))
a.
(48)
We know that
[V/(x=))) (<x))).. < (f) [1::-1 -xill S 1 (f).
(49)
Then plugging (49) into (48), we can get that
E [[)))( - m. ll. < (1 E mo VS(z0))l. + +(1 (
Σ (1-a)) v)(a.))
+ a.
< -1-10) (1-a)'E mo v.(ao))l. + 1-a a nL - (f(
+ aE
(1-a)--i6 V((..))
40

---

Published as a conference paper at ICLR 2026
Plugging it in Eq. 47, we have that
Ao
(nn((())
2 T-1
S
+
Σ
[11
||mo [/((a))
177
T
2
T
n 11 (f) + aE Σ - (g: - vf(a;))) |
+
T
1=0
Ao
(1)
2
2(1 a)n 1 (f)
+
E mg - vf(<x))l.
7/'
2
aT
T-1
20
+
E
(1 - a) (g: -.o-vf(z=)))
vf(z,))
T
t=
[m
F.1 CONVERGENCE RATE WITH RESPECT TO ADAPTIVE GRADIENT VARIANCE
The proof of Theorem 4.5 largely borrows from Kovalev (2025b), upon which we change the de- pendence on adaptive noise and improve some coefficient constant.
Theorem 4.5. Let H be a well-structured preconditioner set. For any 2 0, a E (0,1), 1 0, and T E N, let {x. be the iterates of Algorithm 3 with || = 1| and my V fxoo)) Let Lill (f) be the smoothness of the loss f w.r.f. I1-1 according to Definition 2.3. Suppose Assumption 4.2 holds with adaplive gradient variance a0d (x(((t)=))) < oz Then it holds that
T-1
2n L (f) + nT
Do
20H
E T
[V(md)
aT 20
10
Let dn- AOLLI (f) af, < then
When T < c we choose = 2/3 and
Au T 5/12 V L
The rate is O (OxTT
When T 2 an we choose a = 0a -3/4
"""' The rate is O (Anbi
Von
T1/4
If ag 2 1. then
When T & ar, we choose a 1 and 1) =
T 1/2, The rate is O (V 11,1,,1f3
An
AOLI-I1 (f)T
When T 2 ug
choose and 17
A/4TT 8/4 The rate is O (A (5))
von
VT
71/4
Proof of Theorem 4.5. By applying Proposition F.2 with ||-| ll.l have that
Ao
L
(f)
2 aT
2(1 10--00 a)m (1)
E B
<
E
|
v v
TT
2
2
+
-
Σ
E
(1-
(50)
1=0
H.*
We only need to bound [| Vf(zo) and Σ (1 a)- vf(x.))
For
H.* notational simplicity, define w; a and 6; g: Vf(=x)) By Assumption 4.2,
41

---

Published as a conference paper at ICLR 2026
know that [|6]|6,] 0 for 1. Then have that
Σ (1-a) aagi vf(a;))
E
wioi
H
Mi+
E
min
Σ wid; H
Σ w;o:
HEH.T((HS
min (E
B
w/o: 1H1
Σ wio:)
min (CH
w H-18 18
min (YH
wf 66,
Now by the condition on du and the definition of the adaptive gradient variance in Definition 4.1, we know that min H HH E|o 1 S oz4 for each i [4]. Therefore, we further have
E
Σ - -1-a) a)" ag: vf(z)))
S o
Σ
S
oza
(51)
i=1
where the second inequality holds by the definition of wi and the condition that a E (0, 1). Similarly, we also have
E mo - (.( = E Elgo - Vi(20)) S o
(52)
Plugging in Eq. 51 and Eq. 52 into Eq. 50, we can get
T-1
An
1L (f)
M
20H
+ 2(1 - a11
E
|V fV
+
L (f) + 2VOOH
nT
2
aT
A
20
20 2V/On
II (f) +
(53)
r/''
aT
Next, we will choose appropriate hyperparameters 1/ and a to achieve the optimal rate.
For any fixed 1, balance the first terms the right-hand side of (53), choose
Ager
= V
2TL 11 (f)
Also, for simplicity, denote ag V DOLi 11e (f)/oH. Then the convergence rate becomes
200LIH1 af
20t
|V(x)ll S <21
+ 2 22/an
aT
S 22/20x(0
Val (Vat
ao
at + Va
(54)
We further stratify the values of a, ag and T to minimize the right-hand side:
When a < 2/3 of 2 aa. We only need to minimize of VarT' which is achieved at 2/3 because it is monotone decreasing function in a. So the convergence rate is always no better than that in the case of a > 2/3
When 2/3 + S Va. We only need to minimize Va + Val" Then do /T
is the
global minimizer but there constraints 2/3 $1
42

---

Published as a conference paper at ICLR 2026
When ag T-1/6 have that
T Then need choose - VT
2g
and the rate is oz
1/3 + ( 11 (f)T - 20
When do 2 VT. we have that
Go VT
2 1.
Then we need to choose a and the rate
oH + v
2
1 1/2--//2
-When T-1/6 I ao I VT, we have that T
S 90 vT
S 1. We can choose 2g
vT
The rate becomes (1 (f)) V02111111111 1/4
This completes the proof.
F.2 CONVERGENCE RATE UNDER GENERAL-NORM ASSUMPTION
Definition F.3 (Distortion of norms). For any larget norm ||-Il and reference norm |H on
finite-dimensional vector space, the corresponding distortion of [|-I] with respect to l|-llret is defined
as
x
== sup wn
ac lee
sup
||æ|||
(55)
Since all norms on the Enite-dimensionee space are equivalent, ([II-1111111ee is always finite.
Theorem 4.6. For any 2 a E (0,1), > O, and T E N. let {æ:)7=o be the iterates of Algorithu 3 with any norm I1-II- Suppose Assumption 4.2 holds with the gradient variance I11 (f. ) I o.. for some 1111, E [0, oo). Then it holds that
1 Σ [Vf(2))l nJT
Ao
2n
2 oT IH,. +2 min (1,a"?</(1 || l1z))
(f)
+
a
where v0ll ||,,1| (12) = sup
supr c measures the distortion between the two norms.
Proof of Theurem 4.6. Since El|mm ( [|+] S 11-1. it follows from Proposition F.2 that
Do
I
10
2(1 (1)-))n LI-(())
5
+
nT
2
of
a
1
2a
E
Σ
(1
ag -Vf(())())))
(56)
T
t=0
i=1
There two ways to control the last terms, and we discuss them separately below. For the first approach, we directly apply triangle incquality to get
E.E Σ (1 (11-a)= a) 'g. Vf(z,)))
< E
a(1 - a)² || v((x))l.
a(1 - v)(2;))1 01-11-
(57)
For the second approach, we first convert
|| - to
||
||2 and get
2
||||||
E
(1- -f((a))
<
sup
E
Σ a(1 (11-aa0 a(1-a)) vf(x,))
[2:
|
sup
a2(
a)
2(-
Ellgg vf(x,)
|
|,|||_
2
x 2
2 t
< sup
sup
Σ
a
2 a 2 g: vs(x;) [13]
|
| ll.
1=0
<
(111-11
o
43

---

Published as a conference paper at ICLR 2026
Using Jensen's 's inequality, this further implies that
t a Σ
S sa1/2/111 -V-(aa)))
||,, -1l)) ---
(58)
Now, by taking the minimum over the two bounds in (57) and (58), we obtain from (56) that
Au (
20 af
2(1 211-a)n LIp.1 (f)
V S nT +
+
a
20 -l. min (1,a"/2/(() (00(1-ll,ll] -122))
This completes the proof.
F.3 DIMENSION DEPENDENT LOWER BOUND FOR NSD
In this subsection, we construct the example for the lower bound in Theorem 4.7.
Lemma FA. Fix any O. For any distinct points Io, I1...., JT where T 2, there exists function R + R, such that its derivative p' is 1-Lipschitz, p(xo) - inf, p(z) S 1 and (Ix) for I....
Proof of Lemma F.4. We use g(x) to denote (xx in the proof. For any set of points {z, = C R. will construct g(x) such that g(x) explain what it requires to construct this function For such g. because of the periodicity, we can always find 2g V/ I /1 I S yr' Tu + for T" S T so that for any 2t 20, there a ys such that there exists n E N satisfying 2, = yy + c. n and therefore g(x,) = g For any Ie zo, g(z,) -e by definition. Also for zo. it holds that p(æo) p(æ) and g(x) is 1-Lipschitz. Then it suffices to construct g(x) in the interval [To, To + i) to satisfy the following conditions
for xo and g(2 + g(z) for 2 zp. We first
((x) is 1-Lipschitz in [mo, + H-
For any x >> wp, be written as xo 8 + ne- for some 8 E (0, and negative integer n,, and thus p(x) = - g(z)dx+ pro g(x)dr. Therefore, ensure that p(x.) inf p(x)) S 1, we require p(ro) p(x0+5) san root g(r)dz 2 -1 for any 0 < 8 < and + g(x)dr 2 0.
g(y.) for 0, I.... T"
We will further define 41 xu + in the following construction.
For each f = 0, 1.... T', we construct on the interval [ye, 3t+1] as follows:
-cc (I ye), E lye. (vt + /t+1)/2];
g(x) 1-e- (x v0+1),
x E ((), + #t+1)/2 vt+1].
is straightforward to see that g 1-Lipschitz on [no To + 6 -1] and g(y)) = - for =
0, 1," 1. Also, note that g(x) 2 - for all Io zo + =. Thus, for any 0 < 8 < !
always holds that pzo+ g(x)dr -ed -1. Then it only remains show g g(x)dr 0.
44

---

Published as a conference paper at ICLR 2026
By direct calculation, we have
T
11+1
E((c1 11) + (yt+1 ye
g(x)dx
Σ
g(x)dr= Σ
30
1=0
y1
T
= =-1
(1++1 y11²
1=0
t= (y++1 - y1))
T"
2 --1 +1+
4
T' +'+1
-1 4T' + 1)
where the inequality holds by Cauchy-Schwand inequality. Since T + TT55 I diately follows that goot g(x)dr 2 0. This completes the proof.
Tez. it imme-
za
Theorem 4.7. For any fixed Do; I,,o²,d, ,d,,,,TTT d,,, learning rate 1, and any averaging parameter o, there exists a loss function f :R - TR, a sequence of stochastic iid loss functions fo: JI. "'.".."JT JJT1 and
an initialization Bo satisfying the following conditions:(1) f(o) f(x))((())))))( = Do and L (f)
L: (2) For any x E Rd it holds that E f( = f()) and (( - vf(x) | <
When running Algorithm& 3 with 1-11 || || bo learning rate n, averaging parameter and initial- ization Zo = 0, it holds that
E
min LETT
[V
1o}
Proof of Theorem 4.7. Inspired by Lemma in Chewi al. (2023), we first rescale the original problem parameter-free scaling for simplicity. Indeed, for any f, (ft [T 0 2n satisfying the
conditions (a) and (b), we can define hxx) A Aff////aaa and hy (x) A, !. fe( / Lx). Then it can be verified that h satisfies that h h(zo) - inf æ h(x) = 1 and Li (h) < 1. Therefore, it suffices to construct h and associated stochastic loss functions ha hi...., hr-1 such that h( inf h(x)= = 1, LI-II (h) S and h1 [[(x))] & a /LAo. and then the construction completed with the reverse transform fax) Do h(v L./ Aoar) and f((x) = Ao h4( Tga))
Correspondingly, we can rescale the learning rate and the iterates of Algorithm 3 on the loss function to transform {== be iterates obtained by running Algorithm 3 on the loss function can be casily checked that æ, = / Lä,, where (#t) are the iterates obtained by running Algorithm 3 on ho...., hr-1 with learning rate // L// Au and momentum factor Then if it holds that [m T-1 [[Vh@ min {e 25- (d 1//-11111/// we immediately have
1/2 -2 25-20') where o' -/vVLa LL
2o')
E
[[[(a)))]
min 1=0.1....7711 T-11
T.D
-mnnfe 1200ee--5--0 -
(dLA )
which gives the desired result in Theorem 4.7. Given the above discussion, we only need to construct
a loss function f Rd + IR and associated stochastic loss functions fo. fi...,, fr-1. such that (xx)) inf f f(x) = 1, II-- (f) < 1 and B[(l))(( -V < and show that
for all = 0, 0,...,T 1,
f((x))]1 = min (e 23
dtot
7 e-5 25-
Below present a construction for such hard instance.
45

---

Published as a conference paper at ICLR 2026
Construction of loss functions. the target quantity as
We consider initialization Zg 0. For convenience, define
/ 1/2
min 51/471/2
(59)
V5
We first construct a sequence of independently random noise vectors òu , 8--1 as follows.
For constant C o² Se and constant 0 iid variables R4 Bernoulli()). The Bernoulli distribution is well-defined because 0 S 1 by
2a each random vector d, - Re where
5c2
the choice of in Eq. 59. Then we know that E[6,] = -C#14 = 211
B|||8|1|] diElio, Cd00 =E
and
Σ Ri,i 01 ))) 2
E| 8|
E[o.]1l C
C2
d 0 d(d 1)B R 011
C2 [d |01 0)2 + (1 0) + + 1)(20(1-0))
C² [d0(1 - 0) + d(d- (1-00
S C² (d0 + 4d
< 50 = o²
(60)
The last inequality holds because d0 < by the definition of 0. And we can verify that [E[ (,]1,] =
and E [|o E[6.]1]]] s d0 ṭ² by plugging in Sc and 0
a²
dea do?-
Next, we construct the loss function f. Consider the set of points S {0, 17, 21, ..... (N 1)m)
with N = - We then invoke Lemma F.4 with set Sn.c and level -e to obtain one-dimensione. function p. such that its derivative p' is I-Lipschitz, p(0) inf, p(x) S and p' pknnn) -e for all k < N. Now we define d R as
( Σ p(x;)
(61)
Leveraging the properties of p, we can show that for any x. x E R.d.
f(æu) - inf f(x) < Σ
(p(0) inf p(z)) S 1,
iml
[V) f(('))l
Σ (x(x)) p' (x/)) S 2| 2'1la0
where the last inequality holds because is 1-Lipschitz. This shows that f satisfies the desired condition (a). Then for each t = 0....... T - 1, we define the stochastic loss function ft as
f(()) = f(æ) + (8. x) + e _ (1d, x).
(62)
Its gradient is given by
fz) vf(x) + 6z + d
la-
By the previous construction of 6,, it is clear that E (z)) fz))), and it follows from (60) that the variance of (xx) under || || satisfies [(()) v f Eil|,, [[ o² Therefore, the stochastic loss functions
satisfy the condition (b). Next, we proceed to establish the lower bound for E Emin f where zp. TI..... ØT are obtained by running Algorithm 3 the constructed loss functions fo. f1,..., fr- with ap 0.
46

---

Published as a conference paper at ICLR 2026
Lower bound gradient norm. First note that by the construction of the loss functions and the choice zy = 0, the coordinate-wis dynamics have the same distribution across coordinates, ie., (Zo,s 2. has the same distribution as (1 ...... 2r-1.)) for all i,j E [d]. Utilizing this observation, we have
min [+x)))) E
= E
min rel21
l (wen))
min ln' ((( 1E|2
E min l (m)))))] LE|T
(63)
So it suffices to focus the dynamics in the first coordinate.
By the construction of the function p in the previous step, we have (0) = -c. Therefore, when Fr,1 have [<=(( = p' (ari )/d + 6G,1 e/d St,1- 1- Consequently, since so, 0, the first coordinate of æ will remain to be zero until at some step 5,,1 o 0, in which case we must have
dt,1 C. This implies that
min(t E (T) F1,1 # 03 min fLE [
[7] [V/(m))] = -c] =
and this stopping time t follows geometric distribution with parameter 5e2 distribution of o, Hence,
dof
again by the
J1 = 7 1/1] = (1 r3
P T
2 cxp 0 11)
2
Now conditioned on the event that t. we can show that
1 1 8
Vdo
4
42 Voc
V5e²
Il which is smaller than T by the choice of in Eq. 59. Therefore, we have FT,1 0 for all
t = 0, 1,...,7 and there are at most T - t distinct points among 20, 21,1 ZT,1- Then since [m041 m2/ is either 0 or 7 by the update rule of Algorithm 3 with that 20,1, 21,1: 2T,1 E {0, m), 2n...., (N 1)n} on the event 7 2 1. in which case we have (1(xa.) = for all .,...,77 T by our construction of p. Leveraging this, follows from
Eq. 63 that
E min [>x [
2 E min y (((_))) Lie(?)
P 7 d 2 -2
E min (((2)))) [E(T]
This gives the desired lower bound and completes the proof.
47


Reviews:
[{"review_id": "OclJ5UEKGe", "reviewer": "Reviewer_7CSx", "summary": "This paper provides a rigorous theoretical separation between adaptive optimizers (like Adam) and normalized steepest descent (NSD) (like SignGD). The authors' central thesis is that these two algorithm families utilize different assumptions, even when operating in the same non-Euclidean geometry. The paper shows that NSD's convergence is governed by standard smoothness ($L\\_{||\\cdot||\\_{\\mathcal{H}}}(f)$), while adaptive optimizers are governed by a provably stronger (more restrictive) \"adaptive smoothness\" ($\\Lambda\\_{\\mathcal{H}}(f)$). The authors justify this distinction by showing that this stronger assumption is what allows adaptive optimizers to achieve Nesterov acceleration, a feat that is provably impossible under the standard smoothness assumption alone. This \"tale of two notions\" is extended to the stochastic setting with the introduction of \"adaptive variance\" (a more precise, structure-aware noise measure) and is complemented by a new unified convergence proof for adaptive methods in the non-convex setting.", "questions": "Please refer to the weaknesses section.\n\nIn addition:\n- Is there a function that is not adaptively smooth but still has a finite $L\\_{\\\\|\\cdot\\\\|\\_{\\mathcal{H}}}(f)$? Otherwise, the two assumptions would characterize the same class of functions, differing only by constants.\n- Regarding the practical implications, it seems that full-matrix AdaGrad should outperform Adam, since its corresponding $\\mathcal{H}$ is a superset of that for Adam, leading to smaller adaptive smoothness. Is there any empirical evidence supporting this?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- By identifying the two distinct smoothness notions and linking the stronger \"adaptive smoothness\" to the ability to achieve acceleration (which is provably impossible for the weaker, standard smoothness), the paper provides a clear separation.\n- The authors' parallel \"adaptive variance\" argument is well-supported, as they provide not just a pessimistic, dimension-dependent upper bound for standard variance (Prop D.4) but also a corresponding lower bound (Thm 4.7) to prove that this $d$-dependence is unavoidable.\n- Beyond its main thesis, the paper provides a strong technical contribution by delivering the first unified non-convex convergence analysis for adaptive optimizers using general well-structured preconditioner sets.", "weaknesses": "- I am not fully clear about the distinction between adaptive methods and NSD, as the author claims they exploit different notions of smoothness. For instance, under the adaptive smoothness assumption, NSD could potentially also achieve the same rate as in Theorem 3.3, and when combined with the acceleration technique in Eq. (4), could possibly also attain an $O(1/T^2)$ rate for convex functions. Conversely, adaptive methods could also match the rate of NSD under $L\\_{\\\\|\\cdot\\\\|\\_{\\mathcal{H}}}(f)$ smoothness.\n- Regarding the theoretical results, Assumption 3.1 appears stronger than the standard boundedness-in-expectation condition. It requires that the noise be bounded for every realization of randomness. Additionally, Theorem 3.2 does not appear to guarantee convergence; could the authors clarify why this is the case?\n- Finally, the cited lower bound for non-acceleration applies to $L\\_{\\\\|\\cdot\\\\|\\_{\\infty}}(f)$. It remains unclear whether this separation holds for a general $\\mathcal{H}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "ZgBpWBh9RG", "reviewer": "Reviewer_E5SU", "summary": "This paper analyzes a class of adaptive preconditioning algorithms for convex and non-convex, stochastic optimization under an assumption on the objective function called adaptive smoothness. The non-convex section essentially extends the analysis of Xie at el (2025a) from the convex to the non-convex setting (Theorems 3.2 and 3.3), which requires a lot of technical work for the case of non-diagonal preconditioners. The convex section extends the accelerated $1/T^2$ result of Kovalev (2025a) from diagonal preconditioners to a more general class of preconditioners (Theorem 4.4), analyzes normalized steepest descent (NSD) under an adaptive noise assumption (Theorem 4.6), and provides a lower bound of sign descent (i.e. NSD w.r.t. $\\ell_\\infty) with a standard, non-adaptive noise assumption.", "questions": "Questions:\n1. Do the results in stochastic setting actually require almost surely bounded noise, as in Assumption 3.1? (see Weakness #2).\n\nSmall suggestions:\n- It should be added as a condition to Lemma E.2 that $X$ and $A$ are diagonalizable, since the proof uses an eigendecomposition for both of these matrices. Similar conditions apply in Lemma E.1 for $X$ and $X-Y$. This does not affect the proof, since the analysis only applies these lemmas for symmetric matrices.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The paper is well-written and contributes to an important problem, namely understanding the improved performance of preconditioning based optimizers.\n2. There are a lot of theoretical results, and from what I can tell, these results are not simple repetitions of known ideas. In particular, the results in the non-convex setting rely on matrix inequalities that involve a good bit of technical work. I checked the proofs of these matrix inequalities (Lemma 3.4 and all lemmas it relies on), and they appear correct.\n3. Several of the results demonstrate a clear separation between regimes: the accelerated $1/T^2$ rate under adaptive smoothness (Theorem 4.4) improves on the known $1/T$ lower bound under $\\ell_\\infty$ smoothness. Also, the dimension-free rate of NSD under adaptive noise (Theorem 4.6) improves on the dimension-dependent lower bound under non-adaptive noise (Theorem 4.7).", "weaknesses": "1. There are several examples of exaggerated or inaccurate language related to the contribution of this work. I feel that the paper would be stronger if the writing was more direct, transparent, and objective about the contributions and the relationship to previous work. Below are some examples.\n\n    1a. The paragraph on lines 64-71 seems to misrepresent the authors' contribution. The paragraph states that the contribution is to show the accelerated $1/T^2$ rate for preconditioned algorithms, but really the contribution is to extend the results of Kovalev (2025a) from diagonal pre-conditioners to a more general class. I think Kovalev (2025a) should definitely be cited here, and it should be clarified that the current paper extends the proof techniques of Kovalev (2025a).\n\n    1b. Definition 2.2 should cite Xie et al (2025b). Under the current presentation, it is easy for the reader to mistakenly believe that the adaptive smoothness from Definition 2.2 is a novel concept introduced by the authors, and indeed I got this impression after reading the introduction and first few pages. I recommend that the authors clearly point out when they are building on previous work. This is especially important during the high-level discussion about the power of different smoothness notions: it is easy for the reader to mistakenly get the idea that all of these high-level concepts were introduced by the authors, when really (in my opinion) the main contribution of this work is technical (e.g. matrix inequalities to handle non-commutative preconditioner classes), not conceptual.\n\n    1c. Lines 83-86 state that \"our results demonstrate that adaptive smoothness and adaptive variance are not simply stronger versions of their standard counterparts but profoundly different conditions that unlock qualitatively stronger guarantees\". How is $1/T^2$ qualitatively stronger than $1/T$ and not just quantitatively stronger? To me, this kind of language comes off as over-selling the work, when really the technical contributions speak for themselves. I encourage the authors to spend less time in the draft discussing the \"profound\" implications of their work and more time on direct, transparent discussion.\n\n    1d. It is stated that Lemma 3.4 may be of independent interest. Given that Lemma 3.4 is a bound on terms specific to the algorithm considered in this paper, I don't see how this result could possibly be of interest outside the context of this algorithm.\n\n2. Assumption 3.1 seems to require almost surely bounded noise, which is stronger than previous work. Is this a typo in the statement of Assumption 3.1, or does the proof actually require almost surely bounded noise? If it is the latter, then there needs to be some discussion of this fact and point out that stronger results are only achieved under stronger assumptions. I would also appreciate if the authors discuss why this stronger assumption is necessary in the proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "N33Gs3Hmlx", "reviewer": "Reviewer_MwWV", "summary": "The paper compares standard non-Euclidean smoothness (governing NSD/Lion/Muon-style methods) with a stronger adaptive smoothness that underpins Adam/Adagrad/Shampoo-type optimizers. It extends adaptive smoothness to the nonconvex setting (unified analysis for well-structured preconditioners), proves accelerated $O(\\tilde{T}^{-2})$ convex rates for adaptive methods (unattainable under standard $\\ell_{\\infty}$ smoothness), and introduces adaptive variance that yields dimension-free NSD rates in stochastic nonconvex optimization.", "questions": "-  The paper compares to NSD’s standard-smoothness rates and highlights separations, but the discussion of near-optimality (w.r.t. $d$, $\\tilde T$, and geometry) is mostly qualitative. For instance, are the nonconvex \\emph{$\\tilde O(T^{-1/4})$} stochastic adaptive rates minimax-optimal under the proposed adaptive variance? Are the $\\log d$ factors necessary for broad non-commutative $\\mathcal H$, or artifacts of proof technique?\n- Could you specify practical projection oracles for common H (diagonal, Kronecker, spectral)? \n- Can you propose online, low-cost estimators (e.g., streaming sketches of gradient covariances projected onto H or trace estimators for $P_H(\\Sigma)$? to upper-bound $\\Lambda_H(f)$ and $\\sigma_H(f)$ during training? A brief “estimation recipe” would make the theory far more deployable and allow users to select H adaptively.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Two genuinely different smoothness/variance regimes with algorithmic consequences. The paper formalizes why “adaptive optimizers is approximately NSD with a norm” is not the full story: adaptive methods converge under adaptive smoothness $\\Lambda_{\\mathcal H}(f)$, which is always $\\ge$ the standard smoothness used by NSD (Prop. 2.3). Under adaptive smoothness, accelerated $O(\\tilde T^{-2})$ convergence with Nesterov momentum is achieved (Thm. 4.4), while standard $\\ell_\\infty$-smoothness faces a $\\Omega(T^{-1}/\\log T)$ barrier (via prior lower bounds cited by the authors). The analogous adaptive variance notion similarly strengthens stochastic guarantees (Def. 4.1), yielding dimension-free NSD rates (Thm. 4.6) that are provably unattainable under only $\\|\\cdot\\|_{\\mathcal H,\\ast}$-variance (Thm. 4.7). This idea is interesting and well substantiated by aligned theorems.\n- Unified nonconvex analysis for adaptive preconditioners beyond diagonal cases. Theorem 3.2 (and its corollaries) covers weighted/EMA/cumulative updates over well-structured preconditioner sets $\\mathcal H$ (matrix subalgebras), extending nonconvex analysis beyond diagonal preconditioners that prior works largely required. The matrix inequality (Lemma 3.4) controls  via  $\\mathrm{Tr}(H)\\,\\|S_T\\|_{\\mathrm{op}}$ and explicates where extra $\\log d$ factors enter for non-commutative $\\mathcal H$. This step makes unified treatment possible and should be of independent interest.\n-  Results are parameterized in terms of the geometry $\\mathcal H$ (e.g., diagonal vs. general PSD cones), update style (weighted/EMA/cumulative), and budgeted noise control (minimizing $\\mathrm{Tr}(P_{\\mathcal H}(\\Sigma))$ or $\\sigma_{\\mathcal H}(f)$). The two-phase behavior (deterministic $\\tilde O((\\Delta_0\\Lambda_{\\mathcal H}/T)^{1/2})$ vs. stochastic $\\tilde O(T^{-1/4})$) and explicit \\emph{log-factors} can be useful for practitioners anticipate when acceleration/normalization helps and when geometry-induced constants dominate.", "weaknesses": "- The main guarantees hinge on adaptive quantities—$\\Lambda_{\\mathcal H}(f)$ (minimizing trace bounds over a preconditioner set) and $\\sigma_{\\mathcal H}(f)$ (sup over $x,t$ with minimization over $H\\in\\mathcal H$). These are hard to estimate or upper-bound in realistic deep-learning settings. The paper discusses relationships to bounded covariance (e.g., via $\\mathrm{Tr}(P_{\\mathcal H}(\\Sigma))$) but stops short of estimators/diagnostics practitioners could compute to check assumptions or guide geometry choice. Without empirical proxies (e.g., online estimates of $P_{\\mathcal H}(\\widehat\\Sigma)$, curvature sketches, or trace surrogates), it’s difficult to translate the theory into optimizer selection.\n- While Theorem 4.4 achieves an appealing $O(\\tilde T^{-2})$ term, the bound carries \\emph{$\\log d$ penalties} and depends on a radius $D=\\max_t\\|x_t-x^\\ast\\|_{\\mathcal H}$ (mitigated by a projected variant). The paper provides a projection-based algorithm with the same rate, but the \\emph{constants and projection effects} (e.g., clipping bias, implementation overhead) are not explored. Similarly, non-commutative $\\mathcal H$ introduces unavoidable $\\log d$ blow up via Lemma 3.4; it would help to quantify when these factors remain small (e.g., block-diagonal or Kronecker-structured $\\mathcal H$) or to show empirical results indicating the log-factors are not rate-limiting in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "lgvZR5wJUr", "reviewer": "Reviewer_aLQH", "summary": "The paper relaxes the convexity assumption in the analysis of adaptive optimizers. It also introduces new assumptions in the analysis.", "questions": "Line 053: the adaptive smoothness (cf. Definition 2.2), introduced by Xie et al. (2025b) \nit not called adaptive smoothness in the origin (at least I could not find). It is confusing. Usually the algorithms are adaptive to smoothness. Please, clarify the naming. It is assumption, does it adapt?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contribution is relaxing convexity assumption accompanied by the technical results.\n\nOther contributions consider different assumptions in the analysis.\nFor acceleration the authors use the recently introduced smoothness in Kovalev’s analysis, but convexity is here. Despite the assumption used in other papers I do not consider its incorporation as a significant contribution – Kovalev’s assumptions are standard and more widely used in contrast to the considered assumption which was introduced very recently. But still it enables new rates.", "weaknesses": "- New variance assumption improves dimension dependence. But no surprise since the assumption is different. I mean the improvements are not because of improved analysis or new techniques. The discussion is given in Lines 450-454 and states that the dependence is unavoidable in the worst case. \n\nDetailed discussion is needed. How does the adaptive variance assumption relate to the standard one? Does it hold in practice?\n\n- Some theorems do not properly refer to the assumptions used.\n\n- Line 465: 1/T^-3.5. \\varepsilon?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)