Skip to yearly menu bar Skip to main content


Poster

A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization

Sulaiman Alghunaim · Kun Yuan · Ali H Sayed

East Exhibition Hall B + C #24

Keywords: [ Distributed Inference ] [ Algorithms -> Large Scale Learning; Probabilistic Methods ] [ Optimization ] [ Convex Optimization ]


Abstract:

Decentralized optimization is a powerful paradigm that finds applications in engineering and learning design. This work studies decentralized composite optimization problems with non-smooth regularization terms. Most existing gradient-based proximal decentralized methods are known to converge to the optimal solution with sublinear rates, and it remains unclear whether this family of methods can achieve global linear convergence. To tackle this problem, this work assumes the non-smooth regularization term is common across all networked agents, which is the case for many machine learning problems. Under this condition, we design a proximal gradient decentralized algorithm whose fixed point coincides with the desired minimizer. We then provide a concise proof that establishes its linear convergence. In the absence of the non-smooth term, our analysis technique covers the well known EXTRA algorithm and provides useful bounds on the convergence rate and step-size.

Live content is unavailable. Log in and register to view live content