Direct Runge-Kutta Discretization Achieves Acceleration
We study gradient-based optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) related to the continuous limit of Nesterov's accelerated gradient method. When the function is smooth enough, we show that acceleration can be achieved by a stable discretization of this ODE using standard Runge-Kutta integrators. Specifically, we prove that under Lipschitz-gradient, convexity and order-(s + 2) differentiability assumptions, the sequence of iterates generated by discretizing the proposed second-order ODE converges to the optimal solution at a rate of O(N −2 s s+1 ), where s is the order of the Runge-Kutta numerical integrator. Furthermore, we introduce a new local flatness condition on the objective, under which rates even faster than O(N −2 ) can be achieved with low-order integrators and only gradient information. Notably, this flatness condition is satisfied by several standard loss functions used in machine learning. We provide numerical experiments that verify the theoretical rates predicted by our results.
The author analyze the convergence of the RK method applied to a modified version of the "Nesterov Flow" from Su et al. Using a "local flatness" assumption, they show sub-optimal but accelerated rates of convergence in function of 1) the degree of flatness and 2) the order of integration.  Clarity ======= The paper is very clear, all the assumptions and modifications to the differential equation of Su et al., as well as the Lyapunov function, are well motivated. Also, the paper is a very good introduction to Runge Kutta methods.  Small detail, in section 2.1. : Using "S" for the number of stages and "s" for the order of integration is confusing.  In the experiments, by "iteration" you mean the number of gradient calls or the number of "RK" calls?  General =======  - Direct acceleration using *any* RK method is a very good point: The analysis is very generic.  - The assumption of local flatness up to "s" is a bit strong. Do you think it is possible to weaken that assumption?  - In practice, high-order RK methods are quite costly and unstable (because it cancels Taylor coefficients up to "s", but you do not have any control on the coefficient of order "s+1"). Usually, people who uses these methods don't go too far in the number of stages.  - Also, high-order runge kutta methods usually needs an incredibly high number of internal stages (for example, RK of order 10 requires 17 stages). Do you takes the number of internal stages into account in you complexity bound? Source: "A Runge-Kutta Method of Order 10", Ernst Hairer.  - I have a remark about the choice of the step-size. It looks that the computation of the step "h" is not easy. However, there exist adaptive ways to choose it, based on difference between two RK methods with different orders (ex. RK45, which is implemented in Matlab under the name of ODE45). Could you think this can be used as adaptive stepsize in you experiment?  - There exist also other kind of methods: * Linear multi-step methods * Predictor-corrector method * More generally, RK and linear multi steps are instances of "General linear methods" (See the paper "General linear methods" by J. Butcher for instance). Do you think you analysis can be extended to these other standard methods?  - I have a remark about the order of the RK method. In your analysis, you said that you can approach the optimal rate of convergence by increasing the order of the method. However, I think design high-order runge kutta is quite painful in practice (for example, RK10 requires to generates, then solve, a system of 1000+ equations). Do you think is required in practice (in particular, when you use adaptive step size)?  Decision ========  accept (7/10). I particularly like the fact that *direct* discretisation leads to accelerated rate, but the paper lacks a bit of impact. As the conclusion says:  this does not (yet) fully explain acceleration. However, I think this is a good step toward it. The paper presents a promising research direction: since RK-like optimization schemes are not really popular, this may leads to new method and new kind of analysis. I recommend acceptance.   Post-rebuttal ----------------  I read the rebuttal.