# On Differentially Private Mechanisms for Linear Regression

DevFeed: [On Differentially Private Mechanisms for Linear Regression](<https://devfeed.tech/articles/on-differentially-private-mechanisms-for-linear-regression-122786.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.08737>)

Author: Bardiya Aryanfard, Monika Henzinger, Farhood Rostamkhani

Published: 2026-11-09T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [linear-regression](<https://devfeed.tech/topics/linear-regression.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [batch](<https://devfeed.tech/tags/batch.md>), [box](<https://devfeed.tech/tags/box.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [differential-privacy](<https://devfeed.tech/tags/differential-privacy.md>), [linear-regression](<https://devfeed.tech/tags/linear-regression.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>)

## AI overview

ContinualAdaSSP addresses unconstrained least-squares regression under continual differential privacy, producing parameter estimates at each step of a data stream. The abstract reports a suboptimality gap proportional to √d-polylog(n), space O(d² log n), and update time O(d² log n + d^ω). The paper also gives the first lower bounds for box-constrained least-squares regression: proportional to min(n, √d/log^1.5 d) for (1, O(1/n))-DP and min(n, d/ε) for ε-DP, derived via a fingerprinting-code reduction. Experiments on real-world datasets reportedly show higher accuracy than other known continual mechanisms, including rerunning a batch algorithm at each time step.

## Source excerpt

arXiv:2611.08737v1 Announce Type: cross 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 $n$ data points $(x_i,y_i)$ ($x_i\in\mathbb{R}^d$ and $y_i\in\mathbb{R}$) and must output an estimate of the optimal parameters at each time step $i$. 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 $n$. 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 $\sqrt{d}\operatorname{polylog}(n)$. It requires $O(d^2\log{n})$ space and $O(d^2\log{n}+d^{\omega})$ update time, where $d$ 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,\frac{\sqrt{d}}{\log^{1.5}d})$ for $(1,O(\frac{1}{n}))$-DP, and $\min(n,\frac{d}{\epsilon})$ for $\epsilon$-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.