Nesterov Acceleration with Operator Decomposition

Abstract

We propose Nesterov acceleration with Operator Decomposition (NOD), which extends Nesterov’s accelerated gradient descent (NAG) from smooth strongly convex optimization to the broader setting of strongly monotone, Lipschitz operators. The key insight is to decompose the operator into cyclically monotone and monotone components, with the Asplund decomposition providing the tightest such representation, and to have the algorithm utilize the decomposed oracles. NOD and its analysis subsume the classical theory of Nesterov acceleration and yield an iteration complexity for finding an $\epsilon$-accurate solution of $$ \Theta\left( \sqrt{ \frac{L_{\phi}}{\mu} + \frac{L_{\mathbb{S}}^2}{\mu^2} } \log\frac{1}{\epsilon} \right), $$ where $\mu$ is the strong monotonicity parameter, $L_{\phi}$ is the Lipschitz constant of the cyclically monotone component, and $L_{\mathbb{S}}$ is the Lipschitz constant of the (possibly acyclic) monotone remainder.

Chulhee Yun

Associate Professor

I am an Associate Professor at KAIST AI. I am interested in optimization and machine learning theory.