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 study first-order optimization algorithms under the constraint that thedescent direction is quantized using a pre-specified budget of $R$-bits perdimension, where $R \in (0 ,\infty)$. We propose computationally efficientoptimization algorithms with convergence rates matching theinformation-theoretic performance lower bounds for: (i) Smooth andStrongly-Convex objectives with access to an Exact Gradient oracle, as well as(ii) General Convex and Non-Smooth objectives with access to a NoisySubgradient oracle. The crux of these algorithms is a polynomial complexitysource coding scheme that embeds a vector into a random subspace beforequantizing it. These embeddings are such that with high probability, theirprojection along any of the canonical directions of the transform space issmall. As a consequence, quantizing these embeddings followed by an inversetransform to the original space yields a source coding method with optimalcovering efficiency while utilizing just $R$-bits per dimension. Our algorithmsguarantee optimality for arbitrary values of the bit-budget $R$, which includesboth the sub-linear budget regime ($R < 1$), as well as the high-budget regime($R \geq 1$), while requiring $O\left(n^2\right)$ multiplications, where $n$ isthe dimension. We also propose an efficient relaxation of this coding schemeusing Hadamard subspaces that requires a near-linear time, i.e., $O\left(n \logn\right)$ additions.Furthermore, we show that the utility of our proposedembeddings can be extended to significantly improve the performance of gradientsparsification schemes. Numerical simulations validate our theoretical claims.Our implementations are available athttps://github.com/rajarshisaha95/DistOptConstrComm.

Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget