The Complexity of Dynamic Least-Squares Regression
summary
Settles the dynamic LSR complexity: an nd + d^3 · poly(1/ε) incremental algorithm (oblivious) that yields amortized O(d) per insertion using leverage-score sampling, a JL sketch for fast score estimates and Woodbury updates; adaptation to incremental but adaptive updates inflates the polynomial term (≈d^5). Conditional lower bounds from the OMv conjecture (via a gap‑amplification/iterative‑refinement reduction and matrix‑Chernoff arguments) prove sharp separations d^{2−o(1)} vs ~d and rule out o(d^2) for fully dynamic or high‑accuracy maintenance.
AI-written summary · about
chapters (9)
- 0:00Introduction to LSR
- 2:42Dynamic LSR settings
- 5:03Overview of complexity results
- 10:57Oblivious incremental updates
- 21:25Runtime and algorithmic steps
- 26:28Adaptive update challenges
- 37:09Adaptive upper bound proofs
- 42:36Lower bounds and complexity
- 56:47Summary and future work
related talks
43mResizable Sketches
18mMaximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)
27mWhat Does Dynamic Optimality Mean in External Memory?
41mNo stats, no problem: building feedback-driven optimizers for lakehouses
01h 05mIntroduction to Relational Algorithms
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
25mErasure-Resilient Sublinear-Time Graph Algorithms
47mSublinear Time Eigenvalue Approximation via Random Sampling