English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a standard distributed optimisation setting where $N$ machines,each holding a $d$-dimensional function $f_i$, aim to jointly minimise the sumof the functions $\sum_{i = 1}^N f_i (x)$. This problem arises naturally inlarge-scale distributed optimisation, where a standard solution is to applyvariants of (stochastic) gradient descent. We focus on the communicationcomplexity of this problem: our main result provides the first fullyunconditional bounds on total number of bits which need to be sent and receivedby the $N$ machines to solve this problem under point-to-point communication,within a given error-tolerance. Specifically, we show that $\Omega( Nd \log d /N\varepsilon)$ total bits need to be communicated between the machines to findan additive $\epsilon$-approximation to the minimum of $\sum_{i = 1}^N f_i(x)$. The result holds for both deterministic and randomised algorithms, and,importantly, requires no assumptions on the algorithm structure. The lowerbound is tight under certain restrictions on parameter values, and is matchedwithin constant factors for quadratic objectives by a new variant of quantisedgradient descent, which we describe and analyse. Our results bring over toolsfrom communication complexity to distributed optimisation, which has potentialfor further applications.

Towards Tight Communication Lower Bounds for Distributed Optimisation