Timezone: »
Poster
Non-Ergodic Alternating Proximal Augmented Lagrangian Algorithms with Optimal Rates
Quoc Tran Dinh
We develop two new non-ergodic alternating proximal augmented Lagrangian algorithms (NEAPAL) to solve a class of nonsmooth constrained convex optimization problems. Our approach relies on a novel combination of the augmented Lagrangian framework, alternating/linearization scheme, Nesterov's acceleration techniques, and adaptive strategy for parameters. Our algorithms have several new features compared to existing methods. Firstly, they have a Nesterov's acceleration step on the primal variables compared to the dual one in several methods in the literature.
Secondly, they achieve non-ergodic optimal convergence rates under standard assumptions, i.e. an $\mathcal{O}\left(\frac{1}{k}\right)$ rate without any smoothness or strong convexity-type assumption, or an $\mathcal{O}\left(\frac{1}{k^2}\right)$ rate under only semi-strong convexity, where $k$ is the iteration counter.
Thirdly, they preserve or have better per-iteration complexity compared to existing algorithms. Fourthly, they can be implemented in a parallel fashion.
Finally, all the parameters are adaptively updated without heuristic tuning.
We verify our algorithms on different numerical examples and compare them with some state-of-the-art methods.
Author Information
Quoc Tran Dinh (Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, North Carolina)
More from the Same Authors
-
2021 Poster: FedDR – Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization »
Quoc Tran Dinh · Nhan H Pham · Dzung Phan · Lam Nguyen -
2020 Poster: Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function »
Quoc Tran Dinh · Deyi Liu · Lam Nguyen -
2017 Poster: Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization »
Ahmet Alacaoglu · Quoc Tran Dinh · Olivier Fercoq · Volkan Cevher -
2015 Poster: A Universal Primal-Dual Convex Optimization Framework »
Alp Yurtsever · Quoc Tran Dinh · Volkan Cevher