acceptodds
Withdrawn from ICLR 2027

BiMuon: A Geometry-Aware Stochastic Bilevel Optimization Approach

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Stochastic bilevel optimization provides a general framework for many machine learning applications, such as hyperparameter learning, data reweighting, language model alignment, and actor-critic reinforcement learning. However, most existing bilevel optimization methods treat matrix-valued gradients as flattened vectors and perform optimization in the resulting vectorized space, ignoring the matrix structures common in modern neural networks. Moreover, the lower-level (LL) problem curvature can induce significant spectral imbalance in the upper-level (UL) geometry. Such limitations of existing bilevel optimization methods motivate us to develop BiMuon, a geometry-aware stochastic bilevel optimization method that integrates implicit hypergradient estimation in bilevel optimization with Muon-style orthogonalized updates at the UL. To our knowledge, BiMuon is the first stochastic BLO method with Muon-style orthogonalized matrix updates and an iteration-complexity guarantee, matching the best-known rates achieved by Muon-type methods based on matrix parameterizations.To improve computational and parallel efficiency for models with multiple matrix parameters, we further study BiMuon for blockwide diagonal matrix approximation and derive a relative stepsize allocation rule based on UL progress and blockwise LL sensitivity. We evaluate BiMuon on representation learning and blockwise bilevel optimization, providing empirical support for our methods.

Primary area:
optimization
Keywords:
Bilevel Optimization, Stochastic Optimization

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_YLFGOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes BiMuon for stochastic bilevel optimization with a matrix-valued upper-level variable and a strongly convex lower level. The lower level is tracked by warm-started SGD, the hypergradient is estimated with a truncated Neumann series as in stocBiO, and the upper-level EMA momentum is replaced by its polar factor (exact or Newton–Schulz) before the update, as in Muon. A quadratic example motivates the design: lower-level ill-conditioning is squared in the upper-level Hessian and makes the hypergradient spectrum unbalanced. The paper proves E∣∇Φ(XR)∣\*=O(T−1/4)\mathbb{E}\\|\nabla\Phi(X_R)\\|_\*=O(T^{-1/4}) for both variants, proposes a blockwise variant whose relative stepsizes balance upper-level progress against lower-level sensitivity, and reports experiments on CIFAR-10/100 with frozen features.

Critical strengths
  1. Clear presentation and motivation. The paper is clearly written and easy to read. In particular, the quadratic example in Sec. 3.2 shows in a simple, checkable way how lower-level curvature is squared in the upper-level geometry.
  2. Extending Muon to bilevel optimization. The paper extends Muon from standard single-level matrix optimization to the bilevel setting. The idea is clear, and the theory is solid, covering both the exact-polar and the Newton–Schulz variants.
  3. Experiments are described in detail. The paper gives the seeds, the counts of gradient and Hessian–vector product evaluations, stepsize grids and evaluation procedure, which makes the results easy to reproduce.
Critical weaknesses

W1. Limited novelty. The whole method is described in Sec. 4.2 and consists of three parts:

  • the warm-started SGD tracking of the lower-level solution, Eq. (3);
  • the truncated Neumann-series hypergradient estimator, Eq. (4);
  • the Muon update Xk+1=Xk−βOkX_{k+1}=X_k-\beta O_k, where OkO_k is the polar factor of the EMA momentum (5) or its Newton–Schulz approximation.

The first two are standard in stochastic bilevel optimization (Ghadimi & Wang, 2018; Hong et al., 2023; Ji et al., 2021), and the third is the standard Muon update (Jordan et al., 2024). It appears that BiMuon is a direct combination of these existing components. Against this background, the claim in Sec. 1 that "developing singular-spectrum-regularized approaches for BLO is highly non-trivial due to several technical challenges unseen in single-level settings" is overstated: each challenge listed there (lower-level tracking, hypergradient bias, NS approximation error) is handled by an existing argument.

W2. The theory does not show that orthogonalization helps.

  • The analysis assumes smoothness in the Frobenius norm. Under this assumption, a Muon step of size β\beta has Frobenius length βrank(Mk)\beta\sqrt{\mathrm{rank}(M_k)}, so the bound pays a factor of up to r=min⁡(m,n)r=\min(m,n) (see CpolC_{\rm pol} in (29)). Running the same proof for the FrobNorm baseline, i.e., momentum divided by its Frobenius norm, gives a bound of the same order. Theorem 1 therefore shows no advantage of the polar update over a flattened normalized update. Shen et al. (2025), cited in the paper, make the same observation for single-level Muon.

W3. The experiments are small.

  • The experiments are presented as real-data tasks on CIFAR-10 and CIFAR-100, but the pretrained backbone (ResNet-18/50) is frozen, and only a small model on top of the frozen features is trained: a 256×512256\times512 representation layer and a linear classifier on CIFAR-10, and only a linear classifier on CIFAR-100. The CIFAR-10 task also uses only 1,000 training and 500 validation samples and 60 upper-level iterations.
  • There is no comparison with Adam as the upper-level optimizer, and no experiment on a larger model such as a transformer.
  • The CIFAR-100 experiment is artificial: the differences between blocks are created by multiplying each block by a hand-chosen constant, and the proposed rule uses the exact values of these constants. It is therefore unclear whether the rule helps on a real network, where the block sensitivities are unknown.

Minor.

  • Typos: "blockwide diagonal" (abstract), "execerbated", "signifcant", "converge rate".
  • ρ\rho denotes both the Hessian-Lipschitz constant and the sensitivity ratio.

Summary. Extending Muon to bilevel problems is a reasonable idea. However, the method appears to be a direct combination of existing components, the theory does not show an advantage over flattened normalized momentum, and the experiments are small.

References

  • Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv:1802.02246, 2018.

  • Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147–180, 2023.

  • Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proceedings of the 38th International Conference on Machine Learning (ICML), PMLR 139:4882–4892, 2021.

  • Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks. Technical blog, 2024. https://kellerjordan.github.io/posts/muon/

  • Wei Shen, Ruichuan Huang, Minhui Huang, Cong Shen, and Jiawei Zhang. On the convergence analysis of Muon. arXiv:2505.23737, 2025.

