The Geometry of Sign Gradient Descent
Authors: Lukas Balles
Fabian Pedregosa
Nicolas Le Roux
Venue:  (2020)
Keywords: Sign gradient descent
signSGD
steepest descent
Adam

Abstract: Sign gradient descent has become popular in machine learning due to its favorable communication cost in distributed optimization and its good performance in neural network training. However, we currently do not have a good understanding of which geometrical properties of the objective function determine the relative speed of sign gradient descent compared to standard gradient descent. In this work, we frame sign gradient descent as steepest descent with respect to the maximum norm. We review the steepest descent framework and the related concept of smoothness with respect to arbitrary norms.
By studying the smoothness constant resulting from the $L^\infty$-geometry, we isolate properties of the objective which favor sign gradient descent relative to gradient descent. In short, we find two requirements on its Hessian: (i) some degree of ``diagonal dominance'' and (ii) the maximal eigenvalue being much larger than the average eigenvalue. We also clarify the meaning of a certain separable smoothness assumption used in previous analyses of sign gradient descent.
Experiments verify the developed theory.

Under review as a conference paper at ICLR 2020
THE GEOMETRY OF SIGN GRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Sign gradient descent has become popular in machine learning due to its favorable communication cost in distributed optimization and its good performance in neu- ral network training. However, we currently do not have good understanding of which geometrical properties of the objective function determine the relative speed of sign gradient descent compared to standard gradient descent. In this work, we frame sign gradient descent as steepest descent with respect to the maximum norm (Lm-norm). We review the steepest descent framework and the related concept of smoothness with respect to arbitrary norms. By studying the smoothness con- stant resulting from the 7, -geometry,
isolate properties of the objective which favor sign gradient descent relative to gradient descent. short, we find two re- quirements on its Hessian: (i) some degree of "diagonal dominance" and (ii) the maximal eigenvalue being much larger than the average eigenvalue. We also clar- ify the meaning of certain separable smoothness assumption used in previous analyses of sign gradient descent. Experiments verify the developed theory.
INTRODUCTION
We consider unconstrained, continuous optimization problem, min f(x)), with differen- tiable and lower-hounded objective f: Rd + R. The prototypical first-order optimization algorithm to solve this problem is gradient descent (GD), which iteratively updates E++1 = Dz - ag Vf,, where fe fxx)). Several recent works have considered the sign gradient descent (signGD) method,
Et+1 = x; - 0z sign( Vf).
(1)
where the application of the sign is be understood elementwise. This method is attractive in distributed optimization where it conveniently reduces the communication cost to single bit per gradient coordinate (e.g., Seide et al., 2014; Karimireddy al., 2019), but its interest extends beyond that. Balles & Hennig (2018) and Bernstein et al. (2018) point out that sign gradient descent is closely related to the popular Adam method (Kingma & Ba, 2015) and demonstrate that it often achieves similar practical performance on deep learning tasks. Studying sign gradient descent can thus be seen as a step towards a better understanding of the ubiquitous Adam method.
1.1 OVERVIEW AND CONTRIBUTIONS
In this work, we make the following contributions:
We review the concept of steepest descent with respect to arbitrary norms, which includes both gradient descent and sign gradient descent. While these ideas feature in previous works, we provide concise and general write-up which we hope to useful its own right. We emphasize the role of the smoothness constant of f w.r.t. norm as major driver of the performance of the associated steepest descent method.
2. Since sign gradient descent is steepest descent w.r.t. the maximum norm, study the corre- sponding smoothness constant Los isolating properties of the objective function which favor sign gradient descent. We pinpoint requirements on its Hessian: ((i) some degree of "diago- nal dominance" and (ii) the maximal eigenvalue being much larger than the average eigenvalue.
3. We verify our theory experimentally both quadratic functions and deep networks.

---

Under review as a conference paper at ICLR 2020
Method
Norm
Dual
Update direction
Gradient descent
ll
Sign gradient descent
80
1+ I]
IV (Vg)
Coordinate descent
[ -loo
V Venn (frra)
(see Appendix, A.1)
Block normalized GD
1,,00
1. (Vrms((V))
(see Appendix. A.1)
Table 1: A few steepest descent methods. The table lists the used norm its dual . || and the resulting update direction. The significance the dual norm will be explained in 32.1.
1.2 RESTRICTIONS
While modern machine learning often relies on stochastic optimization, this work focuses on the geometric aspects of sign gradient descent and we restrict ourselves the deterministic setting to facilitate this analysis. Furthermore, our interest in signGD is from an optimization perspective and we will not consider the question of generalization. It should be noted that sign gradient descent has been observed to lead to slightly deteriorating generalization performance compared to gradient descent in neural network training (Wilson al., 2017; Balles Hennig, 2018).
STEEPEST DESCENT AND SMOOTHNESS CONSTANTS
In this section, we review the steepest descent' framework, which encompasses both gradient de- scent and sign gradient descent. Embedding both methods in common framework will facilitate our comparative analysis. Steepest descent with respect to norm
||. defined via the update rule
L++1 mrg f + (Vf. xx) +
- x21l²)
(2)
#ERd
2
minimizing a local linear approximation of plus quadratic norm penalty. This minimizer need not be unique, in which case steepest descent is to be understood as choosing any solution.
It is straight-forward to see that gradient descent is steepest descent with respect the Euclidean norm. Similarly, a version of sign gradient descent arises as steepest descent with respect to the maximum norm, ||=|||o = max; |2a]. Namely,
2t - 0z V sign f.) E arg min #ERS
(f+ ( - xx)
x xz 11a
(3)
20z
This update is equivalent to Eq. (1) to the scaling with the gradient norm | /|1 which may be subsumed the step size.? Table lists few more steepest descent methods, which are discussed in more detail in Appendix A.1.
In the following, we will explore steepest descent in more detail by a) relating to the concept of smoothness w.r.t. arbitrary norms; b) tying its convergence speed to the corresponding smoothness constant; c) linking the smoothness constants to properties of the Hessian.
2.1 SMOOTHNESS WITH RESPECT TO ARBITRARY NORMS
Steepest descent is closely connected to the concept of smoothness w.r.t the relevant norm. We recall that a function f is L-smooth w.r.t. a norm || if
[[V f=))l & Llly - =x|,
Vx, Vx.y5 Rd.
(4)
where || I ||+ denotes the dual norm of |]. defined as ||=||+ maxj|al|s (z. æ). Table lists the dual norm pairs for the methods under consideration in this paper. Smoothness directly motivates steepest descent via the following quadratic bound on the function:
Lemma 1. If f is L-smooth w.n.t. ||-I|, then f(y) < f(x)+ (()) y- 1|1- Va, E IRd.
non-Fuclidean gradient descent (Carlson al., 2015; Kelner et al., 201 4). 2 In this paper we study this version of sign gradient descent to facilitate the analysis in the steepest descent framework. In practice it is more common to use Eq. (1) with constant manually decreasing step size. In Appendix C, discuss possible explanation for this discrepancy.
Also known generalized
2

---

