- 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
-
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.
-
The structured calculations provide useful insight. In the linear model, every gradient and momentum matrix shares the fixed left factor , which justifies a sharper optimization analysis. The trajectory-radius estimate and the shallow-network smoothness calculation are also valid ingredients.
Critical weaknesses
-
The central statistical bound needs correction. Appendix A.3, lines 1036–1038, absorbs the covering error using , 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: has second moments and 1 in these norms. Following the submitted proof introduces a factor into Theorem 6's statistical noise term.
-
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 despite universal-constant notation. For the structured cases, equation (C.26) retains a 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
-
Please give a corrected Theorem 1, including the necessary smoothness/envelope dependence, and state its consequences for Corollary 3 and Theorem 6.
-
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.
-
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.
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 t. For Mt−Ct=βtZ0+(1−β)∑τ=1tβt−τZτ, we apply the Hilbert-space martingale inequality to this fixed-t sequence. We then use failure probability δ/T and take a union bound over t. Then, with probability at least 1−δ, simultaneously for all t, ∣Mt−Ct∣F≤Bσ(βt+ωt)2log(2T/δ)+3B2GF(βt+bt)log(2T/δ),
where ωt2=1+β1−β(1−β2t), bt=(1−β)1{t≥1}. Thus, the horizon penalty log(2T/δ) is now explicit.
We also bound GF=supW,z∥∇f(W;z)−∇FS(W)∥F≤2(L∗RT+b∗), so the corrected Theorem 4 contains
Corollary 5 retains complexity O(qL∗ΔSΓδ2ϵ−4) with the revised Γδ=Bσlog(2T/δ)+BL∗∥W0∥σ+b∗log(2T/δ).
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. 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). Then, L∗,S(Wt)≤2L∗FS(Wt) and T−1∑t=0T−1L∗,S(Wt)≤2L∗T−1∑t=0T−1FS(Wt), which can be controlled through the optimization trajectory. Specifically, in the revised Lemma 26, with probability at least 1−δ,
\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.