Search

Although Nesterov's accelerated gradient (NAG) methods have been studied from various perspectives, it remains unclear why the most popular forms of NAG must handle convex and strongly convex objective functions separately. Motivated by this inconsistency, we propose an NAG method that unifies the existing ones for the convex and strongly convex cases. We first design a Lagrangian function that continuously extends the first Bregman Lagrangian to the strongly convex setting. As a specific case of the Euler--Lagrange equation for this Lagrangian, we derive an ordinary differential equation (ODE) model, which we call the unified NAG ODE, that bridges the gap between the ODEs that model NAG for convex and strongly convex objective functions. We then design the unified NAG, a novel momentum method whereby the continuous-time limit corresponds to the unified ODE. The coefficients and the convergence rates of the unified NAG and unified ODE are continuous in the strong convexity parameter $\mu$ on $[0, +\infty)$. Unlike the existing popular algorithm and ODE for strongly convex objective functions, the unified NAG and the unified NAG ODE always have superior convergence guarantees compared to the known algorithms and ODEs for non-strongly convex objective functions. This property is beneficial in practical perspective when considering strongly convex objective functions with small $\mu$. Furthermore, we extend our unified dynamics and algorithms to the higher-order setting. Last but not least, we propose the unified NAG-G ODE, a novel ODE model for minimizing the gradient norm of strongly convex objective functions. Our unified Lagrangian framework is crucial in the process of constructing this ODE. Fascinatingly, using our novel tool, called the differential kernel, we observe that the unified NAG ODE and the unified NAG-G ODE have an anti-transpose relationship.

In this paper, we generalize the Nesterov accelerated gradient (NAG) method to solve Riemannian optimization problems in a computationally tractable manner. The iteration complexity of our algorithm matches that of the NAG method on the Euclidean space when the objective functions are geodesically convex or geodesically strongly convex. To the best of our knowledge, the proposed algorithm is the first fully accelerated method for geodesically convex optimization problems without requiring strong convexity. Our convergence rate analysis exploits novel metric distortion lemmas as well as carefully designed potential functions. We also identify a connection with the continuous-time dynamics for modeling Riemannian acceleration in Alimisis et al. [1] to understand the accelerated convergence of our scheme through the lens of continuous-time flows.