Yat Tin Chow – Optimization Online

Expander Graph and Communication-Efficient Decentralized Optimization

Published: 2016/12/02

In this paper, we discuss how to design the graph topology to reduce the communication complexity of certain algorithms for decentralized optimization. Our goal is to minimize the total communication needed to achieve a prescribed accuracy. We discover that the so-called expander graphs are near-optimal choices. We propose three approaches to construct expander graphs for … Read more

Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications

Published: 2016/11/08, Updated: 2017/03/02

Yat Tin Chow

Wotao Yin

Tianyu Wu

Convex and Nonsmooth Optimization coordinate update, cyclic, fixed point, image reconstruction, nonexpansive operator, nonnegative matrix factorization, robust least squares, shuffled cyclic

Many problems reduce to the fixed-point problem of solving $x=T(x)$. To this problem, we apply the coordinate-update algorithms, which update only one or a few components of $x$ at each step. When each update is cheap, these algorithms are faster than the full fixed-point iteration (which updates all the components). In this paper, we focus … Read more