Communication Complexity of Dual Decomposition Methods for Distributed Resource Allocation Optimization

Dual decomposition methods are among the most prominent approaches for finding primal/dual saddle point solutions of resource allocation optimization problems. To deploy these methods in the emerging Internet of things networks, which will often have limited data rates, it is important to understand the communication overhead they require. Motivated by this, we introduce and explore two measures of communication complexity of dual decomposition methods to identify the most efficient communication among these algorithms. The first measure is ϵ-complexity, which quantifies the minimal number of bits needed to find an ϵ-accurate solution. The second measure is b-complexity, which quantifies the best possible solution accuracy that can be achieved from communicating b bits. We find the exact ϵ-and b-complexity of a class of resource allocation problems where a single supplier allocates resources to multiple users. For both the primal and dual problems, the ϵ-complexity grows proportionally to 2(1ϵ) and the b-complexity proportionally to 1/2b. We also introduce a variant of the ϵ-and b-complexity measures where only algorithms that ensure primal feasibility of the iterates are allowed. Such algorithms are often desirable because overuse of the resources can overload the respective systems, e.g., by causing blackouts in power systems. We provide upper and lower bounds on the convergence rate of these primal feasible complexity measures. In particular, we show that the b-complexity cannot converge at a faster rate than O(1/b). Therefore, the results demonstrate a tradeoff between fast convergence and primal feasibility. We illustrate the result by numerical studies.

Duke Scholars

Author Vahid Tarokh Electrical and Computer Engineering