Enhancing Differentially Private Linear Regression via Public Second-Moment

arXiv:2508.18037 · cs.LG, stat.ME, stat.ML · Submitted 2026-08-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Enhancing Differentially Private Linear Regression via Public Second-Moment".

Jane: The paper was written by Zilong Cao and Hai Zhang from Northwest University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Welcome back to the arXiv radio hour, everyone. I’m Tom, and as always, I’m here with my co-host Jane. Today we’ve got a paper that’s got me genuinely excited — it’s called “Enhancing Differentially Private Linear Regression via Public Second-Moment.”

Jane: And I’m Jane. Tom, I have to say, the title alone made me perk up. Differential privacy is one of those topics that sounds super intimidating, but the core idea is actually pretty simple. It’s about making sure that when you analyze a dataset, you can’t tell whether any one specific person’s data was included or not.

Tom: Exactly. And the problem this paper tackles is that when you add privacy protection, you usually have to add noise to your calculations, and that noise can really mess up your results. It’s like trying to take a precise measurement while someone’s shaking the table.

Jane: Right. And the authors — Zilong Cao and Hai Zhang from Northwest University — they’ve come up with a clever workaround. They use public data, which doesn’t need privacy protection, to help make the private analysis more stable.

Tom: So the idea is, you’ve got this private dataset you want to analyze, but you also have access to some public data that’s similar in nature. The public data can tell you something about the general shape of the data — like how spread out it is — without revealing anything sensitive.

Jane: And that’s the “second-moment” part of the title. The second-moment matrix is basically a mathematical way of describing the variance and correlations in your data. It tells you the overall structure.

Tom: And by using that public structure, they can transform the private data into a form that’s much easier to work with when you add privacy noise. It’s like pre-cleaning the data before you put it through the privacy filter.

Jane: Which is huge, because one of the biggest challenges in differential privacy is that if your data is spread out in weird ways, you need to add a ton of noise to protect it, and that noise just drowns out the actual signal.

Tom: So the implication here is that we could get accurate results from private data without having to sacrifice as much utility. That’s a big deal for anyone working with sensitive information — medical records, financial data, you name it.

Jane: And it’s not just about accuracy. The paper also shows that their method is more robust, meaning it gives consistent results even when the data is messy or ill-conditioned.

Tom: I love that phrase, “ill-conditioned.” It sounds like the data is having a bad day.

Jane: It kind of is! It means the data has a structure that makes mathematical operations unstable. And this paper’s method smooths that out.

Tom: Alright, so we’ve got the gist. But I want to get into the nitty-gritty of how they actually do this transformation. That’s coming up next.

Summary: Tom: So we’re back, and we’ve got our senior researcher Lu joining us. Lu, we were just talking about how this paper uses public data to help with private regression. Can you break down the actual method for us?

Lu: Sure, Tom. So the paper focuses on something called the ordinary least squares estimator — that’s the standard way to fit a line through data points. The formula involves inverting a matrix that describes the data’s spread. And here’s the catch — when you add privacy noise to that matrix, inverting it becomes really unstable.

Jane: And that instability is the core problem, right? It’s like trying to flip a pancake that’s too big for your spatula — you might get it, but you’re probably going to drop it.

Lu: That’s a great analogy, Jane. The paper’s solution is to use the public second-moment matrix to transform the data before doing the private computation. They essentially “whiten” the data — they stretch and rotate it so that it becomes more uniform and well-behaved.

Tom: So the public data acts like a template for how to reshape the private data?

Lu: Exactly. And the beauty is that this transformation is reversible. After they compute the private estimate on the transformed data, they can transform it back to get the answer in the original space. The final result is still a valid estimate of the original problem.

Jane: And the key insight is that the transformed data has a much better condition number — that’s a measure of how stable the matrix inversion is. A lower condition number means the computation is much more reliable.

Lu: Right. In their experiments, they showed that the condition number dropped dramatically. On a real-world wine quality dataset, the condition number went from about sixty-eight down to one point six after transformation. That’s a massive improvement.

Tom: Wow, sixty-eight to one point six. That’s like going from driving on a bumpy dirt road to a freshly paved highway.

Jane: And that stability translates directly into better accuracy. The paper shows that even with strong privacy protection, their method outperforms the standard approach that uses weaker privacy protection.

Lu: Yes, and that’s the headline result. Their method, which they call DP-PMTOLSE, consistently produced lower error than the standard DP-OLSE, even when the standard method was allowed more privacy budget — meaning less noise.

Tom: So it’s not just a small improvement. It’s a significant leap in performance.

Lu: Definitely. And the theoretical analysis backs it up. They derived error bounds that show their method is less sensitive to the data’s underlying structure, which is why it’s so much more robust.

Jane: I’m curious about the practical side of this. Meng, you’re the engineer — what does this mean for someone actually building a system?

Meng: Well, Jane, the first thing I notice is that the method only needs a small amount of public data. In their experiments, even with just a few dozen public samples, they got most of the benefit. That makes it very practical.

Tom: So you don’t need a huge public dataset to make this work?

Meng: Right. The public data just needs to give a rough estimate of the data’s shape. Once you have that, you can transform the private data and get much better results. And the computational cost is minimal — it’s just a matrix multiplication and inversion, which any modern system can handle.

Jane: That’s reassuring. So this isn’t just a theoretical curiosity — it’s something that could actually be deployed.

Meng: Absolutely. And the fact that it’s compatible with existing differential privacy frameworks means it could be dropped into current systems without a major overhaul.

Tom: So we’ve got the method, we’ve got the results. But what’s the actual improvement over existing approaches? That’s what we’re diving into next.

Improvements: Tom: We’re back, and we’re digging into the specific improvements this paper makes over existing methods. Jane, you’ve been looking at the technical details — what stands out to you?

Jane: Well, Tom, the paper identifies three main weaknesses in the standard approach. First, when your data is unbounded — meaning it can take on any value — the privacy noise you need to add becomes enormous. Second, the standard method relies entirely on private data, so it can’t benefit from any public information. And third, the matrix inversion step is numerically unstable when the data is ill-conditioned.

Lu: And the paper’s method addresses all three at once. By using the public second-moment matrix, they can truncate the data more effectively, which controls the sensitivity and keeps the noise manageable.

Meng: That truncation part is interesting. In the standard method, you have to guess a truncation radius based on the private data itself. That’s circular — you’re using the data you’re trying to protect to determine how much noise to add.

Jane: Exactly. And if you guess wrong, you either truncate too aggressively and lose information, or you don’t truncate enough and the noise becomes too large. The public second-moment gives you a principled way to choose that radius.

Lu: And that’s not just a practical improvement. The paper proves that with their method, the truncation radius is essentially independent of the private data’s structure. That’s a big theoretical win.

Tom: So the public data does double duty — it helps with both the truncation and the numerical stability.

Lu: Precisely. And the numerical stability improvement is the most dramatic. The paper shows that the condition number of the transformed second-moment matrix is close to one which is the ideal value. That means the matrix inversion is about as stable as it can possibly be.

Meng: And the error bounds reflect that. The paper’s theoretical analysis shows that their method’s error doesn’t depend on the condition number of the private data at all. The standard method’s error grows with that condition number, which can be huge for real-world data.

Jane: So for a dataset with a condition number of, say, one thousand the standard method would have a much larger error than their method, even with the same privacy budget.

Lu: Yes, and that’s why their experiments show such a stark difference. On the wine quality dataset, the standard method struggled even with weak privacy, while their method performed well even with strong privacy.

Tom: So the improvement isn’t just incremental — it’s a fundamental change in how the problem is approached.

Meng: And I think that’s the key takeaway. By leveraging public information, you can sidestep many of the worst problems in differential privacy. It’s not a hack; it’s a principled redesign.

Jane: And that opens up a lot of possibilities. I mean, if you can use public data to improve private regression, what else could you improve?

Tom: That’s a great question, and it’s exactly what we’re going to wrap up with. Let’s bring in Lalam to give us the big-picture view.

Conclusion: Tom: Alright, we’re in the final stretch. We’ve been talking about “Enhancing Differentially Private Linear Regression via Public Second-Moment” by Cao and Zhang. Jane, can you give us a quick recap?

Jane: Sure, Tom. The paper tackles the problem of making linear regression private without destroying accuracy. The standard approach adds noise to the sufficient statistics, but that noise can be overwhelming, especially for messy or high-dimensional data. The authors’ insight is to use public data to transform the private data into a more stable form before adding the noise.

Lu: And the transformation is reversible, so you get the final answer in the original space. The theoretical error bounds show that their method is much more robust to the data’s structure, and the experiments confirm it — they see dramatically lower errors and better consistency.

Meng: From an engineering standpoint, it’s also practical. It needs only a small amount of public data, the computation is cheap, and it plugs into existing privacy frameworks.

Tom: So what’s the big-picture impact, Lalam? Where does this take us?

Lalam: This paper points toward a broader principle: public information can be a powerful tool for making private analysis practical. The authors show that even a rough estimate of the data’s shape — the second-moment matrix — can dramatically improve the quality of private estimates. That’s a shift in mindset.

Jane: How so?

