Old Optimizer, New Norm: An Anthology

Prologue

Deep learning optimizers are often motivated from the perspectives of convex and approximate second-order theory. These theoretical frameworks have been used to inspire algorithmic ideas, as well as providing means to analyse the convergence of various optimizers. However, we believe—and will attempt to demonstrate—that there is a wealth of untapped algorithmic opportunity in the simpler realm of exact first-order theory without convexity assumptions.

To make our case, we choose three optimizers that were originally analysed under convex or approximate second-order theory: Adam, Shampoo and Prodigy. After disabling their exponential moving averages (EMA), we show that each algorithm admits a parsimonious theoretical explanation as a variant of steepest descent under a certain norm. EMA can then be thought of as “smoothing out” the algorithm, or making it more robust to mini-batch noise, although nailing down the precise role of EMA is perhaps still an open problem.

By steepest descent, we mean the procedure of choosing a weight update $\Delta{\bm{w}}$ to minimise a local quadratic model of the loss function $\mathcal{L}$ of the form $\mathcal{L}({\bm{w}})+\nabla_{\bm{w}}\mathcal{L}({\bm{w}})^{\top}\Delta{\bm{w}}+\frac{\lambda}{2}\cdot\|{\Delta{\bm{w}}}\|^{2}$, visualized in Figure 1. Crucially, the sharpness parameter $\lambda$ and norm $\|{\cdot}\|$ are chosen a priori, without touching an (approximate) Hessian during training. As such, we consider steepest descent to be a squarely first-order method and not an (approximate) second-order method.

Throughout the anthology, we rely on a dual description of steepest descent:

Equation 1 separates the solution of the steepest descent problem into two pieces: first computing the step size as the dual norm of the gradient divided by the sharpness, and second solving for the step direction as the unit vector that maximizes the inner product with the gradient. The proof of this proposition is given in Appendix B.

Of course, the art of steepest descent lies in choosing a norm $\|{\cdot}\|$ and a sharpness $\lambda$ suited to the optimization problem at hand. While it may be possible to turn this art into a science (Large et al., 2024), that ambition is beyond the scope of this anthology. Here we point out that past methods do implicitly make decisions about norms, and in a somewhat haphazard manner. In fact, they implicitly assign different induced matrix norms to the network layers:

1 tells us that by varying the choice of vector norms $\|{\cdot}\|_{\alpha}$ and $\|{\cdot}\|_{\beta}$, we can induce a large family of matrix norms. In turn, this implies a correspondingly large family of steepest descent optimizers. By foregrounding this issue, we hope that algorithm designers may develop more suitable optimizers by becoming more intentional about their choice of norm.

Story I Adam as Steepest Descent under the Max-of-Max Norm

Adam is a widely used deep learning optimizer: the original paper of Kingma and Ba (2015) now has well over 100,000 citations. Adam has been motivated in various ways, including through convex analysis (Kingma and Ba, 2015) and as an approximate second-order method (Sun and Spall, 2021). However, there have been efforts to build a more direct understanding of Adam: for instance, with exponential moving averages (EMA) switched off, Adam is just sign gradient descent (Balles and Hennig, 2018; Bernstein et al., 2018), which is equivalent to steepest descent under the infinity norm (Carlson et al., 2015). In this story, we connect Adam to a certain “max-of-max” norm, showing how Adam respects the tensor structure of a neural network in a very particular way.

To begin, we review how Adam connects to sign gradient descent. Ignoring bias corrections and numerical stabilizations, Adam is given by the following system of updates:

This connection to sign descent should not be surprising since Adam, published in 2015, builds on the RMSprop optimizer that Tieleman and Hinton (2012) already called “the mini-batch version of just using the sign of the gradient”. And RMSprop itself built on the RPROP optimizer (Riedmiller and Braun, 1993), which also uses gradient signs.

In words, the vector that minimizes a linear functional under an infinity norm penalty is a scalar multiple of a sign vector. The proof is given in Appendix B.

For any list of gradient matrices ${\bm{G}}_{1},...,{\bm{G}}_{L}$ and any sharpness $\lambda>0$, consider the problem:

In words, the matrix-aware steepest descent problem of Equation 10 is solved by layerwise sign descent as given in Equation 11. This observation—that sign descent updates are implicitly doing per-matrix gradient normalization—may be a major reason that Adam, sign descent and Lion (Chen et al., 2023) outperform vanilla gradient descent in large language model training (Zhao et al., 2024; Large et al., 2024). The proof is given in Appendix B.

Story II Shampoo as Steepest Descent under the Spectral Norm

Now, dear reader, we turn our attention to Shampoo (Gupta et al., 2017, 2018). A variant of the Shampoo optimizer won the external tuning track of the 2024 AlgoPerf: Training Algorithms competition (Dahl et al., 2023). While the method was originally motivated as a generalization of the AdaGrad convex optimizer (Duchi et al., 2011) to tensor spaces, more recent work casts Shampoo as an approximate second-order method (Anil et al., 2020; Morwani et al., 2024). We will show that Shampoo—with accumulation disabled—is steepest descent under the max spectral norm over layers.

To begin, we show that Shampoo updates, without accumulation, are semi-orthogonal matrices. At time step $t$ and for each layer, Shampoo collects the gradient matrix ${\bm{G}}_{t}$ and makes the following update to the weight matrix ${\bm{W}}_{t}$:

All operations, including the inverse fourth roots, are matrix operations. The accumulators ${\bm{L}}_{t}$ and ${\bm{R}}_{t}$ are referred to as the “left and right pre-conditioners”. Practitioners usually replace the simple sums in Equations 12 and 13 with EMAs (Shi et al., 2023). If we disable the accumulation, setting ${\bm{L}}_{t}={\bm{G}}_{t}{\bm{G}}_{t}^{\top}$ and ${\bm{R}}_{t}={\bm{G}}_{t}^{\top}{\bm{G}}_{t}$, Shampoo reduces to:

where Equation 16 is reached by substituting the reduced singular value decomposition (SVD) of the gradient ${\bm{G}}_{t}={\bm{U}}_{t}{\bm{\Sigma}}_{t}{\bm{V}}_{t}^{\top}$ into Equation 15. Notice that there is a direct parallel between Equations 6 and 7 for Adam and Equations 15 and 16 for Shampoo. So, Shampoo without accumulation makes a semi-orthogonal weight update. In fact:

where the minimizer ${\bm{U}}{\bm{V}}^{\top}$ is unique if and only if the matrix ${\bm{G}}$ has full rank.

For any list of gradient matrices ${\bm{G}}_{1},...,{\bm{G}}_{L}$ and any sharpness $\lambda>0$, consider the problem:

where $\langle\cdot,\cdot\rangle$ denotes the Frobenius inner product and $\Delta{\bm{W}}_{l}$ has the same shape as ${\bm{G}}_{l}$. Suppose that ${\bm{G}}_{l}$ has reduced SVD given by ${\bm{G}}_{l}={\bm{U}}_{l}{\bm{\Sigma}}_{l}{\bm{V}}_{l}^{\top}$ for each $l=1,...,L$. Then Equation 18 is solved with a step size $\eta=\frac{1}{\lambda}\sum_{l=1}^{L}\operatorname{tr}{\bm{\Sigma}}_{l}$ and an update:

This solution for $\Delta{\bm{W}}_{l}$ is unique if and only if the matrix ${\bm{G}}_{l}$ is of full rank.

The proof is given in Appendix B. A novelty of this proposition in contrast to prior work on stochastic spectral descent (Carlson et al., 2015, 2016) is our use of a max norm over layers to handle the multi-layer case. However, our main contribution here is to draw the connection between 5 and Shampoo as in Equations 15 and 16.

So, Shampoo without accumulation is steepest descent under the spectral norm. Why might this be a good idea in deep learning? The idea that we wish to advance is that one can derive upper bounds on the loss of machine learning models in terms of spectral norms. Here we present the simplest possible example: a linear model and the square loss.

where $\langle\cdot,\cdot\rangle$ is the Frobenius inner product.

In words: the square loss of a linear predictor admits an upper bound that is quadratic in the spectral norm of the weight perturbation. Choosing the weight perturbation to minimize this upper bound is precisely steepest descent under the spectral norm! The proof is given in Appendix B. This optimizer design pattern, which starts by deriving an upper bound on the loss (as in 6) and then minimizes it (as in 5), is known generally as majorization-minimization (Lange, 2016). It is an exact and first-principles design pattern, without Hessian approximations or appeals to convex theory. This design pattern is used extensively by Carlson et al. (2015, 2016) to design optimizers for restricted Boltzmann machines and discrete graphical models. Generalizing the pattern to arbitrary network architectures and loss functions requires more advanced machinery (Bernstein et al., 2023; Streeter, 2023; Large et al., 2024).

And so, dear reader, we have reached the end of our second story. We have shown that Shampoo without accumulation corresponds to projecting the gradient matrix to the closest semi-orthogonal matrix, which solves the problem of steepest descent under the spectral norm. And we showed how steepest descent under the spectral norm emerges from upper bounding the square loss of a linear predictor. This perspective, of viewing Shampoo as a (smoothed out) projection to the space of semi-orthogonal matrices, grounds the algorithm in a prior literature on spectral descent (Carlson et al., 2015, 2016; Fan, 2017). And in Appendix A, we discuss how it might unlock new means for computing the Shampoo updates.

We summarize our first two stories in Table 1. And we still have one more left to tell…

Story III Prodigy: Automatically Computing the Escape Velocity

For our final story, we speak of Prodigy (Mishchenko and Defazio, 2023). The Prodigy optimizer falls amid a series of recent works (Defazio and Mishchenko, 2023; Khaled et al., 2023; Ivgi et al., 2023) that attempt to apply convex theory to design and analyse deep learning optimizers that do not require tuning. In contrast, we argue that Prodigy (without EMA) is but another example of steepest descent, where instead of using the step size $\eta=\|{{\bm{g}}}\|^{\dagger}/\lambda$ from 1, Prodigy uses a heuristic to automatically warm up to a good step size. This demonstrates the value of 1 for disentangling the optimizer design problem. If one knows a good norm $\|{\cdot}\|$ but is ignorant of the sharpness parameter $\lambda$, then one may obtain the step direction by solving $\operatorname*{arg\,max}_{\|{{\bm{t}}}\|=1}{\bm{g}}^{\top}{\bm{t}}$ from 1, while using another means to find a good step size.

Then let us make our case. We focus on Algorithm 3 in the Prodigy paper, since this is the version used in their experiments. We first show that with EMA switched off, Prodigy implements sign gradient descent with a step size that warms up automatically. Ignoring the numerical stabilization and learning rate schedule, Prodigy is given by:

But 2 showed that sign descent is steepest descent under the infinity norm. Therefore Equations 28 and 29 prove our claim that Prodigy without EMA is steepest descent, although with a dynamically chosen step size denoted $\eta_{t}$.

All that remains is to understand the dynamical rule, given by Equation 28, for choosing the step size $\eta_{t}$. We shall argue that this dynamical rule can be understood to approximate a heuristic algorithm for achieving, but not exceeding, what we shall call escape velocity:

Choose a very small initial step size $\eta_{0}$—small enough to be a priori sure that $\eta_{0}\ll\eta_{\star}$, where $\eta_{\star}$ denotes escape velocity: the unknown but optimal initial step size;

At each step, check if the weights ${\bm{w}}_{t}$ have escaped the linearization of the loss around the initial weights ${\bm{w}}_{0}$—if not, double the step size according to $\eta_{t+1}=2\times\eta_{t}$;

Once the weights ${\bm{w}}_{t}$ have escaped the initial linearization, stop increasing the step size. We say that the step size $\eta_{t}$ has reached escape velocity $\eta_{\star}$.

The rationale behind this procedure is that if we knew the optimal initial step size $\eta_{\star}$, then the weights should escape the initial linearization of the loss in a single step. Formally, the directional derivative $({\bm{w}}_{1}-{\bm{w}}_{0})^{\top}{\bm{g}}_{1}$ must vanish if the step size is chosen optimally (Cauchy, 1847). If the directional derivative in the direction of the first weight update is still negative $({\bm{w}}_{1}-{\bm{w}}_{0})^{\top}{\bm{g}}_{1}<0$, then we could have taken a larger step. Said another way, we can use the angle that the gradient ${\bm{g}}_{1}$ makes with the change in weights ${\bm{w}}_{1}-{\bm{w}}_{0}$ to tell us whether or not we should increase the step size. Notice that procedure has no reliance on convexity.

With this in mind, let us massage Prodigy’s step size update (Equation 28) as follows:

where $\theta$ denotes the angle between the gradient ${\bm{g}}_{t}$ and the difference in weights ${\bm{w}}_{0}-{\bm{w}}_{t}$. To help make sense of this expression, we make two assumptions:

${\bm{w}}_{t}$ is still close enough to the initialization ${\bm{w}}_{0}$ that $\cos\theta\approx 1$.

where we have used the fact that a sign vector has unit RMS norm. In words, while assumptions (1) and (2) hold, the step size at time $t+1$ is equivalent to the whole progress up to step $t$. This suggests exponential growth in the step size that continues until assumption (2) breaks, which we think of as the step size reaching the escape velocity $\eta_{\star}$

Our time grows short, dear reader, and our third story draws to an end. We have argued that Prodigy without EMA is sign descent—an example of steepest descent—with a particular mechanism for warming up the step size. Starting with a tiny initial step size, Prodigy multiplicatively increases the step size until the weights escape the initial locally linear region of the loss. Prodigy’s step size adjustment is based on the angle between the gradient and the total weight change. This is a form of online line search. This highlights that once one has a chosen a norm, the steepest descent framework allows freedom to estimate the step size in various different ways.

Epilogue

This anthology has presented new ways of understanding old optimizers. 1 decouples the optimizer design problem into two pieces: first choosing a norm and second finding a step size. This design space is already broad. We have argued that Adam chooses the infinity norm (2) or equivalently the max-of-max norm (3), which respects a layered matrix structure. Shampoo chooses the spectral norm (5). Prodigy chooses the same norm as Adam, and then uses a heuristic to automatically warm up to a good step size, as in Equation 28, which we term reaching escape velocity.

Through the lens of steepest descent, the decisions that Adam, Shampoo and Prodigy make may seem arbitrary. In fact, we think that they are somewhat arbitrary. And there may be more principled ways to make these decisions. To demonstrate this point, we now introduce a tool called the modular norm (Large et al., 2024) and its corresponding steepest descent algorithm. The modular norm generalizes the norms that appeared in 3 for Adam and 5 for Shampoo. Formally:

Given scalar coefficients $s_{1},\dots,s_{L}>0$ and norms $\|{\cdot}\|_{1},\dots,\|{\cdot}\|_{L}$, we define the modular norm as the mapping:

The corresponding steepest descent problem is given by:

where $\langle\cdot,\cdot\rangle$ denotes the Frobenius inner product, and for each $l=1,...,L$ the two matrices $\Delta{\bm{W}}_{l}$ and ${\bm{G}}_{l}$ are of the same shape. If we define the global step size $\eta=\frac{1}{\lambda}\sum_{k=1}^{L}\frac{1}{s_{k}}\|{{\bm{G}}_{k}}\|_{k}^{\dagger}$, then the solution to Equation 32 is given by:

In words, steepest descent under the modular norm updates each layer in a direction informed by that layer’s norm and with a global step size computed as a weighted sum of the dual norms of the gradients over layers. The proof of this proposition is given in Appendix B.

We believe that picking the right norms could improve the speed and scalability of neural network training. We are seeing evidence that equipping neural network layers with better norms can lead to learning rate transfer across scale (Yang et al., 2023; Large et al., 2024). And since Shampoo won the external tuning track of the 2024 AlgoPerf competition (Dahl et al., 2023), it is garnering interest as a fast training method. The second story in our anthology shows that Shampoo is closely connected to the spectral norm.

In conclusion, this work highlights a perspective on optimizer design as choosing two things: a norm and a step size. We have shown that three popular methods—Adam, Shampoo and Prodigy—fit within this perspective. We hope that researchers can design improved training algorithms by choosing norms and step sizes more intentionally.

“Though this be madness, yet there is method in’t.” Hamlet

Acknowledgements

We are grateful to Tim Large and Phillip Isola for invaluable discussions on the stories in this anthology. We also thank Jack Gallagher, Keller Jordan and Victor Butoi for very helpful conversations.

References

Appendix A Computational Strategies for Shampoo

Here we list every means we know of computing or approximating this equation. First, we mention that $({\bm{G}}{\bm{G}}^{\top})^{-\nicefrac{{1}}{{4}}}\,{\bm{G}}\,({\bm{G}}^{\top}{\bm{G}})^{-\nicefrac{{1}}{{4}}}=({\bm{G}}{\bm{G}}^{\top})^{-\nicefrac{{1}}{{2}}}\,{\bm{G}}={\bm{G}}\,({\bm{G}}^{\top}{\bm{G}})^{-\nicefrac{{1}}{{2}}}$, so if one is willing to compute inverse matrix roots, one need only compute either $({\bm{G}}{\bm{G}}^{\top})^{-\nicefrac{{1}}{{2}}}$ or $({\bm{G}}^{\top}{\bm{G}})^{-\nicefrac{{1}}{{2}}}$, whichever has smaller dimension. With that said, to compute Equation 35, one may:

