Papers › The Complexity of Dynamic Least-Squares Regression

The Complexity of Dynamic Least-Squares Regression

1 Jan 2022arXiv:2201.00228archive 2025-07-28

Shunhua Jiang, Binghui Peng, Omri Weinstein

We settle the complexity of dynamic least-squares regression (LSR), where rows and labels (𝐀⁽ᵗ⁾, 𝐛⁽ᵗ⁾) can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an ϵ-approximate solution to min_(𝐱⁽ᵗ⁾) ‖ 𝐀⁽ᵗ⁾ 𝐱⁽ᵗ⁾ - 𝐛⁽ᵗ⁾ ‖₂ for all t∈[T]. We prove sharp separations (d²⁻ᵒ⁽¹⁾ 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 𝐇𝐯⁽ⁱ⁾ 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.

Code

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections