Title: 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 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 (L ∞ -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 ∞ -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.

1. INTRODUCTION:

We consider an unconstrained, continuous optimization problem, min x∈R d f (x), with a differentiable and lower-bounded objective f : R d → R. The prototypical first-order optimization algorithm to solve this problem is gradient descent (GD), which iteratively updates x t+1 = x t -α t ∇f t , where f t := f (x t ). Several recent works have considered the sign gradient descent (signGD) method,

EQUATION

where the application of the sign is to be understood elementwise. This method is attractive in distributed optimization where it conveniently reduces the communication cost to a single bit per gradient coordinate (e.g., Seide et al., 2014; Karimireddy et 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:

1. 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 a concise and general write-up which we hope to be useful in its own right. We emphasize the role of the smoothness constant of f w.r.t. a norm as a 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, we study the corresponding smoothness constant L ∞ , isolating properties of the objective function which favor sign gradient descent. We pinpoint two requirements on its Hessian: ((i) some degree of "diagonal dominance" and (ii) the maximal eigenvalue being much larger than the average eigenvalue.

3. We verify our theory experimentally on both quadratic functions and deep networks.

Method Norm Dual Update direction Gradient descent • 2 • 2 ∇f Sign gradient descent • ∞ • 1 ∇f 1 sign(∇f ) Coordinate descent • 1 • ∞ ∇fi max e (imax) (see Appendix. A.1) Block-normalized GD • B,∞ • B,1 ∇f B,1 normB(∇f ) (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 of the dual norm will be explained in §2.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 to 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 et al., 2017; Balles & Hennig, 2018) .

2. STEEPEST DESCENT AND SMOOTHNESS CONSTANTS:

In this section, we review the steepest descent1 framework, which encompasses both gradient descent and sign gradient descent. Embedding both methods in a common framework will facilitate our comparative analysis. Steepest descent with respect to a norm • is defined via the update rule

x t+1 ∈ arg min

EQUATION

minimizing a local linear approximation of f plus a 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 to the Euclidean norm. Similarly, a version of sign gradient descent arises as steepest descent with respect to the maximum norm, z ∞ := max i |z i |. Namely,

x t -α t ∇f t 1 sign(∇f t ) ∈ arg min

EQUATION

)

This update is equivalent to Eq. ( 1) up to the scaling with the gradient norm ∇f t 1 which may be subsumed in the step size. 2 Table 1 lists a 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 it 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

EQUATION

where • * denotes the dual norm of • , defined as z * := max x ≤1 z, x . Table 1 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.r.t. • , then f (y) ≤ f (x)+ ∇f (x), y-x + L 2 y-x 2 ∀x, y ∈ R d .

Setting x = x t we get f (y) ≤ f t + ∇f t , yx t + L 2 yx t 2 which resembles Eq. ( 2) and minimizing with respect to y results in a steepest descent update with step size α t = 1/L. (The proofs of this lemma and all subsequent results are provided in Appendix E.) Due to the equivalence of norms on R d , a function that is smooth with respect to one norm is also smooth with respect to any other norm. However, the tightest possible smoothness constant,

EQUATION

will differ depending on the choice of norm. In the following, when we say f is L-smooth w.r.t. • , 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 is crucial since it guarantees an improvement in function value:

Lemma 2. If f is L-smooth w.r.t.

• , then a single steepest descent step with step size 1/L satisfies

EQUATION

Without additional assumptions, this yields O(1/T ) convergence to a first-order stationary point:

EQUATION

By nature of Proposition 1, all steepest descent methods will enjoy the same rate of convergence. But Lemma 2 and Proposition 1 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 a role when we compare sign gradient descent and gradient descent in Section 4.

Appendix A contains stronger convergence results under additional assumptions, in particular linear convergence under the Polyak-Łojasiewicz condition. We omit these results here as they are not of primary interest to our discussion and, in fact, hide the dependence on the gradient norm which we see clearly in Lemma 2 and Proposition 1.

2.3. SMOOTHNESS AS A BOUND ON THE HESSIAN:

The definition of smoothness in Eq. ( 4) is unwieldy. For the Euclidean norm, a more intuitive characterization is widely known: a twice-differentiable function

f is L 2 -smooth w.r.t. the Euclidean norm if and only if ∇ 2 f (x) 2 ≤ L 2 for all x ∈ R d .

Here, • 2 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 a bound on the Hessian, but in different matrix norms. In Section 3, we will use this to better understand the smoothness constant w.r.t. the maximum norm, which critically affects the performance of signGD.

Proposition 2. For any norm • on R d , we define the matrix norm

H := sup x ≤1 Hx * . (8) Then, a twice-differentiable f is L-smooth w.r.t. • if and only if ∇ 2 f (x) ≤ L for all x.

The proof can be found in Appendix E; we are not aware of prior works showing this for the general case. For the Euclidean norm, Proposition 2 gives back the familiar spectral norm bound. Contour line of f (x) = 1 2 x T Hx, which forms an ellipse with principal axes given by the eigenvectors and axis lengths given by the inverse eigenvalues. We construct H ∈ R d×d with a fixed λ min = 1 and variable L 2 = λ max > 1 as well as the angle θ between eigenvectors and coordinate axes.

λ max = 2.0 L ∞ = 3.00 θ = 0 • L ∞ = 3.34 θ = 10 • L ∞ = 3.87 θ = 30 • λ max = 4.0 L ∞ = 5.00 L ∞ = 6.03 L ∞ = 7.60

3. UNDERSTANDING THE L ∞ -SMOOTHNESS CONSTANT:

We have seen in Section 2.2 that the smoothness constant w.r.t. a norm is a crucial driver of the convergence speed of the associated steepest descent method. While we have a good intuition for Euclidean smoothness-an upper bound on 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 L ∞ . The Euclidean smoothness constant L 2 will thereby serve as a reference point. We assume f to be L 2 -smooth w.r.t. • 2 and L ∞ -smooth w.r.t. • ∞ in the "tight" sense of Eq. ( 5). Basic inequalities between the norms yield (see Appendix E)

EQUATION

The smoothness constant governing the convergence speed of sign gradient descent will always be larger than the one pertinent to 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 2 shows that the dual gradient norm plays a 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. In this section we will characterize conditions under which L ∞ is "not too bad"-in particular much smaller than its worst case of dL 2 -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 twice-differentiable. As mentioned before, the Euclidean smoothness constant is simply given by the largest-magnitude eigenvalue. The max-norm smoothness constant is determined by

EQUATION

Unfortunately, computing H ∞,1 is NP-hard (Rohn, 2000) . However, we can obtain some insight through the following upper bound. Proposition 3. Let H ∈ R d×d be nonzero, positive semi-definite with eigenvalues λ 1 , . . . , λ d . Then

EQUATION

)

The quantity ρ diag (H) ∈ [d -1 , 1] measures the percentage of diagonal mass of the Hessian and thus relates to the "axis-alignment" of the objective. Indeed, diagonal matrices satisfy ρ diag = 1 and their eigenvectors coincide with the coordinate axes. Proposition 3 thus indicates that L ∞ will depend both on the "axis-alignment" of the Hessian as 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 1 provides a two-dimensional illustration.

Using Proposition 3, we can now answer our question: Under what conditions is L ∞ "not too bad" compared to L 2 ? Firstly, L ∞ benefits from high ρ diag , i.e., an approximately diagonal Hessian or axis-aligned objective. Secondly, the sum of eigenvalues should be much smaller than its worst case of dλ max or, equivalently, the average eigenvalue should be much smaller than the maximal one:

λ := 1 d i λ i λ max .

The second condition will be met if the spectrum is dominated by a 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 H ∞,1 is generally intractable. Section 5 will feature experiments on quadratics of moderate dimension, where H ∞,1 can be computed to confirm these findings for the exact L ∞ .

4. GRADIENT DESCENT VS SIGN GRADIENT DESCENT:

We found in Section 3 that L ∞ will always exceed L 2 , and identified conditions under which L ∞ dL 2 . By Lemma 2, the guaranteed improvement of the two methods at x ∈ R d is

I GD (x) := ∇f (x) 2 2 L 2 vs. I signGD (x) := ∇f (x) 2 1 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,

√ d z 2 ≥ z 1 ≥ z 2 for all z ∈ R d ,

show that this potentially favors sign gradient descent. Following Bernstein et al. (2018) , it will be convenient to define the ratio

φ(z) := z 2 1 d z 2 2 ∈ [d -1 , 1],

which can be seen as a measure of the "density" of the vector z, i.e., how evenly its mass is distributed across coordinates. 3 With that, we can write

EQUATION

If L ∞ dL 2 , for which we have identified conditions in Section 3, and the gradient is dense, i.e. φ(∇f (x))

d -1 , then sign gradient descent will achieve a larger improvement than gradient descent at x ∈ R d .

We can make this comparison even more palpable. We restrict to quadratic functions, such that ∇ 2 f (x) ≡ H and L ∞ = H ∞,1 as well as L 2 = H 2 = λ max . Assume H to be positive definite with eigenvalues λ 1 , . . . , λ d . Then Proposition 3 in Eq. ( 12) yields

EQUATION

Hence, sign gradient descent will outperform gradient descent if (i) the Hessian is to some extent diagonal, (ii) the maximal eigenvalue is much larger than the average eigenvalue, and (iii) the gradient vector is relatively dense.

We emphasize that this is a local comparison at x ∈ R d due to the dependence on the gradient ∇f (x). It is tempting to try and lower-bound the gradient density φ(∇f (x)) ≥ φ g d -1 for all x in order to make global statements. Bernstein et al. (2018) assume such a lower bound when contrasting signGD and GD in their analysis. However, φ(∇f (x)) can easily be shown to 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 we can compute and control all relevant quantities. To validate our theoretical findings, we generate Hessians We consider quadratic objectives varying across two axes: λ max /λ as well as a rotation value θ. The left plot depicts the ratio of the two relevant smoothness constants. L ∞ is sensitive to θ and grows relative to L 2 = λ max as the problem becomes less axis-aligned. The right plot depicts the relative performance of gradient descent and sign gradient descent on these problems. GD drastically (the colormap is clipped) outperforms signGD for mildly conditioned (small λ max /λ) and non-axis-aligned (large θ) problems. However, sign gradient descent is preferable for problems with high λ max /λ, given that they have some degree of axis-alignment (small θ). The dashed line represents equal performance of both algorithms.

with varying λ/λ max and axis alignment. We set the eigenvalues as Λ = diag(1, 1, . . . , 1, λ max ). To control the axis-alignment, we rotate the eigenvectors by some ratio θ in the direction prescribed by a randomly-drawn rotation matrix. We can simply think of θ as a degree of non-axis-alignment; the technical details can be found in Appendix D. For each Hessian, we compute the two smoothness constants L 2 = λ max and L ∞ = H ∞,1 . We then run T = 100 iterations of gradient descent (with α = 1/L 2 ) and sign gradient descent (with α = 1/L ∞ ) and compute the distance to the optimum x T -x * 2 2 as a scale-invariant performance measure. We average over repeated runs with x 0 ∼ N (0, I) to marginalize out the effect of initialization. The results are depicted in Fig. 2 and confirm the findings of Sections 3 and 4. The L ∞ constant-and consequently the performance of signGD-is sensitive to the axis-alignment of H and suffers as we increase θ. For problems with λ max λ that are somewhat axis-aligned, sign gradient descent outperforms gradient descent, even on these simple quadratic problems.

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) . In this section, we want to test whether the theory developed above can help explain these successes. Applying our theory to a deep learning scenario comes with several caveats. First, the objectives are not globally smooth in the sense of Eq. ( 4); see also our discussion in Appendix C. However, the theory of smooth optimization still applies in a local sense within a 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 a stochastic optimization setting, whereas our theory considered only the deterministic case.

