Return to search

LINEAR CONVERGENCE OF DISTRIBUTED GRADIENT TRACKING SCHEMES UNDER THE KL PROPERTY

<p>We study decentralized multiagent optimization over networks modeled as undirected</p>
<p>graphs. The optimization problem consists of minimizing a (non convex) smooth function</p>
<p>plus a convex extended-value function, which enforces constraints or extra structure on the</p>
<p>solution (e.g., sparsity, low-rank). We further assume that the objective function satisfies the</p>
<p>Kurdyka- Lojasiewicz (KL) property, with exponent in [0, 1). The KL property is satisfied</p>
<p>by several (non convex) functions of practical interest, e.g., arising from machine learning</p>
<p>applications; in the centralized setting, it permits to achieve strong convergence guarantees.</p>
<p>Here we establish a first convergence result of the same type for distributed algorithms,</p>
<p>specifically the distributed gradient-tracking based algorithm SONATA, first proposed in</p>
<p>[ 1 ]. When exponent is in (0, 1/2], the sequence generated by SONATA is proved to converge to a</p>
<p>stationary solution of the problem at an R-linear rate whereas sublinear rate is certified</p>
<p>when KL exponent is in (1/2, 1). This matches the convergence behaviour of centralized proximal-gradient</p>
<p>algorithms. Numerical results validate our theoretical findings.</p>

  1. 10.25394/pgs.20046878.v1
Identiferoai:union.ndltd.org:purdue.edu/oai:figshare.com:article/20046878
Date10 June 2022
CreatorsTejaskumar Pradipbhai Tamboli (12856589)
Source SetsPurdue University
Detected LanguageEnglish
TypeText, Thesis
RightsCC BY 4.0
Relationhttps://figshare.com/articles/thesis/LINEAR_CONVERGENCE_OF_DISTRIBUTED_GRADIENT_TRACKING_SCHEMES_UNDER_THE_KL_PROPERTY/20046878

Page generated in 0.002 seconds