acceptodds
Under review as a conference paper at ICLR 2027

Optimal Projection-Free Adaptive SGD for Matrix Optimization

Abstract

Recently, Jiang et al. [2026] developed Leon, a practical variant of One-sided Shampoo [Xie et al., 2025a, An et al., 2025] algorithm for online convex optimization, which does not require computing a costly quadratic projection at each iteration. Unfortunately, according to the existing analysis, Leon requires tuning an additional hyperparameter in its preconditioner and cannot achieve dimension-independent convergence guarantees for convex optimization problems beyond the bounded gradients assumption. In this paper, we resolve this issue by proving certain stability properties of Leon's preconditioner. Using our improved analysis, we show that tuning the extra hyperparameter can be avoided and, more importantly, develop \em the first practical variant of One-sided Shampoo with Nesterov acceleration, which does not require computing projections at each iteration. As a side contribution, we obtain improved dimension-independent rates in the non-smooth non-convex setting and develop a unified analysis of the proposed algorithm, which yields accelerated projection-free adaptive SGD with (block-)diagonal preconditioners.

Primary area:
optimization
Keywords:
optimization theory, convex optimization, online optimization, stochastic optimization

Reviews

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

The paper targets two weaknesses of Leon (Jiang et al., 2026), the projection-free FTRL variant of one-sided Shampoo: it needs an extra scalar δ tuned by hand, and its analysis assumes uniformly bounded gradients. The authors first prove a gradient-stability property of the preconditioning operator (Lemma 4), which lets δ be taken arbitrarily small, removes the hyperparameter and yields dimension-independent guarantees beyond bounded gradients. They then extend UniXGrad-style accumulation of squared gradient differences from scalar step sizes to general preconditioners (Lemma 7), giving a Nesterov-accelerated projection-free method with O(ε-2/(1+3ν)) for ν-Holder smooth convex problems and O(ε-2) in the stochastic convex case. The paper is entirely theoretical.

Critical strengths

1Lemma 4 is the real technical core. The bound ‖∇Ψk+1(m) - ∇Ψk(m)‖2 ≤ η2 (‖√(Sk+1)‖tr - ‖√(Sk)‖tr) ties the change of the regularizer directly to the change of the gradient, which is exactly what cancels the negative Bregman terms that Lemma 3 introduces. The logic closes cleanly; it does not read as an estimate forced to fit. 2Generalizing UniXGrad's gradient-difference accumulation to general preconditioners (Lemma 7) is useful beyond this paper: the earlier analyses of Kavis et al. and Rodomanov et al. cover only scalar step sizes, and bounding ‖∇fk(xk+1) - ∇fk(xk)‖ through the Bregman divergence is the step that makes the extension work. 3The unification is substantive rather than cosmetic. Assumption 1 places AdaGrad, one-sided Shampoo and scalar step sizes in one framework, and Theorem 5 matches the known optimal rates at both ν = 1 and ν = 0, with the stochastic term σ R / √(K+1) cleanly separated from the δ term. 4The proofs are written to be checked: every step in Appendix B names the lemma, the Lowner-Heinz inequality or the differentiability property of the trace square root that it uses.

Critical weaknesses

