Skip to main content
Back to timeline
arXivSource publication:

Bilevel optimization stops flattening weight matrices: BiMuon adds orthogonalized updates and matches single-level Muon's convergence order

Synopsis

BiMuon brings Muon-style orthogonalized matrix updates into stochastic bilevel optimization, so upper-level parameters move along a matrix's singular spectrum instead of a flattened vector updated coordinate by coordinate. Nearly all prior bilevel methods used that flattened form, and the analysis shows lower-level curvature is squared through the bilevel composition, leaving upper-level hypergradients with more unequal singular values. BiMuon tracks the lower-level solution, estimates the hypergradient with a truncated Neumann series, then orthogonalizes the momentum; both the exact-polar and finite Newton–Schulz versions carry finite-time convergence rates, with sample complexity matching the best known for single-level Muon-type methods.

Source-provided article image: BiMuon: A Geometry-Aware Stochastic Bilevel Optimization Approach
arXiv

Interpretation

Upper-level parameters in bilevel optimization can be updated as matrices rather than flattened into vectors and moved coordinate by coordinate. Nearly all prior bilevel methods took the flattened-vector route, vectorizing weight matrices and applying coordinate-wise updates, so they did not exploit the matrix structure common in neural networks. A quadratic bilevel example shows lower-level Hessian conditioning is squared through the bilevel composition, making upper-level hypergradient singular values highly unequal, so flattened updates are dominated by a few spectral directions.

The design separates hypergradient estimation from the orthogonalized update: the lower level tracks its moving solution with warm-started stochastic gradient descent, the upper level estimates the hypergradient with a truncated Neumann series, and Muon-style orthogonalization is applied only to the final upper-level momentum. Muon-style orthogonalization normalizes singular values to curb the dominance of large spectral components, but its convergence guarantees had been established only for single-level stochastic optimization, without lower-level tracking or implicit hypergradient errors. Both the exact-polar and finite Newton–Schulz versions reach a finite-time convergence rate, with sample complexity matching the best known for single-level Muon-type methods; on CIFAR-10 representation learning, both variants reach lower optimized upper-level validation loss than the shared baselines under the same stochastic derivative budget.

Perspective

The demonstrated scope is matrix-valued upper-level representation learning on frozen pretrained features and blockwise stepsize allocation with controlled block sensitivities; the convergence results rest on lower-level strong convexity, smoothness and unbiased stochastic derivative assumptions.

The theoretical spectral-imbalance amplification comes from a quadratic model with isotropic validation curvature and aligned displacements, a local second-order mechanism rather than a general identity for arbitrary smooth bilevel problems; the pointwise approximation result for finite Newton–Schulz does not by itself give the run-wise error condition used in the theorem.