Do the SVD. Apply an SVD routine to compute ${\bm{U}}$, ${\bm{\Sigma}}$ and ${\bm{V}}^{\top}$ and just discard ${\bm{\Sigma}}$.

Do sketching. Sketching is a randomized method (Martinsson and Tropp, 2020) that can be used to approximate the SVD. See, for instance, Sketchy (Feinberg et al., 2023).

Do Newton iteration for inverse $p$th roots. Inverse matrix roots such as $({\bm{G}}{\bm{G}}^{\top})^{-\nicefrac{{1}}{{2}}}$ can be computed via Newton iteration (Lakić, 1998). This is discussed in Chapter 7 of Higham (2008)’s book. And see Anil et al. (2020)’s paper.

Finally, there are in fact a family of degree $2n+1$ polynomial iterations of the form

for suitable $a,b,c,...,z$ that could be used instead of Equation 36. One should choose coefficients $a,b,c,...,z$ so that the univariate polynomial $g(x)=a\cdot x+b\cdot x^{3}+c\cdot x^{5}+...+z\cdot x^{2n+1}$ is a suitable approximation to $\operatorname{sign}(x)$.

Which of these methods is most useful in practice may depend on factors such as the condition number of the matrix ${\bm{G}}$ or the nature of the available computational resources.

Appendix B Proofs

First, let’s study the minimization under the change of variables $\Delta{\bm{w}}=c\cdot{\bm{t}}$, where $c\geq 0$ encodes the “magnitude” and ${\bm{t}}$ is a unit vector ($\|{{\bm{t}}}\|=1$) encoding the “direction”:

Inspecting Equation 39, we see that the minimizer for the direction ${\bm{t}}$ is given by:

And similarly, by inspecting Equation 40, the minimizer for the magnitude $c$ is given by:

Multiplying these expressions, we obtain the minimizer for $\Delta{\bm{w}}$, yielding the result.

: \nameref*prop:sign-descent

The result follows by applying 1. We just need that $\operatorname*{arg\,max}_{\|{{\bm{t}}}\|_{\infty}=1}{\bm{g}}^{\top}{\bm{t}}=\operatorname{sign}({\bm{g}})$, and also that the dual norm $\|{{\bm{g}}}\|_{\infty}^{\dagger}\vcentcolon=\max_{\|{{\bm{t}}}\|_{\infty}=1}{\bm{g}}^{\top}{\bm{t}}={\bm{g}}^{\top}\operatorname{sign}({\bm{g}})=\|{{\bm{g}}}\|_{1}$.

: \nameref*prop:structural-sign-descent

: \nameref*prop:projection

To begin, we observe that the minimizer over semi-orthogonal matrices of the “distance” $\|{{\bm{A}}-{\bm{G}}}\|_{F}$ is the same as the maximizer over semi-orthogonal matrices of the “alignment” $\langle{\bm{A}},{\bm{G}}\rangle$, where $\langle\cdot,\cdot\rangle$ denotes the Frobenius inner product. This is because:

and the term $\|{{\bm{A}}}\|_{F}^{2}$ is fixed at $\|{{\bm{A}}}\|_{F}^{2}=\min(m,n)$ for a semi-orthogonal matrix ${\bm{A}}\in\mathcal{O}_{m\times n}$.

Now, let ${\bm{G}}=\sum_{i}\sigma_{i}\,{\bm{u}}_{i}{\bm{v}}_{i}^{\top}$ denote the SVD of ${\bm{G}}$. Then the alignment satisfies:

where the second equality follows by the cyclic property of the trace, and the inequality is since ${\bm{A}}$ being semi-orthogonal means that ${\bm{u}}^{\top}{\bm{A}}{\bm{v}}\leq 1$ for any two unit vectors ${\bm{u}}$ and ${\bm{v}}$.

Next, observe that for the semi-orthogonal matrix ${\bm{A}}_{\star}=\sum_{i}{\bm{u}}_{i}{\bm{v}}_{i}^{\top}$, we have that:

