acceptodds
Under review as a conference paper at ICLR 2027

Grothendieck Meets Adam: One Probe, Three Budgets in Adaptive Optimization

Abstract

Sign descent and Adam work in the same geometry but pay for curvature differently: the standard smoothness that governs normalized descent and the adaptive smoothness that governs adaptive methods can differ by a factor of the dimension. We show that these two constants, and a pointwise constant between them, are one quantity: the largest expected curvature that a random probe can detect. They differ only in how the probe's budget is enforced: surely, on average at each point, or on average over the landscape. For convex objectives in diagonal geometry, adaptive smoothness is a squared -summing norm and the ideal preconditioner is its Pietsch measure. Each relaxation is governed by one invariant of the preconditioner algebra. Averaging at a point is a semidefinite relaxation whose gap lies between the largest matrix-block size and ; in diagonal geometry it is at most Grothendieck's constant , or for convex objectives, both asymptotically sharp. Averaging over the landscape costs a curvature rotation number, which is at most the rank of the algebra, the number of directions a preconditioner weighs independently, a bound that convex objectives approach; the rank also replaces the dimension in the known comparison of the two smoothness constants. Rotation is one for quadratics and binary logistic regression and grows linearly for log-sum-exp. In box-constrained convex optimization, rotation is the acceleration horizon: up to one logarithm, the minimax risk of deterministic first-order methods over functions of rotation at most is for queries and for , and one adaptive method, analysed without choosing a basis, attains both rates in every well-structured geometry. Gradient noise obeys the same three levels.

Primary area:
optimization
Keywords:
adaptive optimization, Adam, sign descent, preconditioning, smoothness, Grothendieck inequality, 2-summing operators, curvature rotation, acceleration, oracle complexity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_BMEGOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper is a theoretical analysis paper and focuses on the Adam optimizer. The standard smoothness controls the normalized descent and the adaptive smoothness controls adaptive methods. This paper shows that these two constants, and a pointwise constant between them, are one quantity: the largest expected curvature that a random probe can detect.

However, the writing is very unclear. The motivation is unclear, and the objective is confusing. Authors should consider readers without related background.

Critical strengths
  1. The decomposition in Theorem 2.1 provides a useful explanation of the dimension gap.

  2. The accelerated algorithm has a theoretical guarantees in the Theorem 5.1.

Critical weaknesses
  1. The paper structure is very unclear. It should highlight the motivation, challenge, and contribution. It is very unfriendly for readers without a related background.

  2. The paper mentions convex optimization. However, the motivation for the convex optimization is unclear. Given neural network is a non-convex optimization, the convex optimization is not related to the deep learning.

  3. The relationship between section 6 (experiments) and theoretical analysis is unclear. It provides much theoretical analysis. But the experiment is very short. We are not sure whether these analysis could be verified in the practical training

Questions for authors
  1. For the section 6, what is the datasets you use.
3 comments
AuthorsOpenReview ↗

Response to Reviewer BMEG (1/2)

Response to Reviewer BMEG (1/2)

Thank you for the review. Its question has a direct answer: the data are the breast-cancer and digits sets of scikit-learn, specified in Appendix I.1 (lines 2440-2447). The three weaknesses are answered below, each with its place in the paper. Line numbers refer to the revised PDF, in which every change is in blue.

W2 (convexity and deep learning).

Given neural network is a non-convex optimization, the convex optimization is not related to the deep learning.

Most of the paper does not assume convexity. Four of the five results listed under W1 assume none: Theorem 2.1 (the three smoothness constants are one probing problem) and Theorem 4.1 (rotation is at most the rank) hold for every C2C^2 objective with finite LHL_{\mathcal H}; Theorem 3.1 (the Grothendieck constant of every preconditioner family) is stated for all symmetric matrices, hence for indefinite Hessians; Theorem G.1 (Appendix G) concerns gradient noise and places no condition on the objective. Section 6 includes a non-convex model, a tanh⁡\tanh network with d=63d=63, and reports both quantities along its Adam training run.

Among the theorems, convexity is a hypothesis only in Section 5 (Theorems 5.1 and 5.2), which studies the minimax risk f(xT)−min⁡ff(x_T)-\min f and acceleration, as do the results it sharpens (Xie et al., ICLR 2026; Guzmán and Nemirovski, 2015). Elsewhere convexity appears as a special case with a better constant (π/2\pi/2 in place of KGK_G, one direction uu in place of a pair, as in display (1) of the introduction; lines 077-078 state the general case) or in examples (Proposition 4.2(ii)). It also makes one statement stronger: the extremal functions of Theorem 4.1 are convex, so the worst case of the comparison between Adam's constant and sign descent's is approached by convex functions. For non-convex rates the decomposition applies to the known guarantees as they stand: in diagonal geometry, the ratio of the AdaGrad and sign-descent coefficients in the deterministic non-convex rates is at most KG ϱ(f)\sqrt{K_G\thinspace\varrho(f)} (paragraph after Theorem A.13).

