Timezone: »

 
Poster
Direct Runge-Kutta Discretization Achieves Acceleration
Jingzhao Zhang · Aryan Mokhtari · Suvrit Sra · Ali Jadbabaie

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #9
in Thu Poster Session B »
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 $\mathcal{O}({N^{-2\frac{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 $\mathcal{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.
Keywords: Convex Optimization · Dynamical Systems
[ Paper]  [ Poster] 

Author Information

Jingzhao Zhang (MIT)
Aryan Mokhtari (MIT)
Suvrit Sra (MIT)

Suvrit Sra is a faculty member within the EECS department at MIT, where he is also a core faculty member of IDSS, LIDS, MIT-ML Group, as well as the statistics and data science center. His research spans topics in optimization, matrix theory, differential geometry, and probability theory, which he connects with machine learning --- a key focus of his research is on the theme "Optimization for Machine Learning” (http://opt-ml.org)

Ali Jadbabaie (MIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors