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

Apr 11, 2026

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

As data-privacy regulations tighten and statistical models are increasingly deployed on sensitive human-sourced data, privacy-preserving linear regression has become a critical necessity. For the add-remove DP model, Kulesza et al. (2024) and Fitzsimons et al. (2024) have independently shown that the size of the dataset -- an important statistic for linear regression -- can be privately estimated for "free", via a simplex transformation of bounded variables and private sum queries on the transformed variables. In this work, we extend this free lunch result via carefully crafted multidimensional simplex transformations to variables and functions that are bounded in the interval [0,1]. We show that these transformations can be applied to refine the estimates of sufficient statistics needed for private simple linear regression based on ordinary least squares. We provide both analytical and numerical results to demonstrate the superiority of our approach. Our proposed transformations have general applicability and can be readily adapted for differentially private polynomial regression.
Jun 17, 2026

Private Learning with Public Feature Conditioning

We study differentially private (DP) regression in settings where each data sample includes public, non-sensitive features -- common in applications such as recommendation and advertising systems. While such label-DP or semi-sensitive-feature settings have been primarily explored in the context of classification, effective approaches for regression remain underexplored. We introduce Cond-DP, a conditioned variant of DPSGD that leverages the structure of public feature matrices to improve optimization under privacy constraints. Motivated by the observation that these public features often exhibit rapidly decaying spectra, Cond-DP incorporates a data-driven conditioning matrix to reshape the optimization landscape and accelerate convergence. We provide convergence guarantees for convex, strongly convex, and non-convex settings, and recover standard DPSGD as a special case when the conditioning matrix is the identity. We show how to construct an effective conditioning matrix for Cond-DP directly from public features, enabling provably faster convergence than DPSGD in private linear regression without incurring additional privacy cost. Empirically, Cond-DP with this conditioning matrix consistently outperforms state-of-the-art baselines across a wide range of datasets and model architectures under label DP, demonstrating strong and robust performance in practice.
May 28, 2026

The Fast Mixing Mechanism for Differential Privacy

Randomized sketching is a central tool for compressing large-scale optimization problems while preserving accuracy. In particular, sketches that are based on structured matrices, such as the Hadamard matrix, can be applied efficiently and often yield solutions that approximate those of the original problem at much lower computational cost. In differential privacy (DP), Gaussian sketching has been used to solve DP linear regression, beginning with \citet{sheffet2017differentially, sheffet2019old} and later refined by \citet{lev2025gaussianmix, lev2026near}. However, although these methods achieve strong utility guarantees, they usually do not improve runtime over classical DP approaches. In this work, we introduce a new DP sketching mechanism based on fast transforms, which, in certain cases, matches the runtime of classical fast sketching methods. We prove state-of-the-art privacy guarantees for this mechanism and show that, in favorable regimes, they match those of the Gaussian sketch up to a constant factor. As an application, we combine this mechanism with recent sketch-based methods for DP linear regression to obtain a new algorithm with strong utility and improved runtime. We establish privacy and accuracy guarantees for this algorithm, yielding, to the best of our knowledge, the first fast method for DP ordinary least squares.