Questions for authors
  1. Beyond plugging the stocBiO bias and tracking bounds into the descent argument for Muon, which step of the analysis is specific to combining Muon with bilevel optimization?
  2. If ∇Φ\nabla\Phi is assumed to satisfy ∣∇Φ(X)−∇Φ(Y)∣\*≤L∣X−Y∣op\\|\nabla\Phi(X)-\nabla\Phi(Y)\\|_\*\le L\\|X-Y\\|_{\rm op}, as in Kim & Oh (2026), can the dependence on rr be reduced, so that the bound shows an advantage of BiMuon over flattened normalized momentum?
  3. How would one estimate LXY,bL_{XY,b} for a real network? Is there a convergence guarantee for the blockwise variant?
  4. Two sentences in Sec. 6 are confusing: "The LL sensitivity alone, however, should not determine the relative stepsize, since a sensitive block may also provide a strong UL signal" and "Thus, blocks with stronger predicted UL progress receive larger relative stepsizes, whereas blocks with greater influence on the LL target are more strongly regulated". What do "strong UL signal" and "more strongly regulated" mean? Why should a sensitive block with a large ab,ka_{b,k} receive a larger step?
  5. The spectral imbalance in Sec. 3.2 comes from lower-level curvature. Why apply orthogonalized updates only at the upper level?

References

  • Gyu Yeol Kim and Min-hwan Oh. Convergence of Muon with Newton–Schulz. In International Conference on Learning Representations (ICLR), 2026.
7 comments

We thank Reviewer YLFG for finding the paper clearly written, the theory solid for both the exact-polar and Newton–Schulz variants, and the experiments reproducible. We address each point below; changes in the revised PDF are marked in blue.

W1: Limited novelty. The whole method is described in Sec. 4.2 and consists of three parts:

  • the warm-started SGD tracking of the lower-level solution, Eq. (3);
  • the truncated Neumann-series hypergradient estimator, Eq. (4);
  • the Muon update Xk+1=Xk−βOkX _{k+1}=X _{k}-\beta O _{k}, where OkO _{k} is the polar factor of the EMA momentum (5) or its Newton–Schulz approximation.

The first two are standard in stochastic bilevel optimization (Ghadimi & Wang, 2018; Hong et al., 2023; Ji et al., 2021), and the third is the standard Muon update (Jordan et al., 2024). It appears that BiMuon is a direct combination of these existing components. Against this background, the claim in Sec. 1 that "developing singular-spectrum-regularized approaches for BLO is highly non-trivial due to several technical challenges unseen in single-level settings" is overstated: each challenge listed there (lower-level tracking, hypergradient bias, NS approximation error) is handled by an existing argument.

Q1: Beyond plugging the stocBiO bias and tracking bounds into the descent argument for Muon, which step of the analysis is specific to combining Muon with bilevel optimization?

Response: Thank you for this comment. We agree that each component of BiMuon is standard on its own. Their combination, however, raises theoretical difficulties that arise in neither single-level Muon analyses nor flattened bilevel analyses, which is why we describe it as highly non-trivial in Sec. 1. We answer W1 and Q1 together, first summarizing our contributions and then identifying these difficulties.

1. Novelty. Our contributions go beyond combining these components, in four respects.

(1) Geometric intuition from a quadratic model. Gradients of matrix-valued parameters are often spectrally imbalanced, which is the motivation for Muon in single-level training. Sec. 3.2 shows that the bilevel structure adds a further source of imbalance through the LL curvature. In the quadratic model, HUL=μ2HLL−2⊗IH _{UL}=\mu^2H _{LL}^{-2}\otimes I. As a result, even when all error components are equal, the largest and smallest singular values of the hypergradient differ by a factor of κ(HLL)2\kappa(H _{LL})^2, and the polar factor removes this imbalance. Geometry-aware updates are therefore particularly suited to the UL of bilevel problems.

(2) The first convergence guarantee, at the best-known rate. To our knowledge, Theorem 1 is the first finite-time guarantee for stochastic bilevel optimization with Muon-style orthogonalized updates. It gives E∥∇Φ(XR)∥∗=O(T−1/4)\mathbb E\Vert \nabla\Phi(X _R)\Vert _\ast =O(T^{-1/4}), i.e., O~(ϵ−4)\widetilde O(\epsilon^{-4}) stochastic derivative evaluations. This matches single-level Muon [1] and the best-known stochastic bilevel methods without variance reduction [2, 3], with a nuclear-norm stationarity measure that is at least as strong as the Frobenius one. Attaining this rate requires the coupled UL–LL analysis in point 2 below.

(3) Guarantees for both exact-polar (SVD) and Newton–Schulz updates. Most existing convergence analyses of Muon assume the exact SVD-based polar factor, e.g., [1], and the single-level analysis of Newton–Schulz in [4] involves no moving LL target. Theorem 1 covers both versions of BiMuon in the bilevel setting: the exact polar factor, and qq-step Newton–Schulz (NS) with the bound CpolT−1/4/(1−εq)C _{pol}T^{-1/4}/(1-\varepsilon _q), which approaches the exact-polar bound rapidly as qq grows. The guarantee therefore applies to the variant that is actually implemented.

(4) A blockwise extension with guidance on per-matrix stepsizes. For models with many weight matrices, Sec. 6 orthogonalizes each matrix block separately, which reduces cost and allows parallel computation, and derives the relative stepsize of each block from an LL-drift budget: ωb,k∝ab,k/wb\omega _{b,k}\propto a _{b,k}/w _b (Eq. (10)), where ab,ka _{b,k} is the predicted UL progress of block bb and wb=LXY,b2rb/μ2w _b=L _{XY,b}^2r _b/\mu^2 is its LL sensitivity. Single-level Muon implementations scale per-matrix updates by the matrix shape [5]; our rule additionally uses the bilevel structure, giving larger steps to blocks with stronger UL progress and more conservative steps to blocks to which the LL solution is more sensitive.

2. Steps specific to combining Muon with bilevel optimization. Although Muon and bilevel optimization have each been studied individually in the literature, the use of Muon for bilevel optimization introduces the following new technical challenges in the theoretical analysis, unseen in either line of work; they arise exactly where the stocBiO bias and tracking bounds cannot simply be plugged into the descent argument for Muon.

(a) The changed coupled UL–LL descent due to polar decomposition from Muon. The key difference from flattened-vector bilevel analyses lies in how the two levels interact through the descent argument. In flattened analyses (e.g., [2, 6]), the descent inequality is quadratic: progress is measured by ∥∇Φ∥2\Vert \nabla\Phi\Vert ^2, the hypergradient bias (which contains the LL tracking error) enters as a squared term, and the UL displacement β∥vk∥\beta\Vert v _k\Vert, hence the LL drift, shrinks with the hypergradient. Unfortunately, under polar updates, both directions of this coupling change:

Change (1): UL → LL. A polar step has ∥Xk+1−Xk∥F2=β2 rank(Mk)\Vert X _{k+1}-X _k\Vert _F^2=\beta^2\thinspace \mathrm{rank}(M _k) no matter how small the hypergradient is. Thus, the change of Y⋆(Xk)Y^\star(X _k) can be as large as (L/μ)βrank(Mk)(L/\mu)\beta\sqrt{\mathrm{rank}(M _k)} per iteration even when XkX _k is near a stationary point. To address this technical challenge, we bound the resulting tracking error by the rank-driven term L2β2α2μ4T∑kE rank(Mk)\frac{L^2\beta^2}{\alpha^2\mu^4T}\sum _k\mathbb E\thinspace \mathrm{rank}(M _k) instead of a hypergradient-driven one (cf. Lemma 1).