With these limitations in mind, we proceed as follows. We train a vanilla convolutional neural network as well as a ResNet20 (He et 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 the step size over a logarithmic grid to make sure we are close to the optimal step size, as our 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, we approximate the two smoothness constants with directional finite differences following Zhang et al. (2019) . Details can be found in Appendix D.

We then compare the sequence of ratios to the actual training loss performance of the two methods. We see in Figure 3 that the results match our bound: for the CNN, the ratios are close to 1 but initially bigger and signSGD outperforms SGD. For the ResNet20, the ratio is consistently below 1 and SGD , above 1 at the beginning. When using a ResNet20 (bottom), the situation is reversed but the improvement ratio still correctly predicts the relative performance of both algorithms.

is 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 are still some issues. For instance, in the second experiment, SignSGD outperforms SGD later in training, which is not captured by our ratio. While these experiments are by no means conclusive, they give a 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 a basic concept and has become text book knowledge (Boyd & Vandenberghe, 2004, §9.4) . Its origins are hard to trace back. It features-sometimes implicitly-in many works (Nesterov, 2005; 2012; Allen-Zhu & Orecchia, 2014; Kelner et al., 2014; Carlson et al., 2015; Karimi et al., 2016, e.g.) . Kelner et al. (2014) and Carlson et al. (2015) point out that sign gradient 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

x t+1 = arg min x ( ∇f t , x -x t + 1 αt B ψ (x, x t ))

, where B ψ is a Bregman divergence. Despite the obvious similarity, this setting does not cover steepest descent, since many squared norms (notably the maximum norm) can not be written as Bregman divergences.

6.2. PREVIOUS WORKS ON SIGN GRADIENT DESCENT:

A 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 deviates from signGD in that it uses an error feedback mechanism to approximate gradient descent as closely as possible while maintaining high compression rates. Such error 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 et al. (2018) , who present a 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 on the assumption that there exist constants l i > 0 such that

EQUATION

)

