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

Sasmita Harini S; Anshoo Tandon

cs.ITApr 11, 2026

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

Authors: Sasmita Harini S, Anshoo Tandon

Organizations: Indian Institute of Science, Bangalore, India · CDPG, Indian Institute of Science, Bangalore, India

Abstract

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.

Figures & tables

Statistic	DP-SS $\mathrm{Var}(\tilde{\cdot})$	DP-RSS $\mathrm{Var}(\hat{\cdot})$	Improv
$n$	$\dfrac{16}{\varepsilon^{2}}$	$\dfrac{12}{\varepsilon^{2}}$	$1.33\times$
$S_{x^{2}}$	$\dfrac{32}{\varepsilon^{2}}$	$\dfrac{20}{3\varepsilon^{2}}$	$4.80\times$
$S_{xy}$	$\dfrac{32}{\varepsilon^{2}}$	$\dfrac{20}{3\varepsilon^{2}}$	$4.80\times$
$S_{x}$	$\dfrac{32}{\varepsilon^{2}}$	$\dfrac{32}{3\varepsilon^{2}}$	$3.00\times$
$S_{y}$	$\dfrac{32}{\varepsilon^{2}}$	$\dfrac{32}{3\varepsilon^{2}}$	$3.00\times$

Table 1: Comparison of variances: DP-RSS vs. DP-SS

	$n$	$\alpha$	$\beta$	$\sigma$
Setup 1	5,000	$-0.7$	$0.8$	$0.05$
Setup 2	10,000	$0.5$	$0.2$	$0.1$

Table 2: Parameters for synthetic data generation.

Panel of Figure 1 — Figure 1: Comparison of L1 and L2 errors versus privacy budget $\varepsilon$ for different DP regression methods. The sub-plots on the left (resp. right) correspond to Setup $1$ (resp. Setup $2$ ).

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 276 papers

Private Learning with Public Feature Conditioning
Jun 17, 2026Shuli Jiang, Walid Krichene, Nicolas MayorazDifferentially Private Stochastic Gradient Descent Privacy-Preserving ML
1AWS Agentic AI · 2Microsoft · 3Google Research
On the Limits of Sparse Linear Model with Shuffled Differential Privacy
Oct 23, 2026Yan Zhang, Jiong Tuo, Meng Ding +2High-Dimensional Linear Regression Differential Privacy
Provable Responsible AI and Data Analytics Lab · Nankai University · King Abdullah University of Science and Technology (KAUST) +3
Certification-Based Differentially Private Learning
Sep 30, 2026Mihnea Ghitu, Matthew WickerAbstract Interpretation Privacy-Preserving ML
Department of Computing Imperial College London London, United Kingdom

Jun 17, 2026J/K move · Enter open · S save

Private Learning with Public Feature Conditioning

Shuli Jiang, Walid Krichene, Nicolas Mayoraz

1AWS Agentic AI · 2Microsoft · 3Google Research

Differentially Private Stochastic Gradient Descent Privacy-Preserving ML Differential Privacy

Open paper AskPDF arXiv

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.

Abstract

Differential Privacy

Explore similar work

Private Learning with Public Feature Conditioning

On the Limits of Sparse Linear Model with Shuffled Differential Privacy

Certification-Based Differentially Private Learning