Communication complexity of convex optimization

By John N. Tsitsiklis, Zhi-Quan Tom Luo. 1986

We consider a situation where each one of two processors has access to a different convex function fi, i = 1, 2, defined on a common bounded domain. The processors are to exchange a number of binary messages, according to some protocol, until they find a point in the domain at which f1+f2 is minimized, within some prespecified accuracy ¿. Our objective is to determine protocols under which the number of exchanged messages is minimized.

Subfields: Mathematical Optimization

How researchers see this paper

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

In Mathematical Optimization

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, background): “The idea of improving communication-efﬁciency of distributed optimization procedures via message-compression schemes goes a few decades back (Tsitsiklis and Luo, 1987), however, it has recently gained considerable attention due to the growing importance of distributed applications.”
Distributed Mean Estimation with Limited Communication (2016, neutral): “L G ] 2 5 Se p 20”
QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks (2016, background): “To circumvent this, one may quantize down to O (log 1 /(cid:15) ) bits, however, this only matches the upper bound given by [35], and is off from the optimal rate (which we achieve) by a logarithmic factor.”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “This problem has drawn significant attention from theoretical perspectives about its communication complexity [33, 43, 3].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “Perhaps the most closely-related paper is [22], which studied the communication complexity of distributed optimization, and showed that Ω(d log(1/ )) bits of communication are necessary between the machines, for d-dimensional convex problems.”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, background): “Study of communication in such case requires algebraic assumptions [4, 36].”
Optimality guarantees for distributed statistical estimation (2014, background): “For example, Tsitsiklis and Luo [29] provide lower bounds on the diﬃculty of distributed convex optimization, and Luo and Tsitsiklis [24] study limits on certain distributed algebraic computations.”
Distributed learning with compressed gradients (2018, background): “Although the initial results on communication complexity of convex optimization appeared over 30 years ago [16], the area has attracted strong renewed interest due to the veritable explosion of data and parameter sizes in deep learning.”
Harnessing smoothness to accelerate distributed optimization (2016, background): “Similar ideas of using history information trace back to [27], in which the previous gradient is used to narrow down the possible values of the current gradient to save communication complexity for a two-agent optimization problem.”
QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding (2016, background): “In particular, [40] studied two-processor convex minimization in the same model, provided a lower bound of Ω( n (log n + log(1 /(cid:15) ))) bits on the communication cost of n -dimensional convex problems, and proposed a non-stochastic algorithm for strongly convex problems, whose communication…”