IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
Yossi Arjevani, Joan Bruna, Bugra Can, Mert Gurbuzbalaban, Stefanie Jegelka, Hongzhou Lin
Abstract
We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method, thereby providing a systematic way for deriving several well-known decentralized algorithms including EXTRA and SSDA. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds. We provide experimental results that demonstrate the effectiveness of the proposed algorithm on highly ill-conditioned problems.
BibTeX
@inproceedings{NEURIPS2020_ed77eab0,
author = {Arjevani, Yossi and Bruna, Joan and Can, Bugra and Gurbuzbalaban, Mert and Jegelka, Stefanie and Lin, Hongzhou},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {20648--20659},
publisher = {Curran Associates, Inc.},
title = {IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ed77eab0b8ff85d0a6a8365df1846978-Paper.pdf},
volume = {33},
year = {2020}
}