Text

On the Divergence of Decentralized Nonconvex Optimization

In this work, we study a generic class of decentralized algorithms in which
agents jointly optimize the nonconvex objective function
, while only communicating with their neighbors. This class of problems has become popular in modeling many signal processing and decentralized machine learning applications, and efficient algorithms have been proposed for such a type of problem. However, most of the existing decentralized algorithms require that the local function gradients 's as well as the average function gradient are Lipschitz, that is, the local Lipschitz conditions (LLC) and global Lipschitz condition (GLC) are satisfied. In this work, we first demonstrate the importance of the above Lipschitzness assumptions on the state-of-the-art decentralized algorithms. First, by constructing a series of examples, we show that when the LLC on the local function gradient 's are not satisfied, a number of state-of-the-art decentralized algorithms diverge, even if the global Lipschitz condition (GLC) still holds. This observation brings out a fundamental theoretical issue of the existing decentralized algorithms---their convergence conditions are strictly stronger than centralized algorithms such as the gradient descent, which only requires the GLC. Our observation raises an important open question: How to design decentralized algorithms when the LLC, or even the GLC, is not satisfied? To address this question, we design two first-order algorithms, which are capable of computing stationary solutions of the original problem with neither the LLC nor the GLC condition. In particular, we show that the proposed algorithms converge sublinearly to a certain -stationary solution, where the precise rate depends on various algorithmic and problem parameters. In particular, if the local function 's are lower bounded th order polynomials, then the rate becomes for (where the notation hides some constants such as dependency on the network topology). Such a rate is tight for the special case of where each satisfies LLC. To our knowledge, this is the first attempt that studies decentralized nonconvex optimization problems with neither the LLC nor the GLC.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.4 October-December 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 2879-2908

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

DECENTRALIZED OPTIMIZATION
NONCONVEX PROBLEMS
LIPSCHITZ CONTINUOUS GRADIENT

Info Detail Spesifik

https://doi.org/10.1137/20M1353149

Pernyataan Tanggungjawab

Mingyi Hong, Siliang Zeng, Junyu Zhang, Haoran Sun

Versi lain/terkait

Lampiran Berkas

Komentar