Change (2): LL → UL. In the polar descent inequality, progress comes from the first-order term ∥∇Φ(Xk)∥∗\Vert \nabla\Phi(X _k)\Vert _\ast. Also, the bias of the hypergradient estimator MkM _k enters linearly in the nuclear norm 2β∥Mk−∇Φ(Xk)∥∗2\beta\Vert M _k-\nabla\Phi(X _k)\Vert _\ast, rather than as a squared term that a squared-norm analysis can absorb. To address this technical challenge, we average over iterations and convert to the Frobenius norm in the proof of Theorem 1, which bounds the bias term by (r⋅1T∑kE∥Mk−∇Φ(Xk)∥F2)1/2\big(r\cdot\frac1T\sum _k\mathbb E\Vert M _k-\nabla\Phi(X _k)\Vert _F^2\big)^{1/2}; this Frobenius error is then controlled by the momentum-tracking bound (Lemma 7), which incorporates the tracking error of Change (1).

Resulting trade-off: balancing the two levels. The difficulty is that Changes (1) and (2) pull the stepsizes of the two levels in opposite directions: the rank-driven tracking error of Change (1) vanishes only if the UL stepsize β\beta is small relative to the LL stepsize α\alpha, whereas the first-order descent of Change (2) needs β\beta large enough to attain the O(T−1/4)O(T^{-1/4}) rate. We resolve this with the stepsize schedule of Theorem 1, rβ2/α2=rβ02L2T−1/2r\beta^2/\alpha^2=r\beta _0^2L^2T^{-1/2}, which drives the tracking error to zero while preserving the O(T−1/4)O(T^{-1/4}) rate; the rank-driven drift affects only the rank-dependent constants in CpolC _{pol} (29), not the rate. We agree that stepsize separation (β/α→0\beta/\alpha\to0) is itself standard [6]; the new element is a rank-driven drift that does not decay with the hypergradient, combined with a first-order nuclear-norm descent.

(b) Finite Newton–Schulz approximation in the UL–LL coupling. Most existing convergence analyses of Muon assume the exact SVD-based polar factor, e.g., [1], whereas practical implementations apply a few Newton–Schulz (NS) iterations, whose output is not orthogonal. The polar-approximation bound for NS (Lemma 2) is taken from existing single-level analysis [4]; what is specific to the bilevel setting is that the NS error has to be controlled in both directions of the coupling in (a):

(1) UL → LL. The rank-driven tracking bound of Lemma 1 uses ∥Ok∥F2≤rank(Mk)\Vert O _k\Vert _F^2\le\mathrm{rank}(M _k). We show that the NS recurrence maps each positive singular value s∈(0,1]s\in(0,1] of its initial iterate into [s,1][s,1] and keeps zero at zero, so ∥NS(Mk,q)∥op≤1\Vert \mathrm{NS}(M _k,q)\Vert _{op}\le1 and ∥NS(Mk,q)∥F2≤rank(Mk)\Vert \mathrm{NS}(M _k,q)\Vert _F^2\le\mathrm{rank}(M _k), also for rank-deficient momentum (Lemma 9); Lemma 1 therefore holds unchanged.

(2) LL → UL. If ∥NS(Mk,q)−polar(Mk)∥op≤εq\Vert \mathrm{NS}(M _k,q)-\mathrm{polar}(M _k)\Vert _{op}\le\varepsilon _q, inserting the polar factor into the descent step gives ⟨∇Φ(Xk),Ok⟩≥(1−εq)∥∇Φ(Xk)∥∗−2∥Mk−∇Φ(Xk)∥∗\langle\nabla\Phi(X _k),O _k\rangle\ge(1-\varepsilon _q)\Vert \nabla\Phi(X _k)\Vert _\ast -2\Vert M _k-\nabla\Phi(X _k)\Vert _\ast (Lemma 9). The NS error thus only rescales the progress term, while the bias term, which carries the LL tracking error, keeps the form of Lemma 8. We obtain E∥∇Φ(XR)∥∗≤CpolT−1/4/(1−εq)\mathbb E\Vert \nabla\Phi(X _R)\Vert _\ast \le C _{pol}T^{-1/4}/(1-\varepsilon _q), where εq\varepsilon _q decreases doubly exponentially in the NS depth qq.

W2: The theory does not show that orthogonalization helps.

  • The analysis assumes smoothness in the Frobenius norm. Under this assumption, a Muon step of size β\beta has Frobenius length βrank⁡(Mk)\beta \sqrt{\operatorname{rank}(M _{k})}, so the bound pays a factor of up to r=min⁡(m,n)r=\operatorname{min}(m,n) (see CpolC _{\mathrm{pol}} in (29)). Running the same proof for the FrobNorm baseline, i.e., momentum divided by its Frobenius norm, gives a bound of the same order. Theorem 1 therefore shows no advantage of the polar update over a flattened normalized update. Shen et al. (2025), cited in the paper, make the same observation for single-level Muon.

Response: Thank you for this careful comment. We agree that Theorem 1 does not separate the polar update from FrobNorm. Shen et al. [1, Sec. 4.1.1] reach the same conclusion for single-level Muon: under Frobenius smoothness, its bound is no better than that of SGD.

1. The rate is already optimal. Under bounded-variance stochastic gradients, Ω(ϵ−4)\Omega(\epsilon^{-4}) stochastic gradient evaluations are necessary to find an ϵ\epsilon-stationary point [7], so without variance reduction the order T−1/4T^{-1/4} cannot be improved by any update, polar or flattened, and single-level analyses of Muon likewise obtain this order [1, 4]. A difference between the two updates can therefore appear only in the constants, and a worst-case bound under Frobenius smoothness cannot show it even there: this class contains isotropic objectives such as Φ(X)=12∥X−X⋆∥F2\Phi(X)=\frac12\Vert X-X^\star\Vert _F^2, on which the normalized gradient already points straight at X⋆X^\star.

