Near-Optimal Private Linear Regression via Iterative Hessian Mixing

• URL: http://arxiv.org/abs/2601.07545v1
• Date: Mon, 12 Jan 2026 13:50:15 GMT
• Title: Near-Optimal Private Linear Regression via Iterative Hessian Mixing
• Authors: Omri Lev, Moshe Shenfeld, Vishwak Srinivasan, Katrina Ligett, Ashia C. Wilson,
• Abstract summary: We study differentially private ordinary least squares (DP-OLS) with bounded data.<n>The dominant approach, adaptive sufficient- perturbation (AdaSSP), adds an adaptively chosen perturbation to the sufficient statistics.<n>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.
• Score: 7.344623287743932
• 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.

Related papers

• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  We study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ per instance for prediction.<n>We introduce a new extend-time algorithm, which significantly improves previous regret bounds.
  arXiv  Detail & Related papers  (2025-10-31T05:02:33Z)
• The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches [13.972860872034525]
  In this work, we revisit this operation through the lens of Renyi Differential Privacy (RDP)<n>We demonstrate how this improved analysis leads to performance improvement in different linear regression settings.<n> Empirically, our methods improve performance across multiple datasets and, in several cases, reduce runtime.
  arXiv  Detail & Related papers  (2025-05-30T13:52:48Z)
• Better Rates for Private Linear Regression in the Proportional Regime via Aggressive Clipping [19.186034457189162]
  A common approach is to set the clipping constant much larger than the expected norm of the per-sample gradients.<n>While simplifying the analysis, this is however in sharp contrast with what empirical evidence suggests to optimize performance.<n>Our work bridges this gap between theory and practice by crucially operating in a regime where clipping happens frequently.
  arXiv  Detail & Related papers  (2025-05-22T07:34:27Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD.<n>We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective. We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices. Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
  arXiv  Detail & Related papers  (2023-10-31T16:15:13Z)
• Generalizing Gaussian Smoothing for Random Search [23.381986209234164]
  Gaussian smoothing (GS) is a derivative-free optimization algorithm that estimates the gradient of an objective using perturbations of the current benchmarks. We propose to choose a distribution for perturbations that minimizes the error of such distributions with provably smaller MSE.
  arXiv  Detail & Related papers  (2022-11-27T04:42:05Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Bayesian System ID: Optimal management of parameter, model, and measurement uncertainty [0.0]
  We evaluate the robustness of a probabilistic formulation of system identification (ID) to sparse, noisy, and indirect data. We show that the log posterior has improved geometric properties compared with the objective function surfaces of traditional methods.
  arXiv  Detail & Related papers  (2020-03-04T22:48:30Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.