We refer to this assumption as separable smoothness to emphasize the fact that the change in function value separates over individual coordinates. Under this assumption the convergence of signGD depends on i l i whereas the convergence speed of gradient descent is driven by l max := max i l i .

Not only is the meaning of these l i 's unclear, but neither the algorithm itself nor the analysis uses the individual l i 's. It thus seems that the separable smoothness assumption adds an unnecessary level of granularity. Indeed, we will now show that (i) separable smoothness implies ( i l i )-smoothness with respect to the maximum norm, and (ii) existing convergence proofs go through under the latter (weaker) assumption.

To formalize (i), we identify separable smoothness as 1-smoothness w.r.t. the norm • L where L = diag(l 1 , . . . , l d and z 2 L := i l i z 2 i , such that Lemma 1 coincides with Eq. ( 14). With that, we can establish the following result:

Proposition 4. If f is 1-smooth w.r.t. • L , then f is ( i l i )-smooth w.r.t. 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, x t+1 -x t ∈ {-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.

7. 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 to be well-suited to 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 ∇f t 1 , 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 in a more general setting than the one studied here. This work raises several questions for future research. The first one is whether we can design architecture that could further help the convergence of signGD. The second one is 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, block-normalized gradient descent, in Appendix A.

-SUPPLEMENTARY MATERIAL-We now provide additional details and results for the paper. More precisely:

• Appendix A 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 an extension of a 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 in Appendix E.

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-Łojasiewicz condition.

It will be useful to re-write the steepest descent update (Eq. 2) as

EQUATION

)

This equivalence arises from substituting y = -1 αt (x-x t ); a full proof can be found in Appendix E

A.1 ADDITIONAL EXAMPLES FOR STEEPEST DESCENT METHODS:

First, we give two 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 1 -norm,

EQUATION

yields coordinate descent,

x t+1 = x t -α t |∇f t,imax |e (imax) (17)

where the selected coordinate is chosen from i max ∈ arg max i∈[d] |∇f t,i | and e (i) denotes the i-th coordinate vector. The corresponding smoothness assumption is

EQUATION

In fact, this assumption implies the coordinate-wise Lipschitz smoothness assumption,

EQUATION

which is widely-used in the literature on coordinate descent, since

EQUATION

A.1.2 BLOCK-NORMALIZED GRADIENT DESCENT Assume a block structure on R d given by a partitioning

B = {B 1 , . . . , B b } of [d], with B k ⊂ [d], B k ∩ B l = ∅ for k = l, and k B k = [d]. For B ⊂ [d]

, define x B ∈ R |B| to be the vector consisting of (x i ) i∈B . We can now define norms with respect to this block structure, such as

EQUATION

)

