<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>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/20046878 |
| Date | 10 June 2022 |
| Creators | Tejaskumar Pradipbhai Tamboli (12856589) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/LINEAR_CONVERGENCE_OF_DISTRIBUTED_GRADIENT_TRACKING_SCHEMES_UNDER_THE_KL_PROPERTY/20046878 |
Page generated in 0.0021 seconds