When using distributed training to speed up stochastic gradient descent, learning rates must adapt to new scales in order to maintain training effectiveness. Re-tuning these parameters is resource intensive, while fixed scaling rules often degrade model quality. We propose AdaScale SGD, a practical and principled algorithm that is approximately scale invariant. By continually adapting to the gradient's variance, AdaScale often trains at a wide range of scales with nearly identical results. We describe this invariance formally through AdaScale's convergence bounds. As the batch size increases, the bounds maintain final objective values, while smoothly transitioning away from linear speed-ups. In empirical comparisons, AdaScale trains well beyond the batch size limits of popular "linear learning rate scaling" rules. This includes large-scale training without model degradation for machine translation, image classification, object detection, and speech recognition tasks. The algorithm introduces negligible computational overhead and no tuning parameters, making AdaScale an attractive choice for large-scale training.
This paper proposes a novel rule for scaling the learning rate, called the gain ratio, for when the effective batch size (induced by synchronous distributed SGD) is increased. This rule for the gain ratio uses estimates of the trace of the covariance and the norm of the true gradient to determine the appropriate steplength. This results in a method with a R-linear convergence guarantee to a neighborhood that is not dependent on $S$ (which is called scale-invariant). The algorithm additionally tracks the sum of the gain ratios in order to determine the "effective" number of iterations taken, and cut the steplength appropriately. 
Strengths:
The gain ratio proposed in this paper is intuitive. I particularly like how the algorithm estimates the mean and variance information in an unbiased manner to determine an appropriate scaling for the steplength. The method is able to attain a R-linear rate of convergence and appears to perform well in practice for a wide variety of applications. The gain ratio is simple to estimate within a distributed framework.
Weaknesses:
I found some of the terms in the paper to be unclear or ill-defined. The original use of the term "scale" was unclear to me. Does this refer to the number of nodes in the distributed implementation? What is its relationship to batch size?
I found the definition of scale invariance in this paper to also be unclear on first read. The claim is that the algorithm is scale invariant if its final model does not depend on $S$. What is the "final model"? As currently defined, the current analysis does not guarantee that the algorithm will reach the same final model (assuming that $f(w, x) = \ell(h(w, x), y)$, i.e. a composition of a loss function and model), as the PL condition only ensures that one reaches a global minimum, which may not be unique. In fact, the analysis only guarantees convergence to a neighborhood. The description within the analysis appears to imply that scale-invariance is a property of the algorithm attached to its convergence property. Is this the case?
The definition of scale invariance is also already used in optimization to mean algorithms that are not modified when the objective is multiplied by a constant or an affine transformation. This adds to the lack of clarity, and I would suggest the authors use a different term for this kind of invariance (batch size invariant, or something like that?).
Is the theoretical comparison between SGD and AdaScale fair? Note that one can prove a stronger convergence result with SGD because one can actually attain a Q-linear rate of convergence to a neighborhood (for a proof, see for example, Bottou, et al. (2018)). In particular, one should have something like (in the paper's notation):
$$\mathbb{E}[F(w_T) - F^*] \leq (1 - \gamma)^T [F(w_0) - F^*] + \Delta.$$
This means that one can actually guarantee a fixed ratio of decrease in expectation to a neighborhood, whereas AdaScale converges linearly but not with a fixed ratio. 
Some other small questions regarding the theory and experiments:
- Is there a reason why batch normalization was not tried for the CIFAR-10 experiments?
- Is it possible for $r_{t - 1} \gamma > 1$?
- Why was it necessary to estimate $\sigma^2 (w_t)$ and $\|\nabla F(w_t)\|^2$ by both aggregating at the current iteration and exponential averaging? What happens if exponential averaging is removed?
- What are the limitations of this method? How large of a batch size can one use with AdaScale before the algorithm breaks down (if at all)?
Additional Comments:
The algorithm is quite reminiscient of the steplength prescribed in Bollapragada, et al. (2018), which consider the steplength: 
$$( 1 + \frac{\sigma^2(w_t)}{\|\nabla F(w_t)\|^2})^{-1}.$$
This gain ratio prescribed in this paper is the ratio between this quantity for two different batch sizes. Is there a clear explanation for why the relationship between these two quantities would arise?
This method could also be used for determining an appropriate scaling of the steplength in the sequential setting, when a larger batch size is used. Has this been considered?
Despite the concerns regarding the clarity in writing and the rigor in the theory of the paper, I think that the algorithmic idea proposed in this paper is interesting, novel, and practical. Because of the lack of clarity and rigor, I have given this paper a weak reject, but I would be happy to accept the paper if my concerns above were addressed in the final manuscript.