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.
This paper analyzes the performance of sign gradient descent as a function of the “geometry” of the objective. They contrast the performance of sign GD to gradient descent. Both algorithms are steepest descent methods with respect to different norms. Overall, I do not think the insights claimed in the paper are especially novel. It is already known that the choice of a norm can have a significant impact on the speed of steepest descent but practically, the performance depends on quantities that are unknown such as the norm of the gradient over the specific trajectory of the algorithm. I do not find the arguments in section 4 especially convincing as they seem rather high-level to me. Instead I would find it more valuable if one could make a statement about the performance of signGD as a function of known quantities. One could perhaps start by analyzing a specific class of functions (quadratics, Polyak-Lojasiewicz functions, …).
Prior work
It seems to me that most results discussed in the paper are already known in the optimization community. The book by Boyd & Vandenberghe (cited by the authors) has an entire section on the “Choice of norm for steepest descent” where they indeed explain that the choice of the norm used for steepest descent can potentially have a dramatic effect on the convergence rate. Can the authors explain how they see their contribution compared to prior work? I could concede that the result of Proposition 3 is somewhat novel, although I think the authors should discuss prior work on axis-alignment, which dates back to 
Becker, Sue, and Yann Le Cun. "Improving the convergence of back-propagation learning with second order methods." Proceedings of the 1988 connectionist models summer school. 1988.
Section 4
The discussion in section 4 is high-level and I don’t see any particular insight one gains over what’s already known (see again book by Boyd & Vandenberghe). As explained by the authors, the comparison between signGD and GD will depend on the trajectory being followed.
Stochastic setting
Can the authors comment on generalizing their results to a stochastic setting? Since the gradients have a larger norm when using the infinity norm, I would expect that the variance is also larger.
Experimental results
The empirical results on the neural networks do not seem especially convincing, and the authors do seem to acknowledge this. What aspect of the analysis or the experimental setup do you expect to be responsible for this? Have you considered optimizing smaller models first? (something in between the quadratic problem in section 5.1 and the neural net in section 5.2. Some sort of ablation study where one strips away various components (batch-norm, residual connections, ….) of a neural network would also be valuable.
Generalization
One aspect that might be worth investigating is the generalization ability of steepest descent for different norms. There is already some prior work for adaptive methods that could perhaps be generalized, see e.g.
Wilson, Ashia C., et al. "The marginal value of adaptive gradient methods in machine learning." Advances in Neural Information Processing Systems. 2017.