Which Way Is Down? First-Order Optimizers as a Choice of Norm

13 October 2026 · Download PDF · Download code

We consider the general optimization problem

min_{𝜃 \in Θ} 𝒥︀ (𝜃),

(1)

where $Θ$ is a vector space and $𝒥︀$ is differentiable. First-order methods solve it iteratively: starting from $𝜃_{0}$ , they take steps $𝜃_{𝑡 + 1} = 𝜃_{𝑡} + ℎ_{𝑡}$ , where each step $ℎ_{𝑡}$ is computed from the derivative $𝐷 𝒥︀ (𝜃_{𝑡})$ , and possibly from earlier ones. This post is about how to choose $ℎ_{𝑡}$ , and in particular how the choice of a norm on $Θ$ affects it.

1. Derivatives and gradients

The derivative $𝐷 𝒥︀ (𝜃)$ maps a direction $ℎ \in Θ$ to a number, so it is an element of the dual space $Θ^{*}$ of linear maps $Θ \to ℝ$ , and we write its value at $ℎ$ as the pairing $⟨ 𝐷 𝒥︀ (𝜃), ℎ ⟩$ . Both $Θ^{*}$ and the pairing come with $Θ$ itself, so nothing is chosen here. An inner product $⟨ \cdot, \cdot ⟩_{Θ}$ on $Θ$ , on the other hand, is a choice, for example the Frobenius inner product. With an inner product chosen, the linearization reads

𝒥︀ (𝜃 + ℎ) \approx 𝒥︀ (𝜃) + ⟨ 𝐷 𝒥︀ (𝜃), ℎ ⟩ = 𝒥︀ (𝜃) + ⟨ \nabla_{𝜃} 𝒥︀ (𝜃), ℎ ⟩_{Θ} .

(2)

The second form holds because every linear map $Θ \to ℝ$ is $ℎ \mapsto ⟨ 𝑘, ℎ ⟩_{Θ}$ for exactly one $𝑘 \in Θ$ , its Riesz representative,¹¹ This is the Riesz representation theorem, as in Batched Backpropagation as a Linear Solve: $𝑘 \mapsto ⟨ 𝑘, \cdot ⟩_{Θ}$ is linear and one-to-one, and $Θ$ and $Θ^{*}$ have the same dimension. and the gradient $\nabla_{𝜃} 𝒥︀ (𝜃)$ is the representative of $𝐷 𝒥︀ (𝜃)$ . Unlike the derivative, the gradient lies in $Θ$ , but it depends on the inner product: another inner product gives another gradient of the same function. Only the gradient needs an inner product. The derivative and the steps below need none.

Example 1: Two inner products, two gradients

Example 1 (Two inner products, two gradients) Let $Θ = ℝ^{2}$ and $𝒥︀ (𝜃) = 𝜃_{1}^{2} + 𝜃_{2}$ , so that $⟨ 𝐷 𝒥︀ (𝜃), ℎ ⟩ = 2 𝜃_{1} ℎ_{1} + ℎ_{2}$ .²² This follows from $𝒥︀$ alone, as the directional derivative $d / (d 𝑡) 𝒥︀ (𝜃 + 𝑡 ℎ) |_{𝑡 = 0} = 2 𝜃_{1} ℎ_{1} + ℎ_{2}$ , with no inner product involved. Writing the derivative as the array $(2 𝜃_{1}, 1)$ uses the coordinates of $Θ = ℝ^{2}$ , but the value of the pairing does not depend on them. Then

\begin{aligned} ⟨ ℎ, 𝑘 ⟩_{Θ} = ℎ_{1} 𝑘_{1} + ℎ_{2} 𝑘_{2} & \Rightarrow \nabla_{𝜃} 𝒥︀ (𝜃) = (2 𝜃_{1}, 1), \\ ⟨ ℎ, 𝑘 ⟩_{Θ} = ℎ_{1} 𝑘_{1} + 4 ℎ_{2} 𝑘_{2} & \Rightarrow \nabla_{𝜃} 𝒥︀ (𝜃) = (2 𝜃_{1}, 1 / 4), \end{aligned}

(3)

since both give $⟨ \nabla_{𝜃} 𝒥︀ (𝜃), ℎ ⟩_{Θ} = 2 𝜃_{1} ℎ_{1} + ℎ_{2}$ .

2. Two surrogates

The linearization $𝒥︀ (𝜃) + ⟨ 𝑔, ℎ ⟩$ , with $𝑔 = 𝐷 𝒥︀ (𝜃)$ , is a good model of $𝒥︀ (𝜃 + ℎ)$ only for small $ℎ$ , and on its own it has no minimizer: unless $𝑔 = 0$ , it decreases without bound along any direction with $⟨ 𝑔, ℎ ⟩ < 0$ . A step therefore needs a second ingredient that says how large $ℎ$ we allow. The length of $ℎ \in Θ$ is measured by a norm $‖ \cdot ‖$ , which is something that we again have to choose. There are two natural ways to combine the norm with the linearization: as a constraint, or as a penalty,³³ The norm here can be any norm on $Θ$ , not just the one induced by the inner product on $Θ$ .

\begin{aligned} ℎ_{𝐶} & = \underset{‖ ℎ ‖ \leq 𝜂}{arg min} ⟨ 𝑔, ℎ ⟩, \\ ℎ_{𝑃} & = \underset{ℎ \in Θ}{arg min} ⟨ 𝑔, ℎ ⟩ + \frac{𝜆}{2} {‖ ℎ ‖}^{2} . \end{aligned}

(4)

The first is a trust-region model: it trusts the linearization only within a radius $𝜂$ , which caps the length of the step. The second instead penalizes long steps, and as the penalty grows faster than the linearization can decrease, it always has a minimum.⁴⁴ If $𝒥︀$ is $𝐿$ -smooth with respect to $‖ \cdot ‖$ , meaning that $𝒥︀ (𝜃 + ℎ) \leq 𝒥︀ (𝜃) + ⟨ 𝑔, ℎ ⟩ + \frac{𝐿}{2} {‖ ℎ ‖}^{2}$ for all $ℎ$ , then for $𝜆 \geq 𝐿$ the second surrogate is an upper bound on $𝒥︀$ , and $ℎ_{𝑃}$ decreases $𝒥︀$ by at least the decrease of the surrogate. Convergence analyses use this; in practice $𝜆$ is often chosen smaller.

Interactive figure 1: The two surrogates over many steps

Interactive figure 1 (The two surrogates over many steps) The graph shows both steps for

𝒥︀ (𝜃) = 3 𝜃^{2} / 4 - 5 / 4 log cosh 𝜃,

(5)

with the norm $| ℎ |$ . In one dimension every norm is a multiple of $| ℎ |$ , so the choice of norm only matters from two dimensions on. The constrained step always has length $𝜂$ , since the linearization has no minimum inside the trust region, so close to the minimum it jumps back and forth over it. The penalized step shrinks with the derivative, but with $𝜆 = 𝐿$ set by the largest curvature it crawls where $𝒥︀$ is flat. Constrained methods such as sign descent and Muon therefore let $𝜂$ decrease over the iterations, while adaptive norms, later in the post, take longer steps where $𝒥︀$ is flat.

𝜂

𝜆

1.5

𝑘

At iteration $𝑘$ , the dashed line is the linearization at the constrained iterate $𝜃_{𝑘}$ , with the trust region $| ℎ | \leq 𝜂$ shaded, and the dashed parabola is the quadratic model at the penalized iterate $𝜃_{𝑘}$ . Drag $𝜃_{0}$ , change $𝜂$ and $𝜆$ , and step through the iterations with $𝑘$ .

3. The dual norm and the sharp operator

To write the solutions of the constrained and penalized problems in (4) explicitly, we need two things: the dual norm, which measures the size of a derivative in $Θ^{*}$ , and the sharp operator, which maps a derivative back to an element of $Θ$ . In both cases it is important to note that they depend on the choice of a norm on $Θ$ , rather than the inner product on $Θ$ .

Definition 1: Dual norm and sharp operator

Definition 1 (Dual norm and sharp operator) For a norm $‖ \cdot ‖$ on $Θ$ , the dual norm of $𝑔 \in Θ^{*}$ and the sharp of $𝑔$ , $𝑔^{♯} \in Θ$ , are

{‖ 𝑔 ‖}_{*} = max_{‖ ℎ ‖ \leq 1} ⟨ 𝑔, ℎ ⟩, 𝑔^{♯} = - \underset{ℎ \in Θ}{arg min} ⟨ 𝑔, ℎ ⟩ + \frac{1}{2} {‖ ℎ ‖}^{2} .

(6)

The dual norm is the slope of the linearization in its steepest direction; that is, a step of unit length with respect to the chosen norm changes the linearization by at most ${‖ 𝑔 ‖}_{*}$ , so that $| ⟨ 𝑔, ℎ ⟩ | \leq {‖ 𝑔 ‖}_{*} ‖ ℎ ‖$ for all $ℎ \in Θ$ . The sharp operator, the map $𝑔 \mapsto 𝑔^{♯}$ , takes $𝑔$ back to $Θ$ : $- 𝑔^{♯}$ is the penalized step for $𝜆 = 1$ , and its direction and length are set by the dual norm,⁵⁵ Write $ℎ = 𝑡 𝑢$ with $𝑡 \geq 0$ and $‖ 𝑢 ‖ = 1$ . For a fixed $𝑡$ , the best $𝑢$ has $⟨ 𝑔, 𝑢 ⟩ = - {‖ 𝑔 ‖}_{*}$ , which leaves $- 𝑡 {‖ 𝑔 ‖}_{*} + 𝑡^{2} / 2$ , smallest at $𝑡 = {‖ 𝑔 ‖}_{*}$ .

⟨ 𝑔, 𝑔^{♯} ⟩ = {‖ 𝑔 ‖}_{*}^{2} and ‖ 𝑔^{♯} ‖ = {‖ 𝑔 ‖}_{*} .

(7)

The minus sign is a convention. Like a gradient, $𝑔^{♯}$ points where $𝒥︀$ increases, and a step subtracts it. When the minimizer is not unique, $𝑔^{♯}$ is any one of them.

The sharp operator is the map from $Θ^{*}$ back to $Θ$ that a norm provides, while the Riesz map is the one that an inner product provides.⁶⁶ The two coincide exactly when the norm comes from the inner product, ${‖ ℎ ‖}^{2} = ⟨ ℎ, ℎ ⟩_{Θ}$ . The naming convention and notation $𝑔^{♯}$ follow Kelner et al. [1].⁷⁷ Bernstein and Newhouse [2] call $𝑔^{♯} / {‖ 𝑔 ‖}_{*}$ the duality map. Both the constrained and the penalized steps can be written explicitly using the sharp operator. The constrained problem is bounded below by $⟨ 𝑔, ℎ ⟩ \geq - {‖ 𝑔 ‖}_{*} ‖ ℎ ‖ \geq - 𝜂 {‖ 𝑔 ‖}_{*}$ ,⁸⁸ The first inequality is the bound $| ⟨ 𝑔, ℎ ⟩ | \leq {‖ 𝑔 ‖}_{*} ‖ ℎ ‖$ from the definition of the dual norm. The second holds because the constraint gives $‖ ℎ ‖ \leq 𝜂$ and ${‖ 𝑔 ‖}_{*} \geq 0$ . which the step below attains, and writing $ℎ = 𝑘 / 𝜆$ turns the penalized problem into the definition. For $𝑔 \neq 0$ ,

\begin{aligned} ℎ_{𝐶} & = \underset{‖ ℎ ‖ \leq 𝜂}{arg min} ⟨ 𝑔, ℎ ⟩ = - 𝜂 \frac{𝑔^{♯}}{{‖ 𝑔 ‖}_{*}}, \\ ℎ_{𝑃} & = \frac{1}{𝜆} \underset{𝑘 \in Θ}{arg min} ⟨ 𝑔, 𝑘 ⟩ + \frac{1}{2} {‖ 𝑘 ‖}^{2} = - \frac{1}{𝜆} 𝑔^{♯} . \end{aligned}

(8)

Here $𝑔^{♯} / {‖ 𝑔 ‖}_{*}$ is the unit vector, in the chosen norm, along $𝑔^{♯}$ , so $ℎ_{𝐶}$ goes straight to the border of the trust region. Both steps point along $- 𝑔^{♯}$ , which depends on the chosen norm, and differ only in length: $𝜂$ for $ℎ_{𝐶}$ and ${‖ 𝑔 ‖}_{*} / 𝜆$ for $ℎ_{𝑃}$ , so they coincide for $𝜆 = {‖ 𝑔 ‖}_{*} / 𝜂$ .

Example 2: The dual norm and the sharp operator in the plane

Example 2 (The dual norm and the sharp operator in the plane) Let $Θ = ℝ^{2}$ and $⟨ 𝑔, ℎ ⟩ = 3 ℎ_{1} + 4 ℎ_{2}$ . For the Euclidean norm ${‖ ℎ ‖}_{2} = \sqrt{ℎ_{1}^{2} + ℎ_{2}^{2}}$ ,

\begin{aligned} {‖ 𝑔 ‖}_{*} & = max_{{‖ ℎ ‖}_{2} \leq 1} 3 ℎ_{1} + 4 ℎ_{2} = 5, \\ 𝑔^{♯} & = - \underset{ℎ \in ℝ^{2}}{arg min} 3 ℎ_{1} + 4 ℎ_{2} + \frac{1}{2} (ℎ_{1}^{2} + ℎ_{2}^{2}) = (3, 4) . \end{aligned}

(9)

By the Cauchy–Schwarz inequality, $3 ℎ_{1} + 4 ℎ_{2} \leq 5 {‖ ℎ ‖}_{2}$ , with equality at $ℎ = (3, 4) / 5$ , and in the problem for $𝑔^{♯}$ , setting the derivative $(3 + ℎ_{1}, 4 + ℎ_{2})$ of the objective to zero gives the minimizer $ℎ = (- 3, - 4)$ , so $𝑔^{♯} = (3, 4)$ , the gradient for the Euclidean inner product. For the max-norm ${‖ ℎ ‖}_{\infty} = max (| ℎ_{1} |, | ℎ_{2} |)$ ,

\begin{aligned} {‖ 𝑔 ‖}_{*} & = max_{{‖ ℎ ‖}_{\infty} \leq 1} 3 ℎ_{1} + 4 ℎ_{2} = 7, \\ 𝑔^{♯} & = - \underset{ℎ \in ℝ^{2}}{arg min} 3 ℎ_{1} + 4 ℎ_{2} + \frac{1}{2} {max (| ℎ_{1} |, | ℎ_{2} |)}^{2} = (7, 7) . \end{aligned}

(10)

Both coordinates can be moved as far as allowed, so the maximum is $3 + 4$ at $ℎ = (1, 1)$ . For the minimum, fix $𝑡 = max (| ℎ_{1} |, | ℎ_{2} |)$ : the linear part is then smallest at $ℎ = (- 𝑡, - 𝑡)$ , which leaves $- 7 𝑡 + 𝑡^{2} / 2$ , smallest at $𝑡 = 7$ . In both cases $⟨ 𝑔, 𝑔^{♯} ⟩ = {‖ 𝑔 ‖}_{*}^{2}$ and $‖ 𝑔^{♯} ‖ = {‖ 𝑔 ‖}_{*}$ . The same derivative gives different directions for different norms.⁹⁹ The same argument gives $𝑔^{♯} = {‖ 𝑔 ‖}_{1} sign (𝑔)$ for the max-norm, and this map is not linear: ${(3, 4)}^{♯} + {(- 1, 2)}^{♯} = (7, 7) + (- 3, 3) = (4, 10)$ , while ${(2, 6)}^{♯} = (8, 8)$ . So the max-norm is not the norm of any inner product, whose sharp operator, the Riesz map, is linear.

Interactive figure 2: The sharp operator

Interactive figure 2 (The sharp operator) The graph shows the definition for $𝑔 = (3, 4)$ of the example above and the $ℓ_{𝑝}$ -norms ${‖ ℎ ‖}_{𝑝} = {({| ℎ_{1} |}^{𝑝} + {| ℎ_{2} |}^{𝑝})}^{1 / 𝑝}$ , which give the Euclidean norm for $𝑝 = 2$ and the max-norm for $𝑝 = \infty$ . Its contours are those of $𝜑 (ℎ) = ⟨ 𝑔, ℎ ⟩ + 1 / 2 {‖ ℎ ‖}^{2}$ , which is smallest at $- 𝑔^{♯}$ . The dual norm shows in two places: $- 𝑔^{♯}$ lies on the border $‖ ℎ ‖ = {‖ 𝑔 ‖}_{*}$ of the ball $‖ ℎ ‖ \leq {‖ 𝑔 ‖}_{*}$ , and the level set $⟨ 𝑔, ℎ ⟩ + {‖ 𝑔 ‖}_{*}^{2} = 0$ , a line in the plane, touches the ball there. Only $𝑝 = 2$ comes from an inner product. For every other $𝑝$ the sharp operator is nonlinear, and for $𝑝$ near $1$ or $\infty$ it jumps between corners of the ball as $𝑔$ is dragged, which no linear map can do.

𝑝

The ball is shaded and the line dashed, with $- 𝑔^{♯}$ drawn from the origin. Drag $𝑔$ , change $𝑝$ from $1$ to $\infty$ , and drag the point $ℎ$ to check that no point has a smaller value $𝜑 (ℎ)$ than $- 𝑔^{♯}$ .

4. The effect of the chosen norm

Once the norm is chosen, the step is fixed. To write the steps down, we need coordinates. Let $Θ = ℝ^{𝑚 \times 𝑛}$ , so that $𝜃$ is a matrix, for example the weights of a layer in a neural network. The derivative is then represented by the matrix $𝐺$ of partial derivatives $𝜕 𝒥︀ / 𝜕 𝜃_{𝑎 𝑏}$ , with

⟨ 𝑔, ℎ ⟩ = ⟨ 𝐺, ℎ ⟩_{𝐹} = tr (𝐺^{⊤} ℎ), 𝑔 = 𝐷 𝒥︀ (𝜃) .

(11)

