Connecting Optimization and Regularization Paths
We study the implicit regularization properties of optimization techniques by explicitly connecting their optimization paths to the regularization paths of "corresponding" regularized problems. This surprising connection shows that iterates of optimization techniques such as gradient descent and mirror descent are pointwise close to solutions of appropriately regularized objectives. While such a tight connection between optimization and regularization is of independent intellectual interest, it also has important implications for machine learning: we can port results from regularized estimators to optimization, and vice versa. We investigate one key consequence, that borrows from the well-studied analysis of regularized estimators, to then obtain tight excess risk bounds of the iterates generated by optimization techniques.
The authors explore the relation between the trajectory of Gradient Descent (GD) initiated in the origin and the regularization path for l2-regularized minimization of the same objective.  They first study the continuous-time setting where GD is replaced Gradient Flow, assuming that the objective is smooth and strongly convex. The main result (Theorem 1 whose proof I have verified) is as follows: under the appropriate scaling between the time $t$ in GD and the inverse regularization parameter $\eta$, the two trajectories do not diverge much. This result is obtained by quantifying the shrinkage of the gradients as $t$ and $eta$ tend to infinity. In the continuous-time setting, the authors manage to reduce this task to formulating and solving certain ODEs. Then, a discrete-time counterpart of Theorem 1 is established (Theorem 2); its proof is more technical but mostly goes along the same lines (the main technical difference is that instead of solving ODEs one deals with linear recursions). Honestly, I did not check the proof of this later result, but overall it seems credible to me taking into account my verification of Theorem 1 and related technical lemmas.  The authors then briefly state the extensions of these results for non-Euclidean proximal setups (i.e. Mirror Descent), assuming that the potential is smooth and strongly convex.  Finally, the obtained results are applied to establish statistical bounds for the excess risk when Gradient Flow is used to minimize the empirical risk objective. The main result here is Corollary 5, which provides a recipe for early stopping. These results are then tightened for random-design linear regression and classification under separability assumptions. These results are close in spirit to (1) the results of (Hardt et al, 2015), where implicit regularization properties of SGD with early stopping are established in the general setting of empirical risk minimization (ERM), and (2) a more recent line of work (Soudry et al. 2017), (Ji and Telgarsky 2018), (Gunasekar et a;. 2018), where self-regularization properties of SGD are established in the case of separable data.   First let me discuss the main highlight of the paper, Theorems 1-2. The technique that relates the two trajectories through a differential equation is easy-to-use and powerful, and I consider it the main highlight of the paper. I also like the idea of using the known results for l2-regularized ERM to analyze GD with early stopping. That said, it has long been known that the analysis of Gradient Flow is reduced to solving ODEs, see e.g. (D. Scieur, Integration Methods and Accelerated Optimization Algorithms 2017). I would like to see a review of the related literature since I suspect that some of the results in Section 1 can be already known; as far as I can see, the real novelties here are (1) using the ODE-analysis to relate Gradient Flow/Descent to the l2-regularization path, and (2) providing a result for the case of discrete step.   I should also mention that I find the results stated in Sections 3 and 4 particularly interesting and useful for the computational learning theory community. That said, a more thorough discussion of these results and comparison with the existing literature on optimal stopping / margin-type results would be appreciated.  I have decided to evaluate the paper only as weak accept, for a number of reasons listed below:  1. On several occasions, mathematical results are claimed without a proof or reference (lines 69-70, line 80, lines 134-137).  2. The last (non-trivial) step in the proof of Theorem 1 is missing — the authors do not detail how they solve the ODE in the display between l.337 and l.338. I did manage to arrive at l.339 after some algebraic manipulations, making the estimate m\nu + 1 \ge m\nu, and solving an inhomogeneous ODE obtained in the end; I think that all these steps should have been at least hinted on!  3. Theorem 2 is not properly commented upon. 4. The results in Section 2.1 seem rather conceptual: the only known to me non-trivial case of a strongly convex *and* smooth potential is that of Mahalanobis distance which can be reduced to the case of Euclidean norm and |.|^2/2-potential by a linear change of variables. As noted by the authors themselves, the ``truly’’ non-Euclidean setups, such as minimization on the simplex or l1-ball, or on the nuclear-norm ball, do not admit smooth potentials, see e.g.  (Nesterov and Nemirovski, On first-­order algorithms for l 1/nuclear norm minimization).  Instead, one imposes a weaker property of the slow growth of the potential on the feasible set. Most importantly, as noted in (Nesterov 2005) and also by the authors themselves, non-Euclidean setups are never better than the Euclidean one when the objective is both smooth and strongly convex. 5. The quality of writing in general could be improved. For example, on several occasions I spotted contractions in the text, such as “till” or “don’t”; I personally consider their use inappropriate in a scientific paper. 6. The plots are hard to read because of very small axis tick labels and non-uniform grid. If the paper gets accepted, I would appreciate better-looking plots in the camera-ready version, as well as more ample explanations for them.