# Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2013.

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

- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [Memory-Sample Lower Bounds for Learning Parity with Noise](https://mlsanity.com/paper/2107.02320/) (2021)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Distributed Sparse Normal Means Estimation with Sublinear Communication](https://mlsanity.com/paper/2102.03060/) (2021)
- [Optimal high-dimensional and nonparametric distributed testing under communication constraints](https://mlsanity.com/paper/2202.00968/) (2022)
- [On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.17154/) (2022)
- [Distributed Nonparametric Estimation under Communication Constraints](https://mlsanity.com/paper/2204.10373/) (2022)
- [Lower Bounds on the Bayesian Risk via Information Measures](https://mlsanity.com/paper/2303.12497/) (2023)
- [Tight Time-Space Lower Bounds for Constant-Pass Learning](https://mlsanity.com/paper/2310.08070/) (2023)
- [Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?](https://mlsanity.com/paper/2607.02896/) (2026)
- [Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping](https://mlsanity.com/paper/2111.02949/) (2021)
- [Regret Lower Bounds in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2308.08046/) (2023)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Recovery Guarantees for Distributed-OMP](https://mlsanity.com/paper/2209.07230/) (2022)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)

## Abstract (arXiv)

Many machine learning approaches are characterized by information constraints on how they interact with the training data. These include memory and sequential access constraints (e.g. fast first-order methods to solve stochastic optimization problems); communication constraints (e.g. distributed learning); partial access to the underlying data (e.g. missing features and multi-armed bandits) and more. However, currently we have little understanding how such information constraints fundamentally affect our performance, independent of the learning problem semantics. For example, are there learning problems where any algorithm which has small memory footprint (or can use any bounded number of bits from each example, or has certain communication constraints) will perform worse than what is possible without such constraints? In this paper, we describe how a single set of results implies positive answers to the above, for several different settings.