Distributed proximal algorithms for large-scale structured optimization

Efficient first-order algorithms for large-scale distributed optimizationis the main subject of investigation in this thesis.The algorithms considered cover a wide array of applicationsin machine learning, signal processing and control.In recent years, a large number of algorithms have been introducedthat rely on (possibly a reformulation of) one of theclassical splitting algorithms, specifically forward-backward,Douglas-Rachford and forward-backward-forward splittings.In this thesis a new three term splitting technique is developedthat recovers forward-backward and Douglas-Rachfordsplittings as special cases. In the context of structured optimization,this splitting is leveraged to develop a frameworkfor a large class of primal-dual algorithms providing a unifiedconvergence analysis for many seemingly unrelated algorithms.Moreover, linear convergence is established for allsuch algorithms under mild regularity conditions for the costfunctions.As another notable contribution we propose a randomizedblock-coordinate primal-dual algorithm that leads to a fullydistributed asynchronous algorithm in a multi-agent model.Moreover, when specializing to multi-agent structured optimizationover graphs, novel algorithms are proposed. In addition,it is shown that in a multi-agent model bounded communicationdelays are tolerated by primal-dual algorithmsprovided that certain strong convexity assumptions hold.In the final chapter we depart from convex analysis and considera fully nonconvex block-coordinate proximal gradientalgorithm and show that it leads to nonconvex incrementalaggregated algorithms for regularized finite sum and sharingproblems with very general sampling strategies.