Guaranteeing Both Consensus and Optimality in Decentralized Nonconvex Optimization with Multiple Local Updates
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912693521219584 |
|---|---|
| author | Liu, Jie Wang, Zuang Wang, Yongqiang |
| author_facet | Liu, Jie Wang, Zuang Wang, Yongqiang |
| contents | Scalable decentralized optimization in large-scale systems hinges on efficient communication. A common way to reduce communication overhead is to perform multiple local updates between two communication rounds, as in federated learning. However, extending this strategy to fully decentralized settings poses fundamental challenges. Existing decentralized algorithms with multiple local updates guarantee accurate convergence only under strong convexity, limiting applicability to the nonconvex problems prevalent in machine learning. Moreover, many methods require exchanging and storing auxiliary variables, such as gradient-tracking vectors or correction terms, to ensure convergence under data heterogeneity, incurring high communication and memory costs. In this paper, we propose MILE, a fully decentralized algorithm that guarantees both consensus and optimality under multiple local updates in general nonconvex settings. This is achieved through a novel periodic-system-based formulation and a lifting-based analysis, which together yield a closed-form expression for the state evolution across local updates, a theoretical advance not achieved previously. This closed-form characterization allows us to establish, for the first time, guaranteed consensus and optimality in decentralized nonconvex optimization under multiple local updates, in contrast to prior results that only ensure optimality of the average state. We prove that MILE achieves an $O(1/T)$ convergence rate under both exact and stochastic gradients, while requiring only a single variable exchange per interacting agent pair, minimizing communication and memory costs. Numerical experiments on benchmark datasets confirm its effectiveness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_05242 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Guaranteeing Both Consensus and Optimality in Decentralized Nonconvex Optimization with Multiple Local Updates Liu, Jie Wang, Zuang Wang, Yongqiang Optimization and Control Scalable decentralized optimization in large-scale systems hinges on efficient communication. A common way to reduce communication overhead is to perform multiple local updates between two communication rounds, as in federated learning. However, extending this strategy to fully decentralized settings poses fundamental challenges. Existing decentralized algorithms with multiple local updates guarantee accurate convergence only under strong convexity, limiting applicability to the nonconvex problems prevalent in machine learning. Moreover, many methods require exchanging and storing auxiliary variables, such as gradient-tracking vectors or correction terms, to ensure convergence under data heterogeneity, incurring high communication and memory costs. In this paper, we propose MILE, a fully decentralized algorithm that guarantees both consensus and optimality under multiple local updates in general nonconvex settings. This is achieved through a novel periodic-system-based formulation and a lifting-based analysis, which together yield a closed-form expression for the state evolution across local updates, a theoretical advance not achieved previously. This closed-form characterization allows us to establish, for the first time, guaranteed consensus and optimality in decentralized nonconvex optimization under multiple local updates, in contrast to prior results that only ensure optimality of the average state. We prove that MILE achieves an $O(1/T)$ convergence rate under both exact and stochastic gradients, while requiring only a single variable exchange per interacting agent pair, minimizing communication and memory costs. Numerical experiments on benchmark datasets confirm its effectiveness. |
| title | Guaranteeing Both Consensus and Optimality in Decentralized Nonconvex Optimization with Multiple Local Updates |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.05242 |