提出在KL条件下加速去中心化优化算法的收敛性分析。
Enhancing Convergence of Decentralized Gradient Tracking under the KL Property
- 基于KL性质分析去中心化梯度追踪算法SONATA的收敛机制
- 不同θ值下实现R线性或次线性收敛速率
- 适用于非凸优化场景，适合分布式学习研究者
研究网络上的去中心化多智能体优化问题，目标函数为非凸光滑函数加凸扩展值函数，用于施加约束或结构（如稀疏性、低秩）。假设目标函数满足Kurdyka-Łojasiewicz (KL) 性质，指数θ∈[0,1)。该性质在机器学习中常见，能保证集中式优化的强收敛性。本文证明，去中心化梯度追踪算法SONATA在同样条件下也具备类似收敛行为：当θ∈(0,1/2]时，序列以R线性速率收敛到驻点；当θ∈(1/2,1)时，收敛率为次线性；当θ=0时，迭代要么在有限步内收敛，要么以R线性速率收敛。结果与集中式近端梯度算法一致，仅在θ=0时有差异。数值实验验证了理论发现。
原文摘要 · Abstract (English)
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-Łojasiewicz (KL) property, with given exponent $θ\in [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, $\textbf{(i)}$ when $θ\in (0,1/2]$, the sequence generated by SONATA converges to a stationary solution of the problem at R-linear rate;$ \textbf{(ii)} $when $θ\in (1/2,1)$, sublinear rate is certified; and finally $\textbf{(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。