Differentially Private Sparse Linear Regression with Heavy-tailed Responses

2025/06/07 by Meng Ding, Tian, Xizhi, Ding, Meng +4 · 1 citation
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2506.06861

openalex publication_date 2025/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

As a fundamental problem in machine learning and differential privacy (DP), DP linear regression has been extensively studied. However, most existing methods focus primarily on either regular data distributions or low-dimensional cases with irregular data. To address these limitations, this paper provides a comprehensive study of DP sparse linear regression with heavy-tailed responses in high-dimensional settings. In the first part, we introduce the DP-IHT-H method, which leverages the Huber loss and private iterative hard thresholding to achieve an estimation error bound of \( O\biggl( s^{* (1 )/(2)} ⋅ \biggl((log d)/(n)\biggr)^\fracζ1 + ζ + s^{* (1 + 2ζ)/(2 + 2ζ)} ⋅ \biggl((log² d)/(n ε)\biggr)^\fracζ1 + ζ \biggr) \) under the (ε, δ)-DP model, where n is the sample size, d is the dimensionality, s^* is the sparsity of the parameter, and ζ∈ (0, 1] characterizes the tail heaviness of the data. In the second part, we propose DP-IHT-L, which further improves the error bound under additional assumptions on the response and achieves \( O(\frac(s^*)^3/2 log dn ε). \) Compared to the first result, this bound is independent of the tail parameter ζ. Finally, through experiments on synthetic and real-world datasets, we demonstrate that our methods outperform standard DP algorithms designed for ``regular'' data.

Citations

• Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization
• Nearly Optimal Differentially Private ReLU Regression
• Truthful High Dimensional Sparse Linear Regression
• Differentially Private Non-convex Learning for Multi-layer Neural Networks
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model
• Differentially Private ℓ₁-norm Linear Regression with Heavy-tailed Data
• Faster Rates of Private Stochastic Convex Optimization
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• Robust and Differentially Private Mean Estimation
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• On Differentially Private Stochastic Convex Optimization with\n Heavy-tailed Data
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time
• Private Mean Estimation of Heavy-Tailed Distributions
• A Knowledge Transfer Framework for Differentially Private Sparse Learning
• Private Stochastic Convex Optimization with Optimal Rates
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
• The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy
• Robust classification via MOM minimization
• Differentially Private Empirical Risk Minimization Revisited: Faster and More General
• Collecting Telemetry Data Privately
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Adaptive Huber Regression
• Estimation bounds and sharp oracle inequalities of regularized\n procedures with Lipschitz loss functions
• Risk minimization by median-of-means tournaments
• Minimax Optimal Procedures for Locally Private Estimation
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• Differentially Private Empirical Risk Minimization

Cited by

• Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition

Related

• Differentially Private Estimation and Inference in High-Dimensional Regression with FDR Control
• Differentially Private Estimation and Inference in High-Dimensional Regression with FDR Control
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data
• Differentially Private Estimation via Statistical Depth