2. What Theorem 1 establishes. Theorem 1 is a convergence guarantee rather than a comparison: it shows that BiMuon attains this order in the bilevel setting. To our knowledge, it is the first such guarantee for stochastic bilevel optimization with Muon-style updates. It measures stationarity in the nuclear norm, which is at least as strong as the Frobenius norm and is the dual of the spectral norm in which the polar factor is the steepest-descent direction [8], and it covers both the exact polar factor and the finite Newton–Schulz iteration used in practice. The advantage of the polar update over FrobNorm is shown instead by the quadratic model of Sec. 3.2, where the polar factor removes the κ(HLL)2\kappa(H _{LL})^2 singular-value imbalance of the hypergradient that FrobNorm only rescales (App. A.2), and by our experiments, in which exact-polar BiMuon reaches a final UL validation loss of 0.033±0.0050.033\pm0.005 versus 0.189±0.0220.189\pm0.022 for FrobNorm on CIFAR-10, and 0.337±0.0060.337\pm0.006 versus 0.691±0.0050.691\pm0.005 in the transformer experiment (Table 2 in App. F.1 and Table 1).

W3: The experiments are small.

W3.1: The experiments are presented as real-data tasks on CIFAR-10 and CIFAR-100, but the pretrained backbone (ResNet-18/50) is frozen, and only a small model on top of the frozen features is trained: a 256×512256\times 512 representation layer and a linear classifier on CIFAR-10, and only a linear classifier on CIFAR-100. The CIFAR-10 task also uses only 1,000 training and 500 validation samples and 60 upper-level iterations.

W3.2: There is no comparison with Adam as the upper-level optimizer, and no experiment on a larger model such as a transformer.

Response: Thank you for these comments. We answer W3.1 and W3.2 together. The original experiments were designed so that the LL problem, a regularized linear classifier, satisfies the strong convexity of Assumption 1, and we agree that the frozen backbone, the small splits and the 60 UL iterations limit their scale. In this rebuttal period, we have added a larger-scale transformer experiment (Sec. 7.2 and App. F.5), which addresses all three points while keeping the LL strongly convex: it trains the weights of four transformer blocks rather than a single layer on frozen features, uses 40 and 20 times larger LL and UL splits, and runs 1,000 UL iterations. We have also added a stocBiO+Adam baseline in the CIFAR-10, transformer and input-anisotropy experiments (Sec. 7.1, 7.2 and App. F.3).

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

This paper proposes BiMuon, a stochastic bilevel optimization method that combines implicit hypergradient estimation with Muon-style upper-level updates. Specifically, it applies exact polar normalization or a finite Newton–Schulz approximation to the hypergradient momentum, thereby reshaping the singular spectrum of the update. For problems with a nonconvex upper-level objective and a strongly convex lower-level objective, the authors establish, under their stated regularity and approximation assumptions, an O(ϵ−4)O(\epsilon^{-4}) outer-iteration complexity and a O~(ϵ−4)\widetilde O(\epsilon^{-4}) stochastic derivative complexity for obtaining E∥∇Φ(XR)∥∗≤ϵ\mathbb{E}\|\nabla\Phi(X_R)\|_*\le\epsilon. Representation-learning experiments on CIFAR-10 and synthetic data report improved upper-level validation loss compared with unnormalized and scalar-normalized hypergradient-momentum updates. The authors additionally propose a blockwise stepsize allocation rule that accounts for both predicted upper-level progress and lower-level sensitivity.

Critical strengths

The paper is motivated by an interesting perspective on how lower-level curvature can affect the geometry and conditioning of the upper-level objective. This provides a useful starting point for exploring geometry-aware hypergradient updates. The work is well rounded, combining algorithm development, theoretical convergence guarantees, and numerical experiments. The manuscript is also clearly written and logically organized.

Critical weaknesses
  1. My main concern is that the connection between upper-level ill-conditioning and the benefit of hypergradient spectral normalization is not clear. Section 3.2 illustrates how lower-level curvature can amplify the condition number of the upper-level Hessian in a quadratic example. However, the spectrum of this Hessian and the singular spectrum of the hypergradient momentum are different objects. Equalizing the latter does not generally imply improved effective conditioning or faster optimization. Indeed, unequal hypergradient singular values can also reflect unequal parameter errors, in which case normalization may remove useful magnitude information. The convergence analysis establishes a guarantee for BiMuon but does not identify conditions under which its spectral transformation improves upon ordinary hypergradient descent.
Questions for authors
  1. Given that upper-level Hessian conditioning and hypergradient spectral imbalance are different properties, under what cases does BiMuon’s spectral normalization improve optimization compared with ordinary hypergradient descent, or what theoretical or empirical evidence supports this connection?

  2. Figure 2(b) provides an interesting diagnostic of the momentum spectrum before transformation, but it does not directly measure upper-level curvature or establish that reduced spectral imbalance causes better optimization. Could the authors conduct controlled bilevel experiments with explicitly prescribed condition numbers for the upper-level Hessian (comparing well-conditioned with highly ill-conditioned problems) and compare the performance of Muon updates with ordinary hypergradient updates?

  3. The experimental evaluation is limited to relatively modest upper-level parameter sizes. The first experiment uses a 256×512256 \times 512 upper-level matrix (131,072 parameters), while the second uses four 100×512100 \times 512 blocks (204,800 parameters in total). It therefore remains unclear whether BiMuon remains effective and computationally competitive for substantially larger upper-level variables, particularly when the individual matrices undergoing spectral transformation are larger. Could the authors evaluate scalability by increasing the upper-level dimensions and reporting optimization performance, runtime, and memory usage relative to ordinary hypergradient updates?

6 comments

We thank Reviewer xZ6p for finding our view of how lower-level curvature shapes the upper-level geometry interesting, and the work well rounded and clearly written. We address each point below; changes in the revised PDF are marked in blue.

W1: My main concern is that the connection between upper-level ill-conditioning and the benefit of hypergradient spectral normalization is not clear. Section 3.2 illustrates how lower-level curvature can amplify the condition number of the upper-level Hessian in a quadratic example. However, the spectrum of this Hessian and the singular spectrum of the hypergradient momentum are different objects. Equalizing the latter does not generally imply improved effective conditioning or faster optimization. Indeed, unequal hypergradient singular values can also reflect unequal parameter errors, in which case normalization may remove useful magnitude information. The convergence analysis establishes a guarantee for BiMuon but does not identify conditions under which its spectral transformation improves upon ordinary hypergradient descent.

Q1: Given that upper-level Hessian conditioning and hypergradient spectral imbalance are different properties, under what cases does BiMuon’s spectral normalization improve optimization compared with ordinary hypergradient descent, or what theoretical or empirical evidence supports this connection?

Response: Thank you for this thoughtful comment. We answer W1 and Q1 together. In short, BiMuon improves upon hypergradient descent when the UL curvature is strongly ill-conditioned and a few large eigenvalues sit above a bulk of small ones; the bilevel structure produces the first condition whenever κ(HLL)\kappa(H_{LL}) is large. Point 1 gives the theoretical and empirical evidence for this connection, point 2 discusses the magnitude information, and point 3 explains the role of Theorem 1.

