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

Anshoo Tandon; Sasmita Harini S

arxiv: 2604.11820 · v1 · submitted 2026-04-11 · 💻 cs.IT · cs.LG· math.IT

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

Sasmita Harini S , Anshoo Tandon This is my paper

Pith reviewed 2026-05-10 16:31 UTC · model grok-4.3

classification 💻 cs.IT cs.LGmath.IT

keywords differential privacylinear regressionsimplex transformationsufficient statisticsordinary least squaresfree lunch resultpolynomial regressionadd-remove model

0 comments

The pith

Multidimensional simplex transformations refine private estimates of linear regression statistics without added privacy cost.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper extends an existing free lunch result in differential privacy by creating multidimensional simplex transformations that apply to variables and functions bounded in the interval from zero to one. These transformations let private sum queries recover more accurate values for the sufficient statistics that ordinary least squares linear regression needs, such as dataset size. Analytical bounds and numerical experiments show the refined estimates produce better regression accuracy than prior approaches while keeping the same privacy guarantees, and the same technique extends to polynomial regression.

Core claim

By applying carefully crafted multidimensional simplex transformations to variables and functions bounded in [0,1], the estimates of sufficient statistics needed for differentially private simple linear regression based on ordinary least squares can be refined, extending the free lunch result of prior work while preserving differential privacy guarantees.

What carries the argument

The multidimensional simplex transformation of [0,1]-bounded variables and functions, which converts private sum queries into more accurate recoveries of the statistics required for ordinary least squares without new error sources.

If this is right

Private estimates of dataset size and other ordinary least squares statistics become more accurate under the same privacy budget.
The approach directly improves the utility of differentially private simple linear regression models.
The same transformations apply to differentially private polynomial regression with no change in the privacy analysis.
General bounded-variable statistical tasks can adopt the transformations to reduce utility loss from privacy mechanisms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Normalized real-world data could see reduced accuracy loss in private regression pipelines when these transformations are applied after scaling.
Similar multidimensional transformations might extend the free lunch benefit to other summary statistics used in private machine learning beyond linear models.
Empirical tests on synthetic data with known ground-truth statistics would quantify the exact accuracy gain across different privacy budgets.

Load-bearing premise

The transformations preserve both the differential privacy guarantees and the ability to recover accurate sufficient statistics for ordinary least squares without introducing offsetting errors.

What would settle it

Running the method and a standard private-sum baseline on the same bounded dataset and finding that the refined estimates produce higher error in the recovered regression coefficients than the baseline would falsify the claimed refinement.

Figures

Figures reproduced from arXiv: 2604.11820 by Anshoo Tandon, Sasmita Harini S.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper extends the recent simplex free-lunch trick to multiple dimensions so you can get tighter private estimates of the sums and products for simple OLS regression on [0,1]-bounded data.

read the letter

The main point is that the authors take the 2024 simplex transformations for privately estimating dataset size and generalize them to several dimensions. This lets you refine the full set of sufficient statistics (sums, cross-products, and n) for ordinary least squares while staying inside the add-remove DP model and without paying extra privacy budget. They supply both an analytical argument that the maps are invertible and preserve the privacy guarantees, plus numerical comparisons that show lower error than plain noisy sums. The claim that the same idea carries over to polynomial regression is a reasonable next step they flag but do not fully develop here. That is the concrete new piece: the multidimensional construction itself, not a wholesale new mechanism. The work sits squarely on top of the two cited papers and does not pretend otherwise, which keeps the contribution proportionate. The boundedness assumption is stated up front and is load-bearing; if your data sits outside [0,1] you have to scale it first, and any scaling step needs its own privacy accounting. The numerical section would be stronger with more detail on the range of epsilon values, the synthetic versus real data splits, and direct head-to-head tables against the original one-dimensional method. Still, nothing in the construction looks circular or self-referential, and the invertibility argument appears internally consistent once the bounds are granted. This is the sort of targeted refinement that people who actually implement private linear models will want to check. It is worth sending to referees so they can verify the derivations and stress-test the numerics on their own data. I would put it on a reading-group list for a privacy or statistical estimation session.

Referee Report

1 major / 3 minor

Summary. The paper extends the free-lunch simplex transformation result of Kulesza et al. (2024) and Fitzsimons et al. (2024) for privately estimating dataset size under add-remove DP. It introduces multidimensional simplex transformations applicable to variables and functions bounded in [0,1], and applies them to refine recovery of OLS sufficient statistics (sums, products, and n) for simple linear regression. Analytical derivations and numerical experiments are claimed to demonstrate superiority over prior approaches, with the transformations asserted to preserve DP guarantees and exact recoverability; general applicability to polynomial regression is also suggested.

