{"id":"arxiv/2605.07795","url":"https://arxiv.org/abs/2605.07795","tags":["math.OC"],"score":0,"title":"Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits","domain":"math.OC","source":"arxiv","authors":["Grigory Begunov","Alexander Tyurin"],"reviews":0,"subject":"math.OC","summary":"In centralized, distributed, and federated learning with stochastic gradients and $n$ workers, it was recently shown that it is infeasible to find an $\\varepsilon$-stationary point faster than $\\tildeΩ\\left(\\min\\left\\{\\frac{d κL Δ}{\\varepsilon} + \\frac{h L Δ}{\\varepsilon} + \\frac{h σ^2 L Δ}{n \\varepsilon^2},\\; \\frac{h σ^2 L Δ}{\\varepsilon^2} + \\frac{h L Δ}{\\varepsilon}\\right\\}\\right)$ 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) \\geq f^*$ for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-08","reactions":{}}