This method is a 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 empirically 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 z • operator as:

EQUATION

)

The following Lemma connects this operator to the dual norm: Lemma 3. For all x, z ∈ R d , we have

EQUATION

A.3 ADDITIONAL CONVERGENCE RESULTS FOR STEEPEST DESCENT:

For smooth and convex functions, Kelner et al. (2014) showed O(1/T ) convergence in suboptimality. We restate this result here for completeness.

Theorem 1 (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

α t = 1/L satisfies f T -f ≤ 2LR 2 T + 4 (27) with R := max x s.t. f (x)≤f (x0) min x s.t. f (x )=f x -x .

The rate has a dependence on the initial distance to the nearest minimizer measured in the respective norm.

It is also straight-forward to show linear convergence in suboptimality under an additional assumption, known as the Polyak-Łojasiewicz (PL) condition. It is usually given for the Euclidean case as ∇f (x) 2 2 ≥ 2µ(f (x) -f ) but can likewise be formulated for arbitrary norms.

Definition 1. A function f : R d → R satisfies the PL condition w.r.t. a norm • if ∇f (x) 2 * ≥ 2µ(f (x) -f ) for all x ∈ R d .

We refer to this as PL with respect to • even though only the dual norm appears in the definition, since it is the natural counterpart to smoothness w.r.t. • and used to prove linear convergence for steepest descent w.r.t. • . As with smoothness, we have equivalence of the PL condition for all norms, but constants may differ. Note that strong convexity implies the PL condition, but the class of PL functions also covers some non-convex functions.

Theorem 2. If f is L-smooth and fulfills the PL condition with constant µ w.r.t • , then steepest descent (Eq. 2) with step size α t ≡ 1/L satisfies

EQUATION

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 2 and the PL condition gives

EQUATION

)

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 a 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 maximum norm.

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 ∇ 2 f (x) L for all x ∈ R d with L = diag(l 1 , . . . , l d ). It is tempting to think of them as bounds on the eigenvalues of ∇ 2 f (x), but this is only true for diagonal matrices. In the following, we will see that these values also depend on the axis-alignment of the Hessian and will generally exceed the eigenvalues. Moreover, since " " is only a partial ordering, it is not clear what the "tightest" possible bound of this form would be. Since the performance of signGD depends on i l i , the most favorable bound will be min l1,...,l d ≥0 i