Significance. If the central construction holds, the work offers a meaningful refinement to the utility of differentially private linear regression by improving estimation of key statistics at no extra privacy cost. The generalization from scalar to multidimensional transformations over [0,1] intervals broadens the free-lunch technique, and the dual analytical/numerical support plus suggested extension to polynomial regression add to its potential impact in privacy-preserving statistics and ML.

major comments (1)

The central claim that the multidimensional transformations recover the original sufficient statistics (e.g., sums and cross-products) exactly, without introducing new error sources that could offset the refinement, is load-bearing. Explicit invertibility of the maps and a bound showing that any post-transformation noise does not increase overall error relative to the baseline must be shown in the main technical section describing the transformations.

minor comments (3)

Abstract: the claim of 'analytical and numerical superiority' would benefit from a one-sentence indication of the metric (e.g., reduced variance in the recovered slope or intercept) to orient readers.
The boundedness assumption to [0,1] is stated but the practical preprocessing (scaling) and its effect on the final regression coefficients should be addressed explicitly, even if only as a remark.
Ensure the bibliography contains complete entries for the two 2024 works cited as the foundation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, positive assessment of its potential impact, and recommendation for minor revision. We address the single major comment below and have revised the manuscript accordingly to strengthen the presentation of our central technical claims.

read point-by-point responses

Referee: The central claim that the multidimensional transformations recover the original sufficient statistics (e.g., sums and cross-products) exactly, without introducing new error sources that could offset the refinement, is load-bearing. Explicit invertibility of the maps and a bound showing that any post-transformation noise does not increase overall error relative to the baseline must be shown in the main technical section describing the transformations.

Authors: We agree that explicit invertibility and an error bound are essential to substantiate the central claim. While the original manuscript derives the transformations and states exact recoverability in Section 3 with supporting analysis in the appendix, we acknowledge that a self-contained proof and bound were not placed in the primary technical exposition. In the revision we have added a new subsection (3.2) that (i) proves bijectivity of the multidimensional simplex map on [0,1]^d by exhibiting the explicit inverse, and (ii) states and proves a lemma bounding the additional Laplace noise variance after transformation. The lemma shows that the mean-squared error of the recovered sufficient statistics is at most that of the baseline scalar free-lunch method for identical privacy parameters, because the transformation reduces query sensitivity without increasing the number of noisy releases. We have also added a short numerical check confirming the bound holds in the reported experiments. These changes are confined to the main body and do not alter any results or claims. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper extends the externally published free-lunch simplex result from Kulesza et al. (2024) and Fitzsimons et al. (2024) by introducing new multidimensional transformations over [0,1]-bounded variables. These transformations are explicitly defined and shown to preserve DP and enable refined recovery of OLS sufficient statistics (sums, products, n) under add-remove DP. No equation reduces a claimed prediction or statistic to a fitted parameter defined by the authors themselves, no load-bearing premise rests on self-citation, and no uniqueness or ansatz is smuggled via overlapping-author citations. The central argument is self-contained once boundedness and map invertibility are granted as explicit assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Ledger populated from abstract statements only; full paper would likely add more technical assumptions on privacy composition and transformation invertibility.

axioms (2)

domain assumption Input variables and functions are bounded in [0,1]
Explicitly stated as the setting for the new transformations.
domain assumption Simplex transformations preserve differential privacy and allow recovery of sufficient statistics
Core premise inherited from the cited free-lunch results and extended here.

pith-pipeline@v0.9.0 · 5466 in / 1529 out tokens · 61870 ms · 2026-05-10T16:31:55.077105+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Deep learning with differential privacy

Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 308–318,

work page 2016
[2]

Alabi, A

D. Alabi, A. McMillan, J. Sarathy, A. Smith, and S. Vadhan. Differentially private simple linear regression. Proceedings on Privacy Enhancing Technologies (PoPETs), 2022(2):184–204,

work page 2022
[3]

K. Amin, M. Joseph, M. Ribero, and S. Vassilvitskii. Easy differentially private linear regression. In International Conference on Learning Representations (ICLR 2023),

work page 2023
[4]

Differential privacy and robust statistics

Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. InProceedings of the ACM Symposium on Theory of Computing, STOC 2009,

work page 2009
[5]

URLhttps://openreview.net/forum?id= gtCfDKm9ME. J. Fitzsimons, J. Honaker, M. Shoemate, and V. Singhal. Private means and the curious incident of the free lunch.arXiv preprint arXiv:2408.10438,

work page arXiv
[6]

A bias-variance-privacy trilemma for statistical estimation

G. Kamath, A. Mouzakis, M. Regehr, V. Singhal, T. Steinke, and J. Ullman. A bias-variance-privacy trilemma for statistical estimation.arXiv preprint arXiv:2301.13334,

work page arXiv
[7]

Kulesza, A