This uses the Frobenius inner product, which makes $𝐺$ the Riesz representative of $𝑔$ : the gradient for the Frobenius inner product.¹⁰¹⁰ This might seem like a limitation, but as shown in Section 4.1 every inner product on $Θ$ can be written using the Frobenius inner product. Some norms on $Θ$ , such as the max-norm, only look at the entries of $ℎ$ , as if the matrix were one long vector of $𝑚 𝑛$ numbers. Others, such as the spectral norm, use that $𝜃$ is a matrix, a linear map from inputs to outputs, which is what the weights of a layer are. For matrices, ${‖ \cdot ‖}_{1}$ and ${‖ \cdot ‖}_{\infty}$ act on the entries as for vectors, while ${‖ \cdot ‖}_{2}$ is the spectral norm, the largest singular value. Each norm then gives a dual norm and a sharp operator in terms of $𝐺$ , and with them a known method. Since both the constrained and the penalized steps follow from ${‖ 𝑔 ‖}_{*}$ and $𝑔^{♯}$ , each example shows only the one that gives the known method. The other step is a rescaled version of it, for example normalized gradient descent in place of gradient descent. The table below collects the norms of this section.¹¹¹¹ The downloadable code computes $𝑔^{♯}$ for the Frobenius norm, a diagonal inner product, the max-norm, and the spectral norm by solving the defining problem as a small conic program [3], and prints it next to the closed form.

Table 1: Three norms and the methods they give. For the first row the method is the penalized step $- 𝑔^{♯} / 𝜆$ , and for the last two it is the constrained step $- 𝜂 𝑔^{♯} / {‖ 𝑔 ‖}_{*}$ .

Norm on $Θ$	${‖ 𝑔 ‖}_{*}$	$𝑔^{♯}$	Method
Inner product	${‖ {𝒜︀}^{- 1} (𝐺) ‖}_{𝒜︀}$	${𝒜︀}^{- 1} (𝐺)$	Gradient descent
Max-norm	${‖ 𝐺 ‖}_{1}$	${‖ 𝐺 ‖}_{1} sign (𝐺)$	Sign descent
Spectral	${‖ 𝐺 ‖}_{nuc}$	${‖ 𝐺 ‖}_{nuc} 𝑈 𝑉^{⊤}$	Muon

The norms fall into two families. A norm from an inner product has a linear sharp operator, the Riesz map, and its step is a preconditioned gradient step. Every other norm has a nonlinear sharp operator, and its step is not the gradient for any fixed inner product, one that does not depend on $𝑔$ .

4.1. Norms from an inner product

Every inner product on $Θ$ can be written as

⟨ ℎ, 𝑘 ⟩_{𝒜︀} = ⟨ 𝒜︀ (ℎ), 𝑘 ⟩_{𝐹}

(12)

where the linear map $𝒜︀ : Θ \to Θ$ is symmetric and positive definite, i.e.,

⟨ 𝒜︀ (ℎ), 𝑘 ⟩_{𝐹} = ⟨ ℎ, 𝒜︀ (𝑘) ⟩_{𝐹} and ⟨ 𝒜︀ (ℎ), ℎ ⟩_{𝐹} > 0 for all ℎ \neq 0 .

(13)

Since $⟨ 𝑔, ℎ ⟩ = ⟨ 𝐺, ℎ ⟩_{𝐹} = ⟨ {𝒜︀}^{- 1} (𝐺), ℎ ⟩_{𝒜︀}$ ,¹²¹² We look for the $𝑘 \in Θ$ with $⟨ 𝑘, ℎ ⟩_{𝒜︀} = ⟨ 𝐺, ℎ ⟩_{𝐹}$ for all $ℎ$ . By the definition of $⟨ \cdot, \cdot ⟩_{𝒜︀}$ , the left side is $⟨ 𝒜︀ (𝑘), ℎ ⟩_{𝐹}$ , so $⟨ 𝒜︀ (𝑘) - 𝐺, ℎ ⟩_{𝐹} = 0$ for all $ℎ$ , which gives $𝒜︀ (𝑘) = 𝐺$ and $𝑘 = {𝒜︀}^{- 1} (𝐺)$ . The inverse exists because $𝒜︀$ is positive definite. the gradient for $⟨ \cdot, \cdot ⟩_{𝒜︀}$ is $\nabla_{𝒜︀} 𝒥︀ = {𝒜︀}^{- 1} (𝐺)$ .¹³¹³ In Example 1, the second inner product is $𝒜︀ = diag (1, 4)$ , and its gradient $(2 𝜃_{1}, 1 / 4)$ is ${𝒜︀}^{- 1}$ applied to the first. The inverse ${𝒜︀}^{- 1}$ may look unusual, but it is the familiar preconditioner of scientific computing, where a problem is rescaled before it is solved: a gradient step with $\nabla_{𝒜︀} 𝒥︀$ is plain gradient descent in the rescaled variables $𝜉 = {𝒜︀}^{1 / 2} (𝜃)$ .¹⁴¹⁴ With $𝜉 = {𝒜︀}^{1 / 2} (𝜃)$ , the derivative of $𝒥︀ ({𝒜︀}^{- 1 / 2} (𝜉))$ is represented by ${𝒜︀}^{- 1 / 2} (𝐺)$ , so a gradient step in $𝜉$ changes $𝜉$ by $- \frac{1}{𝜆} {𝒜︀}^{- 1 / 2} (𝐺)$ , and $𝜃 = {𝒜︀}^{- 1 / 2} (𝜉)$ by $- \frac{1}{𝜆} {𝒜︀}^{- 1} (𝐺)$ . With $𝒜︀$ close to the curvature of $𝒥︀$ , the rescaled problem is well conditioned, and the step comes close to Newton’s method.

Example 3: Preconditioned gradient descent

Example 3 (Preconditioned gradient descent) Let ${‖ ℎ ‖}^{2} = ⟨ ℎ, ℎ ⟩_{𝒜︀}$ , so that $⟨ 𝑔, ℎ ⟩ = ⟨ \nabla_{𝒜︀} 𝒥︀, ℎ ⟩_{𝒜︀}$ with the gradient $\nabla_{𝒜︀} 𝒥︀ = {𝒜︀}^{- 1} (𝐺)$ . Then