since the $\{{\bm{u}}_{i}\}$ and $\{{\bm{v}}_{i}\}$ are orthonormal. Comparing against Equation 45, we see that ${\bm{A}}_{\star}$ indeed maximizes the alignment, since it achieves the upper bound of $\sum_{i}\sigma_{i}$. And ${\bm{A}}_{\star}$ therefore also minimizes the distance $\|{{\bm{A}}-{\bm{G}}}\|_{F}$ amongst semi-orthogonal matrices ${\bm{A}}$. Note that if ${\bm{U}}$ is the matrix that has the $\{{\bm{u}}_{i}\}$ as columns, and likewise for ${\bm{V}}$ and the $\{{\bm{v}}_{i}\}$, then this solution may equivalently be expressed as ${\bm{A}}_{\star}={\bm{U}}{\bm{V}}^{\top}$.

All that remains is to explore the uniqueness of this solution:

If ${\bm{G}}$ is full rank, the solution ${\bm{A}}_{\star}$ is unique. ${\bm{G}}$ being full rank means that all the singular values $\sigma_{i}$ are positive. In this case, we see from Equation 45 that to maximize the alignment the semi-orthogonal matrix ${\bm{A}}$ must satisfy ${\bm{u}}_{i}^{\top}{\bm{A}}{\bm{v}}_{i}=1$ for all $i$. Since ${\bm{A}}$ has spectral norm one, in turn this requires that ${\bm{A}}{\bm{v}}_{i}={\bm{u}}_{i}$ and ${\bm{A}}^{\top}{\bm{u}}_{i}={\bm{v}}_{i}$ for all $i$. These conditions uniquely pick out ${\bm{A}}=\sum_{i}{\bm{u}}_{i}{\bm{v}}_{i}^{\top}$.

If ${\bm{G}}$ is not full rank then the solution ${\bm{A}}_{\star}$ is not unique. This solution is just as good:

: \nameref*prop:shampoo-steepest

Let’s start with the dual norm. For a matrix ${\bm{G}}$ with SVD $\sum_{i}\sigma_{i}\,{\bm{u}}_{i}{\bm{v}}_{i}^{\top}={\bm{U}}{\bm{\Sigma}}{\bm{V}}^{\top}$ we have:

The uniqueness claim follows by the same argument as for 4.

: \nameref*prop:majorization

First observe that the square loss is quadratic in ${\bm{W}}$ so there are no cubic terms or higher. The bound must agree to first-order with the first-order Taylor expansion of $\mathcal{L}({\bm{W}}+\Delta{\bm{W}})$, which is precisely $\mathcal{L}({\bm{W}})+\langle\nabla_{\bm{W}}\mathcal{L}({\bm{W}}),\Delta{\bm{W}}\rangle$, since otherwise the bound would be violated for sufficiently small $\Delta{\bm{W}}$. To obtain the second-order piece of the bound, it’s easiest just to multiply out $\mathcal{L}({\bm{W}}+\Delta{\bm{W}})$ and see that the second-order piece of $\mathcal{L}({\bm{W}}+\Delta{\bm{W}})$ satisfies:

: \nameref*prop:steepest-modular

For each layer $l=1,...,L$, we decompose $\Delta{\bm{W}}_{l}$ into its magnitude and direction: $\Delta{\bm{W}}_{l}=c_{l}\cdot{\bm{T}}_{l}$, for $c_{l}\geq 0$ and $\|{{\bm{T}}_{l}}\|_{l}=1$. Under this change of variables, the minimization becomes:

where Equation 53 follows by observing that at the minimum we must have $s_{1}c_{1},...,s_{L}c_{L}$ all taking the same value of $\eta\geq 0$ (still to be determined), since otherwise we could increase the sum $\sum_{l}c_{l}\|{{\bm{G}}_{l}}\|_{l}^{\dagger}$ by increasing any of the slack $c_{l}$ without paying a penalty in terms of the max. We can now read off the minimizers from Equations 51, 52 and 53:

Combining, we obtain the overall minimizer for each $l=1,...,L$ via $\Delta{\bm{W}}_{l}=c_{l}\cdot{\bm{T}}_{l}=-\frac{\eta}{s_{l}}\operatorname*{arg\,max}\,\langle{\bm{G}}_{l},{\bm{T}}_{l}\rangle$, where $\eta$ is given by Equation 56, proving the result.

: \nameref*prop:tractable-norms