Lalam: Traditionally, differential privacy treats all data as equally sensitive. But in reality, we often have access to public data that shares characteristics with the private data — census demographics, public research datasets, open government statistics. This paper shows how to leverage that public information without compromising privacy.

Tom: So it’s about being smarter about what we already know.

Lalam: Exactly. And the implications go beyond regression. The same principle could apply to other statistical models, machine learning training, even synthetic data generation. If we can use public data to precondition private computations, we could unlock accurate analysis for many more applications.

Meng: And that could be huge for healthcare, finance, social science — anywhere sensitive data is collected.

Jane: I think that’s the most exciting part. This isn’t just a better algorithm; it’s a template for how to think about privacy and utility together.

Tom: Well said, Jane. So, to sum up: “Enhancing Differentially Private Linear Regression via Public Second-Moment” shows that public data can be a game-changer for private analysis. It improves accuracy, robustness, and practicality, all while maintaining strong privacy guarantees.

Lu: And it opens the door for future work — applying this idea to other models, exploring how much public data is needed, and understanding the trade-offs in different settings.

Tom: Alright, that’s a wrap on this paper. Thanks to Lu, Meng, and Lalam for joining us. And thanks to you, our listeners, for tuning in. We’ll be back soon with another exciting paper from arXiv. Until then, stay curious.

Jane: Goodbye, everyone!

Zilong Cao, Hai Zhang

Northwest University

cs.LG, stat.ME, stat.ML

Submitted: 2026-08-15

Updated: 2026-08-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 37/100

Key concepts

Differential Privacy: A method ensuring that when analyzing a dataset, the results are not affected by whether any single specific person's data was included in the calculation.
Second-Moment Matrix: A mathematical tool used to describe the variance and correlations within a dataset, providing insight into its overall structure. This public data helps transform private data for better analysis.
Ill-Conditioned Data: Data that has a structure making mathematical operations, like matrix inversion, unstable. The paper's method smooth out these issues to ensure reliable computation.

Terminology

Differentially Private — 25× in this paper · explained in 3 episodes
Accuracy — 19× in this paper · explained in 1 episode
Robustness — 18× in this paper · explained in 5 episodes
Differential Privacy — 15× in this paper · explained in 4 episodes
Core — 6× in this paper · explained in 2 episodes
Trace — 4× in this paper · explained in 2 episodes
Public-moment-transformed Truncation — 2× in this paper
Synthetic Data Generation — 2× in this paper · explained in 5 episodes
Zero-Concentrated Differential Private — 2× in this paper
Anisotropy — 1× in this paper · explained in 3 episodes
Consistency — 1× in this paper · explained in 3 episodes
Differential Privacy (DP) — 1× in this paper · explained in 7 episodes
Non-asymptotic Analysis — 1× in this paper · explained in 2 episodes

Summary

Summary

This paper addresses the challenge of enhancing differentially private (DP) linear regression by leveraging public data, specifically the public second-moment matrix, under the sufficient statistics perturbation (SSP) framework. The authors propose a novel method to improve the utility and robustness of the ordinary least squares estimator (OLSE) when privacy constraints are applied.

The paper begins by highlighting a key limitation of traditional DP approaches: Traditional DP approaches often require adding noise based solely on private data, which can significantly degrade utility. The authors note that existing DP linear regression methods fall into three categories—gradient perturbation, objective perturbation, and sufficient statistics perturbation (SSP)—and that prior works relying solely on private data face several limitations: "(i) they struggle with unbounded data, leading to unbounded sensitivities and excessive noise; (ii) utility improvements are inherently limited when only private information is used; and (iii) the resulting estimators often suffer from numerical instability."

The core problem is that the closed-form OLS solution, given by (X⊤X/n)−1 X⊤y/n, depends on the empirical second-moment matrix Σ̂ = (1/n)X⊤X and its inverse. In the DP setting, noise perturbation G added to Σ̂ results in the perturbed matrix (Σ̂ + G), whose inverse is often numerically unstable and inaccurate, especially when Σ̂ is ill-conditioned, as a high condition number exacerbates the sensitivity of matrix inversion to perturbations.

To address this, the authors introduce a public second-moment transformation framework. They transform the private data using the public second-moment matrix Σ̂pub and obtain a DP linear regression estimator based on the transformed data, ultimately recovering the original private estimation through Σ̂pub. The transformation is motivated by the observation that an isotropic sub-Gaussian random vector z satisfies the high probability bound ∥z∥22 ≤ O(d(1 + log(2/η))), and applying a linear transformation M−1/2 to approximately whiten the data makes the transformed second-moment matrix well-conditioned, typically satisfying κ(E[z̃z̃⊤]) ≈ 1.