\begin{aligned} {‖ 𝑔 ‖}_{*} & = max_{{‖ ℎ ‖}_{𝒜︀} \leq 1} ⟨ \nabla_{𝒜︀} 𝒥︀, ℎ ⟩_{𝒜︀} = {‖ \nabla_{𝒜︀} 𝒥︀ ‖}_{𝒜︀} = ⟨ 𝐺, {𝒜︀}^{- 1} (𝐺) ⟩_{𝐹}^{1 / 2}, \\ 𝑔^{♯} & = - \underset{ℎ \in Θ}{arg min} ⟨ \nabla_{𝒜︀} 𝒥︀, ℎ ⟩_{𝒜︀} + \frac{1}{2} {‖ ℎ ‖}_{𝒜︀}^{2} = \nabla_{𝒜︀} 𝒥︀ . \end{aligned}

(14)

By the Cauchy–Schwarz inequality, $⟨ \nabla_{𝒜︀} 𝒥︀, ℎ ⟩_{𝒜︀} \leq {‖ \nabla_{𝒜︀} 𝒥︀ ‖}_{𝒜︀} {‖ ℎ ‖}_{𝒜︀}$ , with equality at $ℎ = \nabla_{𝒜︀} 𝒥︀ / {‖ \nabla_{𝒜︀} 𝒥︀ ‖}_{𝒜︀}$ . In the problem for $𝑔^{♯}$ , completing the square gives

⟨ \nabla_{𝒜︀} 𝒥︀, ℎ ⟩_{𝒜︀} + \frac{1}{2} {‖ ℎ ‖}_{𝒜︀}^{2} = \frac{1}{2} {‖ ℎ + \nabla_{𝒜︀} 𝒥︀ ‖}_{𝒜︀}^{2} - \frac{1}{2} {‖ \nabla_{𝒜︀} 𝒥︀ ‖}_{𝒜︀}^{2},

(15)

which is smallest at $ℎ = - \nabla_{𝒜︀} 𝒥︀$ , so $𝑔^{♯} = \nabla_{𝒜︀} 𝒥︀$ . The sharp operator is the Riesz map, and the penalized step

ℎ_{𝑃} = - \frac{1}{𝜆} {𝒜︀}^{- 1} (𝐺)

(16)

is preconditioned gradient descent with the preconditioner ${𝒜︀}^{- 1}$ , and for the Frobenius norm, $𝒜︀ = ℐ︀$ , plain gradient descent.

Interactive figure 3: A norm from an inner product

Interactive figure 3 (A norm from an inner product) The graph shows the constrained step for an inner product on $ℝ^{2}$ , $⟨ ℎ, 𝑘 ⟩_{𝒜︀} = ℎ^{⊤} 𝐴 𝑘$ , where

𝐴 = 𝑅_{𝜑} [\begin{matrix} 1 & 0 \\ 0 & 𝜅 \end{matrix}] 𝑅_{𝜑}^{⊤}, 𝑅_{𝜑} = [\begin{matrix} cos 𝜑 & - sin 𝜑 \\ sin 𝜑 & cos 𝜑 \end{matrix}],

(17)

has the eigenvalues $1$ and $𝜅$ , with eigenvectors turned by the angle $𝜑$ . The unit ball is an ellipse, and the step $ℎ_{𝐶} = - 𝐴^{- 1} 𝑔 / {‖ 𝑔 ‖}_{*}$ , for $𝜂 = 1$ , is where the line $⟨ 𝑔, ℎ ⟩ + {‖ 𝑔 ‖}_{*} = 0$ touches it. Unlike the steps for $𝑝 = 1$ and $𝑝 = \infty$ , it never jumps between corners, and unlike the steps of the other $ℓ_{𝑝}$ -norms, its direction depends linearly on $𝑔$ , since the sharp operator $𝐴^{- 1}$ is linear.

𝜅

𝜑

Currently, $𝐴 =$

The Euclidean unit circle and the Euclidean step $- 𝑔 / ‖ 𝑔 ‖$ are dotted.

4.2. Norms not from inner products

Recall that the norm need not come from an inner product. Every method still minimizes the same linearization $⟨ 𝑔, ℎ ⟩$ , with the derivative $𝑔 = 𝐷 𝒥︀ (𝜃) \in Θ^{*}$ . What changes is the norm that limits the step, and with it the sharp operator, the map from $Θ^{*}$ back to $Θ$ . For a norm that does not come from an inner product, the sharp operator is nonlinear,¹⁵¹⁵ If $𝑔 \mapsto 𝑔^{♯}$ were linear, then ${‖ 𝑔 ‖}_{*}^{2} = ⟨ 𝑔, 𝑔^{♯} ⟩$ would be a quadratic form in $𝑔$ , so the dual norm would come from an inner product on $Θ^{*}$ , and then so would the norm on $Θ$ , its dual. so it is not the Riesz map of any fixed inner product, and the step is not a gradient for any inner product that does not depend on $𝑔$ . The max-norm is one such norm: as in the plane, $𝑔^{♯} = {‖ 𝐺 ‖}_{1} sign (𝐺)$ , and its constrained step $ℎ_{𝐶} = - 𝜂 sign (𝐺)$ is sign descent. The example below shows the spectral norm, whose constrained step is Muon.

Example 4: The spectral norm: Muon

Example 4 (The spectral norm: Muon) The spectral norm of a matrix $ℎ$ is its largest singular value, ${‖ ℎ ‖}_{2} = 𝜎_{max} (ℎ)$ . Let $𝜃 \in ℝ^{𝑚 \times 𝑛}$ be the weights of a linear layer $𝑍 = 𝜃 𝑋$ . A step $ℎ$ changes the outputs by $ℎ 𝑋$ , and the spectral norm is the largest such change relative to the inputs,

{‖ ℎ 𝑋 ‖}_{𝐹} \leq {‖ ℎ ‖}_{2} {‖ 𝑋 ‖}_{𝐹} for all 𝑋 .

(18)

As such, bounding the spectral norm effectively bounds the change of the outputs for every input. The dual norm and the sharp follow from the compact singular value decomposition $𝐺 = 𝑈 Σ 𝑉^{⊤} = \sum_{𝑘} 𝜎_{𝑘} 𝑢_{𝑘} 𝑣_{𝑘}^{⊤}$ , which keeps only the nonzero singular values,

