Abstract
Least-squares regression (LSR) is a fundamental optimization problem in machine learning and statistics. In many modern applications, data arrives dynamically, necessitating efficient updates to the solution. This paper establishes the computational complexity of dynamic LSR, revealing a sharp dichotomy between update types. We prove that maintaining a constant-approximate solution in a fully dynamic setting (supporting both insertions and deletions) requires nearly quadratic time ($\Omega(d^2)$) per update, assuming the Online Matrix-Vector (OMv) conjecture. Conversely, for the insertion-only (partially dynamic) setting, we present a novel algorithm that achieves near-linear time ($\tilde{O}(d)$) updates, even when facing adaptive adversaries. Our results provide both a theoretical lower bound and a practical, high-performance algorithm for streaming data applications.
Introduction
Least-squares regression (LSR) is ubiquitous in fields ranging from control theory to continual learning. Given a matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b \in \mathbb{R}^n$, the goal is to find $x$ that minimizes $\|Ax - b\|_2$. In dynamic environments, where rows are added or removed over time, recomputing the solution from scratch is computationally expensive.
The traditional approach for dynamic updates is the Kalman filter, which utilizes the Woodbury matrix identity to maintain an exact solution in $O(d^2)$ time per update. However, as the dimensionality $d$ grows, this quadratic cost becomes a significant bottleneck. This research investigates whether it is possible to break the $O(d^2)$ barrier by relaxing the requirement from an exact solution to an $\epsilon$-approximate one.
The Computational Dichotomy
The core contribution of this work is the discovery of a fundamental separation in complexity based on the nature of the updates:
- Fully Dynamic LSR: When the system must support both the insertion and deletion of data points, the problem is inherently difficult. We show that even a constant relative approximation (e.g., $\epsilon = 0.01$) cannot be maintained faster than $\Omega(d^{2-o(1)})$ time per update.
- Partially Dynamic LSR: In the insertion-only setting, the complexity drops significantly. We provide an algorithm that maintains an $\epsilon$-approximate solution in $\tilde{O}(d)$ amortized time.
Algorithmic Innovation for Insertion-Only Updates
Our approach for the partially dynamic setting builds upon the framework of online row sampling. The algorithm maintains a small, representative subset of rows sampled according to their online leverage scores.
Overcoming the $O(d^2)$ Bottleneck
Calculating exact leverage scores typically requires $O(d^2)$ time. To achieve near-linear complexity, we employ a Johnson-Lindenstrauss (JL) dimensionality reduction trick to compress the matrix, allowing for the estimation of leverage scores in $O(d)$ time.
Robustness Against Adaptive Adversaries
A significant challenge in randomized streaming algorithms is the presence of adaptive adversaries—entities that choose future inputs based on the algorithm's previous outputs. Standard sketching techniques often fail in this scenario because the outputs leak information about the algorithm's internal randomness. We solve this by "refreshing" the JL sketch every time a new row is sampled. To ensure this remains efficient, we utilize a refined analysis based on Freedman’s inequality with truncated martingales, which reduces the dependence on the matrix's condition number ($\kappa$) from $O(\kappa^2)$ to $O(\log \kappa)$.
Hardness of the Fully Dynamic Setting
To prove the $\Omega(d^2)$ lower bound for the fully dynamic case, we utilize fine-grained complexity reductions from the Online Matrix-Vector (OMv) Conjecture. This conjecture posits that no algorithm can compute a sequence of matrix-vector products significantly faster than the naive quadratic approach.
Because LSR involves approximate real-valued calculations while OMv is defined over Boolean math, we introduced an intermediate "online projection" problem. By applying a gap-amplification technique inspired by iterative refinement, we demonstrated that the hardness of OMv persists even for low-precision, constant-factor approximations of LSR.
Empirical Results
We validated our partially dynamic algorithm using both synthetic and real-world datasets. On the VirusShare dataset ($T=177,856$ points, $d=482$ features), our algorithm demonstrated significant performance gains:
- Efficiency: Our method completed the task in 17.5 seconds, compared to 45.3 seconds for the exact Kalman filter approach.
- Accuracy: The algorithm maintained a relative error of approximately 1.005, significantly outperforming uniform sampling and matching the accuracy of more expensive exact row sampling methods.
Conclusion
This research clarifies the complexity landscape of dynamic least-squares regression. We show that while deletions make the problem fundamentally hard, the insertion-only regime allows for highly efficient, near-linear time updates. Our proposed algorithm is not only theoretically robust against adaptive adversaries but also practically superior for high-dimensional streaming data tasks. Future work may extend these martingale analysis techniques to other importance sampling schemes in streaming literature.
Summary updated