The paper was submitted to the Optimization primary area. Its objects are Adam and sign descent, and its constants are those of the ICLR 2025, ICML 2025 and ICLR 2026 papers of Xie et al. that it builds on.

W3 (how Section 6 relates to the theory).

The relationship between section 6 (experiments) and theoretical analysis is unclear.

Section 6 measures the two quantities that Theorems 3.1 and 4.1 bound, on Hessians recorded along Adam training runs. Its first paragraph defines them (lines 474-476): the pointwise gap ν(A)/∥A∥∞→1\nu(A)/\Vert A\Vert_{\infty\to1}, which Theorem 3.1 bounds by KGK_G (by π/2\pi/2 for positive semidefinite AA), and the rotation of the recorded Hessians, which Theorem 4.1 bounds by dd. Figure 4(a) draws the bounds π/2\pi/2 and KGK_G as dashed lines above the measured gaps, and the caption names both theorems. The text then sets each number against the result that governs it (lines 477-484): every pointwise gap is below 1.131.13, against π/2\pi/2 and KGK_G; rotation is exactly 11 for logistic regression, as Proposition 4.2(ii) predicts; it is 1.0821.082 for the network, against the bound d=63d=63.

The claims of the paper are theorems, each with a complete proof (Appendices B to H). The experiment is not their evidence. It answers a separate question: do the worst cases of the theorems occur on training trajectories? On these runs they do not, which is the stated conclusion: "On these runs the optimizer never meets the dimension factor of ΛH≤d LH\Lambda_{\mathcal H}\le d\thinspace L_{\mathcal H}" (lines 483-484). The runs are small (d≤63d\le63) because both quantities require exact Hessians and semidefinite programs, and the norm ∥A∥∞→1\Vert A\Vert_{\infty\to1} is NP-hard to compute. Appendix I gives the protocol with every model, seed and solver, and the supplementary material regenerates the figure.

AuthorsOpenReview ↗

Response to Reviewer BMEG (2/2)

Response to Reviewer BMEG (2/2)

Q1 (datasets). Binary logistic regression uses the breast-cancer data of scikit-learn (1010 principal components, d=10d=10). Softmax regression uses the digit images of scikit-learn, restricted to the first C∈{3,5,8}C\in\lbrace3,5,8\rbrace classes (66 principal components, d=6Cd=6C). The network is a one-hidden-layer tanh⁡\tanh network 6→6→36\to6\to3 on the digit classes {0,1,2}\lbrace0,1,2\rbrace (d=63d=63). This is Appendix I.1 (lines 2440-2447). The revised PDF now names the two datasets in the first sentence of Section 6 (lines 471-474).

W1 (structure: motivation, challenge, contribution). The revised PDF now has an explicit contributions paragraph with a notation key in the introduction (lines 115-125). The three elements are at the following places.

Motivation (lines 056-066). Sign descent and Adam are analysed with two different smoothness constants, L∞L_\infty and Λ\Lambda. They can differ by the dimension dd, and the factor decides whether accelerated rates are available. The paragraph ends with the question the paper answers: "What is the factor dd made of?"

Challenge (Section 2). The two constants are defined by different optimization problems, a norm that is NP-hard to compute and a semi-infinite semidefinite program over the whole landscape, so neither is expressed in terms of the other.

Contribution (lines 067-114, five titled paragraphs, and the contributions paragraph), in summary:

  1. Both constants, and a new one between them, are the largest curvature a probe can read under three budgets (Theorem 2.1).
  2. The first gap is a Grothendieck constant that depends only on the family of preconditioners; for Adam it is below 1.7831.783 (Theorem 3.1).
  3. The second gap is the rotation of the curvature across the landscape. It is at most the rank of the family, and convex functions approach this bound (Theorem 4.1).
  4. In box-constrained convex optimization, rotation is the number of gradient queries before which no deterministic first-order method can accelerate (Theorem 5.2).
  5. Gradient noise has the same three levels (Theorem G.1).

Figure 1 states the result in one inequality, and Table 1 lists the constants for six preconditioner families. Items 1 to 5 are the content of the contributions paragraph.

Every result has a complete proof in Appendices B to H (roadmap at line 648), and we will answer any question on a specific step.

We ask you to reconsider the rating in the light of the scope of Theorems 2.1, 3.1, 4.1 and G.1, which assume no convexity, and of the role of Section 6.

Thanks a lot for the response. However, I still have concerns about its contribution, presentation and application in the Neural networks. I will keep my scores.

Reviewer_xUCmOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the smoothness assumptions used to analyze steepest descent algorithms and adaptive optimizers such as AdaGrad and Adam. Specifically, it builds on the adaptive smoothness assumptions proposed by Xie et al. (2026) and related works like Kovalev 2026.

The authors introduce a “local” version of adaptive smoothness ΓH∘\Gamma_{\mathcal{H}}^\circ that only requires a matrix to dominate the Hessian at the current point xx. They show that this local version is the same up to an independent constant as the smoothness under the norm of the preconditioner algebra.

Next, they also show that adaptive smoothness is at most the rank of the algebra times the smoothness under the preconditioner algebra. They provide a few examples showing the separation between these smoothness notions.