The authors establish that the transformation is affine invariant, meaning it does not alter the original OLSE. They show that β̃A = (Σ̂B 1/2/σ̂B)β̂A = (Ã⊤Ã/nA)−1(Ã⊤ỹA/nA), where Ã = AΣ̂B-1/2 and ỹA = yA/σ̂B, demonstrating that we can translate discussion from the original OLSE β̂A to the transformed OLSE β̃A totally.

The paper's main contributions are threefold. First, they propose a novel data transformation technique leveraging a public second-moment matrix, which improves the effect of data truncation, reduces data sensitivity, and enhances the stability and accuracy of DP-OLSE, and they demonstrate the transformation is reversible for OLSE. Second, they analyze the stability condition of the perturbed inverse second-moment matrix and reduce the requirement for the size of private data from O(d 3/2 log(1/η)/(√ρ·n·η) · (κ̄(Σ) + ∥Σ−1∥ log(2n/η))) to O(d 3/2 log(1/η)/(√ρ·n·η) · log(2n/η)), making stability independent of the (private) second-moment matrix Σ. Third, they guarantee the DP estimator's error bound is O(d 3/2∥β∥κ(Σ) log(1/η)/(√ρ·n) · log(2n/η)) rather than the non-public bound O(d 3/2∥β∥κ(Σ) log(1/η)/(√ρ·n) · (log(2n/η)∥Σ−1∥ + κ̄(Σ))), eliminating the impacts of the averaged condition number and the norm of the inverse second-moment matrix.

The paper presents three main algorithms. Algorithm 1 (PMT) performs Public-moment-transformed Truncation, transforming private data via ξ̃i = Σ̂-1/2ξi and truncating based on the radius √(d(1 + log(2nξ/η))). Algorithm 2 (DP-PMTSE) provides Differentially Private PMT Second-moment Estimation, adding Gaussian noise G ∼ GUE(σ2) with σ = √(2d(1 + log(2nξ/η)))/(√(2ρ·nξ)) to the transformed second-moment matrix. Algorithm 3 (DP-PMTOLSE) is the core algorithm for Differential Private PMT Ordinary Least Square Estimator, which transforms both features and responses, adds Gaussian noise to both the second-moment matrix and the cross-moment vector, and recovers the original estimator via β̂ADP ← σ̂B · Σ̂B-1/2 · β̃ADP.

The theoretical results include Theorem 1, which bounds the transformed second-moment matrix: with probability at least 1 − 2η, L·I ⪯ Σ̂-1/2ΣΣ̂-1/2 ⪯ U·I, where L = n/(√n + O(√(d + 2 log(1/η))))2 and U = n/(√n − O(√(d + 2 log(1/η))))2. Corollary 2 shows that with high probability, no sample is truncated, and the truncation radius is independent of private and a priori information. Theorem 2 guarantees that Algorithm 2 satisfies ρ-zCDP and the Gaussian noise matrix is bounded by ∥G∥2 ≤ O(d 3/2(1 + log(2nξ/η)) log(1/η)/(√ρ·nξ)).

Theorem 3 provides the main result for DP-PMTOLSE, guaranteeing 2ρ-zCDP and, with probability at least 1 − O(η), the error bound ∥β̂ADP − β̂A∥2 ≤ O(d 3/2∥β∥∥Σ̂A∥∥Σ̂B-1∥ log(1/η)(1 + log(2nA/η))/(√ρ·nA·L2(1 − O(√(d + log(1/η))/√nA))4)).

The paper compares its method to a naive truncation method (Algorithm 4, DP-OLSE) in Theorem 4, which has the error bound ∥β̂ADP − β̂A∥2 ≤ O(d 3/2∥β∥2κ(Σ̂A) log(1/η)/(√ρ·nA) · (log(2nA/η)/λmin(Σ̂A) + κ̄(Σ̂A))).

The authors highlight two theoretical advantages. First, Strong robustness: the standard method requires more private data when the second-moment matrix is ill-conditioned, while the proposed method eliminates the impact of the unknown second-moment matrix, decreasing the consumption of private data meanwhile strengthening the regression robustness and utility. Second, Better error bound: the rate of convergence in the standard method depends on the averaged condition number κ̄(Σ) and ∥Σ−1∥, while the proposed method effectively eliminates the impacts of the unknown second-moment Σ, especially when the second-moment matrix is ill-conditioned.

