我们研究了在差分隐私（DP）约束下的最小二乘线性回归问题，分别考虑批处理和持续观测两种场景。持续观测设置中，机制会不断接收 $n$ 条数据点 $(x_i, y_i)$（其中 $x_i \in \mathbb{R}^d$, $y_i \in \mathbb{R}$），并在每个时间步 $i$ 输出对最优参数的估计。虽然批处理下的差分隐私线性回归已有大量研究，但持续观测下仍缺乏针对无约束问题的有效方案，已有工作仅限于约束回归且更新复杂度随 $n$ 多项式增长。
本文提出 ContinualAdaSSP，这是首个在持续差分隐私框架下处理无约束线性回归的机制。其次优性差距为 $\sqrt{d}\,\operatorname{polylog}(n)$，空间需求 $O(d^2\log n)$，更新时长 $O(d^2\log n + d^{\omega})$（其中 $d^{\omega}$ 为矩阵乘法的指数）。
我们进一步给出线性回归的基本下界。针对盒约束最小二乘问题，证明了在 $(1, O(\frac{1}{n}))$‑DP 条件下的下界为 $\min\bigl(n, \frac{\sqrt{d}}{\log^{1.5} d}\bigr)$，在 $\epsilon$‑DP 条件下为 $\min\bigl(n, \frac{d}{\epsilon}\bigr)$。这些下界通过将指纹码问题（见 [Peter et al., 2024]）归约得到，揭示了该任务的内在难度。
实验在多个真实数据集上进行。结果表明，ContinualAdaSSP 在每个时间步的预测精度显著优于所有已知的差分隐私方案，包括在每一步重新运行批处理算法的基线方法。
点评