14 Accepted at the SeQureDB Workshop at ACM SIGMOD 2026 and TPDP Workshop 2026 A. Kulesza, A. T. Suresh, and Y. Wang. Mean estimation in the add-remove model of differential privacy. InProceedings of the 41st International Conference on Machine Learning (ICML),

work page 2026
[8]

Differentially private linear re- gression and synthetic data generation with statistical guarantees.arXiv preprint arXiv:2510.16974v2,

Shurong Lin, Aleksandra Slavkovic, and Deekshith Reddy Bhoomireddy. Differentially private linear re- gression and synthetic data generation with statistical guarantees.arXiv preprint arXiv:2510.16974v2,

work page arXiv
[9]

Revisiting differentially private linear regression: optimal and adaptive prediction & esti- mation in unbounded domain

Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & esti- mation in unbounded domain. InProceedings of the Conference on Uncertainty in Artificial Intelligence (UAI 2018),

work page 2018
[10]

In practice, however, the raw data may only be known to lie in a general rectangle [x min, xmax]×[y min, ymax]

A DP-RSS for General Bounded Data Algorithm 3 and the theoretical results in Section 4 are stated for data satisfyingx i, yi ∈[0,1]. In practice, however, the raw data may only be known to lie in a general rectangle [x min, xmax]×[y min, ymax]. We now describe how DP-RSS adapts to this setting via alinear normalisation, which reduces the general case exac...

work page 2026
[11]

Since the noise scale isb= ∆ 1(f)/ε1 = 1/ε1, the Laplace mechanism theorem guaranteesε 1-differential privacy

