首个针对非光滑分布式优化的下行通信压缩理论，实现最优收敛速度。
MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes
- 设计自适应步长的MARINA-P算法，优化服务器到工作节点的通信效率。
- 证明在非光滑凸设置下达到最优O(1/√T)收敛率，通信复杂度与经典次梯度法相当。
- 首次建立下行压缩下的理论保证，适合资源受限的联邦学习场景。
非光滑、通信高效的联邦优化对众多机器学习应用至关重要，但其理论研究仍不充分。现有工作多集中于光滑凸与非凸情形，对非光滑凸设置缺乏深入理解。此外，多数研究忽视了服务器到工作节点的通信（下行链路），仅关注工作节点到服务器的通信（上行链路）。本文考虑上行开销可忽略的场景，聚焦通过改进EF21-P和MARINA-P等方法来优化下行通信。将EF21-P的非光滑凸理论从单机扩展至分布式设置，并将MARINA-P推广至非光滑凸设置。对两种算法均证明了最优的O(1/√T)收敛速率，并建立了匹配经典次梯度方法的通信复杂度边界。在恒定、递减及自适应（Polyak型）步长下提供理论保证。实验表明，采用相关压缩器的MARINA-P在平滑非凸与非光滑凸设置中均优于其他方法。本工作首次为带有服务器到工作节点压缩的分布式非光滑优化提供理论结果，并涵盖多种步长策略的全面分析。
原文摘要 · Abstract (English)
Non-smooth communication-efficient federated optimization is crucial for many machine learning applications, yet remains largely unexplored theoretically. Recent advancements have primarily focused on smooth convex and non-convex regimes, leaving a significant gap in understanding the non-smooth convex setting. Additionally, existing literature often overlooks efficient server-to-worker communication (downlink), focusing primarily on worker-to-server communication (uplink). We consider a setup where uplink costs are negligible and focus on optimizing downlink communication by improving state-of-the-art schemes like EF21-P (arXiv:2209.15218) and MARINA-P (arXiv:2402.06412) in the non-smooth convex setting. We extend the non-smooth convex theory of EF21-P [Anonymous, 2024], originally developed for single-node scenarios, to the distributed setting, and extend MARINA-P to the non-smooth convex setting. For both algorithms, we prove an optimal $O(1/\sqrt{T})$ convergence rate and establish communication complexity bounds matching classical subgradient methods. We provide theoretical guarantees under constant, decreasing, and adaptive (Polyak-type) stepsizes. Our experiments demonstrate that MARINA-P with correlated compressors outperforms other methods in both smooth non-convex and non-smooth convex settings. This work presents the first theoretical results for distributed non-smooth optimization with server-to-worker compression, along with comprehensive analysis for various stepsize schemes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。