Under review as a conference paper at ICLR 2020
Setting 2, get f - + (Vf.. xx)) + + 211ly xz 1| which resembles Eq. (2) and minimizing with respect to y results steepest descent update with step size a = 1/L. (The proofs of this lemma and all subsequent results provided in Appendix E.)
Due to the equivalence norms on R", a function that is smooth with respect to one norm is also smooth with respect any other norm. However, the tightest possible smoothness constant,
[V Vz)1l..
sup 2fy
(5)
will differ depending on the choice of norm. In the following, when we say f L-smooth w.r.t. I|- we will always assume L to be given by Eq. (5). As we will see next, this constant will govern the convergence speed of the corresponding steepest descent method.
2.2 CONVERGENCE OF STEEPEST DESCENT
We now recall existing convergence results for steepest descent methods based on the smoothness constants w.r.t. arbitrary norms. The assumption of smoothness crucial since guarantees an improvement in function value:
Lemma 2. If f is L-smooth w.r.t || then single steepest descent step with step size 1/L satisfies
1
f(x s f(x) 2L [
Without additional assumptions, this yields O(1/T) convergence to a first-order stationary point: Proposition 1. If is L-smooth w.rlf || then steepest descent (Eq. 2) with or = 1/1 satisfies
T-1
2L - f*) Σ I
T
T
By nature of Proposition 1, all steepest descent methods will enjoy the same rate of convergence. But Lemma 2 and Proposition differ across different steepest descent methods in (i) the smoothness constant, and (ii) the norm in which the gradient magnitude is measured. These two aspects will play role when compare sign gradient descent and gradient descent Section 4.
Appendix A contains stronger convergence results under additional assumptions, in particular linear convergence under the Polyak-Lojasiewicz condition. We omit these results here they are of primary interest to our discussion and, in fact, hide the dependence on the gradient norm which we see clearly in Lemma and Proposition
2.3 SMOOTHNESS AS BOUND ON THE HESSIAN
The definition of smoothness in Eq. (4) is unwieldy. For the Euclidean norm, a more intuitive characterization widely known: a twice-differentiable function f is smoshh w.r.t. the Euclidean norm if and only if ||V S Lg for all æ E Rd. Here, || - l2 for matrices denotes the spectral norm, given by the largest-magnitude eigenvalue for symmetric matrices. In the following proposition we show that smoothness with respect to any other norm likewise arises from bound on the Hessian, but in different matrix norms. In Section 3, we will use this better understand the smoothness constant w.r.t. the maximum norm, which critically affects the performance of signGD,
Proposition 2. For any norm ||- on Rd, we define the matrix norm
sup =1
||
(8)
Then, a difiediiferettiablee f is L-smooth w.r.t. || and only (V < for all x.
The proof can be found in Appendix E; we are not aware of prior works showing this for the general For the Fuclidean norm, Proposition 2 gives back the familiar spectral norm bound.
3

---

Under review as a conference paper at ICLR 2020
0_ = 0%
0 = 10
0 30
Figure I: Loe increases as the Hes- sian becomes less axis-aligned. Contour line of f(x) = Hæ, which forms an ellipse with prin- cipal axes given by the eigenvec- tors and axis lengths given by the inverse eigenvalues, We construct H E Rdxd with a fixed Amin and variable L2 Amax > as well as the angle 0 between eigen- vectors and coordinate axes.
Amax 2.0
Loo 3.00
Loo 3.34
Lo 3.87
Amax = 4.0
Lio0
5.00
1. = 6.03
1 = 7.60
3 UNDERSTANDING THE SSOOOHHNSS CONSTANT
We have seen in Section 2.2 that the smoothness constant w.r.t. norm is crucial driver of the con- vergence speed of the associated steepest descent method. While we have a good intuition for Eu- clidean smoothness-
upper bound the eigenvalues of the Hessian this is somewhat lacking for smoothness w.r.t. the maximum norm. Our goal in this section is to understand which properties of the objective function affect the constant Lo The Euclidean smoothness constant L2 will thereby serve as a reference point. We assume f to be L2-smooth w.r.t. || || and Log- w.r.t. || llsc in the "tight" sense of Eq. (5). Basic inequalities between the norms yield (see Appendix E)
La < Lix S dl2.
The smoothness constant governing the convergence speed of sign gradient descent will always be larger than the one pertinent gradient descent. This does not mean that signGD is always worse than GD. In addition to being a bound, the smoothness constant is only one factor influencing the convergence speed; Lemma shows that the dual gradient norm plays role as well. As we will discuss in Section 4, this gradient norm is larger for signGD which can make up for the disadvantage of a larger smoothness constant. this section we will characterize conditions under which Tooe is "not too bad"-in particular much smaller than its worst case of such that signGD can be competitive with gradient descent.
Our discussion will use the Hessian-based formulation of the smoothness constants (Proposition 2). We assume f to be wiice-differentialle As mentioned before, the Euclidean smoothness constant is simply given by the magenitea eigenvalue. The max-norm smoothness constant is deter- mined by
Too
sup V (x)),,,,,, ZERe
|
bo,1 bo,,
sup |Hæl|1-
(10)
||
Unfortunately, computing |o,, through the following upper bound.
1 is NP-hard (Rohn, 2000). However, we can obtain some insight
Proposition 3. Let E Raxd be nonzero, positive semi-defiite with eigenvalues Ai.....
Ag. Then
Σ, HH Eis H
H 1oo,1 S Pding H
with Pding H
(11)
The quantity Paing (H) E [d-1, measures the percentage diagonal mass of the Hessian and thus relates to the "axis-alignment" of the objective. Indeed, diagonal matrices satisfy Paing and their cigenvectors coincide with the coordinate axes. Proposition thus indicates that L will depend both on the "axis-alignment" of the Hessian well as its eigenvalues. This is in stark contrast to gradient descent, for which the relevant matrix norm, H 2, is invariant to rotations. Figure provides a two-dimensional illustration.
Using Proposition 3, we can now answer our question: Under what conditions is Loc. "not too bad" compared to l.2? Firstly, Te benefits from high Pding. i.e., an approximately diagonal Hessian
4

---

Under review as a conference paper at ICLR 2020
axis-aligned objective. Secondly, the sum of eigenvalues should be much smaller than its worst of d'Amax or, equivalently, the average eigenvalue should be much smaller than the maximal one: X == E X; < Amax- The second condition will be met if the spectrum is dominated by small number of "outlier eigenvalues" that far exceed the bulk of eigenvalues. Notably, both the relative axis-alignment and the skewed spectrum have been observed in neural network training (Adolphs et al., 2019; Chaudhari et al., 2017: Ghorbani et al., 2019).
The discussion in the preceding paragraphs was based on an upper bound, since || intractable. Section 5 will feature experiments on quadraties of moderate dimension, where || H bo.1
oo. is generally
can be computed confirm these findings for the exact Lo
4 GRADIENT DESCENT VS SIGN GRADIENT DESCENT
We found in Section 3 that Loo will always exceed L2, and identified conditions under which Loo dL2. By Lemma 2, the guaranteed improvement of the two methods at a R is
[GD( = [V
VS. Isgaaaa (a) = [Vf(2
L2
L
We will now compare the two methods based on these improvement guarantees, thus taking into account the dual gradient norm in addition to the smoothness constant. Basic inequalities between the two relevant norms, Vd[==122 122 2 |||||| 2 ||||| for = E RR show that this potentially favors sign gradient descent. Following Bernstein et al. (201 8), it will be convenient to define the ratio
||
<(z) = d|| 12
E [d [d='.]].
which can be seen as a measure of the "density" of the vector i.e., how evenly its mass is dis- tributed across coordinates." 3 With that, we can write
R(x) = IsignGD
/V L2 <(V
dL2 L.o
(12)
Ian (ax)
M L
If Loo < dL2, for which have identified conditions in Section 3, and the gradient is dense, iee. (V(())) >> d=1, then sign gradient descent will achieve larger improvement than gradient descent at æ E Rd.
We can make this comparison even more palpable. We restrict to quadratic functions, such that [x)( H and Th H 1o well as Lg H
Amax- Assume H to be positive definite with eigenvalues λ1, A4. Then Proposition 3 in Eq. (12) yields
R(ar)
Zzign(i(
Paing!
H
Amax
(VV(())
(13)
IGD(
Eld-1,11
E[L.d]
Eld-1.1]
Hence, sign gradient descent will outperform gradient descent if (i) the Hessian is some extent di- agonal, (ii) the maximal eigenvalue is much larger than the average eigenvalue, and (iii) the gradient vector is relatively dense.
We emphasize that this is local comparison at E Rd due to the dependence on the gradient fx))..
tempting try and lower-bound the gradient density d(V(()) > Φy >>>>> d for all x in order to make global statements. Bernstein et al. (2018) assume such lower bound when contrasting signGD and GD in their analysis. However, oi (x) can easily be shown attain d-1 even on quadratics. Any non-trivial lower bound would thus have to be restricted to the trajectory of the optimizer and take into account the initialization, which seems out of reach at the moment. The
effect of the gradient norm thus remains an empirical question which we now address.
5
EXPERIMENTS
5.1 QUADRATIC PROBLEMS
We first consider synthetic quadratic problems of moderate dimension d = 12, where com- pute and control all relevant quantities. To validate our theoretical findings, we generate Hessians
Note that d(z) for x (1,...,1) 1)T and Φ(z) d for 0).
5

---

Under review as a conference paper at ICLR 2020
L L2
T
sign
r 1|2
||
-r'112
10
10.0
9
10.0
101
Amao A
7.5
Amax/ A
7.5
100
5.0
5.0
3
10-1
2.5
2
2.5
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Figure 2: We consider quadratic objectives varying across two axes: Amax A as well rotation value 0. The left plot depicts the ratio of the two relevant smoothness constants, Loo is sensitive to 0 and grows relative to L2 Ama as the problem becomes less axis-aligned. The right plot depicts the relative performance of gradient descent and sign gradient descent these problems. GD drastically (the colormap is clipped) outperforms signGD for mildly conditioned (small Xmax/ and non-axis aon-axes-lligned (large 0) problems. However, sign gradient descent is preferable for problems with high \max/ X, given that they have some degree of axis-alignment (small f). The dashed line represents equal performance of both algorithms.
with varying X/ A/Amax and axis alignment. We set the eigenvalues as A diag(1, (, .......... .,,,,,,,,,,, Amax). To control the axis-alignment, we rotate the cigenvectors by some ratio 9 in the direction prescribed by randomly-dram rotation matrix. We can simply think of as degree of non-axis-alignment the technical details can be found in Appendix D. For each Hessian, we compute the two smoothness constants L2 Amax and Los || |oo, We then run T 100 iterations of gradient descent (with a = 1/2 and sign gradient descent (with a = Lo) and compute the distance to the op- performance measure. We average over repeated runs with 20 ~ [00, I) to marginalize out the effect of initialization. The results are depicted in Fig. 2 and confirm the findings of Sections and 4. The T.xo constant-and consequently the performance of signGD sensitive to the axis-alignment of H and suffers as we increase A. For problems with Amax > that are somewhat axis-aligned, sign gradient descent outperforms gradient descent, even on these simple quadratic problems.
timum | x=" 1|2
5.2 NEURAL NETWORK EXPERIMENTS
Variants of sign gradient descent have been shown to achieve surprisingly good performance in neural network training tasks (Balles & Hennig, 2018; Bernstein et al., 2018). this section, we want to test whether the theory developed above can help explain these successes. Applying theory to deep learning scenario comes with several caveats. First, the objectives are not globally smooth in the sense of Eq. (4); also discussion in Appendix C. However, the theory of smooth optimization still applies in a local sense within neighborhood of the current iterate. Second, even computing local smoothness constants is intractable in these complex and high-dimensional problems. Finally, neural networks are usually trained in stochastic optimization setting, whereas our theory considered only the deterministic case.
With these limitations in mind, we proceed as follows. We train vanilla convolutional neural network as well as a ResNet20 (He al., 2016) on the CIFAR-10 dataset using gradient descent and sign gradient descent (in their stochastic versions). For each architecture and algorithm, we optimize step size over logarithmic grid to make sure we are close to the optimal step size, as theory assumes. At regular intervals (once per epoch) along the trajectory of the two methods, we approximate the local improvement ratio R(x) defined in Eq. (12). While the gradient density is easy to compute by evaluating the full-batch gradient, approximate the two smoothness constants with directional finite differences following Zhang et al. (2019), Details can found in Appendix D.
We then compare the sequence of ratios to the actual training loss performance of the methods. We see in Figure 3 that the results match our bound: for the CNN, the ratios are close to but initially bigger and signSGD outperforms SGD. For the ResNer20, the ratio is consistently below 1 and SGD

---

Under review as a conference paper at ICLR 2020
CNN
SGD
along the SGD trajectory
SignSGD
along the SianSGo trajectory
(mimibatch) Training Lass
Improvement ratio R(6))
1.2
1.1
1.0
2000
4000
5000
8000
10000
20
60 Epochs
80
100
120
Number Iterations
ResNet20
Resnet20
10a
Sign5GD
elong the SGD trajectory
(minibetch) J Training Loss
Improvement rallo Rix)
along SignSGD trajectory
2.2
2.0
1.8
1.6
5000
10000 15000
20000 25000 30000
100
200
400
Number iterations
Epochs
Figure 3: Experiments on CIFARIO 10 dataset. When using a CNN (top), signSGD outperforms SGD (top left), which matches the behaviour predicted by the improvement ratio (top right), above at the beginning. When using ResNet20 (bottom), the situation is reversed but the improvement ratio still correctly predicts the relative performance of both algorithms.
the faster algorithm. We can also note that the ratios computed along the two trajectories do not differ substantially, suggesting some degree of robustness. There still some issues. For instance, in the second experiment, SignSGD outperforms SGD later training, which not captured by our ratio. While these experiments are means conclusive, they give strong indication that the theory of this paper is relevant to explaining the practical performance of sign-based optimization methods.
6 RELATED WORK
6.1 STEEPEST DESCENT
Steepest descent is basic concept and has become text book knowledge (Boyd & Vandenberghe, 2004, $9.4). Its origins are hard to trace back. works (Nesterov,
implicitly-in many 2005; 2012; Allen-Zhu & Orecchia, 2014; Kelner al., 2014; Carlson et al., 2015; Karimi al., 2016, e.g.). Kelner et al. (2014) and Carlson et al. (2015) point out that sign gra- dient descent is steepest descent w.r.t. the maximum norm; the former applies signGD to max-flow problems in graphs.
Steepest descent resembles mirror descent (Nemirovsky & Yudin, 1983; Beck & Teboulle, 2003), which updates Ft+1 = arg min,(((V ft, x - xx) + (x, xx)), where By. is a Bregman di- vergence. Despite the obvious similarity, this setting does not cover steepest descent, since many squared norms (notably the maximum norm) can not be written Bregman divergences.
6.2 PREVIOUS WORKS ON SIGN GRADIENT DESCENT
version of sign gradient descent has first been explored in neural network training by Seide et al. (2014) with the goal of gradient compression for distributed optimization. The proposed algorithm

---

Under review as a conference paper at ICLR 2020
deviates from signGD in that it uses enror feedback mechanism to approximate gradient descent as closely as possible while maintaining high compression rates. Such eπror feedback was later refined and given theoretical grounding by Karimireddy et al. (2019).
The use of sign gradient descent itself (or rather its stochastic version) was popularized by Bernstein al. (2018), who present theoretical analysis in the stochastic setting. The relatively strong assumptions of this work have since been relaxed by Bernstein et al. (2019) and Safaryan Richtárik (2019). All three papers are based the assumption that there exist constants 1; > 0 such that
f(y)= S f(x) + (Vi(=), 2) 2 55400 44
x.)²: Yx, y E Rd
(14)
We refer to this assumption as sepurable smoothness to emphasize the fact that the change in func- tion value separates over individual coordinates. Under this assumption the convergence of signGI depends E; 4 whereas the convergence speed of gradient descent is driven by 4max max; 4.
Not only is the meaning of these 4 's unclear, but neither the algorithm itself nor the analysis uses the individual 1 s. It thus seems that the separable smoothness assumption adds an unnecessary level of granularity. Indeed, we will now show that
separable smoothness implies (E; -mmoothhsssss with respect to the maximum norm, and iii existing convergence proofs go through under the latter (weaker) assumption.
To formalize (i), we identify separable smoothness as 1-smoothness w.rt. the norm || |12 where L diag(h,...... and ||= == (E,4,3% such that Lemma coincides with Eq. (14). With that, we can establish the following result:
Proposition 4. If f is 1-smooth w.r.t || ||.. then f is 4:)4)-mmoohh w.r.f the maximum norm.
Statement (ii) follows from the simple fact that the quadratic bounds provided by the two conditions coincide for any method with updates of equal magnitude in each coordinate, 2++1 E {-c, c)d, which includes any version of sign gradient descent. Since existing convergence results base upon this bound, they go through under either condition. We refer to Appendix B for details.
Based on these considerations we argue that smoothness w.r.t. the maximum norm is the more natural assumption under which to analyze sign gradient descent. We discuss this issue in much more detail in Appendix B.
CONCLUSIONS
Our analysis relates the speed of signGD to the axis-alignment of the objective's Hessian and the spread of its eigenvalues. This furthers our understanding of when this method and similar ones, like Adam, might outperform standard GD. It is notably of interest that these properties of the Hessian have independently been studied (Chaudhari et al., 2017: Ghorbani et al., 2019; Adolphs et al., 2019) with the conclusion that modern architecture tend be well-suited the use of signGD.
Besides the limitations discussed in $5.2, we also sidestepped the question of the scaling of the sign gradient descent update with V fell.. which arises from the steepest descent formalism but is not common in practice. Appendix C discusses this issue and how the absence of the scaling term makes sense more general setting than the one studied here.
This work raises several questions for future research. The first one is whether we can design archi- tecture that could further help the convergence of signGD. The second one whether we can design optimizers that adapt to the geometry of the space. Ideally, one might want the norm of steepest descent to be optimized alongside the parameters. Finally, one might ask whether there are other norms and corresponding steepest descent methods that work even better on contemporary neural network architectures. We explore one option, norm-norral gradient descent, in Appendix A.
REFERENCES
Leonard Adolphs, Jonas Kohler, and Aurelien Lucchi. Ellipsoidal trust region methods and the marginal value of Hessian information for neural network training. arXiv preprint arXiv: 1905.09000901111 2019.
8

---

Under review as a conference paper at ICLR 2020
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint arXiv:1407.1537, 2014.
Lukas Balles and Philipp Hennig. Dissecting Adam: The sign, magnitude and variance of stochastic gradients. Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research. PMLR, 2018.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 2003.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. SignSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th In- ternational Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research. PMLR, 2018.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Arizzadeneshelii and Animashree Anandkumar. SignSGD with majority vote is communication efficient and fault tolerant. In 7th International Conference on Learning Representations (ICLR), 2019.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
David Carlson, Ya-Ping Hsieh, Edo Collins, Lawrence Carin, and Volkan Cevher. Stochastic spectral descent for discrete graphical models. IEEE Journal of Selected Topics in Signal Processing, 10 (2), 2015.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-SGD, Biasing gra- dient descent into wide valleys. In 5th International Conference on Learning Representations (ICLR), 2017.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via Hessian eigenvalue density. arXiv preprint 1901.10/901 2019.
Boris Ginsburg, Patrice Castonguay, Oleksii Hrinchuk, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary, Jason Li, Huyen Nguyen, and Jonathan M Cohen. Stochastic gradient methods with layer- wise adaptive moments for training of deep networks. arXiv preprint arXiv: /286, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python, 2001. URL http:// / /www. scipy org/.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the chine Learning and Knowledge Discovery in Databuses. Springer, 2016.
condition. Joint European Conference on Ma-
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Proceedings of the 36th International Con- ference on Machine Learning (ICML), volume of Proceedings of Machine Learning Research. PMLR, 2019.
Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time gorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms. SIAM, 2014.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations (ICIR), 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.

---

Under review as a conference paper at ICLR 2020
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
Yurii Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103 (I), 2005.
Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2). 2012.
Jiri Rohn. Computing the norm b|, is NP-hard. Linear & Multilinear Algebra, 47, 2000.
Mher Safaryan and Peter Richtárik. On stochastic sign descent methods. 1905. 2019.
arXiv preprint
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pat data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Adams Wei Yu, Lei Huang, Qihang Lin, Ruslan Salakhutdinov, and Jaime Carbonell. Block- normalized gradient method: An empirical study for training deep neural network. arXiv preprint arXiv:1707.0482 04822, 2017.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Analysis of gradient clipping and adaptive scaling with relaxed smoothness condition. arXiv preprint arXiv: 1905. 2019.
10

---

Under review as a conference paper at ICLR 2020
-SUPPLEMENTARY MATERIAL-
We now provide additional details and results for the paper. More precisely:
Appendix gives additional details on steepest descent methods.
Appendix B extends the discussion on the relationship between separable smoothness and smoothness w.r.t. the maximum norm.
Appendix C discusses extension of recently-proposed relaxed smoothness condition as a possible explanation of normalized methods (such as sign gradient descent without the scaling by the norm).
Appendix D provides details on the experiments.
All proofs, including those of results in the appendices, can be found Appendix
A DETAILS ON STEEPEST DESCENT
In this section, we provide a more comprehensive overview of steepest descent methods as well as additional results. In particular, we recall the linear convergence under the Polyar-Lojasiewiez condition.
will be useful to re- re-write the steepest descent update (Eq. 2) as
(z. 10000222100 [1e113) -11111--
x++1 zz Ot V
with z arg max yER
(15)
This equivalence arises from substituting
1 (æ mz); a full proof can be found in Appendix E
A.1 ADDITIONAL EXA MPLES STEEPEST DESCENT METHODS
First, we give additional examples for steepest descent methods to demonstrate the versatility of this framework.
A.1.1 COORDINATE DESCENT
Steepest descent with respect to the L -nom.
Øt+1 E arg min f (V (V - xx) +
--112 ||0 xell?]
1
(16)
20r
yields coordinate descent,
F1+1 D; are V. fe.tmm (f
(17)
where the selected coordinate is chosen from imax arg max:e(d] V fr. and ( denotes the i-th coordinate vector. The corresponding smoothness assumption is
|VV(()) [x()) 5 Lilly a||1-
(18)
In fact, this assumption implies the coordinate-wise Lipschitz smoothness assumption,
Vf( + he( Vf(x), < 4 |1 Vi [d],
(19)
which is widely-used in the literature on coordinate descent, since
V f(x + h)) - vs(z),) < (x + he(l)) - [f(x)
(20)
(18)
< L1 x + he - æ011 = L1/4/.
11

---

Under review as a conference paper at ICLR 2020
A.1.2 BLOCK- BOOCK-NORMALIZED GRADIENT DESCENT
Assume block structure on R given by a partitioning B [BI,... ...... B.} of [d]. with Ba [d].
B&BB, nB, 0 for k + I, and Uj By = [d]. For B C [d]. define na RIBl to be the vector consisting of (B))EBB We can now define norms with respect to this block structure, such as
|| |
max l with dual norm BEB
| B,
Σ
(21)
BEB
Steepest descent w.r.t. || |lB,c0 results in normalizdd gradient descent,
ffll = [V normg( ff), norma(2) =
2
(22)
|ZB
I lla
This method is block-wise equivalent of sign gradient descent, normalizing the update magnitude over blocks instead of element-wise. Variants of this method have recently been studied empiri- cally for neural network training (Yu et al., 2017; Ginsburg et al., 2019). It would be interesting future work to analyze this method in the steepest descent framework, similar to our analysis of sign gradient descent in this paper.
A.2 PROPERTIES OF THE STEEPEST DESCENT OPERATOR
We define the |||l|| operator as:
|||| = max (z, (2,0) x)
z
-1-l arg max
(z,
(23)
||||
VERd
The following Lemma connects this operator to the dual norm: Lemma 3. For all x, z 12d, we have
(a) (x,, 2) S ||==||
(24)
(b) || (z, Hl))
(25)
(c) ||z||=|||| |||||-
(26)
A.3 ADDITIONAL CONVERGENCE RESULTS FOR STEEPEST DESCENT
For smooth and convex functions, Kelner et al. (2014) showed O(1/T) convergence in suboptimal- ity. We restate this result here for completeness.
Theorem (Theorem 1 in Kelner et al. (2014)). If f is L-smooth w.r.t || and convex, then steepest descent (Eq. 2) with step size a; = 1/L satisfies
LL
fT l < + with R = a s.. ((m)Sf(mm) m² st. [(x)) )=f
(27)
min
|
x=
The rate has dependence on the initial distance to the nearest minimizer measured in the respective norm.
is also straightfforwat to show linear convergence in suboptimality under an additional assump- tion, known as the [[V](()) (x) - f*) but can likewise formulated for arbitrary norms. Definition 1. A function f: IRd + RR satisfies the PL condition w.r.t norm if [
(PL) condition. It is usually given for the Euclidean case as
2p([(=)) - f) for all æ E IRd.
We refer to this PL with respect to || even though only the dual norm appears in the definition, since it the natural counterpart to smoothness w.r.t. ||- and used to prove linear convergence for
steepest descent w.r.t. ||- |]. As with smoothness, norms, but constants may differ. Note that strong convexity implics the PL condition, but the class of PI. functions also covers some non-convex functions.
have equivalence of the PL condition for all
12

---

Under review as a conference paper at ICLR 2020
Theorem 2. If is L-smooth and fulfills the PL condition with constant W.ET descent (Eq. 2) with step size a; = L/L satisfies
then steepest
--- -1- (Jo (*).
(28)
We are not aware of any published work showing this simple result in its general form. We give the very short proof here.
Proof of Theorem 2. Combining Lemma and the condition gives
1
Set1 S J.
2T. V
(29)
4 (f- f*).
S ft L
(30)
Subtracting f from both sides and iterating backwards yields the statement.
B DETAILS ON THE RELATIONSHIP BETWEEN SEPARABLE SMOOTHNESS AND SMOOTHNESS W.R.T. THE MAXIMUM NORM
This section presents additional insights on the relationship between separable smoothness and smoothness w.r.t. the maximum norm. We discuss how separable smoothness relates to properties of the Hessian of the objective and give two-dimensional quadratic example to support intuition. Finally, we show that existing convergence proofs for (stochastic) sign gradient descent go through when replacing the separable smoothness assumption with the weaker smoothness w.r.t. the maxi- mum
B.1 SEPARABLE SMOOTHNESS AS A DIAGONAL BOUND ON THE HESSIAN
Bernstein et al. (2018) note that, for twice-differentiable f. separable smoothness results from L < f(x L for all æ E I& with L diag(4,.... l4). is tempting to think of them as bounds will
on the eigenvalues of V fxx), but this is only true for diagonal matrices. In the following, see that these values also depend on the axis-alignment of the Hessian and will generally exceed the eigenvalues. Moreover, since "=" is only partial ordering, it is not clear what the "tightest" possible bound of this form would be. Since the performance of signGD depends on E; 4, the most favorable bound will be
min 200
Σ4 s.t. - L ~> I
Vo E Tdd
(31)
We will adopt this definition in the following.
This opens up alternative view on the relationship between separable smoothness and smoothness w.r.t. the maximum norm, which operates on the bessiaa-bbseed definitions of the notions of smoothness.
Proposition 5. Let H Raxd be positive semi-definite with eigenvalues A , da and define
Loo (H)
max [1
Hz
L (H)
min 4:20
Σ 4
s.t.
H 1 diag(h. ........ ..).
(32)
Then
Loo H)) < Leep H) S Pdiag H
A
(33)
Hence, Lee boper-bounds Lxs while at the same time being upper-bounded by the same quantity that appears in Proposition 3.
13

---

Under review as a conference paper at ICLR 2020
0
0%
0 = 10
0 = 30
2.0
Amax =
Amax = 4.0
H
diag(4;)
Amax
Figure 4: For H E Raxd, plot contour line of f(æ) 1 Hæ, which forms ellipse with principal axes given by the eigenvectors and axis lengths given by the inverse eigenvalues. We fix Amin 1 and vary Amax 1 well as the angle 0 between eigenvectors and coordinate axes. Separable smoothness bounds H by a diagonal matrix, diag(4) ž H, corresponding to an axis-aligned ellipse that lies fully within the H-ellipse. (We choose I, according to Eq. 31.) The bound changes with the axis-alignment of H, becoming both smaller and more circular (i.e., larger and more similar 4) H rotates further from the coordinate axes. In contrast that, Euclidean smoothness bounds H by Amax I > H, i.e., a circle, which is rotation-invarie
B.2 SEPARABLE SMOOTHNESS FOR TWO-DIMENSIONAL QUADRATICS
To build some intuition for the separable smoothness condition, consider the case of two- dimensional quadratic with positive definite Hessian f(x = H [ [ In this, case, we can
find the solution to Eq. (31) in closed form (proof in Appendix E):
4 a + 16/, 1== d 1b].
(34)
visualization given Figure and clearly shows that the choice of I; sensitive to the axis alignment of the Hessian.
The eigenvalues H evaluate to
a d
(a
d)2
11/2 = 2
+
+ b2
(35)
4
We see that, for [b] > O, we will have Imax > Amax. We also see that Imax can exceed Amux and is thus misleading to assume the convergence of GD to driven by 4max.
Also note that L.c = H |bo.1 + d + 2|6| E, 4, reflecting the link to smoothness w.r.t the maximum norm, as discussed the main text.
'Of course, we could deviate from the definition of Eq. (31) and choose 7, Amax guarantee 1 Amus- However, this bound would not be favorable for the performance of signGDD, which depends Σ, 4,
14

---

Under review as a conference paper at ICLR 2020
B.3 EXISTING CONVERGENCE PROOFS Go TROUGH UNDER SMOOTHNESS W.R.T. THE MAXIMUM NORM
Let #++1 2t c-c, for some E R. Then the separable smoothness bound implies
f fit (V - xx) + 1
2
4 (I++1,1 x1,))
(36)
= + - + 2
Σ4.
and the -mooothhsss w.r.t. the maximum norm yields (via Lemma 1)
Se+1 s + (V T++1 -x4) =2 Toc
|
(37)
6²
= -e (V (441 - ax.)
T.xc
Hence, smoothness w.r.t the maximum norm with constant L = E, provides exactly the same local bound for any method with updates of equal magnitude in each coordinate. This includes any version of sign gradient descent, including in the stochastic setting. Since the convergence proofs given by Bernstein et al. (2018; 2019) and Safaryan & Richtárik (2019) all start from this bound, they go through when replacing the separable smoothness assumption with the weaker assumption of (2), 1 4s)smoothssss w.r.t. the maximum norm.
C GENERALIZING RELAXED SMOOTHNESS
We have discussed a scaled version of sign gradient descent, .t = Ct alVVfill sign V ft), whereas in practice the update is usually x++1 2g Oa sign fi) with constant or manually decreasing step size a₁, Without this additional / term, this is a normalized method with an update magnitude determined solely by the step size, independent of the gradient V There are many possible reasons why this might be beneficial in practical settings like neural network training. One rationale is that these applications are usually in the stochastic optimization setting, where decreasing step size is needed anyway to enforce convergence. Since || fillll is not available in the stochastic setting, it might be easier to subsume a similar scaling effect in the manually-tunee step size schedule.
There is however another potential explanation in terms of the smoothness exhibited by neural net- work training objectives. Zhang et al. (2019) discussed the normalized gradient descent method,
1
Ø1+1 Dt VVA 3 V
(38)
This method is normalized since its update magnitude upper-bounded by || - ær|12 a irrespective of the gradient magnitude. For small gradient V < 3, the method reverts back to classical gradient descent. They show that this normalized method is better geared towards the type of regularity exhibited by, say, neural network training objectives, which are not smooth in the sense of Eq. (4). They propose a "relaxed" smoothness assumption which allows the curvature to grow with the gradient norm instead of bounding it globally in classical smoothness.
Since they consider normalized gradient descent, their discussion based on Euclidean geometry. We show here that their reasoning can be generalized arbitrary norms, similarly the standard smoothness assumption discussed in the main text. This provides a possible explanation of the practical success of normalized methods, which sign gradient descent (Eq. 1) if we omit the scaling by felli.
C.I RESULTS OF ZHANG ET AL. (2019)
The relaxed smoothness condition proposed by Zhang et al. (2019) reads [>)((= - (,(0) + r / [ ((x)
2
(39)
15

---

Under review as a conference paper at ICLR 2020
where || 1/22 for matrices denotes the spectral norm. This allows for the curvature grow with the gradient norm, in contrast to classical smoothness, which demands a global bound on the Hessian.
This relaxed smoothness gives rise to normalized gradient descent since, will see later, pro- vides a bound the form
fi+1 S ft + (Vft, zx) + 2 BlVAl))) 22112- A,B20
(40)
This resembles the bound of Lemma but the quadratic term now scales with the gradient norm. minimized by a normalized gradient descent update with appropriately chosen a and J3.
The main finding of Zhang al. (2019) is that gradient descent become arbitrarily slow for the class of functions satisfying this relaxed smoothness, whereas normalized gradient descent (Eq. 38)
retains an O(1/²2) rate of convergence to e-stationary point.
C.2 NORMALIZED STEEPEST DESCENT
In this section, we generalize the concept of relaxed smoothness to arbitrary norms, which will give rise to general normalized steepest descent methods. We define relaxed smoothness w.r.t. to some norm || analogously to the Fuclidean case (Eq. 39), but use the dual norm for the gradient and the induced matrix norm of Proposition 2 for the Hessian.
Definition 2. A function f is called (L) (1)) -mmoosh with respect to some norm ||
[<) S (0) + [=))),
(41)
where || for matrices is the norm defined Eq. (8).
Under this smoothness assumption, we have the following local quadratic bound:
Lemma 4. Assume f is (L) -smooth with respect to norm Then for 2, E Rd with
yy æ|| S Zay.
f(y) S f(x) + (VI(z) - x) + (5 + 4L [V(+))))))) - x012
(42)
This resembles the bound in Lemma but the quadratic term now scales with the gradient norm. In analogy to steepest descent, we can now construct an optimization method that minimizes this bound in each step. Using Lemma 4 with æ; yields
f(v) < St + (VS.. m.) (5 + 4T. [VA]))) ax.1?
(43)
Choosing I441 as the minimizer w.r.t. y results the update
3t+1 3t (5L + 4L (V.ll))
1
V
(44)
We refer to the resulting method as normalized steepest descent. To see that it is in fact normalized method, recall from Lemma that || fll and, hence, the update magnitude is upper- bounded by (1)
We now show that the convergence theorem of Zhang al. (2019) carries over to this generalized setting. The proofs (see Appendix E) are straight-forward adaptations of that in Zhang et al. (2019), with little bit of extra care with regards to the norms.
Theorem 3. Assume f is (L))) -mmotth with respect to a norm || ||. Then normalized steepest descent (Eq. 44) converges to an e-stationary point. [[ 1|+ S in at most
()) (2
T: =8(fo fa) fax max
(45)
2
[(0)
iterations.
16

---

Under review as a conference paper at ICLR 2020
D EXPERIMENTAL DETAILS
D.1 QUADRATIC EXPERIMENTS
Generating Hessians. W draw random rotation matrix R from the Haar distribution' and set the Hessian to be H R A (R"")", where R for 0 E [0, 1] is non-integer matrix power and A' denotes the conjugate transpose matrix. We can think of this as rotating the eigenvectors of the Hessian by fraction of 0 in the direction prescribed by R. The non-integer matrix power Rº is computed via the eigendeconposition
UDU The matrix power is then given by R = UD where D for the diagonal matrix D is obtained its elements to the power O.
Computing Los. To compute the smoothness constant w.r.t. the maximum norm, we have to com- pute the matrix norm |||lo.. maxi|=ll>> < |aall We use the fact that the solution is attained at {-1. 1]dd (see Rohn, 2000) and frrre-force search for the maximum H this set. Since there are 2d vectors in 1-,,1) this is only possible for relatively small dimension.
On the performance measure. When comparing gradient descent and sign gradient descent on these quadratic problems, that we are interested in comparison over a range of different quadratics with varying Amax The function value, which scales with Xmax would not be suitable for such comparison. Since comparing optimization methods which are adapted to different norms, it might make a difference which norm choose compute the distance the optimum. We opted for the Fuclidean norm to benefit the baseline method (gradient descent) as the lesser of two evils.
the distance the optimum performance measure. The reason
D.2 NEURAL NETWORK EXPERIMENTS
In this section we give mode details on the experimental setting used in Figure
Dataset. We used the CIFAR10 (Krizhevsky et al., 2009) dataset, which contains 50,000 images of size (32, 32, 3). In all cases we used a batch-size of 1000 samples.
Architecture. We considered two different architectures for these experiements. The first one is convolutional neural network (CNN) as implemented in keras, 6 consisting of 4 convolutional layers with ReLU activations, and one last dense layer with softmax activation function. The second architecture that we consider ResNet20, (He et al., 2016) model, consisting of 20 layers and 0.27 million parameters.
Algorithm and hyperparameter selection. We consider both SGD and signSGD with an added momentum term since this matches most closely the algorithms used in practice for this task. For SignSGD, the sign is computed in this case on the full update, and not only on the gradient.
These algorithms have two hyperparameters to tune: the step-size and momentum.
We select the step-size independently for each algorithm and architecture to yield the high- est decrease in training loss at 200 and 600 epochs for the CNN and ResNet20 architecture, respectively, which is when both architectures reach 85% test set accuracy.
For the momentum parameter, we use the Keras default of 0.9 for all optimizers and archi- tectures.
'The uniform distribution the special orthogonal group SO(d) d-dimensional rotation matrices. We used the special lorttho_groorr function provided by the scipy.sta. stats package (Jones al., 2001). httpps / / thub. com com//eras-- tean/keras.ae.ee ob/master peattter/exampppe /s far1 cnnn..
py
17

---

Under review as a conference paper at ICLR 2020
Estimating smoothness constants. ness using directional finite differences. At a point æ, we approximate
Following Zhang al. (2019), approximate the smooth-
V + 78) (2))2
f min
. 0 fx)
(46)
7 7
Vf(x + 78) - (z))
_ = min
. 02 sign Vf())),
(47)
> S |||00
where 0n and 02 are the respective "opttmal" step size for GD and signGD.
E PROOFS
We now list the proofs all theoretical results from the main text.
E.1
PROOF LEMMA
Proof.
Define g(T) = f(x + T(U x)) for E [0, with g((r) (Vf(z - -(v x)). y x))
Then
f(y) = f(x)+ + f/' g((T)dr
= f(x) + [ (V + + x)) x)dT
f(()) (Vf(x), x) / (Vf(x + T -(y- Vf(x), 2)
(20 S f(x) + (Vf(z), x) + VVf(x + T x)) vf(=)) fly =||dr (48)
(4)
& f())) + (Vf(z). y 2) + L|| - x) 2||dr
L' rdr
f(x) (V)()) z) + L
x1?
L
= -a()) + (V y x) マタ ly x
The first inequality is due to Lemma 3(a) and the second inequality uses the T-smoothness.
E.2 CONVERGENCE PROOFS FOR STEEPEST DESCENT
Proof of Lemma 2. We apply Lemma with y = + x
1, [
I
f(x*) S f(x) + (Vf(x), x+ - x) +
2 /11x²= x01
-(x) + (V/(x), -, (2))l)) + -
1
v (zx
(49)
2
f(x) (V)) v)(x))) - 1 [>>(>))
By Lemma 3, we have (v)(x), (x())ll11) = [/( = |V Substituting this in yields the desired bound.
Proof of Proposition 1. Lemma 2 gives
|/ < 2L(f - ft+1)
(50)
Rearranging and summing for 0, O....,T T yiclds
1
I <
2L T-1
Σ (fr fet1)
2T ST)
2L - fd)
(51)
T
T
T
T
0
0=0
18

