2019/02/11 by Bin Shi, Shi, Bin, Simon S. Du +5 · 1 citation
Computer Science · Economics, Econometrics and Finance · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.1902.03694
openalex publication_date 2019/02/11 · openalex created_date 2019/04/11 · openalex updated_date 2026/07/28
We study first-order optimization methods obtained by discretizing ordinary differential equations (ODEs) corresponding to Nesterov's accelerated gradient methods (NAGs) and Polyak's heavy-ball method. We consider three discretization schemes: an explicit Euler scheme, an implicit Euler scheme, and a symplectic scheme. We show that the optimization algorithm generated by applying the symplectic scheme to a high-resolution ODE proposed by Shi et al. [2018] achieves an accelerated rate for minimizing smooth strongly convex functions. On the other hand, the resulting algorithm either fails to achieve acceleration or is impractical when the scheme is implicit, the ODE is low-resolution, or the scheme is explicit.