1.There are no experiments at all. "Practical" appears three times in the abstract, "first practical variant" once, and the paper contains not a single numerical result - not even a toy matrix problem. For a submission whose stated purpose is to remove a practical nuisance parameter, this is the central problem. Even ten lines of synthetic matrix optimization against Leon and USGD, with per-iteration timing (the second gradient sample in Algorithm 2 is not free), would change the review substantially. 2.The novelty is repair rather than construction. The algorithmic skeleton - FTRL with Ψ*k, the fk construction for Nesterov, UniXGrad-style accumulation - is inherited. The increment is one stability lemma plus more careful bookkeeping. Theorem 3 has the same functional form as Theorem 3.2 of Jiang et al., only with weaker hypotheses, and Theorem 5's rate is the known optimum for this family. The "what was previously impossible" column is not filled. 3.The δ story needs to be sharpened. The bounds in Theorems 1 and 3 both contain δ R dim(X), which comes from the initialization S-1 = δ2 I, since ‖√(S0)‖tr = δ dim(X); sending δ to zero removes it. So where exactly did the original analysis get stuck? Which inequality required δ to be tied to the gradient bound? Without an answer, a reader may conclude that the dimension dependence was an accounting artifact rather than a real obstacle - and that is precisely the question that determines what this paper is worth. 4.The bridge from the assumptions to deep learning is narrow. Assumption 2(ii) and 4(ii) measure second moments in a fixed B, and Assumption 3 requires Holder smoothness with respect to ‖.‖B, while the algorithm runs an adaptive Sk. Section 3.3 offers E[G GT] ≤ C2 with C of low effective rank as the motivating model, but no evidence is given that transformer gradients live there. The rescaling argument for the √(n) factors in G and ρ is also loose: the rescaling changes ε and γ as well, so Definition 1 should be re-derived rather than declared invariant. 5.The practical question is left unanswered: what δ should one use? At δ = 0, Sk is singular and the pseudoinverse is needed (Lemma 9). But in bf16, δ = 1e-10 - the value people actually use in Adam-like code - will likely wreck the conditioning of Sk1/2. Is the Adam analogy with ε = 1e-8 valid here? 6.The noise injected by line 10 of Algorithm 2 is never discussed. That line accumulates out(ĝk+1 - gk) from two independent samples. The second moment of the difference carries a 2 σ2 noise term, so Sk ends up driven largely by noise, which weakens exactly the adaptivity the method preserves. The theory absorbs this into σ, but the practical consequence - the reason UniXGrad is often considered fragile - is left out.

Questions for authors

1.Can you add numerical experiments, even on a synthetic matrix problem, against Leon, USGD and a Muon-style method? 2.At which step of Jiang et al.'s proof does δ have to be coupled to the gradient bound? 3.What δ do you recommend in practice, is it stable in bf16, and how far is it from the pseudoinverse (δ = 0) version? 4.What is the explicit update of Algorithm 2 in the matrix case, and how does it differ line by line from Algorithm 1? 5.How does the noise inflation from accumulating gradient differences affect adaptivity, and is there a correction for it?

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

The paper presents a regret analysis of Leon, a projection-free adaptive method based on a smoothed dual potential. The bound requires no bounded-gradient assumption and permits any initialization δ>0\delta>0, with a pseudoinverse extension to δ=0\delta=0. An existing O2NC reduction yields stochastic nonconvex stationarity guarantees under second-moment assumptions.

Combining the Leon potential with Nesterov acceleration and squared gradient-difference accumulation yields a feasible method attaining universal rates for convex Hölder-smooth optimization under structured smoothness and noise assumptions. The analysis covers scalar, diagonal, and matrix preconditioning. No experiments or detailed implementation-cost comparisons are provided.

Critical strengths
  1. The regret analysis removes Leon’s bounded-gradient requirement. Jiang et al. (2026, Theorem 3.2) assume a uniform gradient bound GG and initialize the preconditioner with G2IG^2I. The present analysis permits independent initialization and, via a pseudoinverse extension, δ=0\delta=0. This extends the guarantee to stochastic settings with bounded second moments but unbounded gradient realizations.

  2. The accelerated method preserves feasibility without projection. It adapts to unknown Hölder smoothness and stochastic noise, attaining an O(T−2)O(T^{-2}) bound in the smooth deterministic case. The guarantee requires neither a bounded-trajectory assumption nor per-iteration weighted projections, and covers scalar, diagonal, and matrix preconditioning.

Critical weaknesses
  1. The regret analysis is useful but incremental (lines 87–92, 260–269). Removing bounded gradients and allowing δ=0\delta=0 broaden Leon’s guarantee, but the matrix update and regret order remain unchanged. The nonconvex result uses an existing O2NC reduction. The accelerated result must therefore carry the main case for acceptance.

  2. The accelerated method’s novelty and practical benefit remain unclear (lines 79–81, 97–99). Xie et al. (2025b) already provide unprojected acceleration under bounded trajectories. Automatic feasibility removes this assumption, but the paper should compare assumptions and rates and identify the new argument for adaptive matrix acceleration. Moreover, two gradient evaluations per iteration and matrix operations may offset the iteration improvement. Without experiments or a quantitative cost comparison at matched accuracy, I am not persuaded that the overall contribution warrants acceptance.

