Source-linked AI summary
D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, Markus Püschel
TL;DR
The paper addresses distributed separable optimization in networks where each node has private costs and constraints. It proposes D-ADMM, an ADMM-based distributed algorithm, and reports fewer communications than prior algorithms across several problems.
Problem
Distributed algorithms are needed to solve networked separable optimization problems while preserving private node costs and constraint sets.
Method
D-ADMM assigns variable copies to nodes, enforces equality across network edges, and uses a network coloring scheme for asynchronous operation.
Results
D-ADMM required fewer communications than previous algorithms in simulations of LASSO, BPDN, and SVM.
Takeaways & Limitations
Lower communication requirements are relevant to battery-operated sensor networks where communication is often the most energy-consuming task.
Takeaways & Limitations
Convergence is proven when the network is bipartite or all functions are strongly convex, while the efficiency advantage remains theoretically unexplained.
Abstract
from arXiv · showhide
We propose a distributed algorithm, named Distributed Alternating Direction Method of Multipliers (D-ADMM), for solving separable optimization problems in networks of interconnected nodes or agents. In a separable optimization problem there is a private cost function and a private constraint set at each node. The goal is to minimize the sum of all the cost functions, constraining the solution to be in the intersection of all the constraint sets. D-ADMM is proven to converge when the network is bipartite or when all the functions are strongly convex, although in practice, convergence is observed even when these conditions are not met. We use D-ADMM to solve the following problems from signal processing and control: average consensus, compressed sensing, and support vector machines. Our simulations show that D-ADMM requires less communications than state-of-the-art algorithms to achieve a given accuracy level. Algorithms with low communication requirements are important, for example, in sensor networks, where sensors are typically battery-operated and communicating is the most energy consuming operation.
I. INTRODUCTION
The paper formulates separable optimization over a connected network, where nodes retain private costs and constraints while cooperating through neighbor communication. It proposes an ADMM-based distributed approach motivated by reducing communication requirements relative to prior methods.
- The goal is to minimize the sum of private convex cost functions subject to the intersection of private closed convex constraint sets.
- Low communication cost is especially relevant in sensor networks because communication is often the most energy-consuming task for battery-powered nodes.
- A distributed algorithm uses no central node or data aggregation point, and each node communicates only with its neighbors.
- D-ADMM builds on an extended ADMM formulation whose convergence proof applies to some problems of interest.
- Unlike earlier ADMM reformulations requiring one or two communication steps per iteration, the proposed algorithm uses a different reformulation and experimentally requires fewer communications.
II. ALGORITHM DERIVATION
The algorithm reformulates the network optimization problem by giving each node a variable copy and enforcing equality across edges, then applies Extended ADMM using node coloring. The resulting D-ADMM updates colored node groups in parallel and converges under bipartite networks or strong convexity.
- Color-based reformulation: Node coloring partitions the variables and constraints into C color groups, enabling the reformulated problem to be handled by Extended ADMM.Nodes with the same color are non-neighbors, so their optimization problems can be solved in parallel.
- Problem reformulation: The reformulation assigns each node a copy x_p and enforces x_i = x_j on every edge, which guarantees consensus across a connected network.The constraints can be written as (B^T ⊗ I_n) x̄ = 0 using the graph’s node-arc incidence matrix.
- Extended ADMM: Extended ADMM generalizes ordinary ADMM to C blocks, but its established convergence guarantee for C > 2 requires all functions to be strongly convex.For C = 2, the method reduces to ordinary ADMM, which converges under much milder assumptions; convergence for broader cases was described as believed rather than established.
- D-ADMM updates: D-ADMM replaces edge-wise dual variables with node-wise dual variables and updates nodes sequentially by color, with same-color nodes operating in parallel.Knowing each node’s own color and its neighbors’ colors provides automatic coordination without a separate coordination mechanism.
- Convergence: D-ADMM produces copies converging to (x⋆, ..., x⋆), where x⋆ solves the original problem, when the network is bipartite or every f_p is strongly convex.A bipartite network can use two colors, satisfying the two-block convergence condition; non-bipartite networks rely on strong convexity.
III. APPLICATIONS
D-ADMM recasts several network optimization problems as separable programs, including consensus, sparse recovery, and distributed support vector machines. The applications use specific data partitions and show practical convergence and communication advantages over prior methods.
- Applications: D-ADMM converges in practice across the reformulated applications and outperforms previous work in communication count, despite limited general convergence guarantees.For these problems, strong convexity generally does not hold, so the stated guarantee relies on the applicable network condition.
- Consensus: Consensus computes the network-wide average by assigning node p the quadratic cost fp(x) = (1/2)(x − θp)^2.The resulting node subproblem has a closed-form solution.
- Sparse solutions of linear systems: Sparse linear-system recovery is addressed through LASSO and BPDN, with row or column partitions distributing blocks of A across nodes.In row partitions, b is divided with A; in column partitions, every node knows the full b.
- Sparse solutions of linear systems: The paper pairs LASSO with column partitioning and BPDN with row partitioning because the reverse assignments cannot be trivially recast as the target separable form.Basis Pursuit was previously solved for both partition types.
- LASSO: column partition: Column-partitioned LASSO requires duality and strict-convex regularization to recover a primal solution after solving the distributed formulation.Ordinary dual LASSO is insufficient because its objective is not strictly convex.
- Distributed support vector machines: Distributed SVM training assigns local data matrices and labels to nodes while transmitting only the global variable (s, r), whose size is n + 1.The local slack variables ξ̄p remain internal to each node.
IV. SIMULATION RESULTS
Simulations compare D-ADMM with distributed alternatives across consensus, LASSO, BPDN, and SVM using communication steps (CSs) as the main performance measure. D-ADMM required the fewest CSs for LASSO, BPDN, and SVM, while matching the fastest consensus method closely.
- Performance measure: A communication step occurs when every node transmits an n-dimensional vector to its neighbors; one D-ADMM iteration equals one CS.The compared algorithm from [12] requires two CSs per iteration because nodes transmit two vectors.
- Evaluation scope: The simulations evaluate D-ADMM and related algorithms on consensus, LASSO, BPDN, and SVM.Figure 3 contains one panel for each problem.
- Interpretation: The CS measure excludes per-node computational complexity and is not necessarily related to execution time.D-ADMM may be slower than synchronous competitors because it operates asynchronously.
- Experimental setup: The experiments used five 50-node networks, stopping when relative error reached ǫ or when M CSs were exhausted.The centralized solution x⋆ served as the reference for the stopping criterion.
- Consensus: D-ADMM had performance very similar to the fastest consensus algorithm,.Algorithm [22] was designed only for consensus and cannot be easily generalized to the full problem class.
- LASSO and BPDN: In both LASSO and BPDN, D-ADMM always required fewer CSs to converge than the evaluated alternatives.The BPDN-specific Algorithm 3 of reached the maximum CS count in all but the last two networks.
- SVM: For SVM, D-ADMM required the smallest number of CSs to converge.Algorithm [12] reached the maximum number of CSs and was therefore omitted from the SVM figure.
V. CONCLUSIONS
The paper proposes a distributed algorithm for separable optimization in networks with private node data. Its asynchronous, coloring-based operation reduces communication requirements experimentally, although the theoretical reason for this efficiency remains open.
- Contribution: D-ADMM solves separable network optimization problems while each node retains a private cost and constraint set.The global objective minimizes the sum of node costs subject to the intersection of node constraint sets.
- Algorithm: A network coloring scheme coordinates asynchronous node operation in the proposed algorithm.
- Empirical result: Experiments show fewer communication requirements than previous algorithms across several problems.
- Open question: The theoretical explanation for D-ADMM’s greater efficiency than previous algorithms remains open.