l i s.t. -L ∇ 2 f (x) L ∀x ∈ R d (31)

We will adopt this definition in the following.

This opens up an alternative view on the relationship between separable smoothness and smoothness w.r.t. the maximum norm, which operates on the Hessian-based definitions of the two notions of smoothness.

Proposition 5. Let H ∈ R d×d be positive semi-definite with eigenvalues λ 1 . . . , λ d and define

EQUATION

)

Hence, L sep upper-bounds L ∞ while at the same time being upper-bounded by the same quantity that appears in Proposition 3.

λ max = 2.0 θ = 0 • θ = 10 • θ = 30 • λ max = 4.0 H diag(l i ) λ max I

Figure 4 : For H ∈ R d×d , we plot contour line of f (x) = 1 2 x T Hx, which forms an ellipse with principal axes given by the eigenvectors and axis lengths given by the inverse eigenvalues. We fix λ min = 1 and vary λ max > 1 as well as the angle θ between eigenvectors and coordinate axes. Separable smoothness bounds H by a diagonal matrix, diag(l i )

H, corresponding to an axis-aligned ellipse that lies fully within the H-ellipse. (We choose l 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 l i ) as H rotates further from the coordinate axes. In contrast to that, Euclidean smoothness bounds H by λ max I H, i.e., a circle, which is rotation-invariant.

B.2 SEPARABLE SMOOTHNESS FOR TWO-DIMENSIONAL QUADRATICS:

To build some intuition for the separable smoothness condition, we consider the case of a twodimensional quadratic with positive definite Hessian ∇ 2 f (x) ≡ H = a b b d . In this, case, we can find the solution to Eq. ( 31) in closed form (proof in Appendix E):

EQUATION

)

A visualization is given in Figure 4 and clearly shows that the choice of l i is sensitive to the axis alignment of the Hessian.

The eigenvalues of H evaluate to

EQUATION

)

We see that, for |b| > 0, we will have l max > λ max . 4 We also see that l max can exceed λ max and it is thus misleading to assume the convergence of GD to be driven by l max .

Also note that L ∞ = H ∞,1 = a + d + 2|b| = i l i , reflecting the link to smoothness w.r.t. the maximum norm, as discussed in the main text.

B.3 EXISTING CONVERGENCE PROOFS GO TROUGH UNDER SMOOTHNESS W.R.T. THE MAXIMUM NORM:

Let x t+1 -x t ∈ {-c, c} d for some c ∈ R. Then the separable smoothness bound implies

f t+1 ≤ f t + ∇f t , x t+1 -x + 1 2 i l i (x t+1,i -x t,i ) 2 =c 2 = f t + ∇f t , x t+1 -x t + c 2 2 i l i (36)

and the L ∞ -smoothness w.r.t. the maximum norm yields (via Lemma 1)

EQUATION

Hence, smoothness w.r.t. the maximum norm with constant L ∞ = i l i 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 ( i l i )-smoothness w.r.t. the maximum norm.

C GENERALIZING RELAXED SMOOTHNESS:

