STOCHASTIC GRADIENT/MIRROR DESCENT: MINI- MAX OPTIMALITY AND IMPLICIT REGULARIZATION
Stochastic descent methods (of the gradient and mirror varieties) have become increasingly popular in optimization. In fact, it is now widely recognized that the success of deep learning is not only due to the special deep architecture of the models, but also due to the behavior of the stochastic descent methods used, which play a key role in reaching "good" solutions that generalize well to unseen data. In an attempt to shed some light on why this is the case, we revisit some minimax properties of stochastic gradient descent (SGD) for the square loss of linear models-originally developed in the 1990's-and extend them to general stochastic mirror descent (SMD) algorithms for general loss functions and nonlinear models. In particular, we show that there is a fundamental identity which holds for SMD (and SGD) under very general conditions, and which implies the minimax optimality of SMD (and SGD) for sufficiently small step size, and for a general class of loss functions and general nonlinear models. We further show that this identity can be used to naturally establish other properties of SMD (and SGD), namely convergence and implicit regularization for over-parameterized linear models (in what is now being called the "interpolating regime"), some of which have been shown in certain cases in prior literature. We also argue how this identity can be used in the so-called "highly over-parameterized" nonlinear setting (where the number of parameters far exceeds the number of data points) to provide insights into why SMD (and SGD) may have similar convergence and implicit regularization properties for deep learning.
This is a very interesting paper and it suggests a novel way to think of "implicit regularization". The power of this paper lies in its simplicity and its inspiring that such almost-easy arguments could be made to get so much insight. It suggests that minimizers of the Bregrman divergence are an alternative characterization of the asymptotic end-points of  "Stochastic Mirror Descent" (SMD) when it converges. So choice of the strongly convex potential function in SMD is itself a regularizer!  
Its a very timely paper given the increasing consensus that "implicit regularization" is what drives a lot of deep-learning heuristics. This paper at its technical core suggests a modified notion of Bregman-like divergence (equation 15) which on its own does not need a strongly convex potential. Then the paper goes on to show that there is an invariant of the iterations of SMD along its iterations which involves a certain relationship (equation 18) between the usual Bregman divergence and their modified divergence. I am eager to see if such relationships can be shown to hold for more complicated iterative algorithms! 
But there are a few points in the paper which are not clear and probably need more explanation and let me list them here. ( and these are the issues that prevent me from giving this paper a very high rating despite my initial enthusiasm )
1. 
Can the authors explain how is the minimax optimality result of Theorem 6 (and Corollary 7) related to the main result of the paper which is probably Proposition 8 and and 9? Is that minimax optimiality a different insight separate from the main line of the arguments (which I believe is Proposition 8 and 9)? 
2.
Is the gain in Proposition 9 over Proposition 8 is all about using loss convexity to ensure that the SMD converges and w_\infty exists? 
3. 
The paper has highly insufficient comparisons to many recent other papers on the idea of "implicit bias" like, https://arxiv.org/abs/1802.08246, https://arxiv.org/abs/1806.00468 and https://arxiv.org/abs/1710.10345. It seems pretty necessary that there be a section making a detailed comparison with these recent papers on similar themes.