- 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 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
- 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.
- 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.
- 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 , where 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 has Frobenius length , so the bound pays a factor of up to (see 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 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".
- 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
- 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?
- If is assumed to satisfy , as in Kim & Oh (2026), can the dependence on be reduced, so that the bound shows an advantage of BiMuon over flattened normalized momentum?
- How would one estimate for a real network? Is there a convergence guarantee for the blockwise variant?
- 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 receive a larger step?
- 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
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 , the hypergradient bias (which contains the LL tracking error) enters as a squared term, and the UL displacement , 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 no matter how small the hypergradient is. Thus, the change of can be as large as per iteration even when is near a stationary point. To address this technical challenge, we bound the resulting tracking error by the rank-driven term 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 . Also, the bias of the hypergradient estimator enters linearly in the nuclear norm , 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 ; 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 is small relative to the LL stepsize , whereas the first-order descent of Change (2) needs large enough to attain the rate. We resolve this with the stepsize schedule of Theorem 1, , which drives the tracking error to zero while preserving the rate; the rank-driven drift affects only the rank-dependent constants in (29), not the rate. We agree that stepsize separation () 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 . We show that the NS recurrence maps each positive singular value of its initial iterate into and keeps zero at zero, so and , also for rank-deficient momentum (Lemma 9); Lemma 1 therefore holds unchanged.
(2) LL → UL. If , inserting the polar factor into the descent step gives (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 , where decreases doubly exponentially in the NS depth .
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 has Frobenius length , so the bound pays a factor of up to (see 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, stochastic gradient evaluations are necessary to find an -stationary point [7], so without variance reduction the order 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 , on which the normalized gradient already points straight at .
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 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 versus for FrobNorm on CIFAR-10, and versus 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 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).
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.
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⊗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, 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), i.e., O(ϵ−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 q-step Newton–Schulz (NS) with the bound CpolT−1/4/(1−εq), which approaches the exact-polar bound rapidly as q 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 (Eq. (10)), where ab,k is the predicted UL progress of block b and wb=LXY,b2rb/μ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.