acceptodds
Under review as a conference paper at ICLR 2027

Generalization Analysis of Muon

Abstract

Muon is a matrix-aware first-order optimizer designed for matrix-structured parameters and has demonstrated strong performance in training large neural networks. Existing analyses mainly study its convergence behavior on training examples, whereas its behavior on testing examples remains less understood. In this paper, we study the convergence of Muon measured by the nuclear norm of the population gradient. We first establish a data-dependent uniform convergence guarantee for the deviation between population and empirical gradients over a ball in with rank at most . Our bound depends on instead of the ambient dimension and incorporates the empirical second-order moment of the gradients. We then establish high-probability convergence rates for Muon. Our generalization and convergence analyses together give a high-probability excess risk bound of order . We further show that the dimension dependency can be removed for linear networks and shallow neural networks. Our studies give the first high-probability generalization guarantee for Muon.

Primary area:
learning theory
Keywords:
generalization analysis, Muon, nonconvex optimization

Reviews

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

The paper studies population-gradient guarantees for exact-polar Muon. It combines a uniform nuclear-gradient bound over an operator-norm ball of bounded rank with a high-probability optimization analysis. The statistical bound uses an empirical gradient second moment, and the proposed consequences include rank-dependent population-stationarity guarantees and dimension-independent results for linear and shallow networks. The linear specialization uses the shared left factor of the sample gradients. The contribution is theoretical and is supported through appendix proofs.

Critical strengths
  1. The paper addresses a useful question about how matrix geometry and rank-dependent complexity enter population-stationarity guarantees for Muon. The combination of an empirical gradient second moment and a structured parameter class could provide informative bounds once the analysis is corrected.

  2. The structured calculations provide useful insight. In the linear model, every gradient and momentum matrix shares the fixed left factor aa, which justifies a sharper optimization analysis. The trajectory-radius estimate and the shallow-network smoothness calculation are also valid ingredients.

Critical weaknesses
  1. The central statistical bound needs correction. Appendix A.3, lines 1036–1038, absorbs the covering error using L∗R≤G∗L_*R\le G_*, which is absent from the assumptions. Smooth scalar gradients with bounded amplitude can vary arbitrarily rapidly, giving a counterexample to Theorem 1's dependence. The combined bound also uses nuclear variance where Assumption 1 supplies Frobenius variance: X=±Iq/qX=\pm I_q/\sqrt q has second moments qq and 1 in these norms. Following the submitted proof introduces a q\sqrt q factor into Theorem 6's statistical noise term.

  2. Several downstream proof steps require revision. Lemma 22 applies a maximum inequality across terminal times whose EMA weights differ; independent Rademacher noise contradicts its horizon-free simultaneous bound. Corollary 5's deterministic rate suppresses 1/(1−β)1/(1-\beta) despite universal-constant notation. For the structured cases, equation (C.26) retains a Bℓ/nB_\ell/\sqrt n term that disappears from Theorem 7, and equations (C.73)/(C.75) apply an empirical L2 entropy result to L-infinity covering numbers. These issues affect the principal guarantees and their claimed dependencies.

Questions for authors
  1. Please give a corrected Theorem 1, including the necessary smoothness/envelope dependence, and state its consequences for Corollary 3 and Theorem 6.

  2. What final rates follow after repairing Lemma 22's time dependence, the variance conversion, and the deterministic momentum dependence? Please make the dimension, horizon, and momentum factors explicit.

  3. What are the corrected linear-network bounds after retaining the baseline derivative-noise term, and which entropy estimate supports Theorem 11? A verified set of corrected results retaining a meaningful contribution could raise my rating from weak rejection to weak acceptance.

1 comment

Thanks for pointing out these issues.

Q1: Rates after repairing Lemma 22, variance conversion, and deterministic momentum dependence.

