# Near-Optimal Private Linear Regression via Iterative Hessian Mixing

arXiv: https://arxiv.org/abs/2601.07545 · HTML: https://mlsanity.com/paper/2601.07545/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 12 Jan 2026.

## Builds on (most cited first, 26 of 26)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks](https://mlsanity.com/paper/2011.06223/) (2020)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation](https://mlsanity.com/paper/2402.13531/) (2024)
- [Stochastic Coded Federated Learning with Convergence and Privacy Guarantees](https://mlsanity.com/paper/2201.10092/) (2022)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Improved Differentially Private Regression via Gradient Boosting](https://mlsanity.com/paper/2303.03451/) (2023)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)
- [The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches](https://mlsanity.com/paper/2505.24603/) (2025)

## Built on by (most cited first, 1 of 1)

- [The Fast Mixing Mechanism for Differential Privacy](https://mlsanity.com/paper/2605.30600/) (2026)

## Abstract (arXiv)

We study differentially private ordinary least squares (DP-OLS) with bounded data (X,Y) via sketching-based mechanisms. While Gaussian sketching approaches have been explored for DP-OLS citepsheffet2017differentially, they are typically viewed as less competitive than the Adaptive Sufficient Statistics Perturbation (AdaSSP) method citepwangadassp, which directly perturbs the sufficient statistics (XtopX, XtopY). This method was shown to be close to information-theoretically optimal, while also exhibiting strong empirical performance. In this work, we propose the Iterative Hessian Mixing (IHM), an algorithm that builds on Gaussian sketching approaches to DP-OLS and is inspired by the Iterative Hessian Sketch of citetpilancihessiansketch. We prove that IHM is differentially private and provide utility guarantees in the form of excess empirical risk bounds. These bounds improve upon those of AdaSSP by removing a multiplicative factor that can be as large as the square root of the data dimension. The design of the IHM is based on new accuracy guarantees that we present for prior Gaussian sketching approaches for DP-OLS, which clarify when these methods are expected to perform well and how IHM circumvents their inherent limitations. We also conduct a rigorous empirical evaluation on a large suite of datasets, demonstrating that IHM consistently outperforms prior baselines, including AdaSSP.