Improved Differentially Private Regression via Gradient Boosting
- URL: http://arxiv.org/abs/2303.03451v2
- Date: Sat, 20 May 2023 21:25:11 GMT
- Title: Improved Differentially Private Regression via Gradient Boosting
- Authors: Shuai Tang, Sergul Aydore, Michael Kearns, Saeyoung Rho, Aaron Roth,
Yichen Wang, Yu-Xiang Wang, Zhiwei Steven Wu
- Abstract summary: We give a new algorithm for private linear regression based on gradient boosting.
In addition to a comprehensive set of experiments, we give theoretical insights to explain this behavior.
- Score: 38.09948758699131
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We revisit the problem of differentially private squared error linear
regression. We observe that existing state-of-the-art methods are sensitive to
the choice of hyperparameters -- including the ``clipping threshold'' that
cannot be set optimally in a data-independent way. We give a new algorithm for
private linear regression based on gradient boosting. We show that our method
consistently improves over the previous state of the art when the clipping
threshold is taken to be fixed without knowledge of the data, rather than
optimized in a non-private way -- and that even when we optimize the
hyperparameters of competitor algorithms non-privately, our algorithm is no
worse and often better. In addition to a comprehensive set of experiments, we
give theoretical insights to explain this behavior.
Related papers
- Regression under demographic parity constraints via unlabeled post-processing [5.762345156477737]
We present a general-purpose post-processing algorithm that generates predictions that meet the demographic parity.
Unlike prior methods, our approach is fully theory-driven. We require precise control over the gradient norm of the convex function.
Our algorithm is backed by finite-sample analysis and post-processing bounds, with experimental results validating our theoretical findings.
arXiv Detail & Related papers (2024-07-22T08:11:58Z) - 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) - Private Gradient Descent for Linear Regression: Tighter Error Bounds and
Instance-Specific Uncertainty Estimation [17.84129947587373]
We provide an improved analysis of standard differentially private gradient descent for linear regression under the squared error loss.
Our analysis leads to new results on the algorithm's accuracy.
arXiv Detail & Related papers (2024-02-21T04:58:41Z) - Online Sensitivity Optimization in Differentially Private Learning [8.12606646175019]
We present a novel approach to dynamically optimize the clipping threshold.
We treat this threshold as an additional learnable parameter, establishing a clean relationship between the threshold and the cost function.
Our method is thoroughly assessed against alternative fixed and adaptive strategies across diverse datasets, tasks, model dimensions, and privacy levels.
arXiv Detail & Related papers (2023-10-02T00:30:49Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection.
This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
arXiv Detail & Related papers (2022-09-09T08:54:13Z) - Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
parameter-free algorithms are online learning algorithms that do not require setting learning rates.
We propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor.
Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties.
arXiv Detail & Related papers (2022-03-19T13:39:49Z) - Stochastic Online Linear Regression: the Forward Algorithm to Replace
Ridge [24.880035784304834]
We derive high probability regret bounds for online ridge regression and the forward algorithm.
This enables us to compare online regression algorithms more accurately and eliminate assumptions of bounded observations and predictions.
arXiv Detail & Related papers (2021-11-02T13:57:53Z) - Adaptive Differentially Private Empirical Risk Minimization [95.04948014513226]
We propose an adaptive (stochastic) gradient perturbation method for differentially private empirical risk minimization.
We prove that the ADP method considerably improves the utility guarantee compared to the standard differentially private method in which vanilla random noise is added.
arXiv Detail & Related papers (2021-10-14T15:02:20Z) - Causal Gradient Boosting: Boosted Instrumental Variable Regression [2.831053006774813]
We propose an alternative algorithm called boostIV that builds on the traditional gradient boosting algorithm and corrects for the endogeneity bias.
Our approach is data driven, meaning that the researcher does not have to make a stance on neither the form of the target function approximation nor the choice of instruments.
We show that boostIV is at worst on par with the existing methods and on average significantly outperforms them.
arXiv Detail & Related papers (2021-01-15T11:54:25Z) - Implicit differentiation of Lasso-type models for hyperparameter
optimization [82.73138686390514]
We introduce an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems.
Our approach scales to high-dimensional data by leveraging the sparsity of the solutions.
arXiv Detail & Related papers (2020-02-20T18:43:42Z)
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.