Questions for authors
  1. Can Lemma 4 be simplified at the cost of constants? For δ>0\delta>0, set F=Ψk+1⋆F=\Psi_{k+1}^{\star}, G=Ψk⋆G=\Psi_k^{\star}, a=∇F(m)−∇G(m)a=\nabla F(m)-\nabla G(m), and Tk=tr⁡SkT_k=\operatorname{tr}\sqrt{S_k}. Monotonicity, smoothness, and convexity give

    \le F(m)-G(m)+\langle a,v\rangle +\frac{\eta}{2}\lVert v\rVert_{S_{k+1}^{-1/2}}^2.$$ Minimization and upper stability imply $$\lVert a\rVert_{S_{k+1}^{1/2}}^2 \le 2\eta\bigl(F(m)-G(m)\bigr) \le 2\eta^2(T_{k+1}-T_k).$$

This replaces 3/23/2 by 22 in Theorem 2, preserves the negative step term, and yields, for η=R\eta=R,

Reg⁡K≤δRdim⁡(X)+Rρ∗(g0)+4RTK.\operatorname{Reg}_K \le \delta R\dim(\mathcal{X}) + R\rho* ( g_0 )+ 4R T_K.

Lemma 9 and continuity of the matrix square root appear to extend this bound to δ=0\delta=0. Does the sharper constant 11 improve anything beyond numerical coefficients? This argument retains the paper’s regret decomposition, Lemma 9, and general-operator extension.

  1. What difficulty does a changing preconditioner introduce? Rodomanov et al. (2024, Section 2) already allow a fixed matrix norm. Which estimate in Lemmas 5–7 handles the changing metric, and which inequality substantiates the claim that earlier analyses underused the negative Bregman term (lines 390–393)?

  2. What precisely is new relative to Xie et al.? How do the assumptions and rates compare with their unprojected Algorithm 2 and Theorem 4.4? Does the priority claim (lines 97–99) concern acceleration with automatic feasibility and no additional bounded-trajectory assumption?

  3. Can the authors exhibit a concrete matrix problem with a stronger bound than both Euclidean and existing matrix-preconditioned methods? Please specify the structural constants, gradient-call complexity, and matrix-operation costs.


Additional Minor Comments

  1. Lines 341–343. A spectral-norm constraint alone does not imply high rank. For q≥2q\ge 2 and D>0D>0,

    min⁡∥X∥op≤D12∥X−2De1e1⊤∥F2\min_{\lVert X\rVert_{\mathrm{op}}\le D}\frac12\lVert X-2De_1e_1^\top\rVert_F^2

    has the unique rank-one optimum X∗=De1e1⊤X^{*}=De_1e_1^\top, despite strong convexity and an active constraint. Please specify conditions supporting high rank or qualify the claim as application-specific.

  2. Line 118. Please define

    Bh(u;v)=h(u)−h(v)−⟨∇h(v),u−v⟩.\mathbb{B}_h(u;v)=h(u)-h(v)-\langle\nabla h(v),u-v\rangle.

    The argument order matters in the proof. For nonsmooth hh, specify the chosen subgradient.

  3. Line 612. “Bilinearity of out” is inaccurate: out⁡(m)=m⟨m,⋅⟩\operatorname{out}(m)=m\langle m,\cdot\rangle is quadratic; (u,v)↦u⟨v,⋅⟩(u,v)\mapsto u\langle v,\cdot\rangle is bilinear. The displayed differential is correct and follows from the product rule.

  4. Line 85. Replace “Sumary” with “Summary.”

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

This paper studies the convergence behaviour of general preconditioned gradient methods, extending the results for the Leon optimizer. The authors generalize existing matrix preconditioning results to a general subspace of linear operators and obtain convergence guarantees without assuming uniformly bounded gradients, thus lifting a strict assumption from the related literature. Moreover, they propose an accelerated extension with faster rates under convexity, for weakly smooth functions, i.e. functions that are Hölder smooth (or even nonsmooth).

Critical strengths

The problem that is studied is interesting and clearly stated in the text. The contribution compared to existing works is highlighted and clear. Moreover, the authors lift a strict assumption from the related literature, making the problem setting more realistic and furthermore propose an accelerated algorithm.

Critical weaknesses

No major weaknesses. I believe the authors could include some experiments to support their claims on the practicality of the method.

Questions for authors

No major questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.