SCIENCE@home

Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms

Haoran Sun,Mingyi Hong

Published 2018 in IEEE Transactions on Signal Processing

ABSTRACT

We consider a class of popular distributed non-convex optimization problems, in which agents connected by a network <inline-formula><tex-math notation="LaTeX">$\mathcal {G}$</tex-math></inline-formula> collectively optimize a sum of smooth (possibly non-convex) local objective functions. We address the following question: if the agents can only access the gradients of local functions, what are the <italic>fastest</italic> rates that any distributed algorithms can achieve, and how to achieve those rates. First, we show that there exist difficult problem instances, such that it takes a class of distributed first-order methods at least <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(1/\sqrt{\xi ({ \mathcal {G} })} \times \bar{L} /{\epsilon })$</tex-math></inline-formula> communication rounds to achieve certain <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-solution [where <inline-formula><tex-math notation="LaTeX">$\xi ({ \mathcal {G} })$</tex-math></inline-formula> denotes the spectral gap of the graph Laplacian matrix, and <inline-formula><tex-math notation="LaTeX">$\bar{L}$</tex-math></inline-formula> is some Lipschitz constant]. Second, we propose (near) optimal methods whose rates match the developed lower rate bound (up to a ploylog factor). The key in the algorithm design is to properly embed the classical polynomial filtering techniques into modern first-order algorithms. To the best of our knowledge, this is the first time that lower rate bounds and optimal methods have been developed for distributed non-convex optimization problems.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-68 of 68 references · Page 1 of 1

CITED BY

Showing 1-54 of 54 citing papers · Page 1 of 1