Communication Lower Bounds for Distributed Convex Optimization: Partition Data on Features

By Zihao Chen, Luo Luo, Zhihua Zhang. 2016

3 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some relevant references are Lee et al. (2014); Ma and Takáč (2015); Smith et al. (2016); Chen et al. (2016b); Fang and Klabjan (2018).”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, background): “Chen et al. (2017) established lower bounds for the round complexity when the data is partitioned on features which is different from the setting in our paper and Arjevani and Shamir (2015) where the data is partitioned on samples.”