\begin{aligned} {‖ 𝑔 ‖}_{*} & = max_{{‖ ℎ ‖}_{2} \leq 1} tr (𝐺^{⊤} ℎ) = {‖ 𝐺 ‖}_{nuc}, \\ 𝑔^{♯} & = - \underset{ℎ \in Θ}{arg min} tr (𝐺^{⊤} ℎ) + \frac{1}{2} {‖ ℎ ‖}_{2}^{2} = {‖ 𝐺 ‖}_{nuc} 𝑈 𝑉^{⊤} . \end{aligned}

(19)

By the cyclic property of the trace,

\begin{aligned} tr (𝐺^{⊤} ℎ) & = tr (𝑉 Σ 𝑈^{⊤} ℎ) = tr (Σ 𝑈^{⊤} ℎ 𝑉) \\ = \sum_{𝑘} 𝜎_{𝑘} {(𝑈^{⊤} ℎ 𝑉)}_{𝑘 𝑘} \leq \sum_{𝑘} 𝜎_{𝑘} = {‖ 𝐺 ‖}_{nuc}, \end{aligned}

(20)

since each diagonal entry of $𝑈^{⊤} ℎ 𝑉$ is at most its spectral norm, ${‖ 𝑈^{⊤} ℎ 𝑉 ‖}_{2} \leq {‖ ℎ ‖}_{2} \leq 1$ . Equality holds at $ℎ = 𝑈 𝑉^{⊤}$ , where $𝑈^{⊤} ℎ 𝑉 = 𝐼$ . For the minimum, fix $𝑡 = {‖ ℎ ‖}_{2}$ : the linear part is then smallest at $ℎ = - 𝑡 𝑈 𝑉^{⊤}$ , which leaves $- 𝑡 {‖ 𝐺 ‖}_{nuc} + 𝑡^{2} / 2$ , smallest at $𝑡 = {‖ 𝐺 ‖}_{nuc}$ . The nuclear norm, the sum of the singular values, is therefore not chosen but appears as the dual of the spectral norm. The constrained step

ℎ_{𝐶} = - 𝜂 𝑈 𝑉^{⊤}

(21)

is minus the matrix with the singular vectors of $𝐺$ and all its nonzero singular values set to $𝜂$ , while the zero ones stay zero. It is the update of Muon [4], applied to an averaged derivative as in the next section. In a network, the constraint is applied to each block.¹⁶¹⁶ That is, the norm is ${max}_{𝑖} {‖ ℎ_{𝑖} ‖}_{2}$ , as in Bernstein and Newhouse [2]. Its dual norm is $\sum_{𝑖} {‖ 𝐺_{𝑖} ‖}_{nuc}$ , and each block takes the step $- 𝜂 𝑈_{𝑖} 𝑉_{𝑖}^{⊤}$ . In practice, Muon computes $𝑈 𝑉^{⊤}$ with a few matrix products by a Newton–Schulz iteration, whose polynomials are improved by The Polar Express Algorithm, and uses $𝑈 𝑉^{⊤}$ only for the weight matrices of the hidden layers. Avoiding the SVD is what makes Muon practical for large networks: an SVD runs poorly on GPUs and needs high precision, while matrix products are fast even in low precision.

Interactive figure 4: The Muon step

Interactive figure 4 (The Muon step) Unlike the graphs above, this plane is not $Θ$ , which here is four-dimensional: it holds the vectors a $2 \times 2$ block acts on, and each matrix is shown through its image of the unit circle. The block $𝐺$ maps the unit circle to an ellipse with the semi-axes $𝜎_{1} 𝑢_{1}$ and $𝜎_{2} 𝑢_{2}$ . The matrix $𝑈 𝑉^{⊤}$ keeps the singular vectors and sets both singular values to $1$ : it maps the circle to itself, and its columns $𝑈 𝑉^{⊤} 𝑒_{1}$ and $𝑈 𝑉^{⊤} 𝑒_{2}$ , which take the place of $𝐺 𝑒_{1}$ and $𝐺 𝑒_{2}$ , are orthonormal.

5. Incorporating the past

The surrogates above have no memory of the past. The linearization is created using only the current iterate $𝜃_{𝑡}$ and its derivative $𝑔_{𝑡} = 𝐷 𝒥︀ (𝜃_{𝑡})$ , and the norm is fixed. Methods with memory use past iterations in two ways: momentum methods change the linearization, and adaptive methods change the norm.

5.1. Momentum

The idea behind momentum is to build the linearization from past derivatives as well. The surrogates keep their form, with a chosen derivative ${\hat{𝑔}}_{𝑡} \in Θ^{*}$ in place of $𝑔_{𝑡}$ ,

\begin{aligned} ℎ_{𝐶} & = \underset{‖ ℎ ‖ \leq 𝜂}{arg min} ⟨ {\hat{𝑔}}_{𝑡}, ℎ ⟩, \\ ℎ_{𝑃} & = \underset{ℎ \in Θ}{arg min} ⟨ {\hat{𝑔}}_{𝑡}, ℎ ⟩ + \frac{𝜆}{2} {‖ ℎ ‖}^{2} . \end{aligned}

(22)

The derivative ${\hat{𝑔}}_{𝑡}$ enters before the sharp operator, in $Θ^{*}$ . When the sharp operator is linear, as for a norm from an inner product, averaging the derivatives is the same as averaging the steps they give.¹⁷¹⁷ A linear sharp operator commutes with averaging, ${(\sum_{𝑘} 𝑤_{𝑘} 𝑔_{𝑘})}^{♯} = \sum_{𝑘} 𝑤_{𝑘} 𝑔_{𝑘}^{♯}$ . A nonlinear one does not: for Muon, the orthogonalized average of the derivatives is not the average of the orthogonalized derivatives.

Example 5: Averaged linearizations: Adam and Muon

Example 5 (Averaged linearizations: Adam and Muon) Average the past derivatives with weights $(1 - 𝛽) 𝛽^{𝑘}$ for $𝛽 \in (0, 1)$ , giving

{\hat{𝑔}}_{𝑡} = (1 - 𝛽) \sum_{𝑘 \geq 0} 𝛽^{𝑘} 𝑔_{𝑡 - 𝑘} .

(23)

