Rotating a quadratic preserves every eigenvalue of its Hessian. It also preserves the behavior of ordinary gradient descent, provided we rotate the initial point along with the objective. A coordinatewise optimizer can behave very differently: taking signs is not invariant under a rotation.
How should we then measure conditioning? Not by switching arbitrarily to a different matrix norm. The clean route is to define steepest descent in a chosen vector norm, derive the two constants in its convergence theorem, and then take their ratio. This viewpoint is useful in our work on balanced low-rank adaptation [1], and belongs to the broader study of optimization geometry [2].
A direction is not yet a speed
Fix \(1\leq p\leq\infty\), and let \(q\) be the dual exponent: \(1/p+1/q=1\). For a gradient covector \(g\), define
\[ d_p(g)\in\underset{v\in\mathbb R^d}{\operatorname{argmin}} \left\{\langle g,v\rangle+\tfrac12\|v\|_p^2\right\}. \]The squared-norm penalty chooses both direction and magnitude, a convenient formulation of norm-steepest descent [5]. Equivalently,
\[ d_p(g)\in-\partial\!\left(\tfrac12\|\cdot\|_q^2\right)(g). \]The subdifferential allows several choices when an endpoint norm is nonsmooth. Every choice has the same two fundamental properties:
\[ \langle g,d_p(g)\rangle=-\|g\|_q^2, \qquad \|d_p(g)\|_p=\|g\|_q. \]Proof: Hölder's inequality, with equality at the optimum
For \(a=\|v\|_p\), Hölder's inequality gives
\[ \langle g,v\rangle+\tfrac12\|v\|_p^2 \geq-a\|g\|_q+\tfrac12a^2 =\tfrac12(a-\|g\|_q)^2-\tfrac12\|g\|_q^2. \]In finite dimension a norming direction attains equality in Hölder. The minimum is therefore \(-\|g\|_q^2/2\), attained precisely by descent directions with norm \(\|g\|_q\) and pairing \(-\|g\|_q^2\). This is also the equality condition in Fenchel duality for the conjugate pair of half-squared dual norms. \(\square\)
For \(1<p<\infty\), the direction is unique; if \(g\ne0\),
\[ (d_p(g))_i=-\|g\|_q^{2-q}|g_i|^{q-1}\operatorname{sign}(g_i), \qquad d_p(0)=0. \]Three geometries are particularly familiar:
- \(p=2\): \(d_2(g)=-g\), ordinary gradient descent.
- \(p=\infty\): choose \(d_\infty(g)=-\|g\|_1\operatorname{sign}(g)\), with \(\operatorname{sign}(0)=0\). This is scaled sign descent. At a zero gradient coordinate, any sign value in \([-1,1]\) is allowed by the minimization problem.
- \(p=1\): choose a coordinate \(i\) maximizing \(|g_i|\), and take \(d_1(g)=-\|g\|_\infty\operatorname{sign}(g_i)e_i\). This is a greedy coordinate step; convex combinations of tied maximizing choices are also valid.
The associated iteration and flow are
\[ x_{k+1}=x_k+\eta d_p(\nabla f(x_k)), \] \[ \dot x(t)\in-\partial\!\left(\tfrac12\|\cdot\|_q^2\right)(\nabla f(x(t))). \]At nonsmooth endpoint norms the flow is a differential inclusion. The following discrete argument works for any selected minimizing direction.
The convergence theorem determines the condition number
Assume that \(f\) has finite minimum \(f_*\) and satisfies
\[ f(x+v)\leq f(x)+\langle\nabla f(x),v\rangle+\tfrac L2\|v\|_p^2, \] \[ \tfrac12\|\nabla f(x)\|_q^2\geq\mu\bigl(f(x)-f_*\bigr), \qquad L,\mu>0. \]The first is smoothness in the chosen norm. The second is its dual-norm Polyak–Łojasiewicz (P–L) inequality. It does not require convexity; in Euclidean geometry it is a standard route to linear convergence [4].
Theorem 1 (norm-steepest descent). Suppose these assumptions hold on a region containing all iterates and their update segments. With \(E_k=f(x_k)-f_*\), the step \(\eta=1/L\) satisfies
\[ E_k\leq(1-1/\kappa_p)^k E_0, \qquad \kappa_p=\frac L\mu. \]For any absolutely continuous solution of the flow satisfying the chain rule on the same region,
\[ f(x(t))-f_*\leq e^{-2\mu t}\bigl(f(x(0))-f_*\bigr). \]Proof: substitute the two identities for the steepest direction
Write \(g=\nabla f(x_k)\) and \(v=\eta d_p(g)\) in the smoothness bound:
\[ E_{k+1}\leq E_k-\eta(1-\eta L/2)\|g\|_q^2. \]With \(\eta=1/L\), the P–L inequality gives \(E_{k+1}\leq(1-\mu/L)E_k\). Iterate. More generally, every \(0<\eta<2/L\) gives the factor \(1-2\eta\mu(1-\eta L/2)\). Along the flow, the chain rule gives \(E'(t)=-\|\nabla f(x(t))\|_q^2\leq-2\mu E(t)\); integrate this scalar inequality. \(\square\)
The constants are global when the assumptions are global, and local only when the assumptions and invariance of the neighborhood are local. A positive Hessian at an isolated minimizer yields nearby constants. With a manifold of minimizers, one needs an appropriate local P–L property—for example from a smooth Morse–Bott structure—not merely a list of positive eigenvalues with all zero directions ignored.
For a quadratic, which matrix norms appear?
Take \(f(x)=\tfrac12 x^\top Hx\), with \(H\succ0\). The sharp constants are
\[ L_p(H)=\sup_{u\ne0}\frac{u^\top Hu}{\|u\|_p^2}, \qquad \mu_p(H)=\inf_{u\ne0}\frac{\|Hu\|_q^2}{u^\top Hu}. \]Proposition 1 (dual operator-norm formula). For an induced norm \(\|M\|_{a\to b}=\sup_{u\ne0}\|Mu\|_b/\|u\|_a\),
\[ L_p(H)=\|H\|_{p\to q},\qquad \mu_p(H)^{-1}=\|H^{-1}\|_{q\to p}. \]Consequently \(\kappa_p(H)=\|H\|_{p\to q}\|H^{-1}\|_{q\to p}\), not in general the same-norm product \(\|H\|_{p\to p}\|H^{-1}\|_{p\to p}\).
Proof: positive quadratic forms reduce the bilinear supremum
By duality, \(\|H\|_{p\to q}\) is the supremum of \(v^\top Hu\) over \(\|u\|_p,\|v\|_p\leq1\). Cauchy–Schwarz for the positive form \(H\) gives
\[ |v^\top Hu|\leq\sqrt{(v^\top Hv)(u^\top Hu)}\leq L_p(H). \]Taking \(u=v\) at a maximizing vector proves equality. Next set \(g=Hu\). Then
\[ \mu_p(H)^{-1} =\sup_{g\ne0}\frac{g^\top H^{-1}g}{\|g\|_q^2} =\|H^{-1}\|_{q\to p}, \]by the same argument with \(H^{-1}\) and the dual exponents exchanged. \(\square\)
For \(p=2\), this reduces to the familiar spectral condition number. For \(p=\infty\), two elementary finite-dimensional formulas are especially useful:
\[ L_\infty(H)=\max_{s\in\{-1,1\}^d}s^\top Hs, \qquad \mu_\infty(H)^{-1}=\max_i(H^{-1})_{ii}. \]The first maximum is over the vertices of the cube; the second is over the vertices \(\pm e_i\) of the \(\ell^1\) ball. A convex quadratic attains its maximum over a polytope at a vertex. This is where the coordinate axes enter.
A rotation changes the sign-descent condition number
Let \(d\) be even, \(0<\varepsilon<1\), and \(v=(1,\ldots,1)^\top/\sqrt d\). Compare
\[ H_{\mathrm{axis}}=\operatorname{diag}(\varepsilon,1,\ldots,1), \qquad H_{\mathrm{spread}}=I-(1-\varepsilon)vv^\top. \]Both have one eigenvalue \(\varepsilon\) and \(d-1\) eigenvalues equal to one: only the orientation of the soft direction differs.
Proposition 2 (same Euclidean, different sign conditioning). These matrices satisfy
\[ \kappa_2(H_{\mathrm{axis}})=\kappa_2(H_{\mathrm{spread}})=1/\varepsilon, \] \[ \kappa_\infty(H_{\mathrm{axis}})=\frac{d-1+\varepsilon}{\varepsilon}, \qquad \kappa_\infty(H_{\mathrm{spread}})=\frac{1+(d-1)\varepsilon}{\varepsilon}. \]Proof: evaluate the cube and cross-polytope maxima
For the diagonal matrix every cube vertex gives \(d-1+\varepsilon\), and the largest inverse diagonal entry is \(1/\varepsilon\). For the spread matrix,
\[ s^\top H_{\mathrm{spread}}s=d-(1-\varepsilon)(v^\top s)^2. \]Because \(d\) is even, a sign vector with half positive and half negative coordinates has \(v^\top s=0\). Thus \(L_\infty=d\). The inverse is
\[ H_{\mathrm{spread}}^{-1}=I+(\varepsilon^{-1}-1)vv^\top, \]whose diagonal entries all equal \((d-1+\varepsilon^{-1})/d\). Multiply by \(L_\infty=d\) to obtain the stated condition number. \(\square\)
At \(d=20\) and \(\varepsilon=0.01\), the Euclidean condition number is \(100\) for both, but the sign condition numbers are \(1901\) and \(119\). A rotated quadratic with the same spectrum can therefore have a substantially different worst-case guarantee for scaled sign descent.
Numerical experimentation
The experiment matches initial vectors by an orthogonal change of coordinates. Ordinary GD then has exactly the same loss in both problems, up to floating-point arithmetic. Scaled sign descent does not. Select soft, hard, or mixed initial directions to distinguish an actual trajectory from a worst-case upper bound.
Geometry before conditioning
There is no optimizer-independent condition number. The Euclidean spectrum is the correct answer for Euclidean steepest descent, but a coordinatewise method asks a different question. This is why the distinction between balanced and hyperbalanced representations in low-rank adaptation becomes meaningful when the optimizer responds to coordinates [1].
Changing coordinates, changing the factorization, and changing the descent norm are three related but distinct operations. The companion post on intrinsic factor dynamics describes how a redundant parameterization itself induces a non-Euclidean mobility. Here we fixed the represented quadratic and changed the optimizer's geometry.
Bibliography
- Valérie Castin, Kimia Nadjahi, Pierre Ablin, and Gabriel Peyré. Balanced LoRA: removing parameter invariance to accelerate convergence. ICML, 2026.
- Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. ICML, 2018.
- Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD: compressed optimisation for non-convex problems. ICML, 2018.
- Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition. ECML PKDD, 2016.
- Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.