---

Under review as a conference paper at ICLR 2020
E.3 PROOF OF PROPOSITION
Note that the matrix norm by construction satisfies
H - H ||||||
(52)
Proof. We first show that Eq. (8) defines matrix norm. Clearly | 2 and H = 0 H = 0.
Furthermore, || |||| H
||
It remains to show subadditivity, Let H H' 12dd
+ H
sup |
|I + H' >=|l S sup H ||. + H =1l.)
|
(53)
<
sup
Ha
+ sup |
H x ||
|| + | |||
|
Now assume [[]](x))] I L for all Rd L, y Id and define g(T) ff + T x))) for r E [0, 1].
d ((())))
VV(i) v((2))).
dr
% V2 f2 7(y 11yyxx)) + 20)dr
/ | ( x))(4 =)||, dr
(54)
(52)
$ / [V2 f(x + T x)) 2||d7
< L1yy - æll / ldt = -1y æ||.
Conversely, assume L-smoothness and fix Rd For any || < and 0.
10 V ( + T8)
VV + +88) v/(2)) Eb||s|| Se.
(55)
Dividing by and letting E + 0, we get
1 (1 / V2 v2f(x TS)dT 8
[()) = lim
c-0 E Jo
(56)
1
lim
+ +
$ L.
8-0 E
This implies [+3((=)] s|s
[>>)(=))||- L.
E.4 PROOF PROPOSITION
Proof. First note that
H
1oo. == sup
Ha = sup
Σ
Σ Hijay
S Σ
High
(57)
||]|| 11
||||||
$1
2,f
Recall that E, Hii Ex Hit
E, >r for positive definite matrices. Then
Hyl = Ei, HHgj
H bo.1 &
Σ A Pding (H) A
(58)
Σ, Hia
1.j
19