A1: In the revised proof of Lemma 22, we first fix tt. For Mt−Ct=βtZ0+(1−β)∑τ=1tβt−τZτM_t-C_t=\beta^t Z_0+(1-\beta)\sum_{\tau=1}^t\beta^{t-\tau}Z_\tau, we apply the Hilbert-space martingale inequality to this fixed-tt sequence. We then use failure probability δ/T\delta/T and take a union bound over tt. Then, with probability at least 1−δ1-\delta, simultaneously for all tt, ∣Mt−Ct∣F≤σ(βt+ωt)B2log⁡(2T/δ)+2GF(βt+bt)3Blog⁡(2T/δ),\\|M_t-C_t\\|_F \leq \frac{\sigma(\beta^t+\omega_t)}{\sqrt{B}} \sqrt{2\log(2T/\delta)} + \frac{2G_F(\beta^t+b_t)}{3B} \log(2T/\delta),

where ωt2=1−β1+β(1−β2t)\omega_t^2=\frac{1-\beta}{1+\beta}(1-\beta^{2t}), bt=(1−β)1{t≥1}b_t=(1-\beta)\mathbf{1}_{\{t\geq1\}}. Thus, the horizon penalty log⁡(2T/δ)\log(2T/\delta) is now explicit.

We also bound GF=sup⁡W,z∥∇f(W;z)−∇FS(W)∥F≤2(L∗RT+b∗)G_F=\sup_{W,z}\Vert \nabla f(W;z)-\nabla F_S(W)\Vert_F\leq2(L_{\ast}R_T+b_{\ast}), so the corrected Theorem 4 contains

  • stochastic noise qσlog⁡(2T/δ)/B\sqrt{q}\sigma\sqrt{\log(2T/\delta)/B}
  • bounded-increment term$\sqrt{q}(L_{\ast}R_T+b_{\ast})\log(2T/\delta)/B$
  • explicit EMA boundary terms 1/[T(1−β)]1/[T(1-\beta)], (1−β)/(1+β)\sqrt{(1-\beta)/(1+\beta)}, and 1−β1-\beta

Corollary 5 retains complexity O(qL∗ΔSΓδ2ϵ−4)O(qL_{\ast}\Delta_S\Gamma_{\delta}^2\epsilon^{-4}) with the revised Γδ=σBlog⁡(2T/δ)+L∗∥W0∥σ+b∗Blog⁡(2T/δ)\Gamma_{\delta} =\frac{\sigma}{\sqrt{B}}\sqrt{\log(2T/\delta)}+\frac{L_{\ast}\Vert W_0\Vert_{\sigma}+b_{\ast}}{B}\log(2T/\delta).

In the revised Theorem 6, we do not use the bounded-variance assumption to control the empirical second moment L∗,S(W)=n−1∑i=1n∥∇f(W;zi)∥∗2\mathcal{L}_{{\ast},S}(W)=n^{-1}\sum_{i=1}^n \Vert\nabla f(W;z_i)\Vert_{\ast}^2. Instead, we show in Lemma 25 that the nonnegativity and spectral-norm smoothness imply the self-bounding property ∥∇f(W;zi)∥∗2≤2L∗f(W;z)\Vert\nabla f(W;z_i)\Vert_{\ast}^2 \leq 2L_{\ast}f(W;z). Then, L∗,S(Wt)≤2L∗FS(Wt)\mathcal{L}_{{\ast},S}(W_t)\leq 2L_{\ast}F_S(W_t) and T−1∑t=0T−1L∗,S(Wt)≤2L∗T−1∑t=0T−1FS(Wt)T^{-1}\sum_{t=0}^{T-1}\sqrt{\mathcal{L}_{{\ast},S}(W_t)}\leq \sqrt{2L_{\ast}}T^{-1}\sum_{t=0}^{T-1}\sqrt{F_S(W_t)}, which can be controlled through the optimization trajectory. Specifically, in the revised Lemma 26, with probability at least 1−δ1-\delta,