1. Two sources of UL spectral imbalance. We agree that the Hessian spectrum and the hypergradient singular spectrum are different objects, so whether equalizing the latter helps depends on where the imbalance comes from. In our setting, the spectral imbalance of the UL hypergradient has two sources. The first is common to matrix-valued parameters: gradients and momenta of weight matrices are typically dominated by a few singular directions [1, 2], which is the motivation for Muon in single-level training. The second is specific to bilevel optimization: the UL objective depends on XX through the LL solution Y⋆(X)Y^\star(X), so the LL curvature is transmitted to the UL. Sec. 3.2 isolates this second source in a quadratic model, and the following computation in this model shows that the UL ill-conditioning does translate into faster optimization with spectral normalization. Here ∇Φ(X)=μ2HLL−2(X−X⋆)\nabla\Phi(X)=\mu^2H_{LL}^{-2}(X-X^\star) and HUL=μ2HLL−2⊗IH_{UL}=\mu^2H_{LL}^{-2}\otimes I (App. A.1), so κ(HUL)=κ(HLL)2\kappa(H_{UL})=\kappa(H_{LL})^2. For an error aligned with the LL eigendirections, X−X⋆=P,diag(xi)V⊤X-X^\star=P\\,\mathrm{diag}(x_i)V^\top, the hypergradient singular values are μ2∣xi∣/hi2\mu^2|x_i|/h_i^2 (App. A.2), so even equal errors produce a singular-value ratio of κ(HUL)\kappa(H_{UL}). Hypergradient descent gives xi+=(1−βμ2/hi2),xix_i^+=(1-\beta\mu^2/h_i^2)\\,x_i with β≤2hmin⁡2/μ2\beta\le2h_{\min}^2/\mu^2 for stability, so shrinking the flattest component by a factor ϵ\epsilon takes at least κ(HLL)2−22log⁡1ϵ\frac{\kappa(H_{LL})^2-2}{2}\log\frac1\epsilon steps; FrobNorm and OpNorm only rescale this direction. The polar step gives xi+=xi−β,sign(xi)x_i^+=x_i-\beta\\,\mathrm{sign}(x_i), so all components are at most β\beta in magnitude after ⌈max⁡i∣xi∣/β⌉\lceil\max_i|x_i|/\beta\rceil steps, for every κ(HLL)\kappa(H_{LL}). Our controlled experiment in Q2 tests this connection beyond the aligned case and confirms it: as κ(HLL)\kappa(H_{LL}) grows from 11 to 300300, the gap of hypergradient descent rises by more than twelve orders of magnitude, whereas that of exact-polar BiMuon stays within a factor of three.

2. Magnitude information. We agree that normalization discards the singular-value magnitudes. This is, however, the mechanism by which Muon helps when the spectrum is imbalanced: a few large singular directions dominate the update and mask the small ones, and the polar factor, which is the steepest-descent direction under the spectral norm [3], gives every direction the same step. This is the regime in which Muon has been effective in practice. (1) Jordan et al. [1] observe that SGD-momentum and Adam updates of Transformer layers are dominated by a few directions and suggest that orthogonalization amplifies rare but important ones. (2) Wang et al. [4] find that Muon learns the tail classes of heavy-tailed data better than Adam, and prove in a one-layer associative-memory model with class-imbalanced data that Muon achieves balanced learning across classes. The magnitudes also still determine the progress: since ⟨∇Φ,polar(∇Φ)⟩=∥∇Φ∥∗\langle\nabla\Phi,\mathrm{polar}(\nabla\Phi)\rangle=\Vert \nabla\Phi\Vert _\ast, each step decreases Φ\Phi, to first order, by β\beta times the sum of all singular values (Lemma 8). We also agree that magnitude can matter in other regimes: when the curvature is isotropic and only the errors differ, hypergradient descent with β=1/λmax⁡(HUL)\beta=1/\lambda _{\max}(H _{UL}) reaches X⋆X^\star in one step, whereas the polar step needs about max⁡i∣xi∣/β\max _i|x _i|/\beta steps. In the bilevel model of Sec. 3.2, however, the UL curvature is isotropic only if κ(HLL)=1\kappa(H _{LL})=1, since κ(HUL)=κ(HLL)2\kappa(H _{UL})=\kappa(H _{LL})^2. Empirically, on CIFAR-10 (Table 2 in App. F.1), exact-polar BiMuon reaches a UL validation loss of 0.033±0.0050.033\pm0.005, versus 0.189±0.0220.189\pm0.022 for FrobNorm and 0.199±0.1280.199\pm0.128 for OpNorm; since these scalar-normalized baselines rescale the momentum without changing its relative spectrum, the gain comes from reshaping the spectrum.

3. What Theorem 1 shows. We agree that Theorem 1 by itself does not identify when BiMuon improves upon hypergradient descent. Its role is to provide, to our knowledge, the first convergence guarantee for stochastic bilevel optimization with Muon-style updates. It covers both the exact-polar (SVD) version and the finite Newton–Schulz (NS) version used in practice, whereas most existing convergence analyses of Muon assume the exact SVD-based polar factor [5, 6]. Both versions attain E∥∇Φ(XR)∥∗=O(T−1/4)\mathbb E\Vert \nabla\Phi(X _R)\Vert _\ast =O(T^{-1/4}), i.e., O~(ϵ−4)\widetilde O(\epsilon^{-4}) stochastic derivative evaluations, the NS version up to a factor 1/(1−εq)1/(1-\varepsilon _q) that approaches one rapidly as the NS depth qq grows. This matches single-level Muon [5] and the best-known stochastic bilevel methods without variance reduction [7, 8], with a nuclear-norm stationarity measure that is at least as strong as the Frobenius one.

Q2: Figure 2(b) provides an interesting diagnostic of the momentum spectrum before transformation, but it does not directly measure upper-level curvature or establish that reduced spectral imbalance causes better optimization. Could the authors conduct controlled bilevel experiments with explicitly prescribed condition numbers for the upper-level Hessian (comparing well-conditioned with highly ill-conditioned problems) and compare the performance of Muon updates with ordinary hypergradient updates?

Response: Thank you for this excellent suggestion, which we have followed. We added the experiment below directly tests the two premises of our paper: LL curvature makes the UL problem ill-conditioned for hypergradient updates (Sec. 3.2), and a spectral UL update, rather than a scalar normalization, removes this bottleneck.

