Steepest descent under four norms

To first order a step Δ changes the loss by ⟨g, Δ⟩. The steepest-descent step of size η is the point of the norm ball of radius η that lies furthest along −g. Change the ball and the direction changes: the Euclidean ball gives −g, the ℓ_∞ box gives −sign(g), the ℓ₁ diamond gives a single coordinate, and an ellipse (a Mahalanobis or Fisher norm) gives −M⁻¹g.

Drag the black arrow tip, or tap anywhere, to set the gradient g. Arrow keys nudge it when the plot has focus.

Ellipse aspect

Ellipse angle

Radius η

ℓ₂ (GD) ℓ_∞ (sign descent) ℓ₁ (coordinate descent) Mahalanobis (natural gradient) supporting lines (trust region)

Try:

norm	‖g‖_*	step Δ	⟨g,Δ⟩	∠(Δ,−g)

How to read it. The black arrow is the gradient g; the grey arrow is −g. Each coloured shape is the ball {Δ : ‖Δ‖ ≤ η} of one norm. In trust-region mode the dashed line through each coloured arrowhead is the supporting line ⟨g, Δ⟩ = −η‖g‖_*, a level set of the linear function ⟨g, ·⟩ (the gradient acting as a covector): it is perpendicular to g and touches the ball at the steepest-descent step, so no other point of the ball gets further along −g. The table gives the dual norm ‖g‖_* = max_‖d‖≤1 ⟨g, d⟩ and the first-order loss change of each step.

Trust region vs squared penalty. The trust-region step minimizes ⟨g,Δ⟩ subject to ‖Δ‖ ≤ η and always has length η in its own norm. The penalty step minimizes ⟨g,Δ⟩ + ‖Δ‖²/(2η); it points the same way but is η‖g‖_* long, so it shrinks as the gradient does. In ℓ₂ the penalty step is plain gradient descent, −ηg; in the Mahalanobis norm it is −ηM⁻¹g (natural gradient when M is the Fisher matrix); in ℓ_∞ it is −η‖g‖₁sign(g).

Where Muon fits. Read the two coordinates as the diagonal entries of a 2×2 weight matrix diag(θ₁, θ₂). Its spectral norm is max(|θ₁|, |θ₂|), so the spectral-norm ball is the ℓ_∞ box, and the exact spectral steepest direction UV^⊤ = diag(sign g₁, sign g₂) is the sign-descent step. Where spectral steepest descent and sign descent differ (matrices with off-diagonal structure, §4.1.C), and where practical Muon differs from both (its approximate Newton–Schulz orthogonalization, §4.4), a 2D picture cannot show.

Things to notice. Rotate g slowly: the ℓ_∞ direction jumps between corners when a gradient component changes sign, and near that point the whole edge of the box is almost as good, which is why sign descent is sensitive to small gradient components. The Mahalanobis direction is pulled toward the long axis of the ellipse, the direction in which the norm counts steps as cheap; set the aspect to 1 and it coincides with ℓ₂.