Finally, they propose an algorithm that achieves an accelerated rate of O(1/N2)O(1/N^2) under the adaptive smoothness assumption, and provide a corresponding lower bound showing that this rate is tight.

Critical strengths

This paper identifies an interesting application of Grothendeik’s inequality to show that ℓ∞\ell_\infty smoothness is at most a constant times pointwise diagonal adaptive smoothness. This makes an interesting connection between the NSD geometry and adaptive smoothness geometry. For general preconditioner algebras, they show that the pointwise adaptive smoothness is upper bounded by L∣∣⋅∣∣H(f)bmaxL_{\vert|\cdot|\vert_{\mathcal{H}}}(f) b_{max}.

The lower bound for first-order algorithms under adaptive smoothness is interesting and matches the upper bounds for the accelerated algorithm up to logarithmic terms.

Critical weaknesses

The presentation and clarity of the paper need significant improvement. There is a lot of mathematical notation, and the writing is not clear. It is hard to understand the main contributions of the paper even after several passes through the introduction.

One of the main contributions of Xie et al. (2026) was establishing that adaptive smoothness enables accelerated convergence rates of the form O~(ΛH/T2)\widetilde O(\Lambda_{\mathcal H}/T^2). Theorem 5.1 obtains the same asymptotic accelerated dependence, although it removes logarithmic factors. Therefore, the new accelerated rate seems to be rather incremental compared to existing work, and it is not clear what the new contribution is. Furthermore, Xie et al. (2026) analyze their accelerated algorithm in the stochastic setting, while Theorem 5.1 is only in the deterministic setting.

The worst-case bound on the adaptive smoothness has been established for specific functions in prior work. For example, Yadav et al. (2025) show that the ℓ∞\ell_\infty smoothness constant of the softmax unigram model is 11 while the diagonal adaptive smoothness is d/2d/2.

Overall, several of the contributions, particularly the accelerated convergence rate and the underlying smoothness notions, are closely related to prior work. The presentation and clarity further exacerbate these issues.

Yadav et al., "Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance", 2025.

Questions for authors

Theorem 5.1 applies to general well-structured preconditioner families. However, the main matching lower bound in Theorem 5.2 is restricted to diagonal geometry, with only a partial extension to one-sided Shampoo. Would it be possible to extend the lower bound to general preconditioner algebras?

Theorem 5.2 builds on the existing resisting-oracle framework of Guzmán and Nemirovski (2015). It would be helpful to clarify the technical novelty of the rotation-controlled construction and its significance beyond the previously established oracle lower bounds.

5 comments
AuthorsOpenReview ↗

Response to Reviewer xUCm (1/4)

Response to Reviewer xUCm (1/4)

Thank you for the review and the precise questions on Theorem 5.2. The first prior-work objection concerns a rate that the submission itself attributes to prior work. The second concerns one example, whose diagonal lower bound is in Yadav et al., now cited; the paper's worst-case result is a theorem about every C2C^2 objective and every well-structured algebra. Line numbers refer to the revised PDF; changes are in blue.

W2 (Theorem 5.1 and the accelerated rate of Xie et al., 2026).

the new accelerated rate seems to be rather incremental compared to existing work, and it is not clear what the new contribution is

What the paper adds to the accelerated rates of Xie et al. and of Kovalev is the other side. Neither proves a lower bound in terms of Λ\Lambda. Xie et al. pair their rate with the Guzmán–Nemirovski bound for the class {L∞≤L}\lbrace L_\infty\le L\rbrace. Kovalev proves none: the optimality he states refers to the classical bounds of Nemirovski and Yudin, which do not involve Λ\Lambda. Whether Λ\Lambda is the right constant on the box had, to our knowledge, no proof. Theorem 5.2 answers it for deterministic first-order methods, for T≤dT\le d and up to one logarithm: over {Λ≤kL∞}\lbrace\Lambda\le kL_\infty\rbrace the minimax risk is LR2/TLR^2/T up to T=kT=k and kLR2/T2kLR^2/T^2 for k≤T≤dk\le T\le d. So the rate ΛR2/T2\Lambda R^2/T^2 cannot be improved uniformly by more than a logarithm (Corollary E.3), and it applies from the horizon T=kT=k. This is the lower bound the review calls interesting.

The accelerated rate itself is not presented as new. The introduction states it as a known property of the adaptive smoothness of Xie et al. (lines 061-064: "Λ\Lambda supports accelerated rates of order ΛR2/T2\Lambda R^2/T^2 up to logarithms"), and the related-work paragraph says "The preconditioner framework and AdaGrad-type rates are due to Xie et al. (2025b; 2026)" (lines 129-130). Section 5 credits Kovalev (2026) with the rate on the ball XRX_R (lines 408-409). Theorem A.12 restates the theorem of Xie et al., in the deterministic diagonal case, with its hypotheses, and Proposition E.4 shows what it yields.

