Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This paper proposes, analyzes, and empirically evaluates PowerSGD (and a version with momentum), a simple adjustment to standard SGD algorithms that alleviates issues caused by poorly scaled gradients in SGD. The rates in the theoretical analysis are competitive with those for standard SGD, and the empirical results argue that PowerSGD algorithms are competitive with widely used adaptive methods such as Adam and RMSProp, suggesting that PowerSGD may be a useful addition to the armory of adaptive SGD algorithms.

Overall I recommend acceptance of this paper, although I think there may be a couple of places where the authors overclaim a bit on the theoretical side. Specifically:
• The convergence analysis assumes a batch size equal to T, the number of steps of PowerSGD. This implies that the amount of work (in FLOPs) done by the algorithm (at least the version being analyzed) is quadratic in T, which makes the convergence rates a bit misleading. If one reframes the convergence rate in terms of FLOPs U=T^2 instead of iterations, then the convergence rate drops from 1/T to 1/sqrt(U), which undermines the claim in remark 3.4 that this analysis is superior to that of Yan et al. (2018).
• In Remark 3.4.3, the authors claim that another point of difference between their results and Yan et al.'s (2018) is that Yan et al. assume bounded gradients, an assumption that is not satisfied for e.g., mean squared error (MSE). But a very similar assumption is hidden in the bounded-gradient-variance assumption Assumption 3.2; for example, Assumption 3.2 is clearly not satisfied by the least-squares regression problem
min_β (1/N)Σ_n (y_n – x_n • β)^2
with the minibatch gradient estimator computed over randomly chosen minibatches B:
\hat g = (1/|B|) Σ_{n \in B} x_n (y_n – x_n • β).
As the norm of β goes to infinity, so does the expected norm of the error of \hat g. I'm not saying this is a particularly big 
deal, just that it's not an improvement over Yan et al.'s result.

That aside, this seems like good work that could have a significant impact on practice.

A couple of other minor points:
• It looks like neither the experiments nor Theorem 3.2 show any benefit to PowerSGDM over PowerSGD. It would be nice to see some discussion (or at least speculation) on why that is.
• Not all of the arrows in Figure 1 are pointing to the right lines.
• In the abstract, it might be good to clarify that the exponentiation is elementwise.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper proposes PowerSGD for improving SGD to train deep neural networks. The main idea is to raise the stochastic gradient to a certain power. Convergence analysis and experimental results on CIFAR-10/CIFAR-100/Imagenet and classical CNN architectures are given. 

Overall, this is a clearly-written paper with comprehensive experiments. My major concern is whether the results are significant enough to deserve acceptance. The proposed method PowerSGD is an extension of the method in Yuan et al. (extended to handle stochastic gradient and momentum). I am not sure how novel the convergence analysis for PowerSGD is, and it would be nice if the authors could discuss technical challenges they overcome in the introduction. 
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper investigates an SGD variant (PowerSGD) where the stochastic gradient is raised to a power of $\gamma \in [0,1]$.  The authors introduce PowerSGD and PowerSGD with momentum (PowerSGDM). The theoretical proof of  the convergence is given and experimental results show that the proposed algorithm converges faster than some of the existing popular adaptive SGD techniques.  Intuitively, the proposed PowerSGD can boost the gradient (since $\gamma \in [0,1]$) so it may be helpful for the gradient of the lower layers of a deep network which may be hit by the vanishing gradient issue. This may give rise to a faster convergence.   So overall the idea makes sense but I have the following concerns. 

1. The major issue I have with this paper is Theorem 3.1 on the ergodic convergence rate of the proposed PowerSGD.  At the first glance, it is $O(\frac{1}{T})$ which is faster than the conventional SGD convergence rate $O(\frac{1}{\sqrt{T}})$.  But after a closer look, this rate is obtained by a very strong assumption on the batch size $B_{t}=T$.  In other words, when the number of iterations is large, the batch size will be large too.  I consider this assumption unrealistic.  Given that $T$ is typically very large (it is iterations, not epochs),  it will require a huge batch size, probably close to the whole training set. In this case, it is basically a GD, not SGD any more. That's why the rate is $O(\frac{1}{T})$, which is the convergence rate of GD.   I would like to see a convergence proof where the batch size $B_{t}$ is treated as a small constant like other SGD proofs assume.  Actually in the experiments the authors never use an increasing batch size. Instead, a constant batch size 128 is used. Therefore,  the faster convergence demonstrated in the experiments can not be explained by Theorem 3.1 or Theorem 3.2. 

2. There are numerous inaccuracies in the proof given the supplementary material.  For instance, in Eq.7,  $\nabla f(x) \sigma(\nabla f(x))$  should be $\nabla f(x)^{T} \sigma(\nabla f(x))$   The random variable $\xi_{t}$ should be a scalar on training samples, not a vector, etc..  The authors should clean it up. 

3. It would be helpful to show the $\gamma$ value on each experiment with different tasks. It would be good to know how $\gamma$ varies across tasks. 

4. I think in the comparative experiments, the plain SGD should be added as another reference algorithm. 

5. The term "PowerSGD" seems to have been used by other papers. 

review_title: Official Blind Review #1

Meta-review: After reading the author's rebuttal, the reviewers still think that this is an incremental work, and the theory and experiments .are inconsistent. The authors are encouraged to consider the the reivewer's comments to improve the paper.
Decision: Reject