Distributed Big-Data Optimization via Block Communications
This work addresses the communication and computation bottleneck in distributed optimization for high-dimensional problems, offering a practical solution for multi-agent systems.
The paper proposes the first distributed algorithm for large-scale optimization where agents optimize and communicate only a subset of variables, using successive convex approximation and block-signal tracking. It achieves asymptotic convergence to stationary solutions, with numerical results on sparse regression demonstrating effectiveness and trade-offs between block size, convergence speed, and communication cost.
We study distributed multi-agent large-scale optimization problems, wherein the cost function is composed of a smooth possibly nonconvex sum-utility plus a DC (Difference-of-Convex) regularizer. We consider the scenario where the dimension of the optimization variables is so large that optimizing and/or transmitting the entire set of variables could cause unaffordable computation and communication overhead. To address this issue, we propose the first distributed algorithm whereby agents optimize and communicate only a portion of their local variables. The scheme hinges on successive convex approximation (SCA) to handle the nonconvexity of the objective function, coupled with a novel block-signal tracking scheme, aiming at locally estimating the average of the agents' gradients. Asymptotic convergence to stationary solutions of the nonconvex problem is established. Numerical results on a sparse regression problem show the effectiveness of the proposed algorithm and the impact of the block size on its practical convergence speed and communication cost.