# The Complexity of Dynamic Least-Squares Regression

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 78 references that are in the map.
- First posted on arXiv 1 Jan 2022.

## Builds on (most cited first, 30 of 30)

- [Continual Lifelong Learning with Neural Networks: A Review](https://mlsanity.com/paper/1802.07569/) (2018)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds](https://mlsanity.com/paper/1905.05067/) (2019)
- [Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back](https://mlsanity.com/paper/1307.2205/) (2013)
- [Iterative Refinement for ℓp-norm Regression](https://mlsanity.com/paper/1901.06764/) (2019)
- [Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture](https://mlsanity.com/paper/1511.06773/) (2015)
- [Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication](https://mlsanity.com/paper/1711.04467/) (2017)
- [Faster Online Matrix-Vector Multiplication](https://mlsanity.com/paper/1605.01695/) (2016)
- [Algorithms and Hardness for Multidimensional Range Updates and Queries](https://mlsanity.com/paper/2101.02003/) (2021)
- [On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter](https://mlsanity.com/paper/1602.06705/) (2016)
- [Answering Conjunctive Queries under Updates](https://mlsanity.com/paper/1702.06370/) (2017)

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

- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Active Learning with Low-Rank Structure for Data Selection](https://mlsanity.com/paper/2606.16045/) (2026)
- [One-Step Curvature Probes Miss the Fitting Operator: Retained Capacity and Terminal Null-Space Correction for Continual Learning](https://mlsanity.com/paper/2610.03952/) (2026)

## Abstract (arXiv)

We settle the complexity of dynamic least-squares regression (LSR), where rows and labels (A(t), b(t)) can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an ε-approximate solution to min_x(t) | A(t) x(t) - b(t) |2 for all t∈ [T]. We prove sharp separations (d2-o(1) vs. ~ d) between the amortized update time of: (i) Fully vs. Partially dynamic 0.01-LSR; (ii) High vs. low-accuracy LSR in the partially-dynamic (insertion-only) setting. Our lower bounds follow from a gap-amplification reduction -- reminiscent of iterative refinement -- rom the exact version of the Online Matrix Vector Conjecture (OMv) [HKNS15], to constant approximate OMv over the reals, where the i-th online product Hv(i) only needs to be computed to 0.1-relative error. All previous fine-grained reductions from OMv to its approximate versions only show hardness for inverse polynomial approximation ε = n-ω(1) (additive or multiplicative) . This result is of independent interest in fine-grained complexity and for the investigation of the OMv Conjecture, which is still widely open.