We investigate the classic least‑squares linear regression problem under differential privacy (DP) in both batch and continual‑observation settings. In the continual setting, a mechanism receives a stream of $n$ data points $(x_i, y_i)$ with $x_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$, and must output an estimate of the optimal parameters at every time step $i$. While DP linear regression has been extensively studied for batch processing, the continual‑observation scenario remains under‑explored; prior work only handles constrained regression and incurs update costs polynomial in $n$.
We introduce ContinualAdaSSP, the first mechanism that supports unconstrained linear regression under continual differential privacy. Its suboptimality gap scales as $\sqrt{d}\,\operatorname{polylog}(n)$, it uses $O(d^2\log n)$ space, and its update time is $O(d^2\log n + d^{\omega})$, where $d^{\omega}$ denotes the matrix‑multiplication exponent.
We also establish fundamental lower bounds for DP linear regression. For the box‑constrained least‑squares problem, we prove a lower bound of $\min\bigl(n, \frac{\sqrt{d}}{\log^{1.5} d}\bigr)$ under $(1, O(\frac{1}{n}))$‑DP, and $\min\bigl(n, \frac{d}{\epsilon}\bigr)$ under $\epsilon$‑DP. These bounds are derived via a reduction from a fingerprinting‑code problem (see Peter et al., 2024), providing new insight into the inherent hardness of this canonical task.
Empirical evaluation on real‑world datasets shows that ContinualAdaSSP consistently outperforms all existing DP mechanisms for this problem, including the naive approach of re‑running a batch algorithm at each time step.
Review