# Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox

arXiv: https://arxiv.org/abs/1702.06269 · HTML: https://mlsanity.com/paper/1702.06269/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2017.

## Built on by (most cited first, 12 of 12)

- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Algorithmic Instabilities of Accelerated Gradient Descent](https://mlsanity.com/paper/2102.02167/) (2021)
- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Uniform Stability for First-Order Empirical Risk Minimization](https://mlsanity.com/paper/2207.08257/) (2022)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [PIM-Opt: Demystifying Distributed Optimization Algorithms on a Real-World Processing-In-Memory System](https://mlsanity.com/paper/2404.07164/) (2024)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [Communication-efficient Byzantine-robust distributed learning with statistical guarantee](https://mlsanity.com/paper/2103.00373/) (2021)

## Abstract (arXiv)

We present and analyze an approach for distributed stochastic optimization which is statistically optimal and achieves near-linear speedups (up to logarithmic factors). Our approach allows a communication-memory tradeoff, with either logarithmic communication but linear memory, or polynomial communication and a corresponding polynomial reduction in required memory. This communication-memory tradeoff is achieved through minibatch-prox iterations (minibatch passive-aggressive updates), where a subproblem on a minibatch is solved at each iteration. We provide a novel analysis for such a minibatch-prox procedure which achieves the statistical optimal rate regardless of minibatch size and smoothness, thus significantly improving on prior work.