SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration
Authors: Dmitry Kovalev
Venue: ICLR 2026 Poster (2026)
Keywords: convex optimization
stochastic optimization
adaptive optimization
gradient methods
accelerated methods
Primary area: optimization

Abstract: In this paper, we revisit stochastic gradient descent (SGD) with AdaGrad-type preconditioning. Our contributions are twofold. First, we develop a unified convergence analysis of SGD with adaptive preconditioning under anisotropic or matrix smoothness and noise assumptions. This allows us to recover state-of-the-art convergence results for several popular adaptive gradient methods, including AdaGrad-Norm, AdaGrad, and ASGO/One-sided Shampoo. In addition, we establish the fundamental connection between two recently proposed algorithms, Scion and DASGO, and provide the first theoretical guarantees for the latter. Second, we show that the convergence of methods like AdaGrad and DASGO can be provably accelerated beyond the best-known rates using Nesterov momentum. Consequently, we obtain the first theoretical justification that AdaGrad-type algorithms can simultaneously benefit from both diagonal preconditioning and momentum, which may provide an ultimate explanation for the practical efficiency of Adam.

Published as a conference paper at ICLR 2026
SGD WITH ADAPTIVE PRECONDITIONING: UNIFIED ANALYSIS AND MOMENTUM ACCELERATION
Dmitry Kovalev
Yandex Research da kova 1 ev @gmaigmal com
ABSTRACT
In this paper, we revisit stochastic gradient descent (SGD) with AdaGrad-type preconditioning. Our contributions are twofold. First, we develop unified con- vergence analysis of SGD with adaptive preconditioning under anisotropic trix smoothness and noise assumptions. This allows us to recover state-of-the- art convergence results for several popular adaptive gradient methods, including AdaGrad-Norm, AdaGrad, and ASGO/One-sided Shampoo. In addition, we es- tablish the fundamental connection between two recently proposed algorithms, Scion and DASGO, and provide the first theoretical guarantees for the latter. Sec- ond, we show that the convergence of methods like AdaGrad and DASGO can be provably accelerated beyond the best-known rates using Nesterov momentum. Consequently, we obtain the first theoretical justification that AdaGrad-type al- gorithms can simultaneously benefit from both diagonal preconditioning and mo- mentum, which may provide an ultimate explanation for the practical efficiency of Adam.
INTRODUCTION
The optimization community has shown strong interest in adaptive stochastic gradient optimization methods over recent years (Duchi et al. 2011 Tieleman, 2012; Kingma & Ba, 2014| Gupta et al.) 2018 Reddi al.] 2019) due to their applications in deep learning (LeCun et al. (2015). This re- search direction has notably led to the development of Adam (Kingma & Ba 2014) and AdamW (Loshchilov & Hutter 2017). algorithms with remarkable performance training deep neural net- works. Unfortunately. despite almost decade of research, these algorithms continue to be the preferred choice for most deep learning tasks, particularly in the training of large language mod- els (Achiam et al. 2023, Liu et al. 22044a] Grattafiori et al.] [0244 Anil et al.] 2023). The lack of worthy contenders to Adam and Adam may be attributed to insufficient theoretical understanding of adaptive optimization algorithms. Therefore, the primary objective of this paper is enhance the theoretical comprehension of this research area. Formally speaking, we consider the following optimization problem:
min f(x), =EX
where is finite-dimensional Euclidean space, and f(x): X R is a continuous convey objec- tive function. We assume that problem T has solution x= E X.
1.1 BASELINE ALGORITHM: ADAGRAD
The starting point for the development of Adam and Adam was the gradient descent (GD) with the AdaGrad-Nomi stepsizes (Streeter & McMahan 2010). Given the parameter >>>>> 0 and the past gradients g; E (z.))) for O..... k. this algorithm performs the following update:
Tk+1
7e9K where
17
It is well known that AdaGrad-Noma can achieve the convergence rate O(I/K) of GD with fixed stepsizes for smooth functions with Lipschitz-continuuu gradients and the rate O(1V/K) of GD
We discuss the justification for using the convexity assumption in Appendix

---

