aiqbench analysis
This is optimization theory for networks of agents that train with stochastic gradients and perform several local steps between communication rounds, a setup common in decentralized learning. The main claims are a stepsize that doesn't shrink with network size and scales as 1/τ rather than 1/τ³, a first linear convergence guarantee in expectation for this setting, and half the communication of gradient-tracking methods. These are theoretical results, and the reported gains depend on the numerical experiments, so readers should check how those scale to real training workloads.
Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
arXiv:2610.41927v1 Announce Type: cross Abstract: Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
Abstract:Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2610.41927 [math.OC]
(or arXiv:2610.41927v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2610.41927 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 311 words
Related coverage
Near-Optimal Decentralized Stochastic Convex Optimization over Networks
arXiv · Jun 5, 2026
Group Distributionally Robust Optimization over Decentralized Networks
arXiv · Oct 22, 2026
Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds
arXiv · Jun 9, 2026
Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
arXiv · Oct 1, 2026