Theorem 5.1 supplies the accelerated upper bound of Theorem 5.2, and the non-accelerated one up to its constant, in the oracle model of Guzmán and Nemirovski: the output must lie in the box XRX_R, and the error is measured against min⁡XRf\min_{X_R}f. By its own hypotheses, the accelerated theorem of Xie et al. cannot serve there:

minimizer and domainoutputdeterministic part of the bound
Xie et al. (2026); deterministic diagonal case restated as Theorem A.12x∗x^\ast a global minimizer; iterates within DD of x∗x^\ast (Algorithm 2), or ∥x∗∥H≤D\Vert x^\ast\Vert_{\mathcal H}\le D (Algorithm 8)unconstrained average (Algorithm 2); average of the points before projection (Algorithm 8)O~((ΛD2log⁡2d+dϵD)/T2)\tilde O\big((\Lambda D^2\log^2 d+d\sqrt\epsilon D)/T^2\big); in diagonal geometry log⁡(∥VT−1∥op2/ϵ)\log(\Vert V_{T-1}\Vert_{\mathrm{op}}^2/\epsilon) in place of log⁡2d\log^2 d
Kovalev (2026, Theorem 5)minimizer over the ball XRX_Rin XRX_RO(ΛR2/K2+δRdim⁡(X)/K2)O\big(\Lambda R^2/K^2+\delta R\dim(X)/K^2\big) (stated for stochastic gradients and Hölder smoothness; shown at σ=0\sigma=0, ν=1\nu=1)
Theorem 5.1minimizer over any convex compact XX of H\mathcal H-diameter at most 2R2Rin XXmin⁡{242 LHR2/(N+1), 32 ΛHR2/(N(N+1))}\min\lbrace 24\sqrt2\thinspace L_{\mathcal H}R^2/(N+1),\ 32\thinspace\Lambda_{\mathcal H}R^2/(N(N+1))\rbrace

In diagonal geometry a constrained accelerated rate with a logarithm is AdaACSA (Ene et al., 2021, Theorem 3.3), as line 410 says; Theorem 5.1 removes that logarithm and holds in every well-structured geometry. On the box, Kovalev's theorem could supply the accelerated half. Theorem 5.1 gives both rates from one run, on any convex compact domain, with no initialization term. Neither the bound of Xie et al. nor that of Kovalev contains the standard constant LHL_{\mathcal H}. This is the claim of the abstract ("one adaptive method [...] attains both rates in every well-structured geometry"). The proof (Appendix E.1) never chooses a basis, so it needs no logarithm for non-commutativity (the analysis of Xie et al. pays log⁡d\log d there, their Lemma 3.3).

Xie et al. (2026) analyze their accelerated algorithm in the stochastic setting, while Theorem 5.1 is only in the deterministic setting

Theorem 5.1 is stated for exact gradients because Theorem 5.2 is a statement about deterministic first-order methods, the model in which the lower bound is proved. We claim no stochastic rate for method (11); the stochastic rates of Xie et al. and of Kovalev stand. The stochastic contribution of the paper is Theorem G.1 with Corollary G.2, which says what their noise constant consists of: the same three levels, with σH2≤rk K⋅σstd2\sigma_{\mathcal H}^2\le\mathrm{rk}\thinspace\mathcal K\cdot\sigma_{\mathrm{std}}^2 in place of the factor dd of Xie et al.

AuthorsOpenReview ↗

Response to Reviewer xUCm (2/4)

Response to Reviewer xUCm (2/4)

W3 (the worst case and Yadav et al., 2025).

The worst-case bound on the adaptive smoothness has been established for specific functions in prior work.

The paper's worst-case claim is Theorem 4.1, a bound over every C2C^2 objective. The result of Yadav et al. (arXiv:2512.00763, an OPT 2025 workshop paper) is one function, and it coincides with the diagonal lower bound in one of the paper's three examples: for the softmax unigram objective, which is log-sum-exp plus an affine term, they prove L∞=1L_\infty=1 and diagonal adaptive smoothness at least d/2d/2. The revised PDF now cites them in the discussion of Proposition 4.2(iii) (lines 371-374), in its proof (line 1384), and in the related-work paragraph (lines 131-132). Theorem 4.1 differs from an evaluation of this kind in three ways.

  1. It is an upper bound for every C2C^2 objective and every well-structured algebra: ΛH≤rk K⋅LH\Lambda_{\mathcal H}\le\mathrm{rk}\thinspace\mathcal K\cdot L_{\mathcal H}. This improves the factor dd of Xie et al. (their Proposition 2.5) to dLd_L for one-sided Shampoo on dL×dRd_L\times d_R matrices, to the number of layers for layer-wise scalar step sizes, and to 11 for AdaGrad-Norm.
  2. It is sharp: in every algebra, convex functions approach rk K\mathrm{rk}\thinspace\mathcal K. Their evaluation gives d/2d/2, half the bound, and is carried out in diagonal geometry only.
  3. With Theorem 3.1 it says what the gap consists of. In diagonal geometry at most KG<1.783K_G\lt1.783 of any gap between L∞L_\infty and Λ\Lambda arises at a single point, so a gap that grows with dd is rotation. For log-sum-exp, Proposition 4.2(iii) gives Λ∘=L∞=1/τ\Lambda^\circ=L_\infty=1/\tau, so the whole factor d/2d/2 is rotation. The pointwise constant, which is what shows this, and the full-matrix values are not in Yadav et al.

