Year: 2019

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.

heading: 1 INTRODUCTION
text: We consider an unconstrained, continuous optimization problem, minx∈Rd f(x), with a differentiable and lower-bounded objective f : Rd → R. The prototypical first-order optimization algorithm to solve this problem is gradient descent (GD), which iteratively updates xt+1 = xt−αt∇ft, where ft := f(xt). Several recent works have considered the sign gradient descent (signGD) method,
xt+1 = xt − αt sign(∇ft) , (1)
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.

heading: 1.1 OVERVIEW AND CONTRIBUTIONS
text: 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.

heading: 1.2 RESTRICTIONS
text: 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).

heading: 2 STEEPEST DESCENT AND SMOOTHNESS CONSTANTS
text: 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
xt+1 ∈ arg min x∈Rd
( ft + 〈∇ft,x− xt〉+ 1
2αt ‖x− xt‖2
) , (2)
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‖∞ := maxi |zi|. Namely,
xt − αt‖∇ft‖1 sign(∇ft) ∈ arg min x∈Rd
( ft + 〈∇ft,x− xt〉+ 1
2αt ‖x− xt‖2∞
) . (3)
This update is equivalent to Eq. (1) up to the scaling with the gradient norm ‖∇ft‖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.

heading: 2.1 SMOOTHNESS WITH RESPECT TO ARBITRARY NORMS
text: 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
‖∇f(y)−∇f(x)‖∗ ≤ L‖y − x‖, ∀x,y ∈ Rd, (4) 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 isL-smooth w.r.t. ‖·‖, then f(y) ≤ f(x)+〈∇f(x),y−x〉+L2 ‖y−x‖
2 ∀x,y ∈ Rd. 1Also 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.
Setting x = xt we get f(y) ≤ ft + 〈∇ft,y − xt〉 + L2 ‖y − xt‖ 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 Rd, 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,
L := sup x6=y ‖∇f(y)−∇f(x)‖∗ ‖y − x‖ , (5)
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.

heading: 2.2 CONVERGENCE OF STEEPEST DESCENT
text: 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
f(x+) ≤ f(x)− 1 2L ‖∇f(x)‖2∗. (6)
Without additional assumptions, this yields O(1/T ) convergence to a first-order stationary point:
Proposition 1. If f is L-smooth w.r.t. ‖ · ‖, then steepest descent (Eq. 2) with αt ≡ 1/L satisfies
1
T
T−1∑
t=0
‖∇ft‖2∗ ≤ 2L(f0 − f?)
T . (7)
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.

heading: 2.3 SMOOTHNESS AS A BOUND ON THE HESSIAN
text: 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 isL2-smooth w.r.t. the Euclidean norm if and only if ‖∇2f(x)‖2 ≤ L2 for all x ∈ Rd. 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 Rd, 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 ‖∇2f(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.
λ m
a x
= 2 .0
L∞ = 3.00
L∞ = 3.34
L∞ = 3.87
λ m
a x
= 4 .0
L∞ = 5.00 L∞ = 6.03 L∞ = 7.60

heading: 3 UNDERSTANDING THE L∞-SMOOTHNESS CONSTANT
text: 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 constantL∞. The Euclidean smoothness constantL2 will thereby serve as a reference point. We assume f to be L2-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)
L2 ≤ L∞ ≤ dL2 . (9)
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 dL2—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
L∞ = sup x∈Rd ‖∇2f(x)‖∞,1, ‖H‖∞,1 := sup ‖x‖∞≤1 ‖Hx‖1. (10)
Unfortunately, computing ‖H‖∞,1 is NP-hard (Rohn, 2000). However, we can obtain some insight through the following upper bound. Proposition 3. LetH ∈ Rd×d be nonzero, positive semi-definite with eigenvalues λ1, . . . , λd. Then
‖H‖∞,1 ≤ ρdiag(H)−1 ∑
i
λi with ρdiag(H) := ∑ i |Hii|∑ i,j |Hij | . (11)
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 L2? 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: λ̄ := 1d ∑ 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∞.

