Communication Lower Bounds for Distributed Convex Optimization: Partition Data on Features
Recently, there has been an increasing interest in designing distributed convex optimization algorithms under the setting where the data matrix is partitioned on features. Algorithms under this setting sometimes have many advantages over those under the setting where data is partitioned on samples, especially when the number of features is huge. Therefore, it is important to understand the inherent limitations of these optimization problems. In this paper, with certain restrictions on the communication allowed in the procedures, we develop tight lower bounds on communication rounds for a broad class of non-incremental algorithms under this setting. We also provide a lower bound on communication rounds for a class of (randomized) incremental algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression
Communication compression is an essential strategy for alleviating communication overhead by reducing the volume of information exchanged between computing nodes in large-scale distributed stochastic optimization. Althou…
Stochastic OptimizationThe Minimax Complexity of Distributed Optimization
In this thesis, I study the minimax oracle complexity of distributed stochastic optimization. First, I present the "graph oracle model", an extension of the classic oracle complexity framework that can be applied to stud…
Distributed OptimizationStochastic OptimizationDistributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds
We investigate distributed online convex optimization with compressed communication, where $n$ learners connected by a network collaboratively minimize a sequence of global loss functions using only local information and…
Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications
Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial i…
Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity
We study structured convex optimization problems, with additive objective $r:=p + q$, where $r$ is ($\mu$-strongly) convex, $q$ is $L_q$-smooth and convex, and $p$ is $L_p$-smooth, possibly nonconvex. For such a class of…
Distributed Optimization