We have discussed a scaled version of sign gradient descent, x t+1 = x t -α ∇f t 1 sign(∇f t ), whereas in practice the update is usually x t+1 = x t -α t sign(∇f t ) with a constant or manually decreasing step size α t . Without this additional ∇f t 1 term, this is a normalized method with an update magnitude determined solely by the step size, independent of the gradient ∇f t . 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 a decreasing step size is needed anyway to enforce convergence. Since ∇f t 1 is not available in the stochastic setting, it might be easier to subsume a similar scaling effect in the manually-tuned step size schedule.

There is however another potential explanation in terms of the smoothness exhibited by neural network training objectives. Zhang et al. (2019) discussed the normalized gradient descent method,

EQUATION

This method is normalized since its update magnitude is upper-bounded by x t+1 -x t 2 ≤ α irrespective of the gradient magnitude. For small gradient ∇f t 2 β, 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 as in classical smoothness.

Since they consider normalized gradient descent, their discussion is based on Euclidean geometry. We show here that their reasoning can be generalized to arbitrary norms, similarly to 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) is if we omit the scaling by ∇f t 1 .

C.1 RESULTS OF ZHANG ET AL. (2019):

The relaxed smoothness condition proposed by Zhang et al. (2019) reads

EQUATION

where • 2 for matrices denotes the spectral norm. This allows for the curvature to 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, as we will see later, vides a bound of the form

EQUATION

This resembles the bound of Lemma 1, but the quadratic term now scales with the gradient norm. It is minimized by a normalized gradient descent update with appropriately chosen α and β.

The main finding of Zhang et al. (2019) is that gradient descent can 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 a ε-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 Euclidean case (Eq. 39), but use the dual norm for the gradient and the induced matrix norm of Proposition 2 for the Hessian.

EQUATION

where • for matrices is the norm defined in Eq. (8).

Under this smoothness assumption, we have the following local quadratic bound:

EQUATION

)

This resembles the bound in Lemma 1, 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 x = x t yields

EQUATION

)

Choosing x t+1 as the minimizer w.r.t. y results in the update

EQUATION

We refer to the resulting method as normalized steepest descent. To see that it is in fact a normalized method, recall from Lemma 3 that ∇f • t = ∇f t * and, hence, the update magnitude is upperbounded by 1/4L (1) .

We now show that the convergence theorem of Zhang et 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 a little bit of extra care with regards to the norms. Theorem 3. Assume f is (L (0) , L (1) )-smooth with respect to a norm • . Then normalized steepest descent (Eq. 44) converges to an ε-stationary point, ∇f * ≤ ε, in at most

EQUATION

iterations.

D EXPERIMENTAL DETAILS:

D.1 QUADRATIC EXPERIMENTS Generating Hessians. W draw a random rotation matrix R from the Haar distribution5 and set the Hessian to be H = R θ Λ(R θ ) * , where R θ for θ ∈ [0, 1] is a non-integer matrix power and A * denotes conjugate transpose matrix. We can think of this as rotating the eigenvectors of the Hessian by a fraction of θ in the direction prescribed by R. The non-integer matrix power R θ , is computed via the eigendecomposition R = U DU * . The matrix power is then given by R θ = U D θ U H where D θ for the diagonal matrix D is obtained by its elements to the power θ.

Computing L ∞ . To compute the smoothness constant w.r.t. the maximum norm, we have to compute the matrix norm H ∞,1 = max x ∞ ≤1 Hx 1 . We use the fact that the solution is attained at x ∈ {-1, 1} d (see Rohn, 2000) and brute-force search for the maximum Hx 1 in this set. Since there are 2 d vectors in {-1, 1} d , this is only possible for relatively small dimension.

On the performance measure. When comparing gradient descent and sign gradient descent on these quadratic problems, we use the distance to the optimum as a performance measure. The reason is that we are interested in a comparison over a range of different quadratics with varying λ max . The function value, which scales with λ max would not be suitable for such a comparison. Since we are comparing optimization methods which are adapted to different norms, it might make a difference which norm we choose to compute the distance to the optimum. We opted for the Euclidean norm to benefit the baseline method (gradient descent) as the lesser of two evils.

D.2 NEURAL NETWORK EXPERIMENTS:

In this section we give mode details on the experimental setting used in Figure 3 :

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 a convolutional neural network (CNN) as implemented in keras,6 consisting of 4 convolutional layers with ReLU activations, and one last dense layer with a softmax activation function. The second architecture that we consider is a 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 highest 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 architectures.