The pairing is linear in $𝑔$ for any norm, so $⟨ {\hat{𝑔}}_{𝑡}, ℎ ⟩$ is the same weighted average of the past linearizations $⟨ 𝑔_{𝑡 - 𝑘}, ℎ ⟩$ . Both steps keep their form with ${\hat{𝑔}}_{𝑡}$ in place of $𝑔_{𝑡}$ ,

ℎ_{𝐶} = - 𝜂 \frac{{\hat{𝑔}}_{𝑡}^{♯}}{{‖ {\hat{𝑔}}_{𝑡} ‖}_{*}}, ℎ_{𝑃} = - \frac{1}{𝜆} {\hat{𝑔}}_{𝑡}^{♯} .

(24)

The past derivatives were taken at earlier points, so as a model of $𝒥︀$ near $𝜃_{𝑡}$ this is worse than the linearization with $𝑔_{𝑡}$ . But when each $𝑔_{𝑡}$ is computed from a minibatch, ${\hat{𝑔}}_{𝑡}$ is a less noisy estimate of the expected derivative. In coordinates, $\hat{𝐺} \leftarrow 𝛽 \hat{𝐺} + (1 - 𝛽) 𝐺$ . Muon takes the step of Example 4 with $\hat{𝐺}$ in place of $𝐺$ , and Adam does the same with the adaptive norm of Example 6.

5.2. Adaptive norms

Past information can also enter the norm. An adaptive method builds an inner product $⟨ \cdot, \cdot ⟩_{{𝒜︀}_{𝑡}}$ from past derivatives, so that the norm changes at every step. Each step is still the one of Example 3, with ${𝒜︀}_{𝑡}$ in place of $𝒜︀$ ,

ℎ_{𝑃} = - \frac{1}{𝜆} {𝒜︀}_{𝑡}^{- 1} (𝐺) .

(25)

Storing a general ${𝒜︀}_{𝑡}$ is out of the question for a network, so two cheap structures are used: a diagonal one, which stores as many numbers as $𝜃$ , and a Kronecker-factored one.

Example 6: A diagonal norm: AdaGrad and Adam

Example 6 (A diagonal norm: AdaGrad and Adam) AdaGrad [5] sums the squared partial derivatives of all past iterations, and Adam [6] takes a moving average of them instead,

𝑣 \leftarrow 𝑣 + 𝐺^{2} (AdaGrad), 𝑣 \leftarrow 𝛽_{2} 𝑣 + (1 - 𝛽_{2}) 𝐺^{2} (Adam),

(26)

where the square, like the square root below, acts entry by entry. So $𝑣$ has the same shape as $𝜃$ , one number per entry. Both measure the step with the weighted norm

\begin{aligned} {‖ ℎ ‖}_{𝑡}^{2} & = \sum_{𝑎} (\sqrt{𝑣_{𝑎}} + 𝜀) ℎ_{𝑎}^{2} = ⟨ {𝒜︀}_{𝑡} (ℎ), ℎ ⟩_{𝐹} = ⟨ ℎ, ℎ ⟩_{{𝒜︀}_{𝑡}}, \\ {𝒜︀}_{𝑡} (ℎ) & = (\sqrt{𝑣} + 𝜀) ⊙ ℎ, \end{aligned}

(27)

where $𝑎$ runs over all entries of $𝜃$ , and $⊙$ multiplies two elements of $Θ$ entry by entry, so that ${𝒜︀}_{𝑡}$ multiplies each $ℎ_{𝑎}$ by $\sqrt{𝑣_{𝑎}} + 𝜀$ . As ${‖ \cdot ‖}_{𝑡}$ comes from an inner product, Example 3 gives

𝑔^{♯} = {𝒜︀}_{𝑡}^{- 1} (𝐺),

(28)

which divides each $𝐺_{𝑎}$ by $\sqrt{𝑣_{𝑎}} + 𝜀$ , and the penalized step with $𝜆 = 1 / 𝜂$ is $- 𝜂 {𝒜︀}_{𝑡}^{- 1} (𝐺)$ . Adam also uses the averaged derivative $\hat{𝐺}$ of Section 5.1 in place of $𝐺$ , so it carries memory in both the linearization and the norm, and its step, without bias correction,¹⁸¹⁸ Adam starts both averages at zero, so after $𝑡$ steps their weights sum to $1 - 𝛽^{𝑡}$ , and early averages are too small. It divides $\hat{𝐺}$ by $1 - 𝛽_{1}^{𝑡}$ and $𝑣$ by $1 - 𝛽_{2}^{𝑡}$ , which scales the step by $\sqrt{1 - 𝛽_{2}^{𝑡}} / (1 - 𝛽_{1}^{𝑡})$ when $𝜀$ is ignored. The factor approaches $1$ on the time scale of $1 / (1 - 𝛽_{2})$ steps. is $- 𝜂 {𝒜︀}_{𝑡}^{- 1} (\hat{𝐺})$ .

Interactive figure 5: The adaptive norm of AdaGrad

Interactive figure 5 (The adaptive norm of AdaGrad) The graph shows AdaGrad on the quadratic $𝒥︀ (𝜃) = 1 / 2 (𝜃_{1}^{2} + 𝜅 𝜃_{2}^{2})$ , next to gradient descent with $𝜆 = 𝐿 = 𝜅$ . At each iterate, the ellipse is the ball of ${‖ \cdot ‖}_{𝑡}$ through the next iterate, which the step reaches where a line of constant linearization touches the ball. Already the first derivative makes the ball narrow in the steep direction $𝜃_{2}$ , where the derivatives are large, and wide along the flat coordinate $𝜃_{1}$ . As $𝑣$ accumulates, the ball, and with it the step, shrinks. AdaGrad thereby takes long steps where gradient descent crawls.

𝜂

𝜅

𝑘

Gradient descent is dotted and AdaGrad solid, with thirty steps each. Drag $𝜃_{0}$ , change $𝜂$ and $𝜅$ , and step through the iterations with $𝑘$ .

Example 7: A Kronecker-factored norm: K-FAC and Shampoo

Example 7 (A Kronecker-factored norm: K-FAC and Shampoo) Let $𝜃 \in ℝ^{𝑚 \times 𝑛}$ be the weights of a linear layer $𝑍 = 𝜃 𝑋$ with inputs $𝑋 \in ℝ^{𝑛 \times 𝑏}$ . A step $ℎ$ changes the outputs by $ℎ 𝑋$ . Measuring this change, weighted on the output side by a symmetric positive definite $𝐿 \in ℝ^{𝑚 \times 𝑚}$ , gives¹⁹¹⁹ In a network, each layer has its own $𝐿$ and $𝑅$ .