heading: 4 GRADIENT DESCENT VS SIGN GRADIENT DESCENT
text: We found in Section 3 that L∞ will always exceed L2, and identified conditions under which L∞ dL2. By Lemma 2, the guaranteed improvement of the two methods at x ∈ Rd is
IGD(x) := ‖∇f(x)‖22
L2 vs. IsignGD(x) := ‖∇f(x)‖21 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 ∈ Rd, show that this potentially favors sign gradient descent. Following Bernstein et al. (2018), it will be convenient to define the ratio
φ(z) := ‖z‖21 d‖z‖22 ∈ [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
R(x) := IsignGD(x) IGD(x) = ‖∇f(x)‖21 ‖∇f(x)‖22 L2 L∞ = φ(∇f(x))dL2 L∞ . (12)
If L∞ dL2, 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 ∈ Rd. We can make this comparison even more palpable. We restrict to quadratic functions, such that ∇2f(x) ≡ H and L∞ = ‖H‖∞,1 as well as L2 = ‖H‖2 = λmax. Assume H to be positive definite with eigenvalues λ1, . . . , λd. Then Proposition 3 in Eq. (12) yields
R(x) = IsignGD(x) IGD(x)
≥ ρdiag(H) ︸ ︷︷ ︸ ∈[d−1,1]
λmax
λ︸ ︷︷ ︸ ∈[1,d] φ(∇f(x)) ︸ ︷︷ ︸ ∈[d−1,1]
(13)
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 ∈ Rd 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.

heading: 5 EXPERIMENTS

heading: 5.1 QUADRATIC PROBLEMS
text: 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
3Note that φ(z) = 1 for z ∝ (1, . . . , 1)T and φ(z) = d−1 for z ∝ (1, . . . , 0)T .
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 L2 = λmax and L∞ = ‖H‖∞,1. We then run T = 100 iterations of gradient descent (with α = 1/L2) and sign gradient descent (with α = 1/L∞) and compute the distance to the optimum ‖xT − x∗‖22 as a scale-invariant performance measure. We average over repeated runs with x0 ∼ 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.

heading: 5.2 NEURAL NETWORK EXPERIMENTS
text: 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 ratioR(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
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.

heading: 6 RELATED WORK

heading: 6.1 STEEPEST DESCENT
text: 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 xt+1 = arg minx(〈∇ft,x − xt〉 + 1αtBψ(x,xt)), 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.

heading: 6.2 PREVIOUS WORKS ON SIGN GRADIENT DESCENT
text: 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 & Richtárik (2019). All three papers are based on the assumption that there exist constants li > 0 such that
f(y) ≤ f(x) + 〈∇f(x),y − x〉+ 1 2
∑
i
li(yi − xi)2, ∀x,y ∈ Rd . (14)
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 li whereas the convergence speed of gradient descent is driven by lmax := maxi li.
Not only is the meaning of these li’s unclear, but neither the algorithm itself nor the analysis uses the individual li’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 li)-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(l1, . . . , ld and ‖z‖2L := (∑ i liz 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 li)-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, xt+1−xt ∈ {−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.

heading: 7 CONCLUSIONS
text: 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 ‖∇ft‖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.

heading: A DETAILS ON STEEPEST DESCENT
text: 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
xt+1 = xt − αt∇f‖·‖t with z‖·‖ ∈ arg max y∈Rd
( 〈z,y〉 − 1
2 ‖y‖2
) . (15)
This equivalence arises from substituting y = − 1αt (x−xt); a full proof can be found in Appendix E

heading: A.1 ADDITIONAL EXAMPLES FOR STEEPEST DESCENT METHODS
text: First, we give two additional examples for steepest descent methods to demonstrate the versatility of this framework.

heading: A.1.1 COORDINATE DESCENT
text: Steepest descent with respect to the L1-norm,
xt+1 ∈ arg min ( ft + 〈∇ft,x− xt〉+ 1
2αt ‖x− xt‖21
) , (16)
yields coordinate descent,
xt+1 = xt − αt|∇ft,imax |e(imax) (17)
where the selected coordinate is chosen from imax ∈ arg maxi∈[d] |∇ft,i| and e(i) denotes the i-th coordinate vector. The corresponding smoothness assumption is
‖∇f(y)−∇f(x)‖∞ ≤ L1‖y − x‖1. (18)
In fact, this assumption implies the coordinate-wise Lipschitz smoothness assumption,
|∇f(x+ he(i))i −∇f(x)i| ≤ L1|h| ∀i ∈ [d], (19)
which is widely-used in the literature on coordinate descent, since
|∇f(x+ he(i))i −∇f(x)i| ≤ ‖∇f(x+ he(i))−∇f(x)‖∞ (18) ≤ L1‖x+ he(i) − x‖1 = L1|h|.
(20)

heading: A.1.2 BLOCK-NORMALIZED GRADIENT DESCENT
text: Assume a block structure on Rd given by a partitioning B = {B1, . . . , Bb} of [d], with Bk ⊂ [d], Bk∩Bl = ∅ for k 6= l, and ⋃ k Bk = [d]. ForB ⊂ [d], define xB ∈ R|B| to be the vector consisting of (xi)i∈B . We can now define norms with respect to this block structure, such as
‖x‖B,∞ = max B∈B ‖xB‖2 with dual norm ‖x‖B,1 =
∑ B∈B ‖xB‖2. (21)
Steepest descent w.r.t. ‖ · ‖B,∞ results in block-normalized gradient descent,
∇f‖·‖B,∞ = ‖∇f‖B,1 normB(∇f), normB(z) = ( zTB1 ‖zB1‖2 , . . . , zTBb ‖zBb‖2 )T . (22)
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.

heading: A.2 PROPERTIES OF THE STEEPEST DESCENT OPERATOR
text: We define the z‖·‖ operator as:
‖z‖∗ := max‖x‖≤1 〈z,x〉 , z‖·‖ ∈ arg max
y∈Rd
( 〈z,y〉 − 1
2 ‖y‖2
) . (23)
The following Lemma connects this operator to the dual norm: Lemma 3. For all x, z ∈ Rd, we have
(a) 〈x, z〉 ≤ ‖x‖‖z‖∗ (24) (b) ‖z‖·‖‖2 = 〈z, z‖·‖〉 (25) (c) ‖z‖·‖‖ = ‖z‖∗ (26)

heading: A.3 ADDITIONAL CONVERGENCE RESULTS FOR STEEPEST DESCENT
text: 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
fT − f? ≤ 2LR2
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)‖22 ≥ 2µ(f(x)− f?) but can likewise be formulated for arbitrary norms. Definition 1. A function f : Rd → R satisfies the PL condition w.r.t. a norm ‖ · ‖ if ‖∇f(x)‖2∗ ≥ 2µ(f(x)− f?) for all x ∈ Rd.
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
fT − f? ≤ (
1− µ L
)T (f0 − f?). (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 2 and the PL condition gives
ft+1 ≤ ft − 1
2L ‖∇ft‖2∗ (29)
≤ ft − µ
L (ft − f?). (30)
Subtracting f? from both sides and iterating backwards yields the statement.

heading: B DETAILS ON THE RELATIONSHIP BETWEEN SEPARABLE SMOOTHNESS AND SMOOTHNESS W.R.T. THE MAXIMUM NORM
text: 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.

heading: B.1 SEPARABLE SMOOTHNESS AS A DIAGONAL BOUND ON THE HESSIAN
text: Bernstein et al. (2018) note that, for twice-differentiable f , separable smoothness results from−L ∇2f(x) L for all x ∈ Rd with L = diag(l1, . . . , ld). It is tempting to think of them as bounds on the eigenvalues of ∇2f(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 li, the most favorable bound will be
min l1,...,ld≥0
∑
i
li s.t. −L ∇2f(x) L ∀x ∈ Rd (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. LetH ∈ Rd×d be positive semi-definite with eigenvalues λ1 . . . , λd and define
L∞(H) := max‖x‖∞≤1 ‖Hx‖1, Lsep(H) := min li≥0
∑
i
li s.t. H diag(l1, . . . , ld). (32)
Then L∞(H) ≤ Lsep(H) ≤ ρdiag(H)−1 ∑
i
λi. (33)
Hence, Lsep upper-bounds L∞ while at the same time being upper-bounded by the same quantity that appears in Proposition 3.
θ = 0◦ θ = 10◦ θ = 30◦

heading: B.2 SEPARABLE SMOOTHNESS FOR TWO-DIMENSIONAL QUADRATICS
text: To build some intuition for the separable smoothness condition, we consider the case of a twodimensional quadratic with positive definite Hessian ∇2f(x) ≡ H = [ a b b d ] . In this, case, we can find the solution to Eq. (31) in closed form (proof in Appendix E):
l1 = a+ |b|, l2 = d+ |b|. (34)
A visualization is given in Figure 4 and clearly shows that the choice of li is sensitive to the axis alignment of the Hessian.
The eigenvalues ofH evaluate to
λ1/2 = a+ d 2 ± √ (a− d)2 4 + b2. (35)
We see that, for |b| > 0, we will have lmax > λmax.4 We also see that lmax can exceed λmax and it is thus misleading to assume the convergence of GD to be driven by lmax. Also note that L∞ = ‖H‖∞,1 = a + d + 2|b| = ∑ i li, reflecting the link to smoothness w.r.t. the maximum norm, as discussed in the main text.
4Of 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.

heading: B.3 EXISTING CONVERGENCE PROOFS GO TROUGH UNDER SMOOTHNESS W.R.T. THE MAXIMUM NORM
text: Let xt+1 − xt ∈ {−c, c}d for some c ∈ R. Then the separable smoothness bound implies
ft+1 ≤ ft + 〈∇ft,xt+1 − xt〉+ 1
2
∑
i li (xt+1,i − xt,i)2︸ ︷︷ ︸ =c2
= ft + 〈∇ft,xt+1 − xt〉+ c2
2
∑
i
li
(36)
and the L∞-smoothness w.r.t. the maximum norm yields (via Lemma 1)
ft+1 ≤ ft + 〈∇ft,xt+1 − xt〉+ 1
2 L∞ ‖xt+1 − xt‖2∞︸ ︷︷ ︸
=c2
= ft + 〈∇ft,xt+1 − xt〉+ c2
2 L∞.
(37)
Hence, smoothness w.r.t. the maximum norm with constant L∞ = ∑ i li 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 & Richtárik (2019) all start from this bound, they go through when replacing the separable smoothness assumption with the weaker assumption of ( ∑ i li)-smoothness w.r.t. the maximum norm.

heading: C GENERALIZING RELAXED SMOOTHNESS
text: We have discussed a scaled version of sign gradient descent, xt+1 = xt − α‖∇ft‖1 sign(∇ft), whereas in practice the update is usually xt+1 = xt − αt sign(∇ft) with a constant or manually decreasing step size αt. Without this additional ‖∇ft‖1 term, this is a normalized method with an update magnitude determined solely by the step size, independent of the gradient ∇ft. 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 ‖∇ft‖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,
xt+1 = xt − α 1
‖∇ft‖2 + β ∇ft. (38)
This method is normalized since its update magnitude is upper-bounded by ‖xt+1 − xt‖2 ≤ α irrespective of the gradient magnitude. For small gradient ‖∇ft‖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 ‖∇ft‖1.

heading: C.1 RESULTS OF ZHANG ET AL. (2019)
text: The relaxed smoothness condition proposed by Zhang et al. (2019) reads
‖∇2f(x)‖2 ≤ L(0) + L(1)‖∇f(x)‖2, (39)
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, provides a bound of the form
ft+1 ≤ ft + 〈∇ft,xt+1 − xt〉+ 1
2 (A+B‖∇ft‖2)‖xt+1 − xt‖22, A,B ≥ 0. (40)
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.

heading: C.2 NORMALIZED STEEPEST DESCENT
text: 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.
Definition 2. A function f is called (L(0), L(1))-smooth with respect to some norm ‖ · ‖ if
‖∇2f(x)‖ ≤ L(0) + L(1)‖∇f(x)‖∗, (41)
where ‖ · ‖ for matrices is the norm defined in Eq. (8).
Under this smoothness assumption, we have the following local quadratic bound:
Lemma 4. Assume f is (L(0), L(1))-smooth with respect to a norm ‖ · ‖. Then for x,y ∈ Rd with ‖y − x‖ ≤ 1
L(1) ,
f(y) ≤ f(x) + 〈∇f(x),y − x〉+ 1 2 (5L(0) + 4L(1)‖∇f(x)‖∗)‖y − x‖2. (42)
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 = xt yields
f(y) ≤ ft + 〈∇ft,y − xt〉+ 1
2 (5L(0) + 4L(1)‖∇ft‖∗)‖y − xt‖2. (43)
Choosing xt+1 as the minimizer w.r.t. y results in the update
xt+1 = xt − 1 (5L(0) + 4L(1)‖∇ft‖∗) ∇f‖·‖t . (44)
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 ‖ = ‖∇ft‖∗ 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
Tε = 18(f0 − f∗) max ( L(0)
ε2 ,
(L(1))2
L(0)
) (45)
iterations.

heading: D EXPERIMENTAL DETAILS

heading: D.1 QUADRATIC EXPERIMENTS
text: 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 the 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 = UDU∗. The matrix power is then given by Rθ = UDθUH whereDθ for the diagonal matrixD 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 2d 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.

heading: D.2 NEURAL NETWORK EXPERIMENTS
text: 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.
5The 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).
6https://github.com/keras-team/keras/blob/master/examples/cifar10_cnn. py
Estimating smoothness constants. Following Zhang et al. (2019), we approximate the smoothness using directional finite differences. At a point x, we approximate
L̂2 = min γ ‖∇f(x+ γs)−∇f(x)‖2 γ‖s‖2 .s = −α1∇f(x) (46)
L̂∞ = min γ ‖∇f(x+ γs)−∇f(x)‖1 γ‖s‖∞ .s = −α2 sign(∇f(x)), (47)
where α1 and α2 are the respective “optimal” step size for GD and signGD.

heading: E PROOFS
text: We now list the proofs of all theoretical results from the main text.

heading: E.1 PROOF OF LEMMA 1
text: Proof. Define g(τ) = f(x + τ(y − x)) for τ ∈ [0, 1] with g′(τ) = 〈∇f(x + τ(y − x)),y − x〉. Then
f(y) = f(x) +
∫ 1
0
g′(τ)dτ
= f(x) +
∫ 1
0
〈∇f(x+ τ(y − x)),y − x〉dτ
= f(x) + 〈∇f(x),y − x〉+ ∫ 1
0
〈∇f(x+ τ(y − x))−∇f(x),y − x〉dτ
(24) ≤ f(x) + 〈∇f(x),y − x〉+
∫ 1
0
‖∇f(x+ τ(y − x))−∇f(x)‖∗‖y − x‖dτ
(4) ≤ f(x) + 〈∇f(x),y − x〉+
∫ 1
0
L‖τ(y − x)‖‖y − x‖dτ
= f(x) + 〈∇f(x),y − x〉+ L‖y − x‖2 ∫ 1
0
τdτ
= f(x) + 〈∇f(x),y − x〉+ L 2 ‖y − x‖2.
(48)
The first inequality is due to Lemma 3(a) and the second inequality uses the L-smoothness.

heading: E.2 CONVERGENCE PROOFS FOR STEEPEST DESCENT
text: Proof of Lemma 2. We apply Lemma 1 with y = x+ = x− 1L∇f(x) ‖·‖
f(x+) ≤ f(x) + 〈∇f(x),x+ − x〉+ L 2 ‖x+ − x‖2
= f(x) + 〈∇f(x),− 1 L ∇f(x)‖·‖〉+ L 2 ∥∥∥∥− 1 L ∇f(x)‖·‖ ∥∥∥∥ 2
= f(x)− 1 L
( 〈∇f(x),∇f(x)‖·‖〉 − 1
2 ‖∇f(x)‖·‖‖2
) .
(49)
By Lemma 3, we have 〈∇f(x),∇f(x)‖·‖〉 = ‖∇f(x)‖·‖‖2 = ‖∇f(x)‖2∗. Substituting this in yields the desired bound.
Proof of Proposition 1. Lemma 2 gives ‖∇ft‖2∗ ≤ 2L(ft − ft+1) (50) Rearranging and summing for t = 0, . . . , T − 1 yields 1
T
T−1∑
t=0
‖∇ft‖2∗ ≤ 2L
T
T−1∑
t=0
(ft − ft+1) = 2L(f0 − fT ) T ≤ 2L(f0 − f ?) T . (51)

heading: E.3 PROOF OF PROPOSITION 2
text: Note that the matrix norm by construction satisfies
‖Hx‖∗ ≤ ‖H‖‖x‖. (52)
Proof. We first show that Eq. (8) defines a matrix norm. Clearly ‖H‖ ≥ 0 and ‖H‖ = 0 iffH = 0. Furthermore, ‖λH‖ = |λ|‖H‖. It remains to show subadditivity. LetH,H ′ ∈ Rd×d
‖H +H ′‖ = sup ‖x‖≤1 ‖(H +H ′)x‖∗ ≤ sup ‖x‖≤1 (‖Hx‖∗ + ‖H ′x‖∗)
≤ sup ‖x‖≤1 ‖Hx‖∗ + sup ‖x′‖≤1
‖H ′x′‖∗ = ‖H‖+ ‖H ′‖. (53)
Now assume ‖∇2f(x)‖ ≤ L for all x ∈ Rd. Let x,y ∈ Rd and define g(τ) = ∇f(x+ τ(y − x)) for τ ∈ [0, 1].
‖∇f(y)−∇f(x)‖∗ = ∥∥∥∥ ∫ 1
0
d
dτ g(τ)dτ ∥∥∥∥ ∗
= ∥∥∥∥ ∫ 1
0 ∇2f(x+ τ(y − x))(y − x)dτ ∥∥∥∥ ∗
≤ ∫ 1
0
∥∥∇2f(x+ τ(y − x))(y − x) ∥∥ ∗ dτ
(52) ≤ ∫ 1
0
‖∇2f(x+ τ(y − x))‖‖y − x‖dτ
≤ L‖y − x‖ ∫ 1
0
1dτ = L‖y − x‖.
(54)
Conversely, assume L-smoothness and fix x ∈ Rd. For any ‖s‖ ≤ 1 and ε > 0, ∥∥∥∥ (∫ ε
0
∇2f(x+ τs)dτ ) s ∥∥∥∥ ∗ = ‖∇f(x+ εs)−∇f(x)‖∗ ≤ εL‖s‖ ≤ εL. (55)
Dividing by ε and letting ε→ 0, we get
‖∇2f(x) s‖∗ = ∥∥∥∥ limε→0 ( 1 ε ∫ ε
0
∇2f(x+ τs)dτ ) s ∥∥∥∥ ∗
= lim ε→0
1
ε
∥∥∥∥ (∫ ε
0
∇2f(x+ τs)dτ ) s ∥∥∥∥ ∗ ≤ L.
(56)
This implies ‖∇2f(x)‖ = sup‖s‖≤1 ‖∇2f(x)s‖∗ ≤ L.

heading: E.4 PROOF OF PROPOSITION 3
text: Proof. First note that
‖H‖∞,1 := sup ‖x‖∞≤1 ‖Hx‖1 = sup ‖x‖∞≤1
∑
i
∣∣∣∣∣∣ ∑
j
Hijxj ∣∣∣∣∣∣ ≤ ∑
i,j
|Hij |. (57)
Recall that ∑ i |Hii| = ∑ iHii = ∑ i λi for positive definite matrices. Then
‖H‖∞,1 ≤ ∑
i,j
|Hij | = ∑ i,j |Hij |∑ i |Hii| ∑
i
λi = ρdiag(H) −1∑
i
λi. (58)

heading: E.5 PROOF OF EQ. (9)
text: Proof. The fact that ‖z‖∞ ≤ ‖z‖2 ≤ ‖z‖1 implies
L2 = sup x6=y ‖∇f(y)−∇f(x)‖2 ‖y − x‖2 ≤ sup x 6=y ‖∇f(y)−∇f(x)‖1 ‖y − x‖∞ = L∞. (59)
Conversely, using 1√ d ‖z‖1 ≤ ‖z‖2 ≤
√ d‖z‖∞
L∞ = sup x6=y ‖∇f(y)−∇f(x)‖1 ‖y − x‖∞ ≤ sup x 6=y
√ d‖∇f(y)−∇f(x)‖2
1√ d ‖y − x‖2
= dL2. (60)

heading: E.6 PROOF OF LEMMA 3
text: Proof. Statement (a) follows immediately from the definition of the dual norm.
Regarding (b), by definition of z‖·‖, we know that 〈z, cz‖·‖〉 − 12‖cz ‖·‖‖2 is maximized by c = 1. Hence the derivative w.r.t. c, d
dc
[ 〈z, cz‖·‖〉 − 1
2 ‖cz‖·‖‖2
] = 〈z, z‖·‖〉 − c‖z‖·‖‖2, (61)
must evaluate to 0 at c = 1, which proves (b).
For (c), we use the equivalent definition
‖z‖∗ = max x6=0 〈x, z〉 ‖x‖ . (62)
Assume w.l.o.g. that z‖·‖ 6= 0. Then
‖z‖∗ = max x6=0 〈x, z〉 ‖x‖ ≥ 〈z ‖·‖, z〉 ‖z‖·‖‖ (b) = ‖z‖·‖‖. (63)
Conversely, Let x′ ∈ arg max‖x‖=1〈x, z〉, such that 〈z,x′〉 = ‖z‖∗. Then 1
2 ‖z‖2∗ = 〈z, ‖z‖∗x′〉 −
1 2 ‖‖z‖∗x′‖2 ≤ 〈z, z‖·‖〉 − 1 2 ‖z‖·‖‖2 (b)= 1 2 ‖z‖·‖‖2, (64)
where the inequality is by definition of z‖·‖.

heading: E.7 PROOF OF PROPOSITION 4
text: Proof. The dual norm of ‖ · ‖L is ‖ · ‖L−1 , such that the assumption of 1-smoothness w.r.t. ‖ · ‖L amounts to ‖∇f(y)−∇f(x)‖L−1 ≤ ‖y − x‖L ∀x,y ∈ Rd. (65) First, by definition of the maximum norm, we get
‖z‖L = √∑
i
liz2i ≤ √∑
i
li‖z‖2∞ = √∑
i
li‖z‖∞. (66)
Secondly, using Cauchy-Schwarz,
‖z‖1 = ∑
i
|zi| = ∑
i
|zi|√ li √ li ≤
√∑
i
z2i li
√∑
i
li =
√∑
i
li‖z‖L−1 . (67)
Combining these two inequalities with the assumption yields the assertion:
‖∇f(y)−∇f(x)‖1 (67) ≤ √∑
i
li‖∇f(y)−∇f(x)‖L−1 (65) ≤ √∑
i
li‖y − x‖L
(66) ≤ √∑
i
li
√∑
i
li‖y − x‖∞ =
(∑
i
li ) ‖y − x‖∞.
(68)
E.8 PROOF OF EQ. (15)
Proof. The equivalence arises from substituting y = − 1αt (x− xt) or x = xt − αty. With a slight abuse of notation:
xt+1 ∈ arg min x
( 〈∇ft,x− xt〉+ 1
2αt ‖x− xt‖2
)
⇐⇒ xt+1 ∈ xt − αt arg min y
( 〈∇ft,−αty〉+ 1
2αt ‖ − αty‖2
)
⇐⇒ xt+1 ∈ xt − αt arg min y
( αt [ −〈∇ft,y〉+ 1
2 ‖y‖2
])
⇐⇒ xt+1 ∈ xt − αt arg max y
( 〈∇ft,y〉 − 1
2 ‖y‖2
) .
(69)

heading: E.9 PROOF OF PROPOSITION 5
text: Proof. First inequality: First, let l̂1, . . . , l̂d ≥ 0 be the minimizer in the definition of Lsep. For any z with ‖z‖∞ ≤ 1, we have
zTHz ≤ zT diag(l̂1, . . . , l̂d)z = ∑
i
l̂iz 2 i ≤
∑
i
l̂i. (70)
Next, we rewrite the definition of L∞ as L∞ = max‖x‖∞,‖y‖∞≤1 xTHy. (71)
and let (x̂, ŷ) be the maximizer. Then due toH being psd, we have
0 ≤ (x̂− ŷ)TH(x̂− ŷ) = x̂THx̂− 2x̂THŷ + ŷTHŷ ≤ 2 ∑
i
l̂i − 2x̂THŷ, (72)
where the last inequality is due to Eq. (70) applied to x̂ and ŷ. This proves the assertion, since∑ i l̂i = Lsep and x̂ THŷ = L∞ by definition. Second inequality: We set li = ∑ j |Hij | and denote L = diag(l1, . . . , ld). Then
[L−H]ii ≥ ∑
j 6=i |Hij | (73)
∑ j 6=i |[L−H]ij | = ∑ j 6=i |Hij | (74)
making L − H diagonally dominant with non-negative diagonal elements, hence positive semidefinite. Therefore, L is in the solution space of the definition of Lsep. Now,
∑
i
li = ∑
i,j
|Hij | = ( ∑ i |Hii|∑ i,j |Hij | )−1∑
i
λi, (75)
where we used ∑ i |Hii| = ∑ iHii = ∑ i λi.
E.10 PROOF OF EQ. (34)
Proof. In two dimensions, the constraint diag(l1, l2)−H 0 can be written as l1 − a ≥ 0 and (l1 − a)(l2 − d)− b2 ≥ 0 (76)
by the leading principle minors criterion for positive definiteness. All “boundary” solutions can be written as
l1 = a+ s, l2 = d+ b2
s , s ≥ 0. (77)
Out of those, the one that minimizes l1 + l2 is easily found to be given by s = |b|, resulting in l1 = a+ |b|, l2 = d+ |b|. (78)

heading: E.11 PROOFS FOR APPENDIX C
text: 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 ∈ Rd. Lemma 5. Assume Eq. (41) holds and let x,y with ‖y − x‖ ≤ 1
L(1) . Then
‖∇f(y)‖∗ ≤ 4 ( L(0)
L(1) + ‖∇f(x)‖∗
) . (79)
Proof. Define x(τ) = x+τ(y−x) as well as g(τ) = ∇f(x(τ)) with g′(τ) = ∇2f(x(τ))(y−x). Then
‖∇f(x(t))‖∗ = ∥∥∥∥∇f(x) + ∫ t
0
g′(τ)dτ ∥∥∥∥ ∗
≤ ‖∇f(x)‖∗ + ∫ t
0
‖g′(τ)‖∗dτ
= ‖∇f(x)‖∗ + ∫ t
0
‖∇2f(x(τ))(y − x)‖∗dτ
(52) ≤ ‖∇f(x)‖∗ + ‖(y − x)‖︸ ︷︷ ︸
≤1/L(1)
∫ t
0 ‖∇2f(x(τ))‖︸ ︷︷ ︸ ≤L(0)+L(1)‖∇f(x(τ))‖∗ (41) dτ
≤ ‖∇f(x)‖∗ + 1
L(1)
∫ t
0
L(0) + L(1)‖∇f(x(τ))‖∗dτ
= ‖∇f(x)‖∗ + t L(0)
L(1) +
∫ t
0
‖∇f(x(τ))‖∗dτ
(80)
Applying the integral form of Groenwall’s inequality7 yields
‖∇f(x(t))‖∗ ≤ ‖∇f(x)‖∗ + t L(0)
L(1) +
∫ t
0
( ‖∇f(x)‖∗ + τ L(0)
L(1)
) exp(t− τ)dτ. (82)
We now specialize to t = 1 and upper-bound the integrand
‖∇f(y)‖∗ = ‖∇f(x(1))‖∗
≤ ‖∇f(x)‖∗ + L(0)
L(1) +
∫ 1
0
 ‖∇f(x)‖∗ + τ︸︷︷︸
≤1
L(0)
L(1)   exp(1− τ)︸ ︷︷ ︸ ≤exp(1)<3 dτ
≤ ‖∇f(x)‖∗ + L(0)
L(1) + 3
( ‖∇f(x)‖∗ + L(0)
L(1)
)∫ 1
0
dτ
= 4
( L(0)
L(1) + ‖∇f(x)‖∗
) .
(83)
We can now approach the proof of Lemma 4.
7 Groenwall’s inequality says that if u(t) ≤ α(t) + ∫ t t0 β(τ)u(τ)dτ for continuous u and β, then
u(t) ≤ α(t) + ∫ t t0 α(τ)β(τ) exp (∫ t τ β(r)dr ) dτ. (81)
We apply it here with u(t) = ‖∇f(x(t))‖∗ and α(t) = ‖∇f(x)‖∗ + tL(0)/L(1) and β(τ) ≡ 1.
Proof of Lemma 4. According to Taylor’s theorem we have
f(y) = f(x) + 〈∇f(x),y − x〉+ 1 2 〈y − x,∇2f(ξ)(y − x)〉 (84)
with some ξ ∈ {x+ τ(y − x) | τ ∈ [0, 1]}. We can bound the quadratic term as
〈y − x,∇2f(ξ)(y − x)〉 (24) ≤ ‖y − x‖‖∇2f(ξ)(y − x)‖∗
(52) ≤ ‖y − x‖2‖∇2f(ξ)‖
(41) ≤ (L(0) + L(1)‖∇f(ξ)‖∗)‖y − x‖2.
(85)
The first inequality is by definition of the dual norm (see Lemma 3). The second inequality is by construction of the induced matrix norm. The final inequality uses the relaxed smoothness assumption (Eq. 41).
Next, since ‖y − x‖ ≤ 1/L(1) by assumption of Lemma 4, we know ‖ξ − x‖ ≤ 1 L(1) . Lemma 5 thus gives us
‖∇f(ξ)‖∗ ≤ 4 ( L(0)
L(1) + ‖∇f(x)‖∗
) . (86)
Plugging this back into Eq. (85) yields
〈y − x,∇2f(ξ)(y − x)〉 ≤ (5L(0) + 4L(1)‖∇f(x)‖∗)‖y − x‖2. (87)
Using that in Eq. (84) proves the assertion.
Finally, we prove Theorem 3
Proof of Theorem 3. Using Lemma 4 with x = xt and y = xt+1 = xt − ηt∇f‖·‖t yields
ft+1 ≤ ft − ηt〈∇ft,∇f‖·‖t 〉+ η2t 2 (5L(0) + 4L(1)‖∇ft‖∗)‖∇f‖·‖t ‖2. (88)
Recall from Lemma 3 that 〈z, z‖·‖〉 = ‖z‖·‖‖2 = ‖z‖2∗ and, hence,
ft+1 ≤ ft − ηt〈∇ft,∇f‖·‖t 〉+ η2t 2 (5L(0) + 4L(1)‖∇ft‖∗)‖∇f‖·‖t ‖2
= ft − ( ηt −
η2t 2
(5L(0) + 4L(1)‖∇ft‖∗) ) ‖∇ft‖2∗
= ft − ‖∇ft‖2∗
2(5L(0) + 4L(1)‖∇ft‖∗) .
(89)
If ε ≤ ‖∇ft‖∗ ≤ L(0)/L(1), we get
ft+1 ≤ ft − ε2
18L(0) (90)
If ‖∇ft‖∗ ≥ L(0)/L(1), we get
ft+1 ≤ ft − ‖∇ft‖2∗
2(5L(0) + 4L(1)‖∇ft‖∗)
= ft − ‖∇ft‖∗
10L(0)/‖∇ft‖∗ + 8L(1)
≤ ft − ‖∇ft‖∗ 18L(1)
≤ ft − L(0)
18(L(1))2
(91)
Hence,
ft+1 ≤ ft −min { L(0)
18(L(1))2 ,
ε2
18L(0)
} . (92)
Now assume that we have T iterations with ‖∇ft‖∗ ≥ ε. Then
f0 − f∗ ≥ f0 − fT = T−1∑
t=0
(ft − ft+1) ≥ T min { L(0)
18(L(1))2 ,
ε2
18L(0)
} . (93)
Rearranging yields
T ≤ 18 f0 − f∗ min { L(0)
(L(1))2 , ε
2
L(0)
} = 18(f0 − f∗) max ( L(0)
ε2 ,
(L(1))2
L(0)
) . (94)

Review summaries:
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.