Communication-Efficient Algorithms For Distributed Optimization
arXiv:1312.0263
Abstract
This thesis is concerned with the design of distributed algorithms for solving optimization problems. We consider networks where each node has exclusive access to a cost function, and design algorithms that make all nodes cooperate to find the minimum of the sum of all the cost functions. Several problems in signal processing, control, and machine learning can be posed as such optimization problems. Given that communication is often the most energy-consuming operation in networks, it is important to design communication-efficient algorithms. The main contributions of this thesis are a classification scheme for distributed optimization and a set of corresponding communication-efficient algorithms. The class of optimization problems we consider is quite general, since each function may depend on arbitrary components of the optimization variable, and not necessarily on all of them. In doing so, we go beyond the common assumption in distributed optimization and create additional structure that can be used to reduce the number of communications. This structure is captured by our classification scheme, which identifies easier instances of the problem, for example the standard distributed optimization problem, where all functions depend on all the components of the variable. In our algorithms, no central node coordinates the network, all the communications occur between neighboring nodes, and the data associated with each node is processed locally. We show several applications including average consensus, support vector machines, network flows, and several distributed scenarios for compressed sensing. We also propose a new framework for distributed model predictive control. Through extensive numerical experiments, we show that our algorithms outperform prior distributed algorithms in terms of communication-efficiency, even some that were specifically designed for a particular application.
arXiv commentThesis defended on October 10, 2013. Dual PhD degree from Carnegie Mellon University, PA, and Instituto Superior Técnico, Lisbon, Portugal
References in corpus (16)
- Emergence of scaling in random networks
- Constrained Consensus
- Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Distributed Optimal Power Flow for Smart Microgrids
- Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
- D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
- Distributed Basis Pursuit
- Cooperative Convex Optimization in Networked Systems: Augmented Lagrangian Algorithms with Directed Gossip Communication
- Optimization and Analysis of Distributed Averaging with Short Node Memory
- Distributed Optimization With Local Domains: Applications in MPC and Network Flows
- A Proof of Convergence For the Alternating Direction Method of Multipliers Applied to Polyhedral-Constrained Functions
- Accelerated Dual Descent for Network Optimization
- Centralized and Distributed Newton Methods for Network Optimization and Extensions
- DCOOL-NET: Distributed cooperative localization for sensor networks