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 isb-complexity, which quantifies the best possible solution accuracy that can be achieved from communicatingbbits. We find the exactε- andb-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 tolog ₂(1/ε)and theb-complexity proportionally to1/2ᵇ. We also introduce a variant of theε- andb-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 theb-complexity cannot converge at a faster rate thanO(1/b). Therefore, the results demonstrate a tradeoff between fast convergence and primal feasibility. We illustrate the result by numerical studies.