Communication-Efficient Projection-Free Algorithm for Distributed Optimization
This work addresses communication efficiency in distributed optimization, which is crucial for large-scale machine learning applications, representing an incremental improvement over existing distributed Frank-Wolfe algorithms.
The paper tackles the problem of distributed optimization by proposing a projection-free algorithm called DCGS, which achieves the same communication complexity as state-of-the-art methods under more realistic assumptions and reduces linear oracle complexity to nearly match communication complexity for polyhedral sets, with experiments showing significant performance improvements in Lasso and matrix completion tasks.
Distributed optimization has gained a surge of interest in recent years. In this paper we propose a distributed projection free algorithm named Distributed Conditional Gradient Sliding(DCGS). Compared to the state-of-the-art distributed Frank-Wolfe algorithm, our algorithm attains the same communication complexity under much more realistic assumptions. In contrast to the consensus based algorithm, DCGS is based on the primal-dual algorithm, yielding a modular analysis that can be exploited to improve linear oracle complexity whenever centralized Frank-Wolfe can be improved. We demonstrate this advantage and show that the linear oracle complexity can be reduced to almost the same order of magnitude as the communication complexity, when the feasible set is polyhedral. Finally we present experimental results on Lasso and matrix completion, demonstrating significant performance improvement compared to the existing distributed Frank-Wolfe algorithm.