Papers āŗ The Complexity of Dynamic Least-Squares Regression
The Complexity of Dynamic Least-Squares Regression
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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
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