Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: The paper tries to study the sign gradient descent by the squared maximum norm.  The authors clarify the meaning of a certain separable smoothness assumption using previous studies for signed gradient descent methods.

1. The authors change the problem. They study the sign gradient times its norm, not the classical sign gradient. 
In fact, this change dramatically changes the flow in continuous time. 

2. The results are too general, which does not focus on machine learning problems. 

3. The paper is clearly not written well with many typos. The organization of the paper also needs to be improved a lot for publication. 

For these reasons, I clearly reject this paper for publications.  
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.

review_title: Official Blind Review #1

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