W4 (relation to prior work overall). The new results are: (i) Theorem 2.1, the three constants as one probing problem under three budgets, a duality over the whole landscape; (ii) Theorem 3.1, the Grothendieck constant of every preconditioner algebra, bmax⁡≤k(H)≤K(H)≤KGbmax⁡b_{\max}\le k(\mathcal H)\le K(\mathcal H)\le K_Gb_{\max}, exact for one matrix block (in diagonal geometry the inequality is Grothendieck's, as lines 132-136 say, and the theorem places it in this comparison); (iii) Theorem 4.1, the rank bound, which is the factor dd of Xie et al. only when every block is real and appears once, and its sharpness among convex functions in every algebra; (iv) Theorem 5.2 with Proposition 5.3, the minimax risk with its horizon at the rotation budget; (v) Theorem G.1, the same three levels for gradient noise. The review lists (ii) and (iv) among the strengths.

AuthorsOpenReview ↗

Response to Reviewer xUCm (3/4)

Response to Reviewer xUCm (3/4)

Q2 (novelty beyond the resisting oracle of Guzmán and Nemirovski, 2015). Their Corollary 1 gives Risk(T)≥c LR2/(Tln⁡n)\mathrm{Risk}(T)\ge c\thinspace LR^2/(T\ln n) for the class {L∞≤L}\lbrace L_\infty\le L\rbrace and T≤nT\le n, with the exponent rr of the smoothing kernel fixed at r=min⁡[p,3ln⁡n]r=\min[p,3\ln n]. Their class carries no adaptive smoothness. For T≤kT\le k their instance on TT coordinates lies in {Λ≤kL∞}\lbrace\Lambda\le kL_\infty\rbrace, because Λ≤TL∞\Lambda\le TL_\infty there (Lemma E.2(a),(b)); the proof of Theorem 5.2 says so. For k<Tk\lt T their theorem gives no statement of this form: their analysis does not control Λ\Lambda, the instance leaves the class once kk is below a constant fraction of TT (its rotation is of order TT, Proposition 5.3 at r=3ln⁡Tr=3\ln T), and no bound of order k/T2k/T^2 follows. Three steps are new.

  1. The exponent as a parameter (Proposition 5.3, Lemma F.2). For every r>2r\gt2 we compute the curvature of the smoothed maximum on mm coordinates. A uniform Hessian bound gives Λ≤4(r−1)m/ϵ\Lambda\le4(r-1)m/\epsilon, the Hessian at the all-way tie gives L∞L_\infty, and the Hessians at two-way ties force every coordinate of a common majorant to pay. The result is 22/rπm1−2/r≤ϱ≤Λ/L∞≤m1−2/r/(1−m−2)\frac{2^{2/r}}{\pi}m^{1-2/r}\le\varrho\le\Lambda/L_\infty\le m^{1-2/r}/(1-m^{-2}). None of this is needed when only L∞L_\infty is tracked.
  2. Tuning to the budget (proof of Theorem 5.2). With m=Tm=T and T1−2/r≈min⁡{k,T}T^{1-2/r}\approx\min\lbrace k,T\rbrace, the instance lies in {Λ≤kL∞}\lbrace\Lambda\le kL_\infty\rbrace and in {ϱ≤k}\lbrace\varrho\le k\rbrace, and the resisting oracle leaves error at least LR2 T1−2/r/(32(r−1)T2)LR^2\thinspace T^{1-2/r}/(32(r-1)T^2). The factor that measures the rotation is the factor gained in hardness. At r=3ln⁡Tr=3\ln T this is their construction on TT coordinates (with the exact kernel of step 3), and as rr decreases to 22 it becomes hard at the accelerated rate.
  3. An exact C2C^2 instance (Lemma F.1, Proposition F.3). Rotation is a statement about Hessians, so the instance must be C2C^2 with a computable Hessian. Their kernel is 2∥h∥r2θ2\Vert h\Vert_r^{2\theta} with θ\theta slightly above one, and their argument needs C1C^1 smoothed functions only. We take 2∥h∥r22\Vert h\Vert_r^2 exactly and prove that the smoothed maximum is C2C^2 across changes of the active set, with the locality that the resisting oracle needs.

Significance. The result is two-sided in the regime k<T≤dk\lt T\le d, where their theorem gives no bound of this form. It identifies the horizon T=kT=k at which acceleration begins, and it shows that Λ\Lambda cannot be improved uniformly by more than a logarithm (Corollary E.3).

Q1 (lower bound for general preconditioner algebras). Yes, up to a horizon that depends on the geometry, and a horizon of that kind cannot be avoided. Let K≅⨁iMbi(R)⊗Ini\mathcal K\cong\bigoplus_i\mathbb M_{b_i}(\mathbb R)\otimes I_{n_i} have real blocks, acting on x=(X(i))x=(X^{(i)}) with X(i)∈Rbi×niX^{(i)}\in\mathbb R^{b_i\times n_i}, and put S=∑imin⁡{bi,ni}S=\sum_i\min\lbrace b_i,n_i\rbrace. The map G(x)=(Xss(i)/ni)G(x)=\big(X^{(i)}_{ss}/\sqrt{n_i}\big), s≤min⁡{bi,ni}s\le\min\lbrace b_i,n_i\rbrace, sends XRX_R onto the box [−R,R]S[-R,R]^S, and for f=F∘Gf=F\circ G the three constants lift exactly: LH(f)=L∞(F)L_{\mathcal H}(f)=L_\infty(F), ΛH∘(f)=Λ∘(F)\Lambda^\circ_{\mathcal H}(f)=\Lambda^\circ(F), ΛH(f)=Λ(F)\Lambda_{\mathcal H}(f)=\Lambda(F). This is the argument of Proposition E.5 with one normalization per block. Hence the lower bound of Theorem 5.2 holds, with the same constant, for 3≤T≤S3\le T\le S in every such geometry: S=dS=d for Adam and AdaGrad, S=min⁡{dL,dR}S=\min\lbrace d_L,d_R\rbrace for one-sided Shampoo (Proposition E.5), and SS equal to the number of layers for layer-wise scalar step sizes.

A cap of order SS, up to a logarithm, cannot be removed. With ∥x∥w2=∑i∥X(i)∥F2/ni\Vert x\Vert_w^2=\sum_i\Vert X^{(i)}\Vert_F^2/n_i one has ∥⋅∥H≤∥⋅∥w\Vert\cdot\Vert_{\mathcal H}\le\Vert\cdot\Vert_w, and XRX_R has ww-radius at most RSR\sqrt S, so Euclidean acceleration in this norm gives Risk(T)≤8SLR2/T2\mathrm{Risk}(T)\le8SLR^2/T^2 for every T≥2T\ge2 and every kk. For full-matrix AdaGrad S=1S=1: acceleration is available from the start whatever the rotation, which is why the paper states the Shampoo horizon with its cap (text after Proposition E.5). On {ΛH≤kLH}\lbrace\Lambda_{\mathcal H}\le kL_{\mathcal H}\rbrace Theorem 5.1 gives the matching 144kLR2/T2144kLR^2/T^2 for T≥3T\ge3 in every geometry; on the rotation class the accelerated bound carries the factor k(H)k(\mathcal H), as after Proposition E.5. The revised PDF now states this general form, with its proof, as Proposition E.6 (lines 1945-2007); it is proved for real blocks, and complex and quaternionic blocks are not claimed.

Reviewer_DAT2OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces a general framework for constructing and analyzing adaptively preconditioned first order methods for convex (and general) optimization. The authors original motivation is to unify the analysis of ADAM and sign descent, but their framework is much more generally applicable. Given any algebra of allowed preconditioners, the authors construct a first-order optimization method which adaptively estimates the projection of the Hessian onto this algebra. They prove a general theorem giving convergence guarantees in terms of quantities depending upon the preconditioner algebra and the Hessians of the target function.

Critical strengths

The viewpoint presented in the paper on adaptive precondition methods, such as ADAM, is very interesting and useful. In particular, I found the idea of a probe measuring and estimating the Hessian of the target function to be quite intuitive.

It is fascinating that deep ideas from functional analysis become fundamental to the analysis of optimization methods.

The analysis takes into account both the errors in estimating the Hessian at each point and the errors due to the Hessian changing from point to point. These two contributions are separated out in an interesting and novel way.

Critical weaknesses

In methods such as ADAM, as far as I understand, the points XX and uu which are used to estimate the Hessian are not random, but are rather taken to be the iterates produced by the algorithm and the gradients at those points. Is the randomized model considered in this paper really justified? Is this a standard setup in this literature?

Questions for authors

Regarding the idea of a probe which measures curvature at random points in random directions, is that really applicable to methods such as ADAM? My concern is that such methods typically only measure curvature at the iterates in the directions of the gradient, right? Is a random model really justified here?

Are you defining Λ∘\Lambda^\circ via the equation (1)? In that case, the Theorem 2.1 really only has non-trivial content for Λ\Lambda and LL, but not for Λ∘\Lambda^\circ, right?

After Theorem 5.1, you say that `The method needs R, but no smoothness constant, rotation number or preconditioner.' This is not quite clear to me. Doesn't the method require you to compute the projection πK\pi_{\mathcal{K}}? This requires knowledge of the algebra H\mathcal{H}, right? Isn't this the preconditioner, i.e., aren't elements from H\mathcal{H} used to precondition the optimization method?

It seems in your experiments (Figure 4) that the gaps are significantly smaller that the Grothendieck's constant. Does this suggest that the analysis can be further improved?

2 comments
AuthorsOpenReview ↗

Response to Reviewer DAT2

Thank you for the review and the four questions. Each is answered below, and for two of them the revised PDF now states the sentence more precisely. Changes are in blue, and line numbers refer to the revised PDF.

W1 and Q1 (is a random probe justified for Adam, whose iterates and gradients are not random?). The probe is not a model of the algorithm, and the paper makes no randomness assumption on iterates. Theorem 2.1 is an identity about the constants in which existing guarantees are stated. The smoothness LHL_{\mathcal H} of sign descent and the adaptive smoothness ΛH\Lambda_{\mathcal H} of AdaGrad and Adam (Xie et al., 2026, Definitions 2.3 and 2.4) are extrema over the whole landscape, and the theorem says that each equals the largest reading of a probe under a budget. The randomness is that of a dual variable, as a mixed strategy is in a minimax theorem. The adaptive constant is a minimum over one preconditioner that must serve all points, and the dual of "one HH for all xx" is a probability distribution over points and directions (Lemma C.3). So the setup is the standard definition of this literature, read through duality. The dual reading is what is new; for convex objectives in diagonal geometry it is Pietsch's description of 2-summing norms (Remark 2.2).

The algorithms stay deterministic. The method of Theorem 5.1 measures curvature as you describe, at its iterates and along gradient differences ut=gt−mtu_t=g_t-m_t, and accumulates πK(utut⊤)\pi_{\mathcal K}(u_tu_t^\top). Its analysis is the primal side of the same identity: whatever these measurements are, the trace of any common majorant pays for the learned metric (Step 6 of the proof, Appendix E.1). The iterates of a run are one deterministic family of measurement points; the probe supremum is the worst case over all such families, which a guarantee for a whole class must control. Section 6 looks at actual iterates: it evaluates both gaps on Hessians recorded along Adam runs.

Q2 (is Λ∘\Lambda^\circ defined by equation (1)?). The formal definition is equation (4): ΛH∘(f)\Lambda^\circ_{\mathcal H}(f) is sup⁡xνH(∇2f(x))\sup_x\nu_{\mathcal H}(\nabla^2f(x)): the least trace of a preconditioner dominating the Hessian at one point, chosen separately at each point. Equation (1) previews Theorem 2.1, and the sentence after it introduces the name Λ∘\Lambda^\circ before the definition. The content of the theorem is as follows. At the sure level the theorem restates the norm, as line 238 says. At the pointwise level it is strong duality for one semidefinite program (Lemma D.1) together with the realization of dual solutions by probes (Lemma C.2). The global level carries the weight: it is the dual of a semi-infinite program over the landscape, reduced to finitely many Hessians by compactness (Lemma C.3), and it is what makes rotation a property of probes that move between points. In the revised PDF the sentence after equation (1) now reads (line 074): "The middle budget corresponds to a pointwise adaptive smoothness Λ∘(f)\Lambda^\circ(f), defined in Section 2 as the supremum over points xx of the least trace of a diagonal preconditioner dominating ∇2f(x)\nabla^2f(x)."

Q3 ("no preconditioner" versus the projection πK\pi_{\mathcal K}). The method is given the family of preconditioners, that is, the algebra K\mathcal K through πK\pi_{\mathcal K} (for Adam: "diagonal"), and the radius RR, as AdaGrad is. It is not given an element HH of the family: not the majorant that attains ΛH(f)\Lambda_{\mathcal H}(f), and none of the numbers LHL_{\mathcal H}, ΛH\Lambda_{\mathcal H}, ϱ\varrho. This is the meaning of the sentence after Theorem 5.1, which now reads (lines 404-405): "The method is given the family H\mathcal H (through πK\pi_{\mathcal K}) and RR; it needs no smoothness constant, no rotation number and no tuned preconditioner H∈HH\in\mathcal H [...]."

Q4 (measured gaps far below Grothendieck's constant: can the analysis be improved?). Not in the worst case, where the constants are sharp: sup⁡dK(Dd+)=KG\sup_dK(\mathcal D_d^+)=K_G and sup⁡dk(Dd+)=π/2\sup_dk(\mathcal D_d^+)=\pi/2 (Theorem 3.1(c)), and convex functions approach the rank bound on rotation (Theorem 4.1). The small values in Figure 4 are a property of those landscapes. The decomposition separates the two: the Grothendieck factor depends on the algebra alone, the rotation on the landscape. The paper contains two instance-dependent refinements. In dimension dd the constant is KG(d)≤KGK_G^{(d)}\le K_G (Theorem 3.1). And structure can remove rotation: for convex ff it is exactly 11 whenever one Hessian dominates all others, as in logistic regression (Proposition 4.2(ii)), which Figure 4(b) confirms. Which natural losses rotate is open problem (iii) of the Discussion; why the trained network rotates so little is part of that question.

The general response relates the paper to the prior works named in another review and lists the changes in the revised PDF.

I thank the authors for carefully addressing my questions. This clears up some of my initial confusion. However, I see that the other reviewers have raised serious issues with the paper. I will tentatively stick with my original assessment instead of lowering my score in light of the issues that the other reviewers raise. However, my confidence in my original assessment has been significantly reduced.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the three reviewers. This note states what the paper claims, how it relates to the three prior works named in the reviews, and what changed in the revised PDF. Individual points are answered under each review. Line numbers refer to the revised PDF.

1. What the paper claims. Sign descent and Adam are analysed with two smoothness constants, LL and Λ\Lambda, that can differ by the dimension dd. The paper explains this factor.

  • Theorem 2.1. LL, Λ\Lambda and a new pointwise constant Λ∘\Lambda^\circ between them are one quantity, the largest curvature a probe can read, under three budgets. This holds for every C2C^2 objective and every well-structured preconditioner family.
  • Theorem 3.1. Λ∘/L\Lambda^\circ/L is at most a Grothendieck constant of the family, between its largest block size bmax⁡b_{\max} and KGbmax⁡K_Gb_{\max}. For Adam it is at most KG<1.783K_G\lt1.783, and KGK_G is asymptotically sharp.
  • Theorem 4.1. Λ/Λ∘\Lambda/\Lambda^\circ, the rotation, is at most the rank of the family, and convex functions approach the bound. The rank replaces dd in the inequality Λ≤dL\Lambda\le dL of Xie et al. (2026).
  • Theorem 5.2. In box-constrained convex optimization, the minimax risk of deterministic first-order methods over functions of rotation at most kk is LR2/TLR^2/T up to T=kT=k and kLR2/T2kLR^2/T^2 for k≤T≤dk\le T\le d, up to one logarithm.
  • Theorem G.1. Gradient noise has the same three levels.

Reviewer DAT2 and Reviewer xUCm describe the Grothendieck connection, the separation of pointwise and landscape effects, and the lower bound as interesting or novel. No review names an incorrect statement or proof step; every result has a complete proof in Appendices B to H.

2. Relation to prior work (Reviewer xUCm, W2 to W4).

prior workwhat it containswhat the paper adds
Xie et al. (ICLR 2026)the framework and both constants; L≤Λ≤dLL\le\Lambda\le dL; a stochastic accelerated rate O~(ΛD2/T2)\tilde O(\Lambda D^2/T^2) for a global minimizer, with logarithmswhy the factor exists and how large it is (Theorems 2.1, 3.1, 4.1); the matching lower bound and the horizon (Theorem 5.2); rk K\mathrm{rk}\thinspace\mathcal K in place of dd, for smoothness and for noise
Kovalev (arXiv, 2026)an accelerated rate without logarithms on the ball XRX_Rcited in Section 5 for this rate; Theorem 5.1 adds any convex compact domain and the non-accelerated rate from the same run
Yadav et al. (OPT 2025 workshop and arXiv)one function, the softmax unigram model: L∞=1L_\infty=1 and diagonal adaptive smoothness at least d/2d/2the bound for all functions and all algebras and its sharpness (Theorem 4.1); for log-sum-exp, the pointwise constant, which shows that the whole factor is rotation (Proposition 4.2(iii)), where it is now cited

The accelerated rate is not claimed as new: the submission states it as a known property of the adaptive smoothness of Xie et al. (lines 061-064), attributes the AdaGrad-type rates to them (lines 129-130), credits Kovalev with the rate on the ball (lines 408-409), and restates the theorem of Xie et al. in the deterministic diagonal case (Theorem A.12). Neither Xie et al. nor Kovalev has a lower bound in terms of Λ\Lambda. Theorem 5.2 supplies it, and Theorem 5.1 gives its accelerated upper bound, feasible and without logarithms.

3. Scope (Reviewer BMEG, W2 and W3). Theorems 2.1, 3.1, 4.1 and G.1 assume no convexity. Among the theorems, convexity is a hypothesis only in Section 5 (minimax risk and acceleration). Section 6 measures the two gaps of Theorems 3.1 and 4.1 along Adam training of five models, one of them a non-convex network; the data are the breast-cancer and digits sets of scikit-learn (Appendix I.1).

4. Revised PDF. The revised PDF is uploaded with this response. Every change is in blue, and the main text stays within the page limit:

  • a contributions paragraph with a notation key is now in the introduction, after "Consequences" (lines 115-125);
  • the sentence after equation (1) (line 074) and the sentence after Theorem 5.1 (lines 404-405) are now worded as in the answers to Reviewer DAT2 (Q2 and Q3);
  • the two datasets are now named in the first sentence of Section 6 (lines 471-474);
  • Yadav et al. are now cited in the discussion of Proposition 4.2(iii) (lines 371-374), in its proof, and in the related-work paragraph (lines 131-132);
  • the related-work clause on Ene et al. (2021) (line 130) and the last sentence of Theorem A.12 (lines 832-833) now state the relation to Theorem 5.1 as Section 5 does (line 410);
  • a new Proposition E.6 (lines 1945-2007), in answer to Q1 of Reviewer xUCm: the lower bound of Theorem 5.2 holds in every preconditioner algebra with real blocks, up to the horizon S=∑imin⁡{bi,ni}S=\sum_i\min\lbrace b_i,n_i\rbrace, beyond which Euclidean acceleration caps the risk at 8SLR2/T28SLR^2/T^2; open problem (ii) of the Discussion points to it (lines 503-504).

No result of the submission changes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.