whereZ 11, Z12, Z13 iid ∼Lap(1/ε 1). Since the noise scale isb= ∆ 1(f)/ε1 = 1/ε1, the Laplace mechanism theorem guaranteesε 1-differential privacy. 16 Accepted at the SeQureDB Workshop at ACM SIGMOD 2026 and TPDP Workshop 2026 Formal verification.For any neighboring datasetsD, D ′ and any measurable setS⊆R 3: Pr[( ˜Sx2 , ˜Sx−x2 , ˜S1−x)∈S|D] Pr[( ˜Sx2 , ˜...

work page 2026
[12]

Thereforew ∗ 2 = σ2 1 σ2 1+σ2 2

Taking the derivative and setting to zero: dV dw1 = 2w1(σ2 1 +σ 2 2)−2σ 2 2 = 0 =⇒w ∗ 1 = σ2 2 σ2 1+σ2 2 . Thereforew ∗ 2 = σ2 1 σ2 1+σ2 2 . Since d2V dw2 1 = 2(σ2 1 +σ 2 2)>0, this is a minimum. Substituting the optimal weights: Var(ˆθ∗) = σ2 2 σ2 1 +σ 2 2 2 σ2 1 + σ2 1 σ2 1 +σ 2 2 2 σ2 2 = σ2 1σ2 2 σ2 1 +σ 2 2 . 17 Accepted at the SeQureDB Workshop at A...

work page 2026
[13]

Part 3: Independence

Variance:All noise variables have variance 8/ε 2: Var(ˆS(2) x2 ) = 5· 8 ε2 = 40 ε2 . Part 3: Independence. ˆS(1) x2 depends on{Z 11}and ˆS(2) x2 depends on{Z 12, Z13, Z21, Z22, Z23}. These are disjoint sets of independent noise variables, so the estimators are independent. Proof of Theorem 4.13.We apply Lemma 4.11 withσ 2 1 = 8/ε2 andσ 2 2 = 40/ε2. Comput...

work page 2026
[14]

Part 3: Independence

Variance: Var(ˆS(2) x ) = 4· 8 ε2 = 32 ε2 . Part 3: Independence. ˆS(1) x depends on{Z 11, Z12}and ˆS(2) x depends on{Z 13, Z21, Z22, Z23}. These are disjoint sets of independent noise variables, so the estimators are independent. 19 Accepted at the SeQureDB Workshop at ACM SIGMOD 2026 and TPDP Workshop 2026 Proof of Theorem 4.17.We apply Lemma 4.11 withσ...

work page 2026

[1] [1]

Deep learning with differential privacy

Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 308–318,

work page 2016

[2] [2]

Alabi, A

D. Alabi, A. McMillan, J. Sarathy, A. Smith, and S. Vadhan. Differentially private simple linear regression. Proceedings on Privacy Enhancing Technologies (PoPETs), 2022(2):184–204,

work page 2022

[3] [3]

K. Amin, M. Joseph, M. Ribero, and S. Vassilvitskii. Easy differentially private linear regression. In International Conference on Learning Representations (ICLR 2023),

work page 2023

[4] [4]

Differential privacy and robust statistics

Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. InProceedings of the ACM Symposium on Theory of Computing, STOC 2009,

work page 2009

[5] [5]

URLhttps://openreview.net/forum?id= gtCfDKm9ME. J. Fitzsimons, J. Honaker, M. Shoemate, and V. Singhal. Private means and the curious incident of the free lunch.arXiv preprint arXiv:2408.10438,

work page arXiv

[6] [6]

A bias-variance-privacy trilemma for statistical estimation

G. Kamath, A. Mouzakis, M. Regehr, V. Singhal, T. Steinke, and J. Ullman. A bias-variance-privacy trilemma for statistical estimation.arXiv preprint arXiv:2301.13334,

work page arXiv

[7] [7]

Kulesza, A

14 Accepted at the SeQureDB Workshop at ACM SIGMOD 2026 and TPDP Workshop 2026 A. Kulesza, A. T. Suresh, and Y. Wang. Mean estimation in the add-remove model of differential privacy. InProceedings of the 41st International Conference on Machine Learning (ICML),

work page 2026

[8] [8]

Differentially private linear re- gression and synthetic data generation with statistical guarantees.arXiv preprint arXiv:2510.16974v2,

Shurong Lin, Aleksandra Slavkovic, and Deekshith Reddy Bhoomireddy. Differentially private linear re- gression and synthetic data generation with statistical guarantees.arXiv preprint arXiv:2510.16974v2,

work page arXiv

[9] [9]

Revisiting differentially private linear regression: optimal and adaptive prediction & esti- mation in unbounded domain

Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & esti- mation in unbounded domain. InProceedings of the Conference on Uncertainty in Artificial Intelligence (UAI 2018),

work page 2018

[10] [10]

In practice, however, the raw data may only be known to lie in a general rectangle [x min, xmax]×[y min, ymax]

A DP-RSS for General Bounded Data Algorithm 3 and the theoretical results in Section 4 are stated for data satisfyingx i, yi ∈[0,1]. In practice, however, the raw data may only be known to lie in a general rectangle [x min, xmax]×[y min, ymax]. We now describe how DP-RSS adapts to this setting via alinear normalisation, which reduces the general case exac...

work page 2026

[11] [11]

Since the noise scale isb= ∆ 1(f)/ε1 = 1/ε1, the Laplace mechanism theorem guaranteesε 1-differential privacy

whereZ 11, Z12, Z13 iid ∼Lap(1/ε 1). Since the noise scale isb= ∆ 1(f)/ε1 = 1/ε1, the Laplace mechanism theorem guaranteesε 1-differential privacy. 16 Accepted at the SeQureDB Workshop at ACM SIGMOD 2026 and TPDP Workshop 2026 Formal verification.For any neighboring datasetsD, D ′ and any measurable setS⊆R 3: Pr[( ˜Sx2 , ˜Sx−x2 , ˜S1−x)∈S|D] Pr[( ˜Sx2 , ˜...

work page 2026

[12] [12]

Thereforew ∗ 2 = σ2 1 σ2 1+σ2 2

Taking the derivative and setting to zero: dV dw1 = 2w1(σ2 1 +σ 2 2)−2σ 2 2 = 0 =⇒w ∗ 1 = σ2 2 σ2 1+σ2 2 . Thereforew ∗ 2 = σ2 1 σ2 1+σ2 2 . Since d2V dw2 1 = 2(σ2 1 +σ 2 2)>0, this is a minimum. Substituting the optimal weights: Var(ˆθ∗) = σ2 2 σ2 1 +σ 2 2 2 σ2 1 + σ2 1 σ2 1 +σ 2 2 2 σ2 2 = σ2 1σ2 2 σ2 1 +σ 2 2 . 17 Accepted at the SeQureDB Workshop at A...

work page 2026

[13] [13]

Part 3: Independence

Variance:All noise variables have variance 8/ε 2: Var(ˆS(2) x2 ) = 5· 8 ε2 = 40 ε2 . Part 3: Independence. ˆS(1) x2 depends on{Z 11}and ˆS(2) x2 depends on{Z 12, Z13, Z21, Z22, Z23}. These are disjoint sets of independent noise variables, so the estimators are independent. Proof of Theorem 4.13.We apply Lemma 4.11 withσ 2 1 = 8/ε2 andσ 2 2 = 40/ε2. Comput...

work page 2026

[14] [14]

Part 3: Independence

Variance: Var(ˆS(2) x ) = 4· 8 ε2 = 32 ε2 . Part 3: Independence. ˆS(1) x depends on{Z 11, Z12}and ˆS(2) x depends on{Z 13, Z21, Z22, Z23}. These are disjoint sets of independent noise variables, so the estimators are independent. 19 Accepted at the SeQureDB Workshop at ACM SIGMOD 2026 and TPDP Workshop 2026 Proof of Theorem 4.17.We apply Lemma 4.11 withσ...

work page 2026