dorsal/arxiv
View SchemaNear-Optimal Private Linear Regression via Iterative Hessian Mixing
| Authors | Omri Lev, Moshe Shenfeld, Vishwak Srinivasan, Katrina Ligett, Ashia C. Wilson |
|---|---|
| Categories | |
| ArXiv ID | 2601.07545vv1 |
| URL | https://arxiv.org/abs/2601.07545 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
We study differentially private ordinary least squares (DP-OLS) with bounded data. The dominant approach, adaptive sufficient-statistics perturbation (AdaSSP), adds an adaptively chosen perturbation to the sufficient statistics, namely, the matrix $X^{\top}X$ and the vector $X^{\top}Y$, and is known to achieve near-optimal accuracy and to have strong empirical performance. In contrast, methods that rely on Gaussian-sketching, which ensure differential privacy by pre-multiplying the data with a random Gaussian matrix, are widely used in federated and distributed regression, yet remain relatively uncommon for DP-OLS. In this work, we introduce the iterative Hessian mixing, a novel DP-OLS algorithm that relies on Gaussian sketches and is inspired by the iterative Hessian sketch algorithm. We provide utility analysis for the iterative Hessian mixing as well as a new analysis for the previous methods that rely on Gaussian sketches. Then, we show that our new approach circumvents the intrinsic limitations of the prior methods and provides non-trivial improvements over AdaSSP. We conclude by running an extensive set of experiments across standard benchmarks to demonstrate further that our approach consistently outperforms these prior baselines.
{
"annotation_id": "0af9c83e-8807-4754-b686-d9e67b83a953",
"date_created": "2026-02-17T05:53:12.646000Z",
"date_modified": "2026-02-17T05:53:12.646000Z",
"file_hash": "6d88cc82b3be997c2540890d3e29a95e54521e96dd9c58ba2180273d32ed44e8",
"private": false,
"record": {
"abstract": "We study differentially private ordinary least squares (DP-OLS) with bounded data. The dominant approach, adaptive sufficient-statistics perturbation (AdaSSP), adds an adaptively chosen perturbation to the sufficient statistics, namely, the matrix $X^{\\top}X$ and the vector $X^{\\top}Y$, and is known to achieve near-optimal accuracy and to have strong empirical performance. In contrast, methods that rely on Gaussian-sketching, which ensure differential privacy by pre-multiplying the data with a random Gaussian matrix, are widely used in federated and distributed regression, yet remain relatively uncommon for DP-OLS. In this work, we introduce the iterative Hessian mixing, a novel DP-OLS algorithm that relies on Gaussian sketches and is inspired by the iterative Hessian sketch algorithm. We provide utility analysis for the iterative Hessian mixing as well as a new analysis for the previous methods that rely on Gaussian sketches. Then, we show that our new approach circumvents the intrinsic limitations of the prior methods and provides non-trivial improvements over AdaSSP. We conclude by running an extensive set of experiments across standard benchmarks to demonstrate further that our approach consistently outperforms these prior baselines.",
"arxiv_id": "2601.07545",
"authors": [
"Omri Lev",
"Moshe Shenfeld",
"Vishwak Srinivasan",
"Katrina Ligett",
"Ashia C. Wilson"
],
"categories": [
"cs.LG",
"stat.ML"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Near-Optimal Private Linear Regression via Iterative Hessian Mixing",
"url": "https://arxiv.org/abs/2601.07545",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6cdcdbed-ce8e-4b88-89ff-02f333f62cde",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}