---

Under review as a conference paper at ICLR 2020
E.5 PROOF OF EQ. (9)
Proof. The fact that ||=||00 < || - | implies
V fyy)
V f())l22
[Vy Vf(2))11 Loo.
L2 = sup
sup aнy
sup œ/y
(59)
|y 2112
y - x: 100
Conversely, using va 31|1= 1 1 || - <d
V fV(y)) vf(2))11
Vf - vf(a)]l2 = dL2.
Loo = sup
sup
(60)
afy
x |00
afy
y
E.6 PROOF LEMMA
Proof. Statement (a) follows immediately from the definition of the dual norm.
Regarding (b), by definition of =1l-11, we know that (z, cz ||c2|- || is maximized by c = 1.
Hence the derivative w.r.t. C,
(z, cz IHl
-
|| [=
= (z, =1113 - -
(61)
de
must evaluate to 0 at 1, which proves (b). For (c), we use the equivalent definition
(x, z)
|| = max x²0
(62)
|
Assume w.l.o.g. that 2l1-11 + 0. Then
(a,, z)
{z z) (b)
||||| max æ#0
|||||||||-
(63)
||00|
| |1|
Conversely, Let x' arg max (x, z). such that (z, x²) = ||||... Then
5 |= = (z, || - |||=||=00| - (z, x|Hl
1 ||
11ll (b) 1
| 113
(64)
2
2
where the inequality by definition of ==1-11_
E.7 PROOF OF PROPOSITION
Proof. The dual norm of || || is || -|,-,, such that the assumption of 1-smoothness w.r.t.
|| ||z
amounts to
[V V vf(2) l is
æille Yx, Rd.
(65)
First, by definition of the maximum norm, get
||
41 <
11
L|| Iba
(66)
Secondly, using Cauchy-Schwarz,
||
Σ
|
Σ
V4
Σ 4
Σ
(67)
VT
Combining these two inequalities with the assumption yields the assertion:
- V((z),
4llVf(() vf(z))lz-
-
Σ 41l -a--xl æ11z
(68)
(66)
Σ 1 Σ 4lly - 21110
4
x 10-
20

---

Under review as a conference paper at ICLR 2020
E.8
PROOF OF EQ. (15)
Proof. The equivalence arises from substituting y - _ (e xt,) or x 2x - o.y. With a slight
abuse of notation:
1
1 E arg
aargmin min
(V fe, x - xzi) +
|| - =x111
20c
1141 E 3t - a arg min
(V aayy + - || - ary1l
20xt
y
(69)
1 ||Bvll?
I++1 E at Og arg min
- (V nn +
1 -1111(²)
#1+1 Bt an arg max
(V
(V [t, y)
E.9 PROOF OF PROPOSITION
Proof. First inequality: First, let l1...., la 2 0 be the minimizer in the definition of Loo For any with |0 < 1, we have
>' S x diag(L. ................................ 1a)= Σ 42 S Σ 4.
(70)
Next, we rewrite the definition of Loo as
Loo
max dell w...llllll s0 $1
x² Hy.
(71)
and let (#, g) be the maximizer. Then due to H being psd, we have
0 v + ")" H - ( - Ha 26 Hÿ + 9 HD S Σ 20"
26 Hý.
(72)
where the last inequality is due Eq. (70) applied & and ÿ. This proves the assertion, since Σ, 4 Leep and a" Hÿ Loo by definition.
Second inequality: We set 4 = E, Hayl and denote L =
1a). Then
[L H|
2
Σ
Hul
(73)
Σ IL
H
Σ
Hul
(74)
jfi
making --H diagonally dominant with non-negative diagonal elements, hence positive semi- definite. Therefore, in the solution space of the definition of Txee- Now,
Σ, Hil Ees
Σ4=
Hij
Σ A
(75)
Hiyl
where we used E, |Ha = E, H = E.
E.10
PROOF Eo. (34)
Proof. In two dimensions, the constraint diag(11,4) 12) H 2 0 can be written as
1 - a 2 and (4 a) - d) b² 2 by the leading principle minors criterion for positive definiteness. All "boundary" solutions can be written as
(76)
122 1 d 122
1 + Out of those, the one that minimizes
0.
(77)
1, easily found be given by [b], resulting in 4 + 16/, 12 = d 16).
(78)
n
21

---

Under review as a conference paper at ICLR 2020
E.11 PROOFS FOR APPENDIX C
All proofs are closely following the ones given for the Euclidean norm in Zhang et al. (2019).
To prove Lemma 4, we first need the following Lemma, which allows control the growth of the gradient norm in the vicinity of a point æ E IR".
Lemma 5. Assume Eq. (41) holds and let with ly æil S Lay. Then
[f S
(a) + /Vf(2))..)
(79)
Proof.
Define x(7) = x + x) as well as g(7) = v](((()) with v (((()())))==z)
Then
[V(((())) [z(x)) + S o'
S [[V/(>))] f llg(()))l
[V[(=>]|- + / ((=)(( - =2))l
(80)
[f(x))] + 11 x
|(>](<(T))]
dr
$1/20
[L0++001\//<<>) (41)
L / (00) +
1
< [[))
(
Laj [V/(x()))l
Applying the integral form of Groenwall's inequality" yields
(())
(( +
()) [
[V < | V/())] +
exp(t r)dr.
(82)
La
We now specialize to f. = and upper-bound the integrand
Laj L' [I
(
(
< [[f(x)|
exp(1 - r) dr
Laj
21
Sexp(1)<3
(83)
(
(
f( dr
< [V]())]|
La) +3 [IV
L()
(()))
[() + +[V[(()))l.
We can now approach the proof of Lemma 4.
7 Groenwall's inequality says that if u(() I a(l) + 1t B(r)u(r)dr for continuous and 8, then
u(t) < a(t) + '' ((T))((T)))))))))))))))))))))))) exp ( B(r)dr) dr.
(81)
We apply it here with u(t) [[Tf(( and att) ||V + (0) (1,0) and B(7) 1.
22

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 4. According to Taylor's theorem have
f(y) = f(x) + (Vf()), - x)
x))
(84)
with some fx + T => e [0,1]}. We can bound the quadratic term
(24)
=, v2 f(E) x))
yy ==1ll>1 x]||+
y x f(E)
(85)
(41) S (7
0 L [[())))) =||2.
The first inequality is by definition of the dual norm (see Lemma 3). The second inequality is by con- struction of the induced matrix norm. The final inequality uses the relaxed smoothness assumption (Eq. 41).
Next, since l1y =| s 1/L(1) by assumption of Lemma know || x S kay Lemma thus gives us
Vf(E)). S L()
+ +VV(()))..)
(86)
Plugging this back into Eq. (85) yields
x, (V) - =)) s (5I(0) + 4L VT( x11
(87)
Using that in Eq. (84) proves the assertion.
Finally, we prove Theorem 3
Proof of Theorem 3. Using Lemma 4 with æ 2t and y 1t+1 v |||| yiclds
v (5I, (0) + 4L [ 1/2
f411 S fo ne ft, V ||)
(88)
Recall from Lemma 3 that (1=11
|
|| and, hence,
fi1 S ft n/c
(V..
V |
(L 00)
2
=
T 2
(5L (0)
4L
(vll))) W
(89)
ft 2 [.
f < Vfll. < (0)) ()) we get
22
F0t1 S St
(90)
(8
If V/ll. 2 (1(0) (I0)) we get
V 11
fet1 S
2(5L(0) (0) (1 [+
- 10T10) / fell- + 87()
(91)
1VA.
ft
18L()
(())
$ ft 18(L
23

---

Under review as a conference paper at ICLR 2020
Hence,
J41 S ft -min [
(92)
18((L))) 18
Now assume that we have T iterations with fill 2 Then
T-1
L
8²
So Sa 2 fT
(Je s(+1) T min
(93)
18(()))22
(8)
0=
Rearranging yields
fo /.
[100 (L
S 18
18(fo f.) max
(94)
min
((0) (Z09)2 7,00
22 L(0)
24


Reviews:
[{"review_id": "r1gsMvgpFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the performance of sign gradient descent as a function of the “geometry” of the objective. They contrast the performance of sign GD to gradient descent. Both algorithms are steepest descent methods with respect to different norms. Overall, I do not think the insights claimed in the paper are especially novel. It is already known that the choice of a norm can have a significant impact on the speed of steepest descent but practically, the performance depends on quantities that are unknown such as the norm of the gradient over the specific trajectory of the algorithm. I do not find the arguments in section 4 especially convincing as they seem rather high-level to me. Instead I would find it more valuable if one could make a statement about the performance of signGD as a function of known quantities. One could perhaps start by analyzing a specific class of functions (quadratics, Polyak-Lojasiewicz functions, …).\n\nPrior work\nIt seems to me that most results discussed in the paper are already known in the optimization community. The book by Boyd & Vandenberghe (cited by the authors) has an entire section on the “Choice of norm for steepest descent” where they indeed explain that the choice of the norm used for steepest descent can potentially have a dramatic effect on the convergence rate. Can the authors explain how they see their contribution compared to prior work? I could concede that the result of Proposition 3 is somewhat novel, although I think the authors should discuss prior work on axis-alignment, which dates back to \nBecker, Sue, and Yann Le Cun. \"Improving the convergence of back-propagation learning with second order methods.\" Proceedings of the 1988 connectionist models summer school. 1988.\n\nSection 4\nThe discussion in section 4 is high-level and I don’t see any particular insight one gains over what’s already known (see again book by Boyd & Vandenberghe). As explained by the authors, the comparison between signGD and GD will depend on the trajectory being followed.\n\nStochastic setting\nCan the authors comment on generalizing their results to a stochastic setting? Since the gradients have a larger norm when using the infinity norm, I would expect that the variance is also larger.\n\nExperimental results\nThe empirical results on the neural networks do not seem especially convincing, and the authors do seem to acknowledge this. What aspect of the analysis or the experimental setup do you expect to be responsible for this? Have you considered optimizing smaller models first? (something in between the quadratic problem in section 5.1 and the neural net in section 5.2. Some sort of ablation study where one strips away various components (batch-norm, residual connections, ….) of a neural network would also be valuable.\n\nGeneralization\nOne aspect that might be worth investigating is the generalization ability of steepest descent for different norms. There is already some prior work for adaptive methods that could perhaps be generalized, see e.g.\nWilson, Ashia C., et al. \"The marginal value of adaptive gradient methods in machine learning.\" Advances in Neural Information Processing Systems. 2017.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJxz7YuTYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies sign gradient descent in the framework of steepest descent with respect to a general norm. The authors show the connection to a smoothness with respect to a general norm, which is further related to a bound on the Hessian. Based on the interpretation of steepest descent, the authors compare the behavior of sign gradient descent with the gradient descent, and show that the relative behavior depends on both the percentage of diagonal ? and the spread of eigenvalues. Some experimental results are reported to verify the theory.\n\nThe paper is very well written and easy to follow. The theoretical analysis is sound and intuitive. However, the paper considers a variant of sign gradient descent where the l_1 norm of the gradients are introduced. The introduction of this l_1 norm is required for the interpretation of a steep descent but is not the one used often in practice.\n\nMost analysis seem follows from standard arguments. The extension from gradient descent to the steep descent with a general norm is a bit standard. In this sense, the paper is a bit incremental.\n\n----------------------\nAfter rebuttal:\n\nI have read the authors' response. I think the contribution may not be sufficient. I would like to keep my original score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BylbgAdatr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper tries to study the sign gradient descent by the squared maximum norm.  The authors clarify the meaning of a certain separable smoothness assumption using previous studies for signed gradient descent methods.\n\n1. The authors change the problem. They study the sign gradient times its norm, not the classical sign gradient. \nIn fact, this change dramatically changes the flow in continuous time. \n\n2. The results are too general, which does not focus on machine learning problems. \n\n3. The paper is clearly not written well with many typos. The organization of the paper also needs to be improved a lot for publication. \n\nFor these reasons, I clearly reject this paper for publications.  ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is rejected based on unanimous reviews.
Decision: Reject