Enhancing Convergence of Decentralized Gradient Tracking under the KL Property

We study decentralized multiagent optimization over networks, modeled as undirected graphs. The optimization problem consists of minimizing a nonconvex smooth function plus a convex extended-value function, which enforces constraints or extra structure on the solution (e.g., sparsity, low-rank). We further assume that the objective function satisfies the Kurdyka-Lojasiewicz (KL) property, with given exponent θ∈ [0,1). The KL property is satisfied by several (nonconvex) functions of practical interest, e.g., arising from machine learning applications; in the centralized setting, it permits to achieve strong convergence guarantees. Here we establish convergence of the same type for the notorious decentralized gradient-tracking-based algorithm SONATA. Specifically, (i) when θ∈ (0,1/2], the sequence generated by SONATA converges to a stationary solution of the problem at R-linear rate; (ii) when θ∈ (1/2,1), sublinear rate is certified; and finally (iii) when θ=0, the iterates will either converge in a finite number of steps or converges at R-linear rate. This matches the convergence behavior of centralized proximal-gradient algorithms except when θ=0. Numerical results validate our theoretical findings.