1. Setup. We use the quadratic bilevel model of App. A.3 and prescribe the LL Hessian, so that the UL Hessian is induced exactly as in Sec. 3.2: with isotropic validation covariance and γ=0\gamma=0, HUL[Δ]=μ2HLL−2Δ\mathcal H _{UL}[\Delta]=\mu^2H _{LL}^{-2}\Delta and κ(HUL)=κ(HLL)2\kappa(H _{UL})=\kappa(H _{LL})^2. We vary κ(HLL)\kappa(H _{LL}) from 11 to 10001000 (table below), including the value 300300 used in App. A.3, and fix the largest UL eigenvalue at λmax⁡=0.01\lambda _{\max}=0.01. This range is practically relevant: in our CIFAR-10 task (Sec. 7.1), the LL Hessian at the final iterates of stocBiO+EMA and exact-polar BiMuon has κ(HLL)\kappa(H _{LL}) between 313313 and 644644 across the five seeds, which corresponds to κ(HUL)≈105\kappa(H _{UL})\approx10^5–4×1054\times10^5 in the quadratic model. Since Hessian spectra of trained networks, including LLMs, are strongly nonuniform [9] and Muon's advantage on quadratics can depend on the spectrum shape at a fixed condition number [10], we test four shapes of the induced UL spectrum (X∈R16×16X\in\mathbb R^{16\times16}, λmin⁡=λmax⁡/κ(HUL)\lambda _{\min}=\lambda _{\max}/\kappa(H _{UL})): (1) Bulk + outlier: one eigenvalue λmax⁡\lambda _{\max} and 15 geometrically spaced in [λmin⁡,min⁡{10λmin⁡,λmax⁡}][\lambda _{\min},\min\lbrace 10\lambda _{\min},\lambda _{\max}\rbrace ]; (2) Low atom + outlier: one at λmax⁡\lambda _{\max} and 15 at λmin⁡\lambda _{\min}; (3) Geometric: 16 geometrically spaced; (4) High atom + trough: 15 at λmax⁡\lambda _{\max} and one at λmin⁡\lambda _{\min}. We compare hypergradient descent with EMA momentum (HG+EMA), FrobNorm, and exact-polar and NS-12 BiMuon, all with the exact hypergradient, momentum 0.90.9, constant stepsizes and 1,000 updates from paired Gaussian initializations. Stepsizes are tuned under the same search rule for every method and frozen before evaluation on five new paired seeds.

2. Results. For spectrum (1), the relative UL objective gap Φ(Xk)/Φ(X0)\Phi(X _k)/\Phi(X _0), averaged over the final 100 updates, is (mean ± SD over five seeds; best per row in bold; all four spectra in App. F.6):

κ(HLL)\kappa(H _{LL})κ(HUL)\kappa(H _{UL})HG+EMAFrobNormExact-polar BiMuonNS-12 BiMuon
11114.9e-17 ± 6.8e-312.3e-6 ± 9.4e-206.9e-6 ± 4.0e-74.7e-6 ± 7.8e-7
101010210^22.1e-16 ± 4.5e-172.2e-5 ± 6.6e-61.4e-5 ± 1.7e-56.5e-6 ± 1.7e-6
10010010410^43.3e-7 ± 8.5e-82.3e-5 ± 5.3e-65.0e-6 ± 3.0e-66.4e-6 ± 1.6e-6
3003009×1049\times10^46.7e-5 ± 1.7e-51.7e-4 ± 9.6e-57.8e-6 ± 8.8e-68.2e-6 ± 1.7e-6
1000100010610^65.5e-5 ± 1.5e-57.7e-5 ± 1.9e-58.5e-6 ± 2.7e-62.7e-5 ± 1.1e-5

These results support our motivation and design in four ways. (1) The bilevel-induced ill-conditioning is a bottleneck for hypergradient updates. As κ(HLL)\kappa(H _{LL}) grows from 11 to 300300, the gap of HG+EMA rises by more than twelve orders of magnitude, confirming that the squared LL conditioning of Sec. 3.2 slows down ordinary hypergradient updates. (2) Polar updates are insensitive to this ill-conditioning. The gap of exact-polar BiMuon stays between 5.0×10−65.0\times10^{-6} and 1.4×10−51.4\times10^{-5} for every κ(HUL)\kappa(H _{UL}), as predicted by the quadratic analysis in W1, point 1, where the polar step moves every component by the same amount. At κ(HUL)=9×104\kappa(H _{UL})=9\times10^4, both BiMuon variants beat HG+EMA and FrobNorm on all five seeds, and NS-12 reduces the mean gap by factors of 8.2 and 21.3; at 10610^6, both variants still have lower mean gaps. (3) The spectral transformation, not normalization, is what helps. FrobNorm, which rescales the momentum without changing its relative spectrum, is worse than HG+EMA at every κ(HUL)\kappa(H _{UL}), so the gain comes from equalizing the singular spectrum, the core design of BiMuon. (4) The gain appears where κ(HUL)\kappa(H _{UL}) is large. When κ(HUL)≤104\kappa(H _{UL})\le10^4, HG+EMA is better, since normalized updates with constant stepsizes stall at about 10−610^{-6} to 10−510^{-5} (W1, points 1 and 2). The ranking also depends on the spectrum: spectrum (2) behaves like spectrum (1), whereas for spectra (3) and (4) HG+EMA remains better at every κ(HUL)\kappa(H _{UL}). Polar updates thus help most when a few large eigenvalues sit above a bulk of small ones, consistent with [9, 10]. All runs use exact hypergradients to isolate the UL update.

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

This paper studied matrix-value bilevel optimization and proposed BiMuon as a geometry-aware stochastic bilevel optimization approach. By showing that the upper-level usually has a larger condition number than the lower-level, the paper is motivated to study adding Muon at the upper-level for bilevel optimization. The paper established the convergence rate of Exact-Polar BiMuon and Finite-NS BiMuon, which matches the best-known rate for stochastic single-level Muon optimization. Experiments show that the proposed method is effective in representation learning and blockwise allocation problems.

Critical strengths
  1. This paper established the first convergence result for bilevel optimization with matrix parameterizations.
  2. The convergence analysis is new and solid.
Critical weaknesses
  1. As applied for the bilevel optimization, this paper only uses Muon for the upper-level, and the motivation to use Muon for the upper-level is not clear to me. For example, for hyperparameter optimization and data reweighting problems, the upper-level variables are usually vectors, which do not require a matrix parameterization. For the representation learning problem studied in this paper, although the author proved that the condition number is larger for the upper level problem, it does not generally imply an imbalanced gradient singular spectrum. Considering a matrix objective Φ(X)=12(1000x112+x122+x212+x222)\Phi(X)=\frac{1}{2}\left(1000 x_{11}^2+x_{12}^2+x_{21}^2+x_{22}^2\right), it Hessian has a large eigenvalue, but the gradient matrix is identity.

  2. The technical challenges of applying Muon at the upper level are not clear. The analysis seems to combine the Muon’s convergence analysis with a biased stochastic gradient framework, using standard bilevel techniques to control the bias. Extending the analysis of Muon in both upper and lower-level problem might introduce more challenges than the current version.

  3. The numerical experiments are relatively small-scaled, and lack baselines, e.g. bilevel optimization with Adam as optimizer.

Questions for authors

What are the technical challenges of analyzing Muon for the upper-level problem?

5 comments

W1: As applied for the bilevel optimization, this paper only uses Muon for the upper-level, and the motivation to use Muon for the upper-level is not clear to me. For example, for hyperparameter optimization and data reweighting problems, the upper-level variables are usually vectors, which do not require a matrix parameterization. For the representation learning problem studied in this paper, although the author proved that the condition number is larger for the upper level problem, it does not generally imply an imbalanced gradient singular spectrum. Considering a matrix objective Φ(X)=12(1000x112+x122+x212+x222)\Phi (X)=\frac{1}{2}(1000x_{11}^{2}+x_{12}^{2}+x_{21}^{2}+x_{22}^{2}), it Hessian has a large eigenvalue, but the gradient matrix is identity.

Response: Thanks for your comments. Due to the length of this comment, we structure our response as follows:

1. Why we consider the use of Muon in the UL of bilevel optimization: As the first work in the literature, to our knowledge, to bring Muon-style updates to stochastic bilevel optimization, we start from the level where they are most needed. The UL hypergradient is spectrally imbalanced for two reasons, and the UL is exposed to both. (1) Imbalance common to weight matrices. Gradients of such weight matrices are typically dominated by a few singular directions: Jordan et al. [9] observed this in the SGD-momentum and Adam updates of Transformer layers, and Magakyan et al. [10, Sec. 3.2] found a single outlier singular value, often an order of magnitude or more above the rest, in the momentum matrices of a Muon-trained GPT-2-style model with 2.8B parameters. This anisotropy motivates orthogonalized updates in single-level training [9], and Fig. 2(b) shows a strong imbalance in the hypergradient momentum of our flattened baselines. (2) Imbalance added by the LL curvature. Our quadratic example (Sec. 3.2) shows that, in the bilevel setting, the LL curvature directly shapes the UL geometry, and does so in squared form: ∇Φ(X)=μ2HLL−2(X−X⋆)\nabla\Phi(X)=\mu^2H_{LL}^{-2}(X-X^\star), so HUL=μ2HLL−2⊗IH_{UL}=\mu^2H_{LL}^{-2}\otimes I and κ(HUL)=κ(HLL)2\kappa(H_{UL})=\kappa(H_{LL})^2. An LL condition number of 100100 thus already gives a UL condition number of 10410^4; point 3 below explains how this carries over to the hypergradient spectrum. This amplification is a property of Φ\Phi itself: it holds at the exact LL solution Y⋆(X)Y^\star(X), so it persists however accurately the LL problem is solved, and no choice of LL optimizer removes it. The LL problem, by contrast, is μ\mu-strongly convex, and the use of a simple warm-started SGD already suffices to achieve its optimal solution at a linear finite-time convergence rate (Lemma 1). In our setting, the major challenge stems from the nonconvex UL, which inherits κ(HLL)2\kappa(H_{LL})^2. Our new controlled experiment (App. F.6) confirms this: as κ(HLL)\kappa(H_{LL}) grows from 11 to 300300, the UL objective gap of hypergradient descent rises by more than twelve orders of magnitude, whereas that of exact-polar BiMuon stays within a factor of three.

2. The need for matrix-valued UL variables in bilevel optimization: Although it is true that the UL variables in classical hyperparameter optimization (HPO) and per-sample data reweighting are vector-valued, the bilevel framework also covers a wide range of applications that contain matrix-valued hyperparameters and model weights. In addition to Example 3.4 of Franceschi et al. [1], whose UL variable is a linear feature map H∈Rd×dH\in\mathbb{R}^{d\times d}, the following are also examples of bilevel formulations that learn neural-network weights at the UL:

  • In meta-learning, the embedding network in MetaOptNet [2] and R2-D2 [3], with a convex linear classifier at the LL, the network body in ANIL [4], and the meta-initialization of all weights in iMAML [5];
  • In IRM [6], the UL variable is the data representation Φ\Phi, which is a matrix in the linear case and a set of weight matrices for a neural network, and the LL requires the classifier on top of Φ\Phi to be simultaneously optimal across all training environments;
  • The data-augmentation network of Lorraine et al. [7] and the teacher network of Meta Pseudo Labels [8].

These parameters retain their layerwise matrix structure even when written as a single vector, and convolution kernels are treated as matrices by flattening, as in Muon [9]. Existing bilevel methods nevertheless update these matrices as flattened vectors and ignore the inherent geometric structure of the problem, which motivates BiMuon. Note that our general matrix-valued bilevel framework also covers the conventional vector-valued bilevel formulation as a special case.

3. On the reviewer's example. Thank you for this insightful example. We agree that Hessian conditioning alone does not, in general, determine the gradient singular spectrum: in your example, it can be verified that the gradient matrix ∇Φ(X)=I\nabla\Phi(X)=I only when X=diag(10−3,1)X=\mathrm{diag}(10^{-3},1). In general, the gradient matrix is still ill-conditioned for XX in a large subspace in R2×2\mathbb{R}^{2\times 2}.

Ill-conditioning is even more pronounced in bilevel optimization, since the UL curvature takes a different and more complex form. As mentioned in our quadratic model (Sec. 3.2) with Σval=I\Sigma_{\mathrm{val}}=I and γ=0\gamma=0, the hypergradient matrix can be computed as ∇Φ(X)=μ2HLL−2(X−X⋆)\nabla\Phi(X)=\mu^2H_{LL}^{-2}(X-X^\star), where HLLH_{LL} is the lower-level Hessian matrix. Further, the UL curvature HUL=μ2HLL−2⊗IH_{UL}=\mu^2H_{LL}^{-2}\otimes I is a Kronecker operator (App. A.1).

A similar "condition-compensation effect" as in your example may happen only in the following scenario: Let HLL=P diag(hi)P⊤H_{LL}=P\,\mathrm{diag}(h_i)P^\top be the eigenvalue decomposition of HLLH_{LL}, with orthogonal PP. Then, if X−X⋆X-X^\star takes the form of X−X⋆=P diag(xi)V⊤X-X^\star=P\,\mathrm{diag}(x_i)V^\top with orthogonal VV, we have (cf. Appendix A.2): ∇Φ(X)=μ2P diag(xi/hi2)V⊤.\nabla\Phi(X)=\mu^2P\,\mathrm{diag}(x_i/h_i^2)V^\top. Furthermore, if xi∝hi2x_i\propto h_i^2, the ratios xi/hi2x_i/h_i^2 are all equal, and ∇Φ(X)\nabla\Phi(X) is not ill-conditioned. Note, however, that such a "compensation" effect requires two very special conditions: i) the left singular vectors of X−X⋆X-X^\star coincide with the eigenvectors of HLLH_{LL}; and ii) xi∝hi2x_i\propto h_i^2.

However, for a general XX, these two special conditions are unlikely to hold simultaneously, since they require both the directions and the magnitudes of the error X−X⋆X-X^\star to be tuned to the LL curvature. Moreover, as mentioned in our paper, the spectrum of UL hypergradient is imbalanced if i) gradients of weight matrices are already imbalanced, and ii) the Kronecker-structured bilevel curvature adds a further imbalance even for comparable error components. Fig. 2(b) also confirms the spectrum imbalance of the hypergradient in practice.

W2: The technical challenges of applying Muon at the upper level are not clear. The analysis seems to combine the Muon’s convergence analysis with a biased stochastic gradient framework, using standard bilevel techniques to control the bias. Extending the analysis of Muon in both upper and lower-level problem might introduce more challenges than the current version.

Q1: What are the technical challenges of analyzing Muon for the upper-level problem?

Response: Thank you for this question.

1) Challenges of applying Muon in the UL: Although Muon and bilevel optimization have each been studied individually in the literature, the use of Muon for bilevel optimization introduces the following new technical challenges in theoretical analysis unseen in either line of work:

  1. The changed coupled UL–LL descent due to polar decomposition from Muon. The key difference from flattened-vector bilevel analyses lies in how the two levels interact through the descent argument. In flattened analyses (e.g., [11, 12]), the descent inequality is quadratic: progress is measured by ∣∇Φ∣2\\|\nabla\Phi\\|^2, the hypergradient bias (which contains the LL tracking error) enters as a squared term, and the UL displacement β∣vk∣\beta\\|v_k\\|, hence the LL drift, shrinks with the hypergradient. Unfortunately, under polar updates, both directions of this coupling change:

    Change (1): UL → LL. A polar step has ∣Xk+1−Xk∣F2=β2,rank(Mk)\\|X_{k+1}-X_k\\|_F^2=\beta^2\\,\mathrm{rank}(M_k) no matter how small the hypergradient is. Thus, the change of Y⋆(Xk)Y^\star(X_k) can be as large as (L/μ)βrank(Mk)(L/\mu)\beta\sqrt{\mathrm{rank}(M_k)} per iteration even when XkX_k is near a stationary point. To address this technical challenge, we bound the resulting tracking error by the rank-driven term L2β2α2μ4T∑kE,rank(Mk)\frac{L^2\beta^2}{\alpha^2\mu^4T}\sum_k\mathbb E\\,\mathrm{rank}(M_k) instead of a hypergradient-driven one (cf. Lemma 1).

    Change (2): LL → UL. In the polar descent inequality, progress comes from the first-order term ∣∇Φ(Xk)∣\*\\|\nabla\Phi(X_k)\\|_\*. Also, the bias of the hypergradient estimator MkM_k enters linearly in the nuclear norm 2β∣Mk−∇Φ(Xk)∣\*2\beta\\|M_k-\nabla\Phi(X_k)\\|_\*, rather than as a squared term that a squared-norm analysis can absorb. To address this technical challenge, we average over iterations and convert to the Frobenius norm in the proof of Theorem 1, which bounds the bias term by (r⋅1T∑kE∣Mk−∇Φ(Xk)∣F2)1/2\big(r\cdot\frac1T\sum_k\mathbb E\\|M_k-\nabla\Phi(X_k)\\|_F^2\big)^{1/2}; this Frobenius error is then controlled by the momentum-tracking bound (Lemma 7), which incorporates the tracking error of Change (1).

    Resulting trade-off: balancing the two levels. The difficulty is that Changes (1) and (2) pull the stepsizes of the two levels in opposite directions: the rank-driven tracking error of Change (1) vanishes only if the UL stepsize β\beta is small relative to the LL stepsize α\alpha, whereas the first-order descent of Change (2) needs β\beta large enough to attain the O(T−1/4)O(T^{-1/4}) rate. We resolve this with the stepsize schedule of Theorem 1, rβ2/α2=rβ02L2T−1/2r\beta^2/\alpha^2=r\beta_0^2L^2T^{-1/2}, which drives the tracking error to zero while preserving the O(T−1/4)O(T^{-1/4}) rate; the rank-driven drift affects only the rank-dependent constants in CpolC_{pol} (29), not the rate.

  2. Finite Newton–Schulz approximation in the UL–LL coupling. Most existing convergence analyses of Muon assume the exact SVD-based polar factor [13, 14], whereas practical implementations apply a few Newton–Schulz (NS) iterations, whose output is not orthogonal. Our Theorem 1 covers both the exact-polar and the finite-NS versions of BiMuon, and in the bilevel setting the NS error has to be controlled in both directions of the coupling in point 1:

    (1) UL → LL. The rank-driven tracking bound of Lemma 1 uses ∣Ok∣F2≤rank(Mk)\\|O_k\\|_F^2\le\mathrm{rank}(M_k). We show that the NS recurrence maps each positive singular value s∈(0,1]s\in(0,1] of its initial iterate into [s,1][s,1] and keeps zero at zero, so ∣NS(Mk,q)∣op≤1\\|\mathrm{NS}(M_k,q)\\|_{op}\le1 and ∣NS(Mk,q)∣F2≤rank(Mk)\\|\mathrm{NS}(M_k,q)\\|_F^2\le\mathrm{rank}(M_k), also for rank-deficient momentum (Lemma 9); Lemma 1 therefore holds unchanged.

    (2) LL → UL. If ∣NS(Mk,q)−polar(Mk)∣op≤εq\\|\mathrm{NS}(M_k,q)-\mathrm{polar}(M_k)\\|_{op}\le\varepsilon_q, inserting the polar factor into the descent step gives ⟨∇Φ(Xk),Ok⟩≥(1−εq)∣∇Φ(Xk)∣\*−2∣Mk−∇Φ(Xk)∣\*\langle\nabla\Phi(X_k),O_k\rangle\ge(1-\varepsilon_q)\\|\nabla\Phi(X_k)\\|_\*-2\\|M_k-\nabla\Phi(X_k)\\|_\* (Lemma 9). The NS error thus only rescales the progress term, while the bias term, which carries the LL tracking error, keeps the form of Lemma 8. We obtain E∣∇Φ(XR)∣\*≤CpolT−1/4/(1−εq)\mathbb E\\|\nabla\Phi(X_R)\\|_\*\le C_{pol}T^{-1/4}/(1-\varepsilon_q), where εq\varepsilon_q decreases doubly exponentially in the NS depth qq.

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

Related papers

Discussion (0)

Sign in to comment.