Estimating smoothness constants. Following Zhang et al. (2019) , we approximate the smoothness using directional finite differences. At a point x, we approximate

EQUATION

where α 1 and α 2 are the respective "optimal" step size for GD and signGD.

E PROOFS:

We now list the proofs of all theoretical results from the main text.

E.1 PROOF OF LEMMA 1

EQUATION

The first inequality is due to Lemma 3(a) and the second inequality uses the L-smoothness.

E.2 CONVERGENCE PROOFS FOR STEEPEST DESCENT:

Proof of Lemma 2. We apply Lemma 1 with y

EQUATION

)

By Lemma 3, we have ∇f (x), ∇f (x) • = ∇f (x) 

EQUATION

EQUATION

EQUATION

Conversely, assume L-smoothness and fix x ∈ R d . For any s ≤ 1 and ε > 0,

EQUATION

Dividing by ε and letting ε → 0, we get

EQUATION

EQUATION

EQUATION

E.5 PROOF OF EQ. ( 9)

EQUATION

Conversely, using 1

EQUATION

E.6 PROOF OF LEMMA 3

Proof. Statement (a) follows immediately from the definition of the dual norm.

Regarding (b), by definition of z • , we know that z, cz

EQUATION

must evaluate to 0 at c = 1, which proves (b).

For (c), we use the equivalent definition

EQUATION

Assume w.l.o.g. that z • = 0. Then

EQUATION

)

where the inequality is by definition of z • .

E.7 PROOF OF PROPOSITION 4:

Proof. The dual norm of

EQUATION

) First, by definition of the maximum norm, we get

EQUATION

Secondly, using Cauchy-Schwarz,

EQUATION

)

Combining these two inequalities with the assumption yields the assertion:

EQUATION

E.8 PROOF OF EQ. ( 15)

Proof. The equivalence arises from substituting y = -1 αt (xx t ) or x = x t -α t y. With a slight abuse of notation: 

x t+1 ∈

Next, we rewrite the definition of L ∞ as L ∞ = max

x ∞, y ∞ ≤1

x T Hy.

and let ( x, ŷ) be the maximizer. Then due to H being psd, we have

EQUATION

where the last inequality is due to Eq. ( 70) applied to x and ŷ. This proves the assertion, since 

EQUATION

making L -H diagonally dominant with non-negative diagonal elements, hence positive semidefinite. Therefore, L is in the solution space of the definition of L sep . Now,

EQUATION

where we used i |H ii | = i H ii = i λ i .

E.10 PROOF OF EQ. (34)

Proof. In two dimensions, the constraint diag(l 1 , l 2 ) -H 0 can be written as l 1 -a ≥ 0 and (l 1 -a)(l 2 -d) -b 2 ≥ 0 (76) by the leading principle minors criterion for positive definiteness. All "boundary" solutions can be written as

EQUATION

)

Out of those, the one that minimizes l 1 + l 2 is easily found to be given by s = |b|, resulting in

EQUATION

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 us to control the growth of the gradient norm in the vicinity of a point x ∈ R d .

Lemma 5. Assume Eq. (41) holds and let x, y with yx ≤ 1 L (1) . Then (

EQUATION

We can now approach the proof of Lemma 4. 7 Groenwall's inequality says that if u(t) ≤ α(t) + 

We apply it here with u(t) = ∇f (x(t)) * and α(t) = ∇f (x) * + tL (0) /L (1) and β(τ ) ≡ 1.

Hence, f t+1 ≤ f t -min L (0) 18(L (1) ) 2 , ε 2 18L (0) .

(92)

Now assume that we have T iterations with ∇f t * ≥ ε. Then

EQUATION

)

Rearranging yields

EQUATION

)

:

Also known as generalized or non-Euclidean gradient descent(Carlson et al.,

2015;Kelner et al., 2014).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 a constant or manually decreasing step size. In Appendix C, we discuss a possible explanation for this discrepancy.

Note that φ(z) = 1 for z ∝ (1, . . . , 1) T and φ(z) = d -1 for z ∝ (1, . . . , 0) T .

Of course, we could deviate from the definition of Eq. (31) and choose li ≡ λmax to guarantee lmax = λmax. However, this bound would not be favorable for the performance of signGD, which depends on i li.

The uniform distribution on the special orthogonal group SO(d) of d-dimensional rotation matrices. We used the special ortho group function provided by the scipy.stats package(Jones et al., 2001).