{‖ 𝐿^{1 / 2} ℎ 𝑋 ‖}_{𝐹}^{2} = ⟨ 𝒜︀ (ℎ), ℎ ⟩_{𝐹}, 𝑅 = 𝑋 𝑋^{⊤}, 𝒜︀ (ℎ) = 𝐿 ℎ 𝑅,

(29)

which is positive definite only if $𝑋 𝑋^{⊤}$ is. Unlike the spectral norm of Example 4, which is the worst case over all inputs, this norm measures the change on the given inputs. Its inverse, ${𝒜︀}^{- 1} (𝐺) = 𝐿^{- 1} 𝐺 𝑅^{- 1}$ , needs only an $𝑚 \times 𝑚$ and an $𝑛 \times 𝑛$ matrix, not a general one of size $𝑚 𝑛 \times 𝑚 𝑛$ .²⁰²⁰ Stacking the columns of $ℎ$ into one long vector $vec (ℎ)$ gives $vec (𝐿 ℎ 𝑅) = (𝑅 \otimes 𝐿) vec (ℎ)$ , so $𝒜︀$ is the Kronecker product $𝑅 \otimes 𝐿$ . This is why such norms and preconditioners are called Kronecker-factored, the KF in K-FAC. Since the inputs change from batch to batch, K-FAC [7] takes moving averages over the iterations of $𝑋 𝑋^{⊤}$ and of $Δ Δ^{⊤}$ , where $Δ$ holds the derivatives of the loss with respect to the outputs $𝑍$ ,²¹²¹ In K-FAC, $𝑋$ has an extra row of ones for the bias, and $Δ$ is computed with targets sampled from the network’s own predictive distribution rather than taken from the data, so that $𝑅 \otimes 𝐿$ approximates a block of the Fisher information matrix.

𝑅 \leftarrow 𝜌 𝑅 + (1 - 𝜌) 𝑋 𝑋^{⊤}, 𝐿 \leftarrow 𝜌 𝐿 + (1 - 𝜌) Δ Δ^{⊤},

(30)

and its basic step is $- 𝜂 𝐿^{- 1} 𝐺 𝑅^{- 1}$ . K-FAC also adds damping to $𝐿$ and $𝑅$ , and takes the step $𝛼 𝑑_{𝑡} + 𝜇 ℎ_{𝑡 - 1}$ with $𝑑_{𝑡} = - 𝐿^{- 1} 𝐺 𝑅^{- 1}$ , where $𝛼$ and $𝜇$ are chosen at every step by minimizing a quadratic model. This is a momentum term whose coefficients change from step to step. Shampoo [8] instead sums the products of the derivative with itself, starting from $𝐿 = 𝜀 𝐼$ and $𝑅 = 𝜀 𝐼$ ,

𝐿 \leftarrow 𝐿 + 𝐺 𝐺^{⊤}, 𝑅 \leftarrow 𝑅 + 𝐺^{⊤} 𝐺,

(31)

and takes the step $- 𝜂 𝐿^{- 1 / 4} 𝐺 𝑅^{- 1 / 4}$ , so its norm uses the fourth roots of $𝐿$ and $𝑅$ .

6. Summary

Table 2 summarizes the methods of the post by their norm and by where past information enters.

Table 2: The methods of the post as choices of the norm and of where past information enters: the linearization through ${\hat{𝑔}}_{𝑡}$ , and the norm. K-FAC also uses the previous step, and implementations of Shampoo often add momentum as well.

Method	Norm	${\hat{𝑔}}_{𝑡}$	Norm memory
Gradient descent	Inner product	$𝑔_{𝑡}$	–
AdaGrad	Diagonal	$𝑔_{𝑡}$	Sum
Adam	Diagonal	Average	Average
K-FAC	Kronecker-factored	$𝑔_{𝑡}$	Average
Shampoo	Kronecker-factored	$𝑔_{𝑡}$	Sum
Sign descent	Max-norm	$𝑔_{𝑡}$	–
Muon	Spectral	Average	–

Cite this post

bibtex


@misc{paltorp2026steepestdescent,
  author = {Paltorp, Mikkel},
  title = {{Which Way Is Down? First-Order Optimizers as a Choice of Norm}},
  year = {2026},
  month = oct,
  url = {https://mipals.github.io/pdf/2026/10-13-steepest-descent/steepest-descent.pdf},
  note = {Blog post}
}

Bibliography

[1] J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford, “An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, pp. 217–226. doi: 10.1137/1.9781611973402.16.
[2] J. Bernstein and L. Newhouse, “Modular Duality in Deep Learning.” [Online]. Available: https://arxiv.org/abs/2410.21265
[3] P. J. Goulart and Y. Chen, “Clarabel: An interior-point solver for conic programs with quadratic objectives.” [Online]. Available: https://arxiv.org/abs/2405.12762
[4] K. Jordan et al., “Muon: An optimizer for hidden layers in neural networks.” [Online]. Available: https://kellerjordan.github.io/posts/muon/
[5] J. Duchi, E. Hazan, and Y. Singer, “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization,” Journal of Machine Learning Research, vol. 12, no. 61, pp. 2121–2159, 2011, [Online]. Available: https://jmlr.org/papers/v12/duchi11a.html
[6] D. P. Kingma and J. Ba, “Adam: A Method for Stochastic Optimization,” in International Conference on Learning Representations (ICLR), 2015. [Online]. Available: https://arxiv.org/abs/1412.6980
[7] J. Martens and R. Grosse, “Optimizing Neural Networks with Kronecker-factored Approximate Curvature,” in Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research, vol. 37. 2015, pp. 2408–2417. [Online]. Available: https://proceedings.mlr.press/v37/martens15.html
[8] V. Gupta, T. Koren, and Y. Singer, “Shampoo: Preconditioned Stochastic Tensor Optimization,” in Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research, vol. 80. 2018, pp. 1842–1850. [Online]. Available: https://proceedings.mlr.press/v80/gupta18a.html