← All setups

Batched Polar Matrix Optimization

Descriptions may be stale. Consult the linked Lean sources.

Batched Polar Matrix Optimization

We consider minimizing a differentiable, possibly nonconvex function f:Rm×n→R, where m,n are nonnegative integers. Its gradient is L-Lipschitz from the spectral norm to the nuclear norm, with L>0, and a given starting matrix x0 has objective gap at most Δ≥0 above a global lower bound. The oracle returns unbiased stochastic gradients using independent, identically distributed samples, with rowwise standard deviations summing to at most s≥0 in a fixed orthonormal basis. Batched polar updates must produce a random output x¯ satisfying E∥∇f(x¯)∥∗≤ε, where ∥⋅∥∗ is the nuclear norm, ε>0, and expectation includes sampling and algorithm randomness.

The optimization problem is infx∈Rm×nf(x). Equip the matrix space with the Frobenius inner product ⟨U,V⟩F=tr(U⊤V) and its norm ∥⋅∥F; gradients are taken with respect to this inner product. Write ∥⋅∥op for the induced Euclidean operator norm, also called the spectral norm. Its dual under the Frobenius pairing is the nuclear norm: ∥G∥∗=sup∥U∥op≤1⟨G,U⟩F. The algorithm receives m,n,L,Δ,s,ε, and x0; the objective and the oracle’s distributional model are accessible only through queries.

Our assumptions:

Assumption 1 (Spectral smoothness). The function f is Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥∗≤L∥x−y∥op,x,y∈Rm×n.

Assumption 2 (Lower bound and initial gap). There exists fmin∈R such that fmin≤f(x)for every x∈Rm×n,f(x0)−fmin≤Δ.

Assumption 3 (Unbiased oracle with a row variance profile). Let ν be a probability measure on a measurable sample space Ω. The oracle is specified by a jointly measurable map g:Rm×n×Ω→Rm×n. For every x, the random matrix g(x,ξ) is Bochner integrable for ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x). There exist a fixed orthonormal basis (bi)i=1m of Rm and numbers σi≥0 with ∑i=1mσi≤s. For every x and i, the vector (g(x,ξ)−∇f(x))⊤bi∈Rn belongs to L2(ν;Rn) and satisfies Eξ∼ν[∥(g(x,ξ)−∇f(x))⊤bi∥22]≤σi2. At call k≥0, a query x receives g(x,ξk), where the measurable sample variables (ξk)k≥0 are mutually independent with common law ν. Algorithm randomness is independent of the entire sample sequence.

Our formulation is algorithm-specific: we analyze batched polar updates. Define the polar direction as the minimum-Frobenius-norm maximizer of the linear objective over the spectral unit ball: S(G)=argmax∥U∥op≤1⟨G,U⟩F,polar(G)=argminU∈S(G)∥U∥F. The second minimizer is unique, including at rank-deficient G. The method chooses a constant step size η>0, a batch size B∈{1,2,…}, and an integer T≥0 from its inputs. Starting at the given x0, it makes B queries at each xt, for t=0,…,T, and follows Gt=1B∑j=0B−1g(xt,ξBt+j),xt+1=xt−ηpolar(Gt). These query and update rules must hold for every possible sequence of oracle replies. A measurable index J, drawn from the algorithm’s randomness independently of the samples, is uniform on {0,…,T}. After B(T+1) oracle calls, the output is x¯=xJ. The output remains xJ after any additional calls. The call count includes the batch at xT, although the output is selected from x0,…,xT.

Let P be the joint law of the algorithm randomness and the sample sequence. The output must be measurable, its gradient’s nuclear norm must be integrable under P, and the required accuracy is EP[∥∇f(x¯)∥∗]≤ε.

Results

Differentiable f:Rm×n→R satisfies ∥∇f(X)−∇f(Y)∥∗≤L∥X−Y∥op, f≥fmin and f(X0)−fmin≤Δ, with L,ε>0 and Δ,s≥0. The jointly measurable, integrable oracle G(X,ξ) uses IID samples and satisfies EG(X,ξ)=∇f(X). For a fixed orthonormal basis (bi)i=1m and σi≥0, E∥[G(X,ξ)−∇f(X)]⊤bi∥22≤σi2 and ∑iσi≤s. The setup requires constant-step, momentum-free batched polar updates and a uniformly selected iterate X^; the target is E∥∇f(X^)∥∗≤ε.

Batched Muon under BatchedSpectralSmooth.
Result Oracle complexity Novelty Limitations
(1) MuonNoiseSeparation (Ours) (review) O((1+s2/ε2)(1+LΔ/ε2))
(2) Muon (Tao et al. 2026, Theorem 4, v1) O(1+LΔε2+LΔ∥Σ∥∗2ε4). Restricted to E[NN⊤∣F]⪯Σ2. (1): Row-profile extension. For varying-sign rank-one noise, s=r=m≤n, ∥Σ∥∗≥rs: if r≥ε, LΔ≥ε2, costs are O(LΔr2/ε4) versus O(LΔr3/ε4). This improves the statement’s certification, not the method; see (3). (1): At s=∥Σ∥∗, extra s2/ε2 cost when s>ε, 2LΔ≤ε2. Requires IID samples and gradient-Lipschitz smoothness; (2) allows conditional sampling and a quadratic remainder bound.
(3) Derived bound (Tao et al. 2026, Appendix D.1) O(1+LΔε2+LΔs2ε4). Same row-profile model; substitute E∥N―B∥∗≤s/B. (1): Matches known rate for LΔ≥ε2; formal verification with explicit constants. Row-profile substitution leaves the descent argument unchanged. (1): Extra s2/ε2 cost when s>ε, 2LΔ≤ε2.

Abbr: Costs count individual stochastic-gradient calls, including every batch sample. ∥⋅∥∗: nuclear norm; ∥⋅∥op: spectral norm; N=G−∇f: noise; N―B: mean of B noise samples; Σ: fixed positive semidefinite covariance envelope; F: sampling history; r: number of rows in the varying-sign example.

Tao, Hongyi, Dingzhi Yu, and Lijun Zhang. 2026. When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-Norm Lower Bounds. https://doi.org/10.48550/arXiv.2605.06615.

Lean setup