\sqrt{\mathcal{L}_{\ast,S}(W_t)} \lesssim \Big(\frac{q^3L_{\ast}\Delta_S\Gamma_{\delta}^6}{T}\Big)^{1/8} +\sqrt{L_{\ast}F_S(W_0)}.$$ This preserves $\widetilde{O}(\sqrt{\widehat{r}_T(d_1+d_2)/n})$ population-stationarity order (Remark 3). **Q2**: Correction of Theorem 1, including smoothness/envelope dependence. Consequences for Corollary 3 and Theorem 6. **A2**: Corrected Theorem 1 states that, with probability at least $1-\delta$, simultaneously for all $W\in B_{R,r}$, $$\Vert\nabla F_S(W)-\nabla F(W)\Vert_{\ast} \lesssim \frac{G_{\ast}\Gamma_{n,\delta}}{n} + \sqrt{\frac{\mathcal{L}_{\ast,S}(W)\Gamma_{n,\delta}}{n}},$$ where $\Gamma_{n,\delta}=\log(1/\delta)+r(d_1+d_2)\log(e+L_{\ast}Rn/G_{\ast})+\log\log(en)$, which shows the smoothness/envelope dependence explicitly. For Muon trajectory, we revise Corollary 3 using $R_T=\Vert W_0\Vert_{\sigma}+\eta T$ and $\hat{r}_T=\max\{1,\max_{0\leq t\leq T}rank(W_t)\}$. The envelope can be bounded by $G_{\ast,\hat{r}_T} \leq L_{\ast}R_T+b_{\ast}$, and a union bound over possible radii and ranks makes the corollary valid for the data-dependent $R_T$ and $\widehat r_T$. The resulting statement becomes: with probability at least $1-\delta$, simultaneously for all $t$, $$\Vert \nabla F_S(W_t)-\nabla F(W_t)\Vert_* \lesssim \frac{(L_{\ast}R_T+b_{\ast})\Gamma_{n,\delta}^{\hat{r}_T}}{n}+ \sqrt{\frac{\mathcal{L}_{\ast,S}(W_t)\Gamma_{n,\delta}^{\hat{r}_T}}{n}},$$ where \$\Gamma\_{n,\delta}^{\hat{r}\_T}=\log \frac{16\hat{r}\_T(\hat{r}\_T+1)(1+|\lceil\log\_2(L\_{\ast}R\_T/b\_{\ast})\rceil|)^2}{\delta}+ \hat{r}\_T(d_1+d_2)\log(e+n)+\log\log(en)\$. In the revised Theorem 6, $\hat{r}_T(d_1+d_2)$ remains the leading dimension-rank complexity through $\Gamma_{n,\delta}^{\widehat r_T}$, and population-stationarity remains $\widetilde{O}(\sqrt{\widehat r_T(d_1+d_2)/n})$. **Q3**: Correction to linear-network bounds after retaining the baseline derivative-noise term. **A3**: Define $B_\ell=(E_Y[\ell'(Y,0)^2])^{1/2}$, and $\nu(W)=V(W)\vee n^{-1}$. The corrected Theorem 7 additionally includes $\Vert a \Vert_2B_x(B_\ell+L_\ell\sqrt{\nu(W)})\sqrt{\frac{\log(1/\delta)}{n}}$, which includes the baseline derivative-noise term $B_\ell/\sqrt n$ in Corollary 8 and Theorem 10. The result remains dimension-independent. Under the eigenvalue decay $\lambda_j\lesssim j^{-p}$, the population-stationarity bound still approaches $\widetilde{\mathcal{O}}(n^{-1/2})$ as $p\to\infty$. **Q4**: Entropy estimate supporting the corrected Theorem 11. **A4**: Revised Lemma 44 ([2]) gives, for bounded $\mathcal H$ and $\epsilon\geq3\mathfrak R_n(\mathcal H)$, $$\log N(\epsilon,\mathcal H,d_{S,\infty}) \leq 1+\frac{64n\mathfrak R_n(\mathcal H)^2}{\epsilon^2} \log^2\Big(\frac{8eB^2n}{\epsilon^2}\Big),$$ which preserves dimension-independence (Lemma 45). [2] Low noise and fast rates. NeurIPS, 2010.
Reviewer_fMzDOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies population nuclear-norm stationarity for Muon with exact SVD updates. It proposes a uniform generalization gap, which leads to a high-probability generalization error for Muon. Then, combining it with the high-probability optimization error of Muon, the authors propose a high-probability bound for population nuclear-norm stationarity, which shows that Muon can achieve a better dependence on dimension than SGD (but I have some concerns about their analysis). It also develops dimension-independent results for linear and shallow neural-network models.

Critical strengths

The results show that Muon can achieve a better dependence on dimension in generalization performance than SGD (If their analysis is right), which provides a new perspective on why Muon is better than SGD. Also, the dimension-independent results for linear and shallow neural-network models are very interesting, showing the advantage of Muon updates.

Critical weaknesses

I find some crucial problems in the proof part, which may contradict the claims and main results in this paper (I will state these in Questions For Authors).

Questions for authors
  1. In the proof of Lemma 22, the right part of line 1145 should be GFbT3+σωTBlog⁡(2δ)\frac{G_F b_T}{3}+\frac{\sigma \omega_T}{\sqrt{B}}\log\left(\frac{2}{\delta}\right), but not for each t simultaneously.

  2. In the proof of Theorem 6, line1326 uses assumption 1, but we only have Eit∥∇f(w;zit)−∇FS(w)∥F2≤σ2\mathbb{E}_{i_t}\left\Vert\nabla f(w;z_{i_t})-\nabla F_S(w)\right\Vert_F^2\leq\sigma^2. If we transfer it by ∥∥∗2≤min⁡(d1,d2)∥∥F2\Vert \Vert_*^2\leq \min (d_1,d_2)\Vert \Vert_F^2, then σ\sigma should be min⁡(d1,d2)σ\sqrt{\min (d_1,d_2)} \sigma in Theorem 6, which leads to the same order dependence on dimension as SGD.

  3. On page 42, (C.73) uses the Sudakov minoration inequality (Lemma 26). However, in (C.73) we consider the $ l_\infty$ metric, whereas in Lemma 26, the result depends on the l2l_2 metric. The transformation between these two metrics may introduce some dimension constant, which may totally ruin the results.

  4. How to derive L∗R≤G∗L_* R \leq G_* in Page20 line 1036?

  5. I have some concerns about Assumption 3, for example, MSE loss does not have this property. It would be helpful for you to provide more discussion on this assumption.

  6. I think there is a need to clarify excess risk and population stationarity. For example, in Theorem 6, you analyze the stationarity but not the excess risk. Given the nonconvex setting, it is almost impossible to analyze the gap in function value, and we should clarify this.

1 comment

Thanks for pointing out these issues.

Q1: The bound in Lemma 22 does not hold for all tt simultaneously.

A1: In the revised proof of Lemma 22, we first fix tt. For Mt−Ct=βtZ0+(1−β)∑τ=1tβt−τZτM_t-C_t=\beta^t Z_0+(1-\beta)\sum_{\tau=1}^t\beta^{t-\tau}Z_\tau, we apply the Hilbert-space martingale inequality to this fixed-tt sequence. We then use failure probability δ/T\delta/T and take a union bound over tt. Then, with probability at least 1−δ1-\delta, simultaneously for all tt, ∣Mt−Ct∣F≤σ(βt+ωt)B2log⁡(2T/δ)+2GF(βt+bt)3Blog⁡(2T/δ),\\|M_t-C_t\\|_F \leq \frac{\sigma(\beta^t+\omega_t)}{\sqrt{B}} \sqrt{2\log(2T/\delta)} + \frac{2G_F(\beta^t+b_t)}{3B} \log(2T/\delta),

where ωt2=1−β1+β(1−β2t)\omega_t^2=\frac{1-\beta}{1+\beta}(1-\beta^{2t}), bt=(1−β)1{t≥1}b_t=(1-\beta)\mathbf{1}_{\{t\geq1\}}. Thus, the horizon penalty log⁡(2T/δ)\log(2T/\delta) is now explicit. We also propagate this dependence to Theorem 4 and all of its corollaries.

Q2: Assumption 1 controls Frobenius variance, converting to nuclear norm introduces the factor min⁡(d1,d2)\sqrt{\min(d_1,d_2)}.

A2: Thanks for pointing this out. In the revision, we do not use the bounded-variance assumption to control the empirical second moment L∗,S(W)=n−1∑i=1n∥∇f(W;zi)∥∗2\mathcal{L}_{{\ast},S}(W)=n^{-1}\sum_{i=1}^n \Vert\nabla f(W;z_i)\Vert_{\ast}^2. Instead, in Lemma 25, we show that the nonnegativity and spectral-norm smoothness imply the self-bounding property ∥∇f(W;zi)∥∗2≤2L∗f(W;z)\Vert\nabla f(W;z_i)\Vert_{\ast}^2 \leq 2L_{\ast}f(W;z). Then, L∗,S(Wt)≤2L∗FS(Wt)\mathcal{L}_{{\ast},S}(W_t)\leq 2L_{\ast}F_S(W_t) and T−1∑t=0T−1L∗,S(Wt)≤2L∗T−1∑t=0T−1FS(Wt)T^{-1}\sum_{t=0}^{T-1}\sqrt{\mathcal{L}_{{\ast},S}(W_t)}\leq \sqrt{2L_{\ast}}T^{-1}\sum_{t=0}^{T-1}\sqrt{F_S(W_t)}, which can be controlled through the optimization trajectory. Specifically, in the revised Lemma 26, with probability at least 1−δ1-\delta,

\sqrt{\mathcal{L}_{\ast,S}(W_t)} \lesssim \Big(\frac{q^3L_{\ast}\Delta_S\Gamma_{\delta}^6}{T}\Big)^{1/8} +\sqrt{L_{\ast}F_S(W_0)}.$$ Thus we avoid converting a Frobenius variance bound into a nuclear-norm one (factor $\sqrt{q}$). Theorem 6 retains the same leading-order bound $\widetilde{O}(\sqrt{\hat{r}_T(d_1+d_2)/n})$, detailed in Remark 3. **Q3**: Eq.(C.73) invokes Sudakov minoration for an $\ell_\infty$ metric although the stated lemma depends on an $\ell_2$ metric. **A3**: Thanks for pointing this out. We revise Eq.(C.73) by using the following direct empirical-$\ell_\infty$ covering-number result (revised Lemma 44, see in [2]): for a uniformly bounded real-valued class $\mathcal H$, and $\epsilon\geq3\mathfrak R_n(\mathcal H)$, $$\log N(\epsilon,\mathcal H,d_{S,\infty}) \leq 1+\frac{64n\mathfrak R_n(\mathcal H)^2}{\epsilon^2} \log^2\Big(\frac{8eB^2n}{\epsilon^2}\Big).$$ We require no conversion from an empirical $\ell_2$ cover to an $\ell_\infty$ cover. This correction preserves the same dimension-independent leading-order dependence, up to logarithmic factors and universal constants, as detailed in the revised Lemma 45. [2] Low noise and fast rates. NeurIPS, 2010. **Q4**: How is $L_* R \leq G_*$ derived? **A4**: We modify the covering radius from $\epsilon=R/n$ to $\epsilon=G_{\ast}/(L_{\ast}n)$ in the proof of Theorem 1. With this choice, the inequality $L_{\ast}R \leq G_{\ast}$ is no longer needed. **Q5**: MSE does not satisfy Assumption 3. **A5**:For $\ell_{\mathrm{mse}}(y,t)=\frac12(t-y)^2$, we have $\ell_{\mathrm{mse}}'(y,t)=t-y$ and $\ell_{\mathrm{mse}}''(y,t)=1$, so the condition $|\ell''(y,t)|\leq\gamma|\ell'(y,t)|$ fails as the residual approaches zero. To address this issue, we have added a separate analysis for MSE in the revision (Section C.3 for details). Under the additional bounded-label assumption $|Y|\leq B_y$, we use the exact identity $|\ell_{\mathrm{mse}}'(y,t)-\ell_{\mathrm{mse}}'(y,t')|=|t-t'|$ and prove a residual-moment localization lemma. Let $\mathscr{L}_{\mathrm{mse},S}(W)=n^{-1}\sum_{i=1}^n(s_W(x_i)-y_i)^2=2F_S(W)$, $G_{mse}=B_y+L_{\sigma} R \Vert a\Vert_2 B_x$, and $A_{mse}=1+L_{\sigma}\Vert a\Vert_2 B_x+\Vert a\Vert_2B_x (L_{\sigma}+L_{\sigma'}R \sqrt{r} B_x)$. We show that, with probability at least $1-\delta$, uniformly over all $W\in B_{R,r}$, $$\Vert \nabla F_S(W)-\nabla F(W)\Vert_* =\widetilde{O}\Big(\frac{A_{mse}}{\sqrt{n}}\Big[\sqrt{\mathscr{L}_{mse,S}(W)}+\frac{L_{\sigma} R\sqrt{r} \Vert a\Vert_2 B_x+G_{mse}\log(4/\delta)}{\sqrt n}\Big] \Big[\sqrt{\mathscr{L}_{mse,S}(W)}+\frac{L_{\sigma} R\sqrt r \Vert a\Vert_2 B_x+G_{mse}\log(4/\delta)}{\sqrt n} \Big]$$ $$+\frac{L_{\sigma}^2 R \sqrt{r} \Vert a\Vert_2^2 B_x^2+G_{mse}L_\sigma\Vert a\Vert_2 B_x}{\sqrt n}\Big).$$ This result remains dimension-independent and retains the localized leading term $\widetilde{\mathcal O}(\sqrt{F_S(W)/n})$, with an additional nonlocalized term $L_\sigma^2R\sqrt{r}\\|a\\|_2^2B_x^2/\sqrt{n}$. **Q6**: The paper analyzes stationarity rather than excess risk in nonconvex setting. **A6**: We agree that “excess risk” typically refers to $F(W)-\inf_W F(W)$. We establish a population-stationarity guarantee in the nuclear norm, and have changed the terminology in the revision.
Reviewer_jda6OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper claims to provide high-probability guarantees for the convergence of the nuclear norm of the gradient of Muon iterates. This is concretely stated as several results: (1) convergence of the generalization gap, i.e. the difference between the population and sample gradients (Theorem 1); (2) convergence of the optimization procedure (Theorem 4); (3) combining the previous two results (Theorem 6); and (4) dimension-independent results for linear networks and shallow neural networks (Theorem 10 and Corollary 12). The primary novelty of the contributions over existing work is that these are high-probability guarantees and that they have improved dimension dependence in the low-rank regime.

Critical strengths

To my knowledge, if assumed to be correct, this paper's contributions would indeed present the first high-probability convergence results for Muon.

Critical weaknesses

There appear to major issues with many of the results. In particular,

  • The proof of Theorem 1 uses L∗R≤G∗L_* R\leq G_* in Line 1036, which is unjustified and different from the bound given in (A.3).
  • Theorem 1 is false as stated, as seen by the following counterexample in R\mathbb{R}. Let R=1R=1, and consider the uniform distribution on [2n][2n]. For every subset AA of [2n][2n], choose a distinct value wA∈(0,1)w_A\in(0,1). Construct f(w;z)f(w;z) satisfying f′(wA;z)=1f'(w_A;z)=1 if z∈Az\in A and f′(wA;z)=−1f'(w_A;z)=-1 otherwise, which is possible by using sums of smooth bump functions to obtain f′(⋅;z)f'(\cdot;z) and then integrating and adding constants to make f(⋅;z)f(\cdot;z) smooth nonnegative losses. Now for any sample SS of nn elements of [2n][2n], let AA be its set of distinct elements, so that ∣A∣≤n|A|\leq n. We can verify G∗=1G_*=1 and L∗,S(wA)=1\mathcal{L}_{*,S}(w_A)=1. Moreover, ∇FS(wA)=1\nabla F_S(w_A)=1 and ∇F(wA)=∣A∣n⋅1−1≤0\nabla F(w_A)=\frac{|A|}{n}\cdot1-1\leq 0, so the left-hand side of Line 237 is at least 11. However, the right-hand side is O(log⁡n/n)O(\sqrt{\log n/n}) and therefore vanishes as n→∞n\to\infty.
  • The proof of Theorem 4 uses an invalid application of Lemma 21 to prove Lemma 22. To apply Lemma 21, tt needs to be fixed with a maximization over jj, but Line 1145 takes a maximum over tt. Essentially, the stated bound is satisfied with probability at least 1−δ1-\delta for any fixed tt, but Lemma 22 states the stronger conclusion that this bound is satisfied for all tt simultaneously with probability at least 1−δ1-\delta. A naive union bound would introduce a factor of TT for this approach.
  • The proof of Theorem 6 uses E[∥∇f(W;zit)−∇FS(W)∥∗2]≤σ2\mathbb{E}[\lVert\nabla f(\mathbf{W};z_{i_t})-\nabla F_S(\mathbf{W})\rVert_*^2]\leq\sigma^2 in Line 1326, but only E[∥∇f(W;zit)−∇FS(W)∥F2]≤σ2\mathbb{E}[\lVert\nabla f(\mathbf{W};z_{i_t})-\nabla F_S(\mathbf{W})\rVert_\text{F}^2]\leq\sigma^2 is guaranteed by Assumption 1. In general, we can only say E[∥∇f(W;zit)−∇FS(W)∥∗2]≤qσ2\mathbb{E}[\lVert\nabla f(\mathbf{W};z_{i_t})-\nabla F_S(\mathbf{W})\rVert_*^2]\leq q\sigma^2, which introduces a factor of q\sqrt{q} to the stated bounds. This is a critical error that significantly undermines the claimed improvement on the dimension dependence, one of the paper's main contributions.

At this point, I considered the errors to be significant enough to warrant rejection. I encourage the authors to resubmit a major revision after carefully checking and revising all of the proofs, for there may be errors beyond the ones listed above.

Questions for authors
  1. "Excess risk" typically refers to the quantity F(W)−inf⁡FF(\mathbf{W})-\inf F. Why do the authors use this term for ∥∇F(W)∥∗\lVert\nabla F(\mathbf{W})\rVert_*?
  2. Which of the flaws identified above are repairable? How do potential fixes affect the main results?
2 comments

We thank the reviewer for pointing out these issues.

Q1: Unjustified inequality L∗R≤G∗L_* R \leq G_* in Theorem 1.

A1: We modify the covering radius from ϵ=R/n\epsilon=R/n to ϵ=G∗/(L∗n)\epsilon=G_{\ast}/(L_{\ast}n) in the proof of Theorem 1. With this choice, the inequality L∗R≤G∗L_{\ast}R \leq G_{\ast} is no longer needed.

Q2: Counterexample

A2: We thank the reviewer for this example. However, the proposed construction does not contradict our theorem. The main reason is that Assumption 2 requires a constant parameter L∗>0L_*>0, whereas the smoothness parameter for this construction grows exponentially with nn:

Specifically, the construction assigns a distinct wA∈(0,1)w_A\in(0,1) to every A⊆[2n]A\subseteq[2n], giving N=22nN=2^{2n} distinct points. Order these points as wA1<⋯<wANw_{A_1}<\cdots<w_{A_N}. For any Aj≠Aj+1A_j\neq A_{j+1}, there exists z∈Aj△Aj+1z\in A_j\triangle A_{j+1}, where △\triangle denotes the symmetric difference of two sets, such that ∣f′(wAj;z)−f′(wAj+1;z)∣=2|f'(w_{A_j};z)-f'(w_{A_{j+1}};z)|=2. Therefore, the smoothness parameter L∗L_* must satisfy 2≤L∗∣wAj−wAj+1∣2\leq L_*|w_{A_j}-w_{A_{j+1}}|. Summing over jj and noting that ∑j∣wAj−wAj+1∣<1\sum_{j}|w_{A_j}-w_{A_{j+1}}|<1, we obtain L∗>2(N−1)=2(22n−1)L_*>2(N-1)=2(2^{2n}-1), which is not a constant. Thus, this construction does not satisfy the conditions of Theorem 1.

Smoothness dependence is standard in uniform-convergence analyses of empirical gradients; e.g., [1] gives a high-probability bound of order O(τCplog⁡n/n)O(\tau\sqrt{Cp\log n/n}), where pp is the dimension of the parameter and CC depends on regularity. We revise Γn,δ=log⁡(1/δ)+r(d1+d2)\Gamma_{n,\delta}=\log(1/\delta)+r(d_1+d_2) log⁡(e+L∗Rn/G∗)+log⁡log⁡(en)\log(e+L_{\ast}Rn/G_{\ast})+\log\log(en) to make this explicit.

[1] The Landscape of Empirical Risk for Nonconvex Losses. Annals of Statistics, 2018.

Q3: Lemma 22 applies a maximal inequality incorrectly without paying for the factor TT.

A3: In the revised proof of Lemma 22, we first fix tt. For Mt−Ct=βtZ0+(1−β)∑τ=1tβt−τZτM_t-C_t=\beta^t Z_0+(1-\beta)\sum_{\tau=1}^t\beta^{t-\tau}Z_\tau, we apply the Hilbert-space martingale inequality to this fixed-tt sequence. We then set failure probability to δ/T\delta/T and take a union bound over tt. Then, with probability at least 1−δ1-\delta, simultaneously for all tt, ∣Mt−Ct∣F≤σ(βt+ωt)B2log⁡(2T/δ)+2GF(βt+bt)3Blog⁡(2T/δ),\\|M_t-C_t\\|_F \leq \frac{\sigma(\beta^t+\omega_t)}{\sqrt{B}} \sqrt{2\log(2T/\delta)} + \frac{2G_F(\beta^t+b_t)}{3B} \log(2T/\delta),

where ωt2=1−β1+β(1−β2t)\omega_t^2=\frac{1-\beta}{1+\beta}(1-\beta^{2t}), bt=(1−β)1{t≥1}b_t=(1-\beta)\mathbf{1}_{\{t\geq1\}}. Thus, the horizon penalty log⁡(2T/δ)\log(2T/\delta) is now explicit. We have propagated this dependence to Theorem 4 and all of its corollaries.

Q4: Theorem 6 uses a nuclear-norm variance bound while Assumption 1 controls the Frobenius norm.

A4: We thank the reviewer for pointing out the mistake. In the revision, we do not use the bounded-variance assumption to control the empirical second moment L∗,S(W)=n−1∑i=1n∥∇f(W;zi)∥∗2\mathcal{L}_{{\ast},S}(W)=n^{-1}\sum_{i=1}^n \Vert\nabla f(W;z_i)\Vert_{\ast}^2. Instead, in Lemma 25, we show that the nonnegativity and spectral-norm smoothness imply the self-bounding property ∥∇f(W;zi)∥∗2≤2L∗f(W;z)\Vert\nabla f(W;z_i)\Vert_{\ast}^2 \leq 2L_{\ast}f(W;z). Then, L∗,S(Wt)≤2L∗FS(Wt)\mathcal{L}_{{\ast},S}(W_t)\leq 2L_{\ast}F_S(W_t) and T−1∑t=0T−1L∗,S(Wt)≤2L∗T−1∑t=0T−1FS(Wt)T^{-1}\sum_{t=0}^{T-1}\sqrt{\mathcal{L}_{{\ast},S}(W_t)}\leq \sqrt{2L_{\ast}}T^{-1}\sum_{t=0}^{T-1}\sqrt{F_S(W_t)}, which can be controlled through the optimization trajectory. Specifically, in the revised Lemma 26, with probability at least 1−δ1-\delta,

\sqrt{\mathcal{L}_{\ast,S}(W_t)} \lesssim \Big(\frac{q^3L_{\ast}\Delta_S\Gamma_{\delta}^6}{T}\Big)^{1/8} +\sqrt{L_{\ast}F_S(W_0)}.$$ Thus we avoid converting a Frobenius variance bound into a nuclear-norm one (factor $\sqrt{q}$). Theorem 6 retains the same leading-order bound $\widetilde{O}(\sqrt{\hat{r}_T(d_1+d_2)/n})$ (Remark 3). **Q5**: Why call $\\|\nabla F(W)\\|_*$ excess risk? **A5.** We agree that “excess risk” typically refers to $F(W)-\inf_W F(W)$, and we establish a population-stationarity guarantee in the nuclear norm. We have changed the terminology in the revision. **Q6**: Which flaws are repairable? Effect on the main results. **A6**: We have repaired all the flaws above. Theorem 1 now contains the smoothness/envelope factor $\log(e+L_{\ast}Rn/G_{\ast})$, while Lemma 22 and Theorem 4 contain the horizon factor $\log(2T/\delta)$. As detailed in Remark 3, the main population-stationarity result retains the same leading order $\widetilde{O}(\sqrt{\hat{r}_T(d_1+d_2)/n})$. We also consistently use the term “population stationarity” instead of “excess risk.”

I thank the authors for their detailed response.

As all the reviewers have pointed out, there are significant mathematical flaws in the submitted manuscript, and I believe that the scope of the revision is substantial to the point of warranting another round of review. If this were a journal submission, I would have been happy to review a revision, but here I must unfortunately maintain my rating and recommend resubmitting to another venue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.