https://github.com/keras-team/keras/blob/master/examples/cifar10_cnn. py

Figures and Tables:

Figure1: L ∞ increases as the Hessian becomes less axis-aligned. Contour line of f (x) = 1 2 x T Hx, which forms an ellipse with principal axes given by the eigenvectors and axis lengths given by the inverse eigenvalues. We construct H ∈ R d×d with a fixed λ min = 1 and variable L 2 = λ max > 1 as well as the angle θ between eigenvectors and coordinate axes.

Figure2: We consider quadratic objectives varying across two axes: λ max /λ as well as a rotation value θ. The left plot depicts the ratio of the two relevant smoothness constants. L ∞ is sensitive to θ and grows relative to L 2 = λ max as the problem becomes less axis-aligned. The right plot depicts the relative performance of gradient descent and sign gradient descent on these problems. GD drastically (the colormap is clipped) outperforms signGD for mildly conditioned (small λ max /λ) and non-axis-aligned (large θ) problems. However, sign gradient descent is preferable for problems with high λ max /λ, given that they have some degree of axis-alignment (small θ). The dashed line represents equal performance of both algorithms.

Figure3: Experiments on CIFAR10 dataset. When using a CNN (top), signSGD outperforms SGD (top left), which matches the behaviour predicted by the improvement ratio (top right), above 1 at the beginning. When using a ResNet20 (bottom), the situation is reversed but the improvement ratio still correctly predicts the relative performance of both algorithms.

li = L sep and xT H ŷ = L ∞ by definition. Second inequality: We set l i = j |H ij | and denote L = diag(l 1 , . . . , l d ). Then [L -H] ii ≥ j =i |H ij | (73)

∇f (y) * ≤ 4 L (0) L (1) + ∇f (x) * .(79)Proof. Define x(τ ) = x+τ (y -x) as well as g(τ ) = ∇f (x(τ )) with g (τ ) = ∇ 2 f (x(τ ))(y -x). Then ∇f (x(t)) * = ∇f (x) + t (τ )dτ * ≤ ∇f (x) * + t 0 g (τ ) * dτ = ∇f (x) * + t 0 ∇ 2 f (x(τ ))(yx) * dτ (52) ≤ ∇f (x) * + (yx) + L (1) ∇f (x(τ )) * dτ = ∇f (x) * + t L form of Groenwall's inequality 7 yields ∇f (x(t)) * ≤ ∇f (x) * + t L exp(tτ )dτ. (82)We now specialize to t = 1 and upper-bound the integrand ∇f (y) * = ∇f (x(1)) * ≤ ∇f (x) * + L + ∇f (x) * .

β(τ )u(τ )dτ for continuous u and β, thenu(t) ≤ α(t) + t t 0 α(τ )β(τ ) exp t τ β(r)dr dτ.

Proof. We first show that Eq. (8) defines a matrix norm. Clearly H ≥ 0 and H = 0 iff H = 0. Furthermore, λH = |λ| H . It remains to show subadditivity. Let H, H ∈ R d×d

Table content: <table><tr><td>E.3 PROOF OF PROPOSITION 2</td><td/></tr><tr><td>Note that the matrix norm by construction satisfies</td><td/></tr><tr><td>Hx  *  ≤ H x .</td><td>(52)</td></tr></table>

arg min ⇐⇒ x t+1 ∈ x t -α t arg min ⇐⇒ x t+1 ∈ x t -α t arg min ⇐⇒ x t+1 ∈ x t -α t arg maxProof. First inequality: First, let l1 , . . . , ld ≥ 0 be the minimizer in the definition of L sep . For any z with z ∞ ≤ 1, we have z T Hz ≤ z T diag( l1 , . . . , ld )z =

Table content: <table><tr><td>x</td><td colspan="2">∇f t , x -x t +</td><td colspan="2">1 2α t</td><td>x -x t</td><td>2</td></tr><tr><td/><td>y y</td><td colspan="4">∇f t , -α t y + α t -∇f t , y + 2α t 1 2 1</td><td>-α t y 2 y 2</td><td>(69)</td></tr><tr><td/><td>y</td><td colspan="2">∇f t , y -</td><td>1 2</td><td>y 2 .</td></tr><tr><td>E.9 PROOF OF PROPOSITION 5</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
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. The 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. Most 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. ---------------------- After rebuttal: I have read the authors* response. I think the contribution may not be sufficient. I would like to keep my original score.