Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
Abstract
In centralized, distributed, and federated learning with stochastic gradients and n workers, it was recently shown that it is infeasible to find an ε-stationary point faster than Ω̃(min{(d κL Δ)/ε + (h L Δ)/ε + (h σ2 L Δ)/(n ε2), (h σ2 L Δ)/ε2 + (h L Δ)/ε}) seconds in both homogeneous and heterogeneous settings under standard assumptions: L-smoothness, σ2-bounded unbiased stochastic gradients, and lower boundedness of the function, i.e., f(x) ≥ f* for all x ∈ ℝd, where Δ= f(x0) − f*, h is the computation time, κ is the communication speed between the workers and the server, and d is the dimension of the iterates and gradients. This result is pessimistic since it does not allow a complexity in which both (d κL Δ)/ε and (h σ2 L Δ)/ε2 improve with n, even when using random sparsification techniques; moreover, this lower bound can be matched by either non-distributed SGD or vanilla Synchronous SGD, which reduces the impact of recent progress in the design of compression-based methods. In this work, we challenge this limitation and propose new compressed methods, Inkheart SGD and M4, and show that under an additional structural assumption, which is necessary due to the lower bound and which does not restrict the class of considered problems, we achieve new state-of-the-art time complexities that break this pessimistic barrier and allow scaling with the number of workers n.
Related
- Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices
- Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing
- A true single-level reformulation for pessimistic bilevel optimization
BibTeX
@misc{begunov2026scalable,
title = {{Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits}},
author = {Grigory Begunov and Alexander Tyurin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.07795},
eprint = {2605.07795},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.07795},
}
RIS
TY - UNPB
TI - Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
AU - Grigory Begunov
AU - Alexander Tyurin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2605.07795
UR - https://arxiv.org/abs/2605.07795
AB - In centralized, distributed, and federated learning with stochastic gradients and n workers, it was recently shown that it is infeasible to find an ε-stationary point faster than Ω̃(min{(d κL Δ)/ε + (h L Δ)/ε + (h σ^2 L Δ)/(n ε^2), (h σ^2 L Δ)/ε^2 + (h L Δ)/ε}) seconds in both homogeneous and heterogeneous settings under standard assumptions: L-smoothness, σ^2-bounded unbiased stochastic gradients, and lower boundedness of the function, i.e., f(x) ≥ f^* for all x ∈ ℝ^d, where Δ= f(x^0) − f^*, h is the computation time, κ is the communication speed between the workers and the server, and d is the dimension of the iterates and gradients. This result is pessimistic since it does not allow a complexity in which both (d κL Δ)/ε and (h σ^2 L Δ)/ε^2 improve with n, even when using random sparsification techniques; moreover, this lower bound can be matched by either non-distributed SGD or vanilla Synchronous SGD, which reduces the impact of recent progress in the design of compression-based methods. In this work, we challenge this limitation and propose new compressed methods, Inkheart SGD and M4, and show that under an additional structural assumption, which is necessary due to the lower bound and which does not restrict the class of considered problems, we achieve new state-of-the-art time complexities that break this pessimistic barrier and allow scaling with the number of workers n.
ER -