Nesterov Acceleration with Operator Decomposition
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908959740264448 |
|---|---|
| author | Lee, Jaewook Ryu, Ernest K. Yun, Chulhee |
| author_facet | Lee, Jaewook Ryu, Ernest K. Yun, Chulhee |
| contents | 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 $ε$-accurate solution of \[ Θ\left(\sqrt{\frac{L_ϕ}μ + \frac{L_{\mathbb{S}}^2}{μ^2}} \,\log \frac{1}ε\right), \] where $μ$ is the strong monotonicity parameter, $L_ϕ$ is the Lipschitz constant of the cyclically monotone component, and $L_{\mathbb{S}}$ is the Lipschitz constant of the (possibly acyclic) monotone remainder. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11105 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nesterov Acceleration with Operator Decomposition Lee, Jaewook Ryu, Ernest K. Yun, Chulhee Optimization and Control 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 $ε$-accurate solution of \[ Θ\left(\sqrt{\frac{L_ϕ}μ + \frac{L_{\mathbb{S}}^2}{μ^2}} \,\log \frac{1}ε\right), \] where $μ$ is the strong monotonicity parameter, $L_ϕ$ is the Lipschitz constant of the cyclically monotone component, and $L_{\mathbb{S}}$ is the Lipschitz constant of the (possibly acyclic) monotone remainder. |
| title | Nesterov Acceleration with Operator Decomposition |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.11105 |