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

In this paper, we study the communication and (sub)gradient computation costsin distributed optimization and give a sharp complexity analysis for theproposed distributed accelerated gradient methods. We present two algorithmsbased on the framework of the accelerated penalty method with increasingpenalty parameters. Our first algorithm is for smooth distributed optimizationand it obtains the near optimal$O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_2(W))}}\log\frac{1}{\epsilon}\right)$communication complexity and the optimal$O\left(\sqrt{\frac{L}{\epsilon}}\right)$ gradient computation complexity for$L$-smooth convex problems, where $\sigma_2(W)$ denotes the second largestsingular value of the weight matrix $W$ associated to the network and$\epsilon$ is the target accuracy. When the problem is $\mu$-strongly convexand $L$-smooth, our algorithm has the near optimal$O\left(\sqrt{\frac{L}{\mu(1-\sigma_2(W))}}\log^2\frac{1}{\epsilon}\right)$complexity for communications and the optimal$O\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ complexity forgradient computations. Our communication complexities are only worse by afactor of $\left(\log\frac{1}{\epsilon}\right)$ than the lower bounds for thesmooth distributed optimization. %As far as we know, our method is the first toachieve both communication and gradient computation lower bounds up to an extralogarithm factor for smooth distributed optimization. Our second algorithm isdesigned for non-smooth distributed optimization and it achieves both theoptimal $O\left(\frac{1}{\epsilon\sqrt{1-\sigma_2(W)}}\right)$ communicationcomplexity and $O\left(\frac{1}{\epsilon^2}\right)$ subgradient computationcomplexity, which match the communication and subgradient computationcomplexity lower bounds for non-smooth distributed optimization.

Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters