Research map / Learning theory and algorithms / Matrix and tensor methods

Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation

ICML 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Nonconvex low-rank and sparse optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a new analysis of noisy full-batch DP gradient descent for linear regression, showing iterates are approximately Gaussian around the OLS solution when no clipping occurs, yielding O(p)-sample accuracy and finite-sample valid confidence intervals.

Problem

Accuracy and uncertainty quantification of differentially private gradient descent for least-squares linear regression, where prior analyses needed Omega(p^{3/2}) samples and gave no valid parameter confidence intervals.

Approach

Under a no-clipping condition, the DP-GD iterate distribution at each step is exactly Gaussian centered at the empirical minimizer plus an exponentially decaying bias; a coupling argument transfers this to the clipped algorithm, enabling tighter error bounds (n ~ p samples) and instance-specific confidence intervals from iterate variability.

Key results

• DP-GD error scales linearly in p/n (sample complexity n = Otilde(p)), matching OLS dimension dependence while AdaSSP needs n = Omega(p^{3/2}), shown with constant error when p/n fixed.
• Theorem gives ||theta_T - theta*|| = Otilde(sqrt(sigma^2 p/n) + sigma p/(sqrt(rho) n)) for rho-zCDP with gamma = Otilde(sigma sqrt p).
• Independent-runs and checkpoint confidence intervals achieve valid finite-sample coverage under the no-clipping condition, with experiments showing coverage and widths comparable to nonprivate OLS intervals.

Measured effects reported in the paper

Surprising findings

• Empirically, error stays low even when 50% of gradients are clipped, suggesting the no-clipping requirement is stronger than necessary in practice.

Limitations

• Theory requires well-conditioned, Gaussian-like data; dependence on condition number remains an open problem.
• Confidence intervals target the clipped empirical minimizer rather than the OLS or population parameter.
• Experiments use only synthetic data.

Experimental setup

Metrics: l2 estimation error confidence interval coverage confidence interval width fraction of gradients clipped

Baselines: AdaSSP OLS independent runs confidence intervals batched means confidence intervals

Builds on: noisy gradient descent AdaSSP zero-concentrated differential privacy

Closest papers by meaning

• Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency (NeurIPS 2023 · similarity 0.91)
• Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy (NeurIPS 2023 · similarity 0.90)
• Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.88)
• Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.88)
• Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.87)
• Online Sensitivity Optimization in Differentially Private Learning (AAAI 2024 · similarity 0.87)