cs.LGNov 5, 2026

On Differentially Private Mechanisms for Linear Regression

Authors: Bardiya Aryanfard, Monika Henzinger, Farhood Rostamkhani

Organizations: Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria

Abstract

We study the classic least-squares linear regression problem under differential privacy (DP) in the batch and the continual observation setting. In the latter setting, the mechanism receives a stream of nn data points (xi,yi)(x_i,y_i) (xi∈Rdx_i\in\mathbb{R}^d and yi∈Ry_i\in\mathbb{R}) and must output an estimate of the optimal parameters at each time step ii. Although differentially private linear regression has been extensively studied in the batch setting, the problem remains underexplored for the continual setting, with prior work being restricted to constrained linear regression and update time polynomial in nn. In this work, we introduce ContinualAdaSSP, the first mechanism for unconstrained linear regression under continual differential privacy. Our mechanism's suboptimality gap is proportional to dpolylog⁡(n)\sqrt{d}\operatorname{polylog}(n). It requires O(d2log⁡n)O(d^2\log{n}) space and O(d2log⁡n+dω)O(d^2\log{n}+d^ω) update time, where dd is the dimension of the input space. We also study fundamental limits of differentially private linear regression by showing the first lower bounds for the box-constrained least-squares linear regression problem. Our lower bounds are proportional to min⁡(n,dlog⁡1.5d)\min(n,\frac{\sqrt{d}}{\log^{1.5}d}) for (1,O(1n))(1,O(\frac{1}{n}))-DP, and min⁡(n,dε)\min(n,\frac{d}ε) for εε-DP, and are derived using a reduction from a fingerprinting code problem from [Peter et al., 2024], providing new insights into the inherent hardness of this canonical task. Our experimental evaluation on real-world datasets shows that the accuracy of our continual observation mechanism clearly outperforms any other known differentially private mechanism for this problem such as rerunning the batch algorithm at each time step.

Figures & tables

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Refined Differentially Private Linear Regression via Extension of a Free Lunch Result

    Apr 11, 2026Sasmita Harini S, Anshoo TandonDifferential PrivacyLinear Regression

  2. Private Learning with Public Feature Conditioning

    Jun 17, 2026Shuli Jiang, Walid Krichene, Nicolas MayorazDifferentially Private Stochastic Gradient DescentPrivacy-Preserving ML

  3. The Fast Mixing Mechanism for Differential Privacy

    May 28, 2026Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2Randomized SketchingDifferential Privacy