# 9.23 Imaging And Graphics Seminar

Topic: Decentralize Optimization

Hold: Shicong Cen

Centralized Optimization

Communication Efficient Distributed Optimization using an Approximate Newton-type Method (Ohad Shamir, Nathan Srebro, Tong Zhang, 2013)

- DANE

Communication-Efficient Distributed Dual Coordinate Ascent (Martin Jaggi, Virginia Smith, Martin Takac, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, Michael I. Jordan, 2014)

- CoCoA
- Distributed dual update for loss functions of linear predictor

DiSCO: Distributed Optimization for Self-Concordant Empirical Loss (Yuchen Zhang, Lin Xiao, 2015)

- Damped Newton + Distributed PCG

AIDE: Fast and Communication Efficient Distributed Optimization(Sashank J. Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczós, Alex Smola, 2016)

- DANE + Nesterov's acceleration
- Convergence analysis of inexact DANE

GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (Shusen Wang, Farbod Roosta-Khorasani, Peng Xu, Michael W. Mahoney, 2017)

- Distributed Newton steps

Decentralized Optimization

On the Convergence of Decentralized Gradient Descent (Kun Yuan, Qing Ling, Wotao Yin, 2013)

D-ADMM: A communication-efﬁcient distributed algorithm for separable optimization (João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, and Markus Püschel, 2013)

On the Linear Convergence of the ADMM in Decentralized Consensus Optimization (Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin, 2014)

EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (Wei Shi, Qing Ling, Gang Wu, Wotao Yin, 2014)

Network Newton (Aryan Mokhtari, Qing Ling, Alejandro Ribeiro, 2014)

- Truncated Taylor series of Newton step applied to regularized problem

A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization (Aryan Mokhtari, Wei Shi, Qing Ling, and Alejandro Ribeiro, 2016)

- Truncated Taylor series of Newton step applied to augmented Lagrangian function

DSA: Decentralized Double Stochastic Averaging Gradient Algorithm Aryan (Aryan Mokhtari, Alejandro Ribeiro, 2016)

- EXTRA + SVRG trick

Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development (Kun Yuan, Bicheng Ying, Xiaochuan Zhao, Ali H. Sayed, 2017)

Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis (Kun Yuan, Bicheng Ying, Xiaochuan Zhao, Ali H. Sayed, 2017)

A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (Wotao Yin, Xianghui Mao, Kun Yuan, Yuantao Gu, Ali H. Sayed, 2018)

- Walk ADMM