Experiments on synthetic data (d = 10, features distributed as N(µ, Ψ), noise ω ∼ N(0, (0.05)2)) show that even with the largest privacy budget, DP-OLSE produces higher errors than DP-PMTOLSE with smaller budget, despite the latter ensuring stronger privacy and injecting more noise. The experiments also demonstrate that DP-PMTOLSE requires the number of public data points to exceed the feature dimension for good performance, and that increasing public data helps reduce estimation error. On the real-world White-wine Quality dataset (4898 samples, 11 features, averaged condition number κ̄(Σ̂pri) = 68.4 for private data and κ̄(Σ̂tran) = 1.6 after transformation), the DP-PMTOLSE achieves a significant performance compared to the DP-OLSE, with DP-PMTOLSE at ρ = 5 still having lower errors and better robustness than DP-OLSE at ρ = 500.

The paper concludes that the second-moment matrix estimation using tiny amounts of public data can greatly enhance DP OLSE, and suggests future research could examine ways to improve DP algorithms by using public information even more and apply this strategy to other DP machine learning methods.

Improvements for AI systems

Based on the paper, here are the specific improvements I can implement in AI systems, along with the resulting capabilities:

Implementation: Add a preprocessing layer that computes a public second-moment matrix (Σ̂ B) from a small, non-sensitive public dataset. Before any private regression task, transform private features via Ã = A·Σ̂ B(-1/2).
Benefit: Reduces the condition number of the feature covariance matrix from potentially ill-conditioned (e.g., κ̄=68.4 in real data) to near-isotropic (κ̄≈1.6), making subsequent DP noise injection far less destructive.
Implementation: Replace fixed or private-data-derived truncation bounds with a radius derived from public data: R = O(d(1 + log(2n/η))) after whitening. This eliminates the need to estimate private trace/spectrum for truncation.
Benefit: Avoids the bias-variance tradeoff of over/under-truncation. The paper proves that with high probability (1−O(η)), no private sample is truncated, preserving the original OLSE while bounding sensitivity.
Implementation: In the Gaussian mechanism for the second-moment matrix, set noise scale based on the transformed sensitivity ∆ = 2d(1+log(2n/η))/n (which is independent of private Σ) rather than the original data's trace or spectral norm.
Benefit: Guarantees the inverse stability condition ∥Σ̃(-1)∥·∥G∥ ≤ 1/2 with far fewer private samples. The paper reduces the required private data size from O(d(3/2)·κ̄(Σ)/√(ρ·n)) to O(d(3/2)·log(1/η)/√(ρ·n)), removing dependence on the private condition number.
Implementation: After computing the DP estimator on transformed data (β̃ DP), recover the original-space estimator via β̂ DP = σ̂ B · Σ̂ B(-1/2) · β̃ DP. This is a post-processing step that preserves DP guarantees.
Benefit: Allows the system to work in a well-conditioned space during optimization but return results in the original feature space, maintaining interpretability and compatibility with downstream tasks.
Implementation: Split the privacy budget ρ into two parts: ρ1 for the transformed second-moment matrix and ρ2 for the cross-moment vector. The paper uses equal splits (ρ1=ρ2=ρ/2) but allows adaptive allocation based on which component is more sensitive.
Benefit: Enables fine-tuning of privacy-utility tradeoffs. The theoretical error bound shows the second-moment noise dominates, so allocating more budget there (e.g., ρ1=0.7ρ) can improve accuracy without weakening the cross-moment protection.

Handle unbounded or heavy-tailed private data without requiring prior knowledge of data range or distribution, because the public-second-moment transformation makes the data approximately isotropic and the truncation radius is distribution-free.
Achieve stable DP linear regression on ill-conditioned feature spaces (e.g., high-dimensional correlated features) where standard SSP fails. The paper's experiments show DP-PMTOLSE with ρ=5 outperforms DP-OLSE with ρ=500 in both accuracy and variance.
Require significantly fewer private samples for reliable DP estimation. The stability condition is now independent of the private covariance's condition number, meaning the system works with n A as small as a few thousand even when κ(Σ) is large.
Provide tighter error guarantees: The theoretical bound improves from O(d(3/2)·∥β∥·κ(Σ)·log(1/η)/√(ρ·n)) (which includes κ̄(Σ) and ∥Σ(-1)∥) to O(d(3/2)·∥β∥·log(1/η)/√(ρ·n)) (which is independent of the private condition number), giving users predictable performance regardless of data conditioning.
Seamlessly integrate with existing DP pipelines: The transformation is affine-invariant for OLSE, so the system can be dropped into any existing SSP-based regression framework without changing the downstream inference logic, while automatically benefiting from public data when available.
Adapt to varying public data availability: The system degrades gracefully—with zero public data it reduces to standard DP-OLSE, but with even a small public set (n B > d), it immediately improves stability and accuracy, as shown in Figure 3 and Figure 5.