Published as a conference paper at ICLR 2026
with diminishing step sizes for non-smooth Lipschitz functions when only stochastic gradients
are available (Orabona 2023: Li & Orabona 2019 Levy et al., 2018). However, the main benefit of
this algorithm that it can achieve both rates with the single parameter choice 77 || ||. In other
words, it can adapt to the level of smoothness and gradient noise of the function [(x),, which is called
"universality" [Nesterov] 2013). Furthermore, [Duchi et al.] (20TT); McMahan & Streeter (2010)
proposed the AdaGrad method, which performs a coordinate- variant of the update (2). aiming
to exploit the potential sparsity of the gradients 9k. Although they provided a limited theoretical
justification for the benefits of voordinate-wing wise updates compared to scalar stepsizes (2). AdaGrad
and its modifications, such as RMSProp (Tieleman 2012) and Adam, have proven be highly
efficient in practice.
1.2 ADAPTIVE GRADIENT METHODS WITH STRUCTURED PRECONDITIONING
Motivated by the success of AdaGrad, many adaptive optimization algorithms has been developed that fall into the category of gradient methods with preconditioning. Such algorithms use the update rule of the form
arg min (gx, 2²) + b11lz 36 "
Fk++1
xEX
where Hg E S is symmetric positive definite preconditioning operator X' X. Besides AdaGrad, which uses a diagonal preconditioning matrix, notable examples of such algorithms in- clude Shampoo (Gupta al. 2018) and its theoretically streamlined variants: One-sided Shampoo (Xie et al. 2025) and ASGO An et al., 2025). Motivated by the structure of neural networks, these algorithms are specifically designed for optimizing the function f(X): R R of an m n ma- trix argument and use preconditioners that respect the function's s structure. In particular, One-sided 1/2G, where G mx= and G. E (x))). Overall, the practical performance of Shampoo and its Adam-like modification, SOAP (Vas et al. 2024), is comparable to that of Adam and sometimes exceeds it.
Shampoo and ASGO use the preconditioner Hg G + eE G,G.) )
Here, we come to the following issue: every time an adaptive preconditioned gradient method is developed, one has provide separate convergence proof, even though the update rules in such algorithms, as well as the convergence proofs, often have a similar structure. Consequently, we arrive to the following question:
Q1. Can we develop a unified convergence analysis that would cover most existing adaptive preconditioned gradient methods, including AdaGrad, Shampoo, ASGO, etc.?
A positive answer to this question was partially provided by the unified approach of Gupta et al. (2117). who showed that the preconditioner operator Hę can be defined optimization problem over linear subspace of self-adjoint operators H. C S. For instance, the update rule for AdaGrad-Norm and AdaGrad can be obtained by choosing H to be the space of multiples of the identity and the space of diagonal operators, respectively. Unfortunately, the unified approach of Guppa et al. (2017) has major flaws: still requires separate convergence proofs for different algorithms,, provides convergence guarantees only for non-smooth functions, and offers no explanation for the benefits of using general preconditioning operators.
solution to a certain
1.3 MATRIX SMOOTHNESS AND ACCELERATION
Matrix smoothness. In attempt find theoretical justification for the success of adaptive preconditioned gradient methods, a considerable amount of recent research has focused on devel- oping theoretical analyses of such methods under the assumption that the function smoothness, as well as the gradient noise level, is measured in terms of the weighted Euclidean norm ||. [B where B S + is a self-adjoint positive definite operator. For instance, [Lu al. (202bb); Jiang et al. (224)) provided an analysis of AdaGrad under anisotropic smoothness, i.e., in the case of the di- agonal operator B: x + b O x, where b, x E IRd.. When the vector b is sparse, they managed to prove substantially better theoretical convergence guarantees for AdaGrad compared to AdaGrad- Norm, thus obtaining theoretical justification for the practical benefits of diagonal preconditioning. Similarly, An et al. (2025); Xie et al. (2025) considered the matrix smoothness, i.e., the case where the operator B: X + BX, where the matrix B E mm is symmetric and positive definite, and X E Rmxn This allowed them to theoretically justify the practical success of Shampoo-like al-
2

---

Published as a conference paper at ICLR 2026
gorithms. However, Question 1 discussed above is relevant here: separate convergence proof is required for each algorithm, even though they share many similarities.
Momentum acceleration. Besides diagonal preconditioning, momentum is another key component that contributes to the efficiency of Adam. It is well-known that Nesterov momentum (Nesterov)
1983) can accelerate the convergence of GD for smooth convex (Nesterov 2013) and convex-
(Hinder et al. 2020) functions up to the rate O(1/T²). Consequently, there is an array of works that aim establish theoretical guarantees for AdaGrad-type methods with Nesterov acceleration, including the works of Levy et al. 2018); Cutkosky (2019); Kavis et al. (2019); RRodomanov el al.) [Kresseer et al. (2024). However, to the best of our knowledge, all such algorithms achieve ac- celerated theoretical convergence rates only for scalar stepsizes. Therefore, another natural question appears:
Q2. Can we design an adaptive preconditioned gradient method that provably benefits from both diagonal AdaGrad-type precondiiioonin and momentum?
To the best of our knowledge, the only attempt to answer this question was made by Trifonov et al. 2025). However, they made additional unrealistic assumptions about the dynamics the precon- ditioning operator and considered only a smooth and strongly convex, non-stochastic setting. Their theoretical results provided highly limited explanation of the benefits of preconditioning, including a lack of adaptation to stochasticity and matrix/anisotropic Hölder smoothness.
1.4 CONTRIBUTIONS AND RELATED WORK
In this paper we give positive answers to Questions and 2 and provide the following contributions:
(i)
We develop a unified analysis framework for adaptive preconditioned stochastic gradient methods under the matrix Hölder smoothness and bounded variance. Using this frame- work, in Section 3 we provide a single convergence proof that is applicable to most ex- isting AdaGrad-type -trre algorithms, recovering the state-of-the-art convergence guarantees for AdaGrad-Nor Norm. AdaGrad, and ASGO/One-sided Shampoo. Moreover, we establish con- vergence guarantees for DASGO, a computationally efficient variant of ASGO proposed by (nn et al. (2025), and find its fundamental connection with the recently proposed Scion method by Pethick et al. (2025).
(ii)
We develop novel unified analysis of adaptive preconditioned stochastic gradient methods with Nesterov acceleration under the additional assumption that the smoothness and noise operators L and E, commute with any preconditioner HІ.- In particular, in Section 4 we show that the convergence of algorithms with diagonal preconditioning. such AdaGrad and DASGO, can be significantly improved with no extra assumptions compared to their aeneeecelerteed counterparts. To the best of our knowledge, this is the first theoretical justification that AdaGrad can benefit from both momentum and diagonal preconditioning.
We also provide discussion of additional related work. First, we discuss the theoretical analysis of the exponential moving average (EMA) in AdaGrad-type algorithms by Défossez et al. (2020). Second, we mention several parameter-fi free AdaGrad-type -ttppee algorithms that do not require tuning the parameter Finally, we discuss the concurrent unified analysis of AdaGrad-type algorithms by Xie et al. (2025), which appeared online earlier than our work but suffers from several substantial drawbacks. The details are postponed to Appendix B due to the maximum page limit.
PRELIMINARIES
2.1 UNIFIED PRECONDITIONING FRAMEWORK
In this paper, we use the notation described in Appendix A The preconditioned gradient method uses the update rule in eq. (3), which requires the preconditioning operator H2 S Similar to the approach of Gupta al. (2017). we restrict the operator H₃ to belong to a certain subspace of self-adjoint operators H C S. As discussed in Section
1.2 we can obtain most existing AdaGrad- type methods by choosing different instances of the space H. However, to develop single unified
RRefe to Assumptions and for precise definitions.
3

---

Published as a conference paper at ICLR 2026
convergence proof for these algorithms, need impose formal assumptions the space H. This is done through the following Definition I and Assumption [
Definition Let (h): I + be scalar function defined on an arbitrary interval I C R. Let S₁ C & be the set of self-adjoint operators, with eigenvalues lying in I. The corresponding operator function (H): S₁ + S is defined as follows:
& (H) - E
(4)
where H = M.P is the cigendecomposition of the operator H E St, that is, X E are the eigenvalues of H. and P; S are the projection operators onto the corresponding eigenspaces.
Assumption 1. The space of linear operators H. C S satisfies the following properties:
(A1.1) The projection onto is order preserving, that is, projæ(H) E ES_ for all H E S4+.
(A1.2) The space H is closed under arbitrary operator functions, that is, (H) E for all H E H and (h)): IR- R.
Next, according to Gupta al. 2017), describe unified way to define the preconditioning operator H₃ E S++ based on the choice of the space H. Given the past gradients gu..... Ik E X, the preconditioning operator Hç is defined solution the following optimization problem:
HA arg min (H, Sa) + +I, ((H)), where S₁ = ----ooof (gi: >), HERnS
(5)
where <(h): I + R is a strictly convex non-negative potential function. The optimization form of this definition allows the use of the standard tool from online optimization, the Follow-the Leader/Be-the-I1 Leader (FTL-BTIL) lemma (Kalai & Vempala 2005). can be summarized in the following inequality:
Σh_14 S 14(0),) where 02 = arg min Ex
(FTL-BTL)
where (0) (0): Similar to Gupta et al 2017). can use this result to obtain the following Lemmal I of the key elements the unified analysis of Adagrad-type algorithms.
I is an arbitrary sequence of functions defined on a domain +
which is one
Lemma
! The preconditioner Hș defined eq. 5 satisfies the following inequality:
(He (L, (HH)).
(6)
The application of Lemma T is not limited to a specific choice of the potential function. However, to obtain Adagrad-type preconditioners, we will use the following potential function @hh). which is given follows:
@(h) = 8- h h h22 n/2/h.
where 8, 17 > 0 are positive parameters. Here appears the first key difference from Gupta et al. 20177;: using our Assumption I. we can explicitly compute the preconditioner Hg, as stated by the following Lemma
Lemma 2 (1)
The auxiliary problem in eq. has the following unique solution:
5 with the potential function s(h) defined in eq.
H n (0I projj
Moreover, the following operator inequality holds:
H H
Overall, the assumptions that impose the space of preconditioning operators H. (Proper- ties AI.I and [A1.2] in Assumption I are closely related to the notion well-structured precon-
ditioner set used by Xie et al. (2025). Consequently, the unified analysis of Xie et al. 2025 shares some similarities with ours but suffers from significant disadvantages discussed in Appendix
"The proof of eq. FTL.BBLL be found in Appendix of Gupta al. 2017)
4

---

Published as a conference paper at ICLR 2026
Table 1: The linear space X, the space of preconditioning operators H. satisfying Assumption T
and the (possibly non-Euclidean) norm R(-) defined in eq. (12) for AdaGrad-Norm (Strecter &
McMahan 2010). AdaGrad (Duchi al. 2011; McMahan Streeter, 2010), ASGO/One-sided
Shampoo (An et al.
2025
Xie et al. 2025 and DASGO (An et al. 2025
Algorithm
X
H
R(-)
AdaGrad-Norm
gd
{g + 3g 6 R)
1 -111
AdaGrrad
Rdd
(0+ b [R]]
1
ASGO/One--ided Shampoo
Ruxn
( BG B ST
Vn o max (.)
DASGO
R
{G diag(b)G b p")
vn 2-000
2.2 ASSUMPTIONS ON THE OBJECTIVE FUNCTION
In this section, we formalize the assumptions that we impose on the objective function f(r). The following Assumption 2 formalizes the convexity and matrix Hölder smoothness properties of the function (xx) Note that in the smooth case (v = 1) Assumption
2 matches the definitions used by 0), more general compared to
An al. 2025 ; Xie al. (2025). In the non-smooth case
the assumption used by An el al. 2025 Corollary 2). Note that Xie et al. (0055) provides no results
in the non- smooth case, and neither of the works of An et [2025) Xie et al. (2025) provides
results in the Hölder smooth case for <v <
HölHer smooth with respect to the norm ||- II where E [0, 1] and L E H That for all æ 22 X and f((x)) E 0f(x)), the following inequalities hold:
Assumption 2. The function f(x) is convex and (|] 7
0 $ f(z))
(Vf(1)), -
m1) I I+0 L
1x2
xilli
(10)
Additionally, using the matrix Hölder smoothness property in Assumption lowing Lemma which will be further used in our convergence analysis.
2 we establish the fol-
Lemma For all x X and V (x) E 0f(x), the following inequality holds:
I | < ( L ト
(f(x)
(11)
where in the case 0, we the convention 0 1.
The matrix smoothness in Assumption 2 is also closely related to the non-Fuclidean smoothness
property, which recently received a lot of attention (Bernstein & Newhouse 2024 Pethick et al.) Riabinin et al. 2025) due to the practical success of the Muon optimizer R, be defined as follows:
2025 Kovalev 2025
Jordan et al. 2024). Let function R(x)
R(x) ||proj (x)1 where X = x(x,-).
(12)
One can verify that the function R(x) is norm on the linear space X, shown in Lemma 4 Besides. Assumption 2 implies that the function fz) is ([]_lle,, -öldder smooth with respect to
this possibly non- -on-Euclidean norm R(-). That is, the following incquality holds for all I1, E X::
f(z2) f(x1(( (V f(z1), - z1) I + |LIlue [R(22 =x1] 1+
(13)
We provide additional discussion of the connection between Assumption 2 and the non-Euclidean Hölder smoothness in eq. (3)) Section 3
Lemma C..
The function R defined in eq. 12 is a norm. That is, it is subadditive, absolutely
homogeneous, non neganeve, and positive definite.
Additionally, we provide the assumptions on the stochastic gradient noise in the following Assump-
tion 3 These are more general than the assumptions used by both An al. (2025) and Xie et al.
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 Adaptive SGD with Preconditioning
1: input: 20 E X, K E (1,
2: for k == o..... K do
3: sample & ~ 'D
4: compute J& V (z
5:
compute H2 E H n S using eqs. ( and
6:
compute 1k+1 X using eq.
7:
output: テK K+1
Σ Ek Zk
2025). In particular, they assume the ordering Eg~p|n(r; (n((a; E). +1 Σ², which implies Prop- erty AA322] and hence, is more restrictive. Moreover, similar to the connection between Assumption 2 and the non-Eucle Eucluuul Hölder smoothness (13), one can show that Assumption [ implies that
variance of the stochastic gradient estimator is bounded with respect to the -uc-ldcci dual norm
R+).). (-). That is, the following inequality holds for all æ E X:
B [ (n(x:; E))) S Σ
(14)
Assumption 3. There exists a stochastic estimator V Va E) = n(æ; {(()((())))) of the (ub)gradient
fxx) (z) of the objective function (xx, where n(x; {) is the noise and & ~ D is random variable. The noise nlx; E) satisfies the following properties:
(A3.1) Zero mean:
Ee=Dlnn(;; {)] 0 for all x E X.
(A3.2) Bounded variance: Eg-oll]n(z:E .1 Elltr for all æ E X, where E E H. H
UNIFIED ANALYSIS OF ADAPTIVE SGD WITH PRECONDITIONING
3.1 GENERAL ALGORITHM AND ITS CONVERGENCE
Based on the discussion in Section 2. formalize the adaptive stochastic gradient method with preconditioning as Algorithm I In this section, we develop the unified convergence analysis of this algorithm. First, we obtain an upper bound on the expected regret B( f(x")] in the following Lemma 5 The proof of this lemma, in many ways, relies the previously obtained Lemmas and 2
Lemma
U Under the conditions of Theorem 1 the following inequality holds:
Σ B(( f(x')] (E)))))))))))
(15)
Next, in the following [e we establish an upper bound on the right-hand side of the inequality in Lemma 5 using Assumption and the previously obtained Lemma 3
Lemma
! Under the conditions of Theorem]
]
the following inequality holds:
[Ek=oB((EE) f(x f(x")] 1
(I. (E(s))) I K 11
(16)
Finally, with the help of Lemmas 5 and we obtain the convergence result for Algorithm T in the following Theorem Note that this result requires the inequality in eq. (17) to hold almost surely, which may not be satisfied, especially in the stochastic setting. However, this issue can be easily resolved with an additional projection step at each iteration. Refer Appendix for details.
Theorem D. Under Assumptions following inequality:
let 1) R, where R > 0 almost surely satisfies the
R(xx x²) R.
(17)
Then, the output TK X of Algorithm
7 satisfies the following inequality:
E|ER
3v dim(X))
Elf(Ix) - fxx))]
(18)
(K +)) K +1
(K +

---

Published as a conference paper at ICLR 2026
3.2 RELATED ALGORIHHM
In this section, discuss the connection of Algorithm with existing adaptive gradient methods with preconditioning.
Connection with AdaGrad-Norm, AdaGrad, and ASGO/One-sided Shampoo. We can ob- tain AdaGrad-Norm, AdaGrad, ASGO/One-sided Shampoo as special instances of Algorithm by choosing the space of preconditioning operators H. satisfying [ accoorii Table | the case = 1, Theorem [
Jacordiigg recovers the state-of-the-arr convergence guarantees for AdaGrad under
In
anisotropic smoothness (Liu et al. 2024b) and for ASGO/One-sided Shampoo (An et al. 2025 Xie
et al.
2025) under matrix smoothness. However, recall that Liu et al.] (2024b); An et al. (2023); Xie al.
2025 require a more restrictive noise variance bound as discussed in Section 2.2 and do not cover Hölder smoothness. In contrast, Theorem [
works for arbitrary E: [O, 1), which implies that Algorithm can adapt to different levels of anisotropic/matrii smoothness.
Connection with DASGO. Notably, Algorithm recovers DASGO, lightweight version of ASGO/One-side sided Shampoo that uses diagonal preconditioning and was proposed by (202)) without any convergence guarantees. Consequently, Theorem provides the first convergence guar- antees for DASGO, to the best of our knowledge. Moreover, in Section 4 we will show that the convergence of DASGO, well AdaGrad, can be accelerated using Nesterov momentum.
Connection between ASGO/One-sided Shampoo and Muon. Recently, Jordan et al. (2024) pro- posed using the Shampoo optimizer (Gupta et al. (0188) with gradient accumulation turned off. This led to the development of Muon, a new optimizer with promising practical performance. The con- vergence of Muon was analyzed from the perspective of gradient methods with the non- non-Euclidean matrix spectral norm by Bernstein & Newhouse (2024); Pethick et al. (2025); Kovalev (2025). No- tably, our analysis captures the connection between ASGOrOne-sided Shampoo and non-Euclidean optimization with the spectral norm. Indeed, as discussed in Section 2.2, Assumption 2 implies the [|]L tr. 1/) -Hölder smoothness in eq. (13) with respect to the norm R--), which, according to Table I. coincides with the matrix spectral norm (up to constant factors). Moreover, in the case of ASGOOOne- sided Shampoo, Theorem | provides the convergence result in terms of the constant |[]||r and the norm R(.).
Connection between DASGO and Scion. Recently, Pethick et al. (2025) proposed Scion, new variant of Muon, which, instead of the spectral norm, can use the matrix norm -122-xo: the maxi- mal Euclidean norm of a row of matrix. Note that in the case of DASGO, the norm R(.)) defined in eq. (2) coincides with the norm || 112-ox up to multiplicative constants, according to Table [ Hence, Scion with the norm || 112+00 can be obtained by turning off the gradient accumulation in DASGO, that is, choosing Sy gk (gx. .) in eq. (5) In other words, DASGO is connected to Scion in the same way as ASGO/ that the iterations of Shampoo not cheap and require matrix inversions, which triggered the de- velopment of the computationally effective alternative, Muon, by Jordan et al.) (2024). However, the iterations of DASGO are not only inexpensive, but they also utilize adaptive preconditioning and have much more attractive theoretical convergence properties compared to Scion. Hence, it is worth trying to use DASGO in the practical scenarios identified by Pethick et al. (2225) to benefit from using the non non-Euclidean norm ||2-000
Shampoo Is connected to Muon. It is important to highlight
4 SGD WITH PRECONDITIONING AND ACCELERATION
4.1 GENERAL ACCELERATED ALGORITHM AND ITS CONVERGENCE
In this section, we develop accelerated adaptive SGD with preconditioning. which summarized in Algorithm [ and provide its unified convergence analysis. First, to simplify the analysis, we use the interpretation of Nesterov momentum acceleration (Nesterov 1983) by Kovalev Borodich (2024). The idea is that we define the functions f& (x): X + R as follows:
[x()) = ox s(az + (1 og )+,, where 0g E (0, 1] and Fy E X,
(19)
where Fy E X is updated according to line 7 at each iteration. We then apply the preconditioned SGD iterations in eq. (3) to this "time-varying" function (x) With this approach, we can upper-
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 Accelerated Adaptive SGD with Preconditioning
1: input: 20 = To E X. K (1,2,...)
2: for k == o..... K do
3: sample & ~ DD
4:
compute d& V fk (Zzz {x),, where (z) is defined in eq. (19)
5:
compute H2 E H n 8 using eqs. and
6:
compute #k+11 X' using eq.
7: compute Tx+1 = 0gT++1 + Ogk TT
8:
output: ØK-1
bound the expected objective function suboptimality [f (T ) f(x") using the expected regret- like sum Σ ((fa(aa( fx())) in the following Lemma
Lemma . Under the conditions of Theorem 2 the following inequality holds:
[K + 2)) f(x") s o - fx(xx)))
(20)
Next, we proceed with the additional Assumption on the operators L, Σ H defined in As- sumptions and 3 It is important to highlight that this assumption always holds when the space of preconditioners H contains only diagonal operators. Hence, this assumption is automatically satisfied for algorithms with diagonal preconditioning like AdaGrad and DASGO.
Assumption 4. The operators L E in Assumption 2 and E in Assumption commute with the space H. that is, LH HL and EH = HE for all H E H.
The key idea for the analysis of Algorithm 2 that under Assumption 4 the square of the precondi- tion operator Hg, defined in eq. (8). solution the optimization problem in eq. (2T). indicated
by Lemma 8 Hence, similar to the analysis of the non-accelerated Algorithm T. we can utilize the
FTL-BTL lemma (FTL-BTL) and obtain one of the key inequalities in Lemma
Under Assumption the operator H& defined by eq. is a solution to the following problem, where = L or B
Lemma 8
H E argmin (Q, BS,) + (B, SQ 7/ In (Q)). QcHrs
(21)
Lemma Q Under Assumption 4 the following inequality holds for B = L B E:
o < <7>
In 1n² (E[) (|
(22)
Finally, using the inequality in Lemma 9 obtain the key upper bound on the regret-like sum f[ (T++1) fx(x*)] in Lemma 10
Lemma 10 D Under the conditions of Theorem
the following inequality holds:
K Blaa((())))) - fa(x))
Cxx (K +2
3(-m)
(23)
+ C - 2) |E dim
Now, all that remains is combine Lemma 10 with Lemma 7 and obtain the main convergence result for Algorithm 2 in Theorem Similar to the non-accelerated result in Theorem [ we require the inequality in eq. (17) to hold almost surely. This can be casily guaranteed by additional projection step at each iteration, as discussed in Appendix D
Theorem 2. Under Assumptions 7
and let 2R, where > 0 satisfies eq. 17 and let satisfies the following inequality:
ag = 2/ + 2). Then, the output ēx+1 E X of Algorithm 2
Cx C
CK C
4v dim
E[f(k++1) f(xx))
5
(24)
(K 42
VK +2
(K 2)2
where the constant Cx 0 satisfies the following relation:
Cx O (1 In K + In
+
E
(25)
v8
8

---

Published as a conference paper at ICLR 2026
4.2 ADAGRAD AND DASGO WITH MOMENTUM ACCELERATION
In this section, we provide a detailed discussion of our results for two special instances of adaptive gradient methods with diagonal preconditioning AdaGrad and DASGO. In the case of DASGO.
let X' Ruxn be the space of m x n. matrices and consider the following special instance of problem
min XERmX
f(X).
(26)
We choose the space of preconditioning operators R=** + R for DASGO according to Table That is, H (G diag(b)G RR",, which obviously satisfies Assumption [ Note that AdaGrad can be obtained from DASGO by simply choosing n = 1. Henceforth, for simplicity, will consider only DASGO.
Next, we specialize Assumptions and 3 to the setting of DASGO. In particular, we define the operator L E H in Assumption and X E IR For example, in the case V/ = 1 and n 1. Assumption 2 exactly matches the anisotropic smoothness assumption used by Liu et al. 2024b). the general case v E [0, 1] and implies the (1141),,) H-Hölder smoothness with respect to the non-Fuclidean norm || 112-000 that iS, the following special instance of the inequality in eq. 13 holds:
L: X + n "²=² diag(l) where 1 = (.,....,4m) RT++
2 1, Assumption g
0 $ f(X2) - f(x)) (V)())), - X1) = T4x |0]
X1
(27)
Similarly, we define the operator Σ H in Property A3.2 E: + n 3 (iag(o))., where a = (oI,..., E - and X E IR Consequently, the variance bound in Property A3.2 turns into the following inequality:
BEWD Σ (1/a.)) s ||a]] where [N1, NoJ VF(X:E) VF(X).
(28)
This incquality is implied, for instance, by the anisotropic noise assumption used by Liu et al. 2024b), and hence, more general.
Further, for simplicity in the presentation of the results, we use the convergence guarantees from Appendix D for the algorithms with projection steps. Using Theorem and assuming 5 obtain the following convergence guarantees for AdaGrad and DASGO:
[/ ||| 1
112-000
2000 +
(29)
-
VK+I
This matches the result of Liu et al. (2024b) for AdaGrad in the smooth case (v and n 1), but also provides convergence guarantees for DASGO. Similarly, using Theorem we establish convergence guarantees for AdaGrad and DASGO with Nesterov momentum:
(
(
[11|| 1
2000
||
(30)
K'
1430
VK +1
which substantially improves upon the non-accelerated result above. We can also compare this result with the state-of of-the-art result of Kavis et al. (2019); Rodomanov et al. (2024) for scalar AdaGrad- type stepsizes under the above assumptions:
|| X I+
Vmlloll [X
|x
Bff( -10x+)--((()))) f(x*) <
(31)
K
Our result in eq. 30 is substantially better than the existing result in eq. 31 as long as ||4]]2 ~ ||a||| [|]]]oo, holds when and or are sparse and X is dense, which aligns with the conclusions made by Liu et al. (024b) for AdaGrad without momentum acceleration.
oc. and || >> | For instance, in the AdaGrad case (n 1), this
ACKNOWLEDGEMENTS
This work was supported by the The Ministry of Economic Development of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000C3113955P400000 grant No 139- 139--5--025-011).

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.087 2023.
Kang An, Yuxing Liu, Rui Pan, Shiqian Ma. Donald Goldfarb, and Tong Zhang. Asgo: Adaptive structured gradient optimization. arXiv preprint arXiv:2503.20762, 2025.
Rohan Anil. Sebastian Borgeaud, Jean- -aan-Baptiste Alayrae, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. 1805, 2023.
Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology. arXiv preprint arXiv:2409.23322 2024.
Eric Carlen. Trace inequalities and quantum entropy: an introductory course. quantum, 529 140): 146, 2010.
Entropy and the
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):11-100, 2020.
Ashok Cutkosky. Anytime mnline-to-batch optimism and acceleration. International conference machine learning, pp. 1446-1454. PMLR, 2019.
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-frre online learning in banach spaces. In Conference On Learning Theory, pp. 1493-1529. PMLR, 2018.
Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by d-adaptation. In Inter- national Conference on Machine Learning, pp. 7449-74799. PMLR, 2023.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.023395 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
llyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimiza- tion under global burdyka-lojasiewicc inequality. Advances in Neural Information Processing Systems, 55366183-8 2022.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21782 2024.
Vineet Gupta, Tomer Koren, and Yoram Singer. A unified approach to adaptive regularization in online and stochastic optimization. arXiv preprint arXiv:1706.06560 2017.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor opti- mization. In International Conference Machine Learning, pp. 1842-1850. PMLR, 2018.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on learning theory, pp. 1894-1938. PMLR, 2020.
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pp. 14465-14499. PMLR, 2023.
Ruichen Jiang, Devyani Maladkar, and Aryan Mokhtari. Convergence analysis of adaptive gradient methods under refined smoothness and noise assumptions. arXiv preprint 24X5v:2406.04592, 2024.
Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse. and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks. Cited on, pp. 10, 2024.
10

---

Published as a conference paper at ICLR 2026
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 7133):91-337, 2005.
Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances neural information processing systems, 32, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. Dowg unleashed: An efficient universal parameter-free gradient descent method. Advances in Neural Information Processing Systems, 36:6748-6769, 2023.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International conference on machine learning, pp. 2698-2707. PMLR, 2018.
Dmitry Kovalev. Understanding gradient orthogonalization for deep learning via non-euclidean
trust-region optimization. arXiv preprint arXiv:2503 2025.
Dmitry Kovalev and Ekaterina Borodich. On linear convergence in smooth convex-concave bilinearly- saddle-point optimization: Lower bounds and optimal algorithms. arXiv preprint arXiv:2411.14601 2024.
Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic optimization. In The Thirty Seventh Annual Conference on Learning Theory, pp. 3257-3324. PMLR, 2024.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):46--444 2015.
Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceler- ation. Advances neural information processing systems, 31, 2018.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. The 22nd international conference on artificial intelligence and statistics, pp. 983- 992. PMLR, 2019.
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437, 2024a.
Yuxing Liu, Rui Pan, and Tong Zhang. Adagrad under anisotropic smoothness. arXiv preprint MrXiv:2406.15244 2024b.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 17110:1711.05101, 2017.
Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- 2010.
mization. arXiv preprint
Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner. arXiv preprint arXhv:2306.06101, 2023.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Con- ference on Machine Learning, pp. 15750-15769. PMLR, 2022.
Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematical Pro- gramming, 152(1):381-444 2015.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence 0(1 (1)22). Dokl. Akad. Nauk. SSSR, 269(3):543, 1983.

---

Published as a conference paper at ICLR 2026
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Francesco Orabona. Normalized gradients for all. arXiv preprint arXiv:2308.05522 2023.
Francesco Orabona and Dávid Pál. Serameter-free stochastic optimization of variationally coherent functions. arXiv preprint arXiv:2102.002:66, 2021.
Thomas Pethick, Wanyun Xie, Kimon Antonakopoulos, Zhenyu Zhu, Antonio Silveti-Falls, and Volkan Cevher. Training deep learning models with norm-constraing Imos. arXiv preprint arXiv:2502.07529, 2025.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint urXxvv:/004.00 2019.
Artem Riabinin, Egor Shulgin. Kaja Gruntkowska, and Peter Richtárik. Gluon: Making muon & scion great again!(bridgingg theory and practice of Imo-based optimizers for 1lms). arXiv preprint arXiv:2505. 13446, 2025.
Anton Rodomanov, Xiaowen Jiang, and Sebastian Stich. Universality adagrad stepsizes for stochastic optimization: Inexact oracle, acceleration and variance reduction. Advances in Neural Information Processing Systems, 37:26770- 77777002681,,, 2024.
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arX4v:1002.4862, 2010.
Tijmen Tieleman. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26, 2012.
Stepan Trifonov, Leonid Levin, Savelii Chezhegov, and Aleksandr Beznosikov. Incorporating pre- conditioning into accelerated approaches: Thcoretical guarantees and practical improvement. arXiv preprint arXiv:2505.2355 2335/0 2025.
Nikhil Vyas, Depen Morwani, Rosie Zhao, Mujin Kwun, Itai Shapira, David Brandfonbrener, Lucas Janson, and Sham Kakade. Soap: Improving and stabilizing shampoo using adam. arXiv preprint arXiv:2409.11 11321, 2024.
Shuo Xie, Tianhao Wang, Sashank Reddi, Sanjiv Kumar, and Zhiyuan Li. Structured preconditioners in adaptive optimization: A unified analysis. arXiv preprint arXiv:2503. 10537, 2025.
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges to global minimum in deep learning via star-convex path. arXiv preprint arXiv:1901.00451, 2019.
12

---

Published as a conference paper at ICLR 2026
Appendix
A NOTATION
In this paper, we use the following notation: di'( is the dimension of the space X:: LL is the space of linear operators X' + X. for arbitrary operator A E L. A' E LL denotes its adjoint operator, I E IL and O L denote the identity and the zero operators, respectively; & C IL is the space of self- adjoint linear operators, S S C S are the spaces of positive definite and positive semi-definite self-adjoint operators, respectively; <; 3. ,, denote the standard Löwner order S; ( and I| denote the standard inner product and Euclidean norm on X' or L, depending on the context, in particular, (A, B) tr(A for A, B E IL; for arbitrary H S4+. ||-|| denotes the weighted Euclidean norm in X, i.e., || (z, Hr) for x E X: || llop and ||- ||ee denote the operator and max ||||||||| | and |Allu
tr(vAA for all A E IL; for arbitrary v, E X, by =(y, +) E L we denote the rank-1 I linear operator x + (x, u) by gd C Rdxd we denote the space of symmetric matrices; by O we denote the Hadamard vector matrix product.
trace norm L, respectively, i.c., ||A olop
B ADDITIONAL RELATED WORK
Exponential moving average. AdaGrad-type algorithms, like RMSProp, often utilize the exponen- tial moving average (EMA): they replace the cumulative sum of the squared gradients ا I|? in eq. 2 with the exponential moving average Σ 3 [|g: | Notably, EMA is the third key com- ponent of Adam, in addition to diagonal preconditioning and momentum. Moreover, Défossez et al.) (2200) showed how analyze AdaGrad with EMA and explained that related the standard AdaGrad in the same way as fixed stepsize SGD is related to decaying stepsize SGD. Consequently, we can develop EMA versions of our algorithms as well as their convergence proofs. However, Défossez et al. (2020) could not justify the benefits of using momentum. Hence, our theoretical justification of the benefits of momentum and diagonal preconditioning, combined with the analysis of FEMA by Défossez et al. 22200), may provide the ultimate explanation for the efficiency of Adam.
Parameter-free algorithms. There is an important research direction aimed designing parameter- free variants of AdaGrad, which can avoid tuning the parameter x ||x"| in eq. (2). This includes the works Cutkosky & Orabonal (2018): Orabona & Pál (2021) Defazio & Mishchenko (2023)
Mishchenko & Defazio (2023); y; Ivgi et al. (2023); Khaled et al. (2023); Kreisler et al. 2024
However, to the best of our knowledge, the existing results are applicable only to scalar stepsizes, which rarely used in practice. Designing parameter-free gradient methods with diagonal or matrix preconditioning is an interesting question for future work.
Concurrent unified analysis framework. Xie al. (2025) developed unified analysis for AdaGrad-type methods, where they also adopt the matrix smoothness assumption. We found their work during the preparation of our literature review, at a point when results had already been finalized. Although the results of Xie et al. (2025) share some similarities with ours and are capa- ble of providing a partially positive answer Question T their analysis has substantial differences and drawbacks. Specifically, it only covers the smooth case and lacks adaptation to non-smooth or Hölder smooth functions. In addition, it requires a more restrictive stochastic gradient noise as- sumption and, most importantly, does not contain any results about using momentum acceleration, thus completely missing an answer to the fundamental Question
C MOTIVATION FOR CONVEX SETTING
In this paper, we focus on the case where the objective function f(x) in problem is convex. There are multiple reasons for this assumption. First, optimization algorithms for convex functions hold substantial practical interest because empirical studies (Zhou et al.) 2019 Kleinberg et al.)
2018) suggest that deep neural networks may adhere to convexity or its variants. Second, for gen-
"Additional references be found in the overview of Orabona 2023
13

---

Published as a conference paper at ICLR 2026
Algorithm 3 Adaptive SGD with Preconditioning and Weight Clipping
1: input: 20 E QR. E (1,2,...)
2: for k == ...... K do
3: sample & ~ DD
4: compute 9 V (z
5: compute H2 E H n S using egs. and
6: compute 1k+1 X using eq. 32
7: output: žK K+1 Σ Zk
Algorithm Accelerated Adaptive SGD with Preconditioning and Weight Clipping
1: input: 20 To QR. K E (1,2....)
2: for k ===0 0..... K do
3: sample εv D
4:
compute gk = V f (Zzi Ex), where fx (x) defined in eq. 19
5:
compute H2 E
S++ using eqs. (5) and
6:
compute 2++1 E X and 1x+1/2 X' using eq 32
7:
compute Tx+1 = 01-1+1122 + ark T
8:
output: ØK-1
eral non-convex functions, it is impossible to achieve meaningful global convergence beyond vague first-order stationarity (Carmon al. 2020). However, in practice, it typically desirable to achieve small values of the objective function, which can only be guaranteed under additional assumptions, such as gradient domination (Fatkhullin et al., (022), star/quasar convexity (Hinder et al. 2020), etc. Such assumptions are, in turn, relaxations of the convexity property itself. Hence, it is natural to consider the convex setting first before trying to relax it. Finally, convex optimization serves as large source of inspiration for designing efficient optimization algorithms. Notably, many optimiza- tion techniques that have practical benefits were initially theoretically justified for convex functions. These include momentum acceleration (Nesterov) (013). local training (Mishchenko et al. 2022) and AdaGrad (Duchi et al. 201T), on which Adam itself is based.
D ALGORITHMS WITH WEIGHT CLIPPING
The upper bounds on the expected functional suboptimality in Theorem for Algorithm and in
Theorem requirement may not be satisfied, for instance, such issue is not artifact of our analysis but common phenomenon in AdaGrad-type algorithms
2 for Algorithm 2 reeuiire the inequality in eq. (17) to hold almost surely. However, this
stochastic case. is important to higlight that
(Duchi et al. 2011; Gupta et al.) 2018 Liu et al., 2024b An et al., 2025 Xie et al.) 2025). To
bypass this issue, typical approach is modify the preconditioned gradient update rule in eq. 3
by adding an extra projection step onto the set QR = {x E X R(x) & R), where R > R(x
The modified update rule is given follows:
Tk+1
arg min 1 || #x41/22| Fk+1/2 arg min (gk, x) + 111l0 [ xEQR
2
(in, FEX
12 H Is
(32)
Note that the set QR is convex and hence the projection step is well-defined. Also, note that the projection is performed with respect to the weighted Euclidean norm ||. IIll which may be ex- pensive, for instance, when the preconditioner H₃ is dense. However, this projection step can be computed efficiently when the preconditioner H, diagonal. For instance, the projection equiv- alent to the coordinate-ve wist clipping or column-wise norm-clipping 2 + min(1, R/ [|= ||]= DASGO, Below, we discuss the modified update rule eq. 32 in relation to the non-accelerated Algorithm T and the accelerated Algorithm in detail, including the additional modifications in Algorithms T and and the modifications in the convergence proofs.
min / R, max{-Ro {}} } in AdaGrad, and to the row-wise
Non-accelerated Algorithm T + Algorithm 3 The only modifications to Algorithm are the initialization zo E Q on line 1 and the modified update rule (32 line 6 in Algorithm as
14

---

Published as a conference paper at ICLR 2026
discussed above.
We also modify the proof of Lemma in Appendix F.I by obtaining the following:
2 ||
x
|| {gh, x²) 2 H. (33)
H
H
[32 the non-expansiveness of the projection, and the fact that x E Qx: (b) uses the update rule for 1/+1/2 eq. (32). One can observe that this eq. (33)
where (a) uses the update rule for r4+1 in eq.
coincides with eq. (43) in Appendix F. Moreover, the inequality eq. (17) holds almost surely due
to the projection step eq. (32). Therefore, the rest the proof of Theorem remains unchanged,
and we obtain the following Theorem
Theorem 3. Under Assumptions
! and let = R, where R > R(x*). Then, the output satisfies the following inequality:
JK X' of Algorithm
3
- L|
3 R
3V8R dim(X)
E Elf(Tk) - f(=)) (K 11+
+
(34)
VK+1
(K+
Accelerated Algorithm erated Algorithm 4 contains the modified initialization zo = To E QR on line and the modified
Algorithm Similarly, the non-accelerated algorithm, the accel-
update rule (32) line 6 in Algorithm 4 In addition the modified eq. (33). also modify the
first inequality in the proof of Lemma 10 in Appendix G.4 as follows:
BiJa(H4+1/22) < E [a(())) 1
(1 Hagk) 1+
19
1+z
(35)
Here, the only difference is the left-hand side ([ compared to Ei (2x41)
in Ap-
pendix G.4] which means that we also have to modify the update rule for Ik+1 on line of AI-
gorithm and apply trivial changes to Lemma 7 unchanged and we obtain the following Theorem
The rest of the proof of Theorem remains
Theorem 4. Under Assumptions
3 and let y 2R, where R > R(x"), and let as 2/(k 2). Then, the output ØK+1 +1 X of Algorithm Aasuummasattt Satiisiiss the following inequality:
CK R I+v
Ck E| 4v8R dim
E[f(ZK+1) - f(x))] -
(36)
(K 22 113x
VK +
(K + 2)²
where the conslant Ck > O satisfies the following relation:
Cx = 0 (1 In K + In [L R
In
Σ 11
(37)
J5
v8
15

---

Published as a conference paper at ICLR 2026
E PROOFS FOR SECTION 2
E.1 PROOF OF LEMMA
Let functions (-1 (H) ................................ (H): S++ + be defined as follows:
L H) (I. (H)) (HH)
1 Fi for i == O....,k.
(38)
Let H E H + be defined as follows:
H11 arg min (I. ((H)).
(39)
HeRns
From eq. ( it is easy verify that the following relation holds for all -1, -1....;
H arg min Σ 4 H
Next, we get the following inequality:
4 (H,)
where (ap uses the assumption that the potential function d(h) is non-negative; uses eq. FTL-
BTL
It remains to to do rearranging and use the definition of the functions (H))
E.2 PROOF OF LEMMA 2
First, using Properties AI. and A1.2 we can show that H, EHM #ns Next, we show that H₃ in
eq. (8) is solution to the problem in eq. (5) by verifying the first-order optimality condition:
(((,Sh) + (I, (H)) S + d'(HR)
S₁ + 81 1/ H
S proju (Sk)
E 76_
where a uses the standard operator function calculus (Carlen 2010); (b) uses eq. 7)
(c) uses
eq. Next, we can show that the solution H2 unique. Indeed, by Theorem 2. 10 Carlen 2010 the function (I, ((H)) is strictly convex, because the function @(h) defined in eq. is strictly convex. Finally, we can prove eq. (9). It follows from the operator monotonicity of the function h + -1/V/, h, which is implied by Löwner-Hein Theorem (Carlen 2010 Theorem 2.6),
and the ordering projx (S++1) ž projx (Sx), which is implied by Property A1.1 and the definition of S₁ in eq. (5).
E.3 PROOF OF LEMMA
Assumption implies the following inequality for all X and V ff(x) 0f(x):
f(x)) + (Vf(z),= + ||
x 1+"
(40)
In the case v E (0, 1), we can minimize the right-hand side in æ, which gives the following:
S s
(f(z)-((x"))
(41)
20 Taking both sides the power 14 gives the desired inequality in the case v E (0, 1]. Finally, in the case y = 0, minimizing the right-hand side of the previous upper bound on f(x") gives the following:
[Vf()) < L |V |L
f(x") f(x) {-o0
(42)
remains to use the fact that both fxx) and f(x*) are finite to obtain the desired inequality in the case 0.
16

---

Published as a conference paper at ICLR 2026
E.4 PROOF OF LEMMA
(i) Non-negativity. It is obvious.
(ii) Absolute homogenity. For arbitrary E R we can obtaín the following:
R t. projy (t X)
1/2 lp
b
[t]
|1proj
(X)
1//2
[t] R(x),
lop
where @a and c tion onto 7.. and the absolute homogentiy of llop-
use the definition of (ax)) in eq.
12 uses the linearity of the projec-
(iii) Positive definiteness. Let R(x) 0. Then proj
(X)
0, which implies the following:
0 (I. projx (X))
X
||=||² ||
where uses the fact that eq. Hence, we get x 0.
H due to Property A1.2 uses the definition of X in
(iv) Subadditivity. Let x, y E X. Then we can obtain the following:
R(x + y)
Iproju v) 11
(ppro)((111))) (z ) + (1 1/c))ul,,) - (er (-c)//(crr - v/c, 11
((ojx)) )) (1 1/c²) proju 1)ll
((1 (1+ ) op + + 1/c) 1/c3) (vlv: (opp))
-| + Iproj (vly. 1)
R(x)+ R(y))
where a and (f) use the definition of R(x) in eq. 12 b uses the bilinearity of
mapping 2 x2, -) and arbitrary constant R: (c) uses Property A1.1 the linearity
the projection onto H. and the fact that llop subadditivity and absolute homogenity of || |laps be obtain by minimizing in
on S ( uses the
The proof is now complete.
17

---

Published as a conference paper at ICLR 2026
F PROOFS FOR SECTION 3
F.1 PROOF OF LEMMA 5
Let Th 24 and R (To ) We can rewrite / = as follows:
I H
(gx. rk) + 11
(43)
H.
where a uses eq.
Next, we sum these equations for A: = 0,.... K and get the following:
k (0k, Tkk
Σ
k=
19 H4
+
k= (IrAIl -1rr++++1
19 li,
+ | 2 Ho
+ 5 1| |1 H. -H,," - 21
19x
+ (Ro: Hy トー K
(Rx. H H
2
19x Ii,,
+ (projx R Hp ス ード
k= (projo/ RR.): H H
k=
>
11 +
H H
k=1
K
19x11 ll
+ (
H. H H
(H (x)
(H (lk.proj. (Sx)) (I. (H{)) + R (I,H
where a use the properties of the projection and the fact that H. E H. due to Property A1.2 and eq. (8); (b) uses the Hölder's inequality for Schatten norms, the definition of the norm R(-)
in eq. (2). and the inequality in eq. 17 (c uses the fact that H t H. which is implied by
eq. 9 and the operator monotonicity of the function h + -1/h, which is implied by Löwner-Heinz
Theorem Carlen 2010 Theorem 2.6); (d) uses Lemma I de) the fact that H, g E H. due to
Property A1.2 and eq. (8)
Next, using the definition of the potential function ((H) in eq. (7), the expression for H3 in eq. (8) and the definition = R, we get the following inequality:
Ek (gh, rk)
(HK. 8I + p (Sk)) + 1n7 + RR)
R(I, (SI + proj (roi)
where (a) the definition rj of Tk, and using Property A3.1
R. After taking the expectation, recalling that & is independent
we get
BKV (xx)) rw)l
RE (0I + proju (Sx))
RI, (ÓI + proj (B(Sx))))
R propro (E[Sx]) VOR[[I]
R proj (E(Sx)) VöR dim
where (a) uses the concavity the function H + {I. 12) which is implied by Theorem 2.10 of Carlen (2010), and the linearity of the projection onto H; (b) uses the fact that function H + (I. H/2 is subadditive for H E S,, which is implied by Lemma 3 of An et al. (2025). It remains to use the convexity property from Assumption 2
F.2 PROOF OF LEMMA 6
Let G3, No E S be defined as follows:
G = V/<>\
N - (a
(44)
18

---

Published as a conference paper at ICLR 2026
Then, obtain the following:
S D E[ + + +((rait)),))
E G No E El + (a
+ +
where (a) uses the definition of S in eq. ( and Assumption 3 (b) uses Property A3. and the fact that Ek is independent of zy.- Using this, we obtain the following relation:
(I. projæ (E(S)])
(I. proj (E|G Nx))
(I, [projm (..) + proj (B[N)))
(I, projx (E(G + proix (2)
where (a) uses the linearity of the expectation and the projection onto H: 1 uses the fact that function H - (I, H1/2) is subadditive for H S+, which is implied by Lemma 3 of An et al. 2025).
We upper-bound pr
follows:
(I, proj (E(
1/2/2 E -- 1/2 proj# (B(N&))
Σ 1/2 |||| proj ( (EIN&))
te [ proj E N&))
Σ lex E
N
Σ tr Σ Billn(x; 6
/k + 1| t
where (a) uses the Cauchy-Schward inequality; (b) uses the definition of ||- and || (c) uses
the linearity of the expectation and the fact that Σー1 E H. which implied by Properties A1.2
and A3.2 d uses the definition of N&: (e) uses Property A3.2
Similarly, we can upper-bound (I. proj (E[Gx)) as follows:
(I. proju (E(Gx))
1u (E GE()))
El (L-1 G
| Eio B (=;)))
[(xx)) - (xx #
x (x;)) (x) ||
(k 1)
R [() (1x)
19
+ 1+v
ΣL E(f - f(x=''
where (a) uses steps similar to the above calculations: uses the linearity of the expectation and
the fact that L E H. which is implied by Property A1.2 and Assumption 2 dc) uses the definition
of G dd uses Lemma and use the concavity of the function + for E [0, 1]. O
F.3 PROOF OF THEOREM
Using Lemmas and we get the following inequality:
K ((( - 3
R L
K B((z))
19

---

Published as a conference paper at ICLR 2026
2 K 1R| + + dim)
which implies the following inequality:
k E f(x))] S 3v K -
L 11 R
R
1+
+3 K 1 R R 3V88 dim)
It remains to use the convexity property in Assumption 2 and the definition of FK on line of Algorithm
20

---

Published as a conference paper at ICLR 2026
G PROOFS FOR SECTION 4
G.1 PROOF OF LEMMA 7
We can upper-bound Σ Bifo fx((--1)] follows:
Ex [(fa(a") fA [x((x+1)]
Σ K
k= ax BBIf (1 (1-a4)) flauIa+1 + (1 a+)
ax 2 (1- f((x+1)
O AB(f(=²) [ 0 (x) [
+ > km (ak 2 (1 - an) (l - f(x)))
[KK + 21)== [(xx-)))))
where a uses the definition of the functions fa( in eq. 19 (b) uses the definition of Tx+1 on
line 7 Algorithm 2 and the convexity property in Assumption 2 uses the definition os
2/(E 2).
G.2
PROOF OF LEMMA g
Σ analogous). Let (s(Q): S++ - R be the objective function in Let B (the case
eq.
21
(Q( (Q, LSx) + (L, 8Q 17² (Q))).
(45)
From Property A1.2 it follows that H H + In addition, from the Löwner-Heinz Theorem (Carlen, 2010 Theorem 2.6), it follows that the function A+ is convex. Hence, it remains to prove that the first-order stationarity condition holds, that the differential of A& (Q) is zero H at H
dA, ( = for all H H.
(46)
The following Lemma 11 will used to compute the differential clA,, (Q)
Lemma 11 Q Under Assumption
let the function B(Q): S4+ + R be defined as follows:
B(Q) (L, (Q)).
(47)
Then the differential of the function B()) all Q E H n S is given as follows:
[ = (LQ H. for all H H.
(48)
Using Lemma we can compute the differential d.4g
H for E H. follows:
dAA (
(L(S) + - 1j H )), H)
(L(Sa proj (St) H)
((S, proj (Sa)) LH)
((S proj (Sx)). LH
where @ uses Lemma
b uses eq.
8
c uses Assumption
(cl
uses the fact that LH E H,
which is implied by the following Lemma
Lemma 12 (.. Under Assumption LH E for all H E H.
The proof is now complete.
G.2.1 PROOF LEMMA
Let constants a, b E IR chosen to satisfy the following inequalities:
O al Q M.
(49)
21

---

Published as a conference paper at ICLR 2026
Let H H. such that | Qllop min ((Amin (Q) -a), b- Amax (Q)). Hence, it is easy to verify that the following inequalities hold:
al d b1.
(50)
Next, we fix an arbitrary e > O. By the Weierstrass approximation theorem, there exists a poly- nomial (t) Σ C,t² such that (a) In(a), p, (a) 1/a, and whose second derivative approximates the function -1/12 on the segment [a, bj up to the precision
(t) 1/f1 Se for all t [].
(51)
From this, using the standard integration arguments, we can conclude that the following approxima- tion inequalities hold for all E aa, b):
1/ (t) - 1 1/4 < cbb a), (p.(t) - In(()) S _c(b a)?.
(52)
Further, obtain the following:
[B(Q + H) B(Q) - -f (LQ -H) H)dr
(Q+ P.. (Q)) f L (Q 7H), H)
+
[Llle (bc(b - a)² [cb a)²) LH Ir . c(b aa
Pr H) pm (Q)) (LL.(Q +H) H)dr| (b2IIL|lee -b] (H]))
(b* + LH ..)
where @a) uses Definition the approximation inequalities above, and the Hölder's inequality for Schatten norms; (b) Uses the fact that Pv, (L) polynomial and the fact that QL LQ and HL LH due to Assumption 4 Next, we take the limit - 0 and use the fundamental theorem of calculus and the continuity of the map Q + ++Q+ Q- on S4_, which implies the following:
B ~H)
(LQ-1.H)
(53)
Since the right-hand side is continuous in Q, we can conclude that the function B(Q) is differen- tiable and its differential is equal the right-hand side.
G.2.2 PROOF OF LEMMA 12
Since the operators L and H are self-adjoint and commute, they simultaneously diagonalizeable:
L = Σ u, (u.,)) and H = E14 (u,,,) 0
where X and μ4 the (possibly repeating) eigenvalues of the operators L and H. respectively, {u; C X' an orthonormal basis of the common eigenvectors in the space X'. Hence, the operator LH is also diagonalizeable follows:
LH = App4 us ()..))).
Further, let IA = {i: X} and Jj. {i My 11} for arbitrary X. μ R. Let p(t) be polynomial such that p(A) = and p(>:) for i & J. Using Property A1.2 we can conclude that
pLL "
uuu, H.
Similarly, by constructing polynomial (tt)such that q(4) 1 and p(u,) = 0 for j $ J and using Property A1.2 we can show that the following inclusion holds:
(H) EjeJ, uy(u,,) H.
Hence, using Property A1.2 obtain the following inclusion:
p LL) + q (H) EiEI,a,, us ((,,,) -) + 22 us (u.,
Finally, we can construct polynomial s(t) such s(2) = 1 and s(1) 0. Using Property A1.2 we can show that
s (p(L) + (H)) = Eie (u(u,.)) H.
From this fact and the above eigendecomposition of the operator LH, it follows that LH H. 1
22

---

Published as a conference paper at ICLR 2026
G.3 PROOF OF LEMMA
Let B = L (the case B = Σ is analogous). Let functions L-1
S++ n H + RR be
defined as follows:
Li(Q) (L, 8Q -1 "n2In((Q) (Q)) 4(Q) l for 0, k....,k.
(54)
Let the operators Q -...... Qs 7 n S++ be defined follows:
Q-1 = (v/² I Q = H for i = o....,k.
(55)
Using Lemma 8 we can show that the following relation holds for all = -1, -I....,k:
Q2
arg min 1i=)) Qunns++
Next, we get the following inequality:
* ((Q:))
((Q)) QQ-1)
E 4(Qc) (QQ1))
J.H,,81+ Sx) 172 In (f) (I, Ln((rr//))1))
0
(LH +I + (S ( 1f + n7² (L. In())
8
[?|[[|e
1 In, /1²)) n Ll lrr
1
proj S+)) + 7 |L| In
@
[
In pro (St) op) + 2 | In
M In proj (s)) 1/2 1/2 + 17 L In
1/a [
n? L|ler In (3 H (1::)
where (a) and (c) use the definition of the functions (H), the definition of the operators Q
(b)
uses eq. FTL BTL) ( uses Lemma Property [A12]] and the properties of the projection onto
H: ee) and use eq. and Definition
uses the Hölder's inequality for Schatten norms; (h)
uses the inequality ||- Too S 11tz: (1) uses eq. (8). It remains take the expectation and use
concavity of the function è 1 In((2) and the Jensen's inequality.
G.4 PROOF OF LEMMA
Let 7ig 9k-
fi( and rh 2k x². We obtain the following inequality:
I-v fa(())) + (V fv (xxx) Tu+1 IK) + af |Lll
B[fa
| - x +x
Fu((K)) - (T)) Hagh)
+ 1
I+. a ||
119x
1+0 LHE
S
[a( - 11ax 122 + (mg, HagK) + itc
I
|1
LH
where (a) uses the definition of the function fa(2:) in eq. 19 and Assumption
2 bb
uses eq. 3 and
(ch uses the definition of ng. Next, similar to the proof of Lemma we can obtain the following inequality:
Assumption 4
o rx)1 < E + (I,
(56)
Combining this with the previous inequality gives the following:
I (( fx(x'')
23

---

Published as a conference paper at ICLR 2026
<
R ( - Σ B
(NK. Hegh) - =ll9a11H. + 1 u-1 ||
11 1 1+v
1 (I,
Σ k= B
211941111 + 1 I42 | 119x
1+v LHE
E
19g E
+ 2/1
-ーー
(I,
+ > K
1
18
1 (S 1 Sk, Ho) + 14o 0k -I
11 [1
+ 2/l | 1
2
2
K
BI H (Sx. H
19
1t L.n
+ E Bem + _ |
I+y
0
(R²
19
Lip
+ 5
1 1/-
I+v
(R²
3 V
+ Σ
E
I+y 0
1
LHE
E 12HR
(RR2
(I.
1)
+ b1
|| tr +
EEr Ek=o (1/a
22
1-1
4
+ + [
1 EH?
2
|
E
Σx
k==
[
8
(R² - (I, H
1>> +
/
5n [|| +
E
E 1 1)
1-
4
+ T+u
(E 1 1/
|L| ir
(R
E 1lox 11111
(B 11g Bmze ))
(R² "²²) |B H K
Ilu]]
|>>|
E
k
|| (E(
where (a) uses the Young's 's inequality, Assumption g and an arbitrary constant 0; (b) uses the
definition of Sy in eq. 55 uses eq. ( (d) uses the definition of Hę in eq. (8): uses the
definition of ng above, Property A3.2 and the definition of the function f'x in eq.
19 uses
the Hölder's inequality, the concavity of the function + -"."" and the Jensen's inequality for the expectation; (g) can be obtained by minimizing in 0: h uses the definition of ||- lkz.. Next, using Lemma we obtain the following technical Lemma
Lemma 13 Under the conditions of Lemma 10 for B L or B = E. and for all y (0,
the following inequality holds:
B Ei-oolloo 11 [ (isee ))
(57)
$ n E H [|ue] + 27 EEio 1-7
27 (cx
where the constant c(B,7) > 0 is defined as follows:
(B, = max exx(()), 23 (E/)
1-7
(58)
v8
Further, using Lemma 13 and the fact that [[]er = dim(()), we obtain the following inequality:
E ([f((((44)) - fa (x*)
L22 || 2t In (ex (L, 1+2)
< (ER² - -11²) |||l H K [er] + -
10²))
24

---

Published as a conference paper at ICLR 2026
+ 2 Ex 1/a)
in (2) + 2 Vōn d
an
2 1/a?
k
| R In (ex (L. 2
+ 2
E 1/at)
k
1 (ck [ 2) + VöR dim
| (c (L, ))
+ 2
|ل
R
In CC 22 1)) = VoR dim(A)
1+5
3 3 KK +3)
L In (cx (L, +2² Rln (CK [, 2)) + VöR dim
+ 2 3 (K + 3)
3
$ 8(KK +2) 3(1->) R
(CK [L, )1)
+ 2(K + +2) E1 Rln (ex [ 2)) + VoR dim(X))
where dal uses the definition 7) = 2R; (b) uses the definition og = 2/(k: + 2); (c) uses the fact that
EK+2 I 3 { + 3) and // 5 1. Finally, we define Cx = 32 In (maxfcx (I, =²) cx ( )))
and verify that eq. 25 holds.
0
G.4.1
PROOF OF LEMMA 13
We start with the following inequality:
E/oo/aa?
B
B
E Exzoll BHH ))
1/a,)
1-y
B
17 [72|[B||
le In
1/21 [B]|HH I1(=)) 27 '))
D
1//2//0
2
B tr
2y1 2 In
(--)
(B|] 7
2n² +2/e)((e) )
(ov8
B
1/a
1-7
B lx
2?11² In
( cv8
(BI) 11.l)) $1)² + (2n In(c))
8
E
1/a?
1-7
|B||rr
(2ym²²²²
E H " || (2n In(c))
cvo
where a uses Lemma b uses arbitrary constant O: (c) uses the subadditivity of the function + [7; ddl uses the inequality In(1) < / for 1.>. > 0. Next, we choose the constant e > 0 as
follows:
max exp(1), 20 Ex
B 11
27-1 }
(59)
V8
which implies the following inequality:
BH? ))
B 1->
E Σイ i 11ail1
||
1-y E 1-7
[ln 2
Ethol/a3
B In (c)
E H Iln + 2
Bl 27 In(c),
where (a) uses the fact that In(c) 2 1.
25


Reviews:
[{"review_id": "Y9EAV8SMlA", "reviewer": "Reviewer_rtr6", "summary": "This paper presents a unified convergence analysis for a class of adaptive stochastic gradient descent (SGD) methods. The analysis is developed for stochastic convex objectives under matrix Hölder smoothness and bounded variance assumptions. The authors' first contribution is a general convergence proof (Theorem 1) that recovers state-of-the-art rates for many adaptive methods and provides the first theoretical guarantees for DASGO. The second main contribution is an accelerated algorithm (Algorithm 2) that combines Nesterov momentum with diagonal preconditioning (e.g., AdaGrad, DASGO).", "questions": "- How should the parameter $\\delta$ be chosen to achieve the optimal guarantee? In practice, it is typically set to a very small value for numerical stability. However, according to Theorem 2, choosing a smaller $\\delta$ may actually lead to a larger upper bound due to its presence in the logarithmic term.\n- Does corresponding lower bound results exist in this setting (or a similar setting)?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper offers a clear and unified theoretical analysis of adaptive optimization methods. Its findings are novel, with a single theorem (Theorem 1) that recovers known bounds for several adaptive algorithms and establishes the first convergence guarantees for DASGO. The framework’s generality extends to both the smoothness and variance assumptions, and the technical contributions are strong.\n2. Algorithm 2 enhances adaptive methods with diagonal preconditioning by incorporating momentum, achieving provable convergence with acceleration. This represents both an innovative algorithmic development and a significant analytical advancement.", "weaknesses": "1. Several results implicitly require the smoothness and noise operators (e.g., $L,\\Sigma$) to live in the same structured space as the preconditioner $\\mathcal H$ (e.g., Assumption 2, even before the acceleration results). For diagonal $\\mathcal H$, this effectively enforces axis-aligned curvature/noise, leaving other cases out of scope. In problems where principal directions are not coordinate-aligned, the guarantees may not hold.\n\n2. The theory sets $\\eta$ proportional to a radius $R \\ge R(x^\\*)$ (or similar), which is rarely, if ever, specified in deep learning practice. A significance of AdaGrad-style methods is being parameter-free (or nearly so); requiring $R$ undermines that appeal.\n\n3. The accelerated variant uses a time-varying Nesterov schedule (e.g., $\\alpha_k = 2/(k+2)$) and gradients of auxiliary $f_k$, which diverges from the standard “constant-momentum” implementations (e.g., $\\beta \\approx 0.9$ in Adam) used in large-scale training.\n\n4. It would be interesting to explore whether further analysis can be done in non-convex setting (or under the PL condition).", "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": "CtlzU4AgRU", "reviewer": "Reviewer_3EqR", "summary": "The paper studies the theoretical aspects of preconditioned optimizers, including ASGO/One-Sided Shampoo, AdaGrad, and DASGO. The paper makes an attempt to unify the analysis of such type of algorithms under specific assumptions, as well as acceleration results of the optimizers with diagonal preconditioners.", "questions": "1. In Theorem 1, the authors mentioned an almost surely upper bound $ R $. Will there be an estimation for $ R $? I understand that for both AdaGrad or ASGO/One-Sided Shampoo, the boundedness of $ R $ can be guaranteed by imposing a projection operation. Will this also work in this framework?\n2. I think the major difference of the paper compared to [3] is the employment of Holder smoothness. Could the authors provide some discussions on how such imrprovements can help better explain the practicalness of the analyzed algorithms.\n\n\n\n[3] Xie, Shuo, et al. \"Structured preconditioners in adaptive optimization: A unified analysis.\" arXiv preprint arXiv:2503.10537 (2025).", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is written in an easy-to-follow way, making all the results and notations easy to understand.\n2. The convergence results are obtained under Holder smoothness, which is a more general assumption compared to the existing works for the same algorithms.", "weaknesses": "1. There seems to be some overclaims in the contribution part. Firstly, there has been established work on the acceleration of adaptive gradient methods. I kindly refer the authors to [1] for acceleration results of adaptive gradient methods in the diagonal preconditioner case. Also, the convergence of DASGO can actually be covered by [2] in Theorem 3.11 for block-wise RMSProp, making the contribution of this paper kind of not significant enough.\n2. Assumption 4 in the acceleration part is very restrictive. It is not satisfied by the majority of algorithms with preconditioners that are not diagonal, making the analysis actually **not** a valid analysis for a general framework.\n\n\n\n[1] Ene, Alina, Huy L. Nguyen, and Adrian Vladu. \"Adaptive gradient methods for constrained convex optimization and variational inequalities.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.\n\n[2] Xie, Shuo, Mohamad Amin Mohamadi, and Zhiyuan Li. \"Adam Exploits $\\ell_\\infty $-geometry of Loss Landscape via Coordinate-wise Adaptivity.\" arXiv preprint arXiv:2410.08198 (2024).", "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": "VxOceTagU7", "reviewer": "Reviewer_YbHY", "summary": "The main goal of this paper is to provide a unified analysis of stochastic gradient descent algorithms based on adaptive preconditioning. The authors aim to develop a theoretical framework that encompasses most existing adaptive preconditioned gradient methods, such as AdaGrad, Shampoo, and ASGO. To this end, under suitable assumptions (namely, convexity of the objective function, matrix Hölder smoothness, and bounded variance) the paper presents a unified convergence proof that recovers known guarantees for many state-of-the-art methods in stochastic optimization. A secondary contribution concerns the study of a Nesterov-type acceleration of the proposed algorithm, showing, for instance, that AdaGrad can benefit simultaneously from both momentum and diagonal preconditioning.\n\nThe contribution is interesting; however, the paper is written in a rather technical style and is primarily accessible to experts in the theoretical analysis of adaptive preconditioned stochastic gradient methods. One of the strengths of the work lies in its careful comparison of the proposed results with existing literature. Nevertheless, as I am not a specialist in the most recent developments of SGD with adaptive preconditioning, it is difficult for me to fully assess the novelty of the contribution, particularly with respect to Gupta et al. (2017), who also provided a unified convergence framework for such algorithms, and the recent preprint by Xie et al. (2025), which the authors mention as a concurrent unified analysis of AdaGrad-type methods.\n\nOverall, the paper has merit, and its contribution is relevant to the community. However, I believe the manuscript requires substantial improvements to better convey the significance and impact of its main results relative to existing work. I would appreciate clarifications and responses from the authors on the key points raised below. While I do not consider the paper ready for publication in its current form, I would be inclined to increase my rating if the exposition were improved and several of the issues outlined below were addressed.", "questions": "* In Section 2.1, Definition 1 and Assumption 1 establish the framework for the unified preconditioning setting. Could the authors comment on the novelty of this definition and assumption compared with previous works that also proposed unified analyses of SGD algorithms with adaptive preconditioning ?  \n\n* What distinguishes Lemma 1 from similar results in Gupta et al. (2017)?  \n\n* The authors claim that Lemma 2 highlights a key difference from Gupta et al. (2017). Could they elaborate further on this point ?  \n\n* At the end of page 4 and in Appendix B, it is mentioned that the unified analysis of Xie et al. (2025) shares many similarities with the results presented in Sections 2 and 3, and that the main distinction lies in Section 4, since Xie et al. (2025) do not include results involving momentum acceleration. I therefore wonder whether the main novelty of this paper essentially lies in Section 4, and if so, whether the authors could place stronger emphasis on this contribution.  \n\n* The function $\\mathcal{R}(x)$ defined in Equation (12) appears to play a central role in the unified analysis presented in Section 3. Is the use of such a function novel in the analysis of adaptive preconditioned SGD algorithms? How does it connect to existing literature on this topic? It seems that existing convergence proofs for specific algorithms (e.g.\\ AdaGrad) may already rely on similar quantities - could the authors clarify this point?  \n\n* Could the proposed unified analysis provide deeper insights into the empirical performance of adaptive preconditioned SGD algorithms compared to existing convergence proofs or algorithm-specific theoretical analyses?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* Provides solid theoretical results through a unified analysis of stochastic gradient descent with adaptive preconditioning.  \n* Offers a clear and well-structured overview of prior work.  \n* Demonstrates overall rigor in the presentation of assumptions and theoretical arguments.  \n* Includes a relevant and insightful analysis of the Nesterov acceleration applied to the proposed algorithm.", "weaknesses": "* The level of novelty of the paper is difficult to assess in comparison with existing work.  \n* The paper lacks numerical experiments that could illustrate the potential benefits of the theoretical results and provide insights into the empirical performance of algorithms encompassed by the proposed unified analysis.", "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": "EIYnUwbOLE", "reviewer": "Reviewer_JqdH", "summary": "This paper presents a unified framework to show the convergence rate of adaptive optimizers under matrix Holder smoothness and more general noise assumptions. They also show the acceleration results of AdaGrad and DASGO with Nesterov momentum.", "questions": "1. It seems that assumption 1 can be shown with the Proposition 3.2 in Xie et al. 2025. Does this suggest that the well-structured preconditioner set is a more fundamental characterization than assumption 1? Can you provide more detailed comparison and insights?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The smoothness assumptions and noise assumptions are more general than previous works, making a stronger theoretical contributions. \n2. The analysis of combining Nesterov momentum with DASGO is insightful. It helps understand why momentum can benefit Adam in reality, which is not achieved by previous works. \n3. The paper tries to connect multiple algorithms including ASGO, DASGO, Muon and Scion.", "weaknesses": "1. Assumption 1 seems to be a worse characterization than well-structured preconditioner set in Xie et al. 2025 though they seem to describe the same class of sets. The comparison needs to be done more explicitly. See questions below. \n2. In the acceleration part, the additional assumption is pretty restrictive. When the preconditioning is not diagonal, it requires $L$ and $\\Sigma$ to be identity matrix, which is a less interesting setting.", "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)