Differentially Private Regression with Unbounded Covariates

• URL: http://arxiv.org/abs/2202.11199v1
• Date: Sat, 19 Feb 2022 17:31:38 GMT
• Title: Differentially Private Regression with Unbounded Covariates
• Authors: Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, Stratis Ioannidis
• Abstract summary: We provide differentially private algorithms for the classical regression settings of Least Squares Fitting, Binary Regression and Linear Regression. We capture the fundamental and widely-studied models of logistic regression and linearly-separable SVMs, learning an unbiased estimate of the true regression vector.
• Score: 19.646866014320608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide computationally efficient, differentially private algorithms for the classical regression settings of Least Squares Fitting, Binary Regression and Linear Regression with unbounded covariates. Prior to our work, privacy constraints in such regression settings were studied under strong a priori bounds on covariates. We consider the case of Gaussian marginals and extend recent differentially private techniques on mean and covariance estimation (Kamath et al., 2019; Karwa and Vadhan, 2018) to the sub-gaussian regime. We provide a novel technical analysis yielding differentially private algorithms for the above classical regression settings. Through the case of Binary Regression, we capture the fundamental and widely-studied models of logistic regression and linearly-separable SVMs, learning an unbiased estimate of the true regression vector, up to a scaling factor.

Related papers

• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  This paper presents a succinct derivation of the training and generalization performance of a variety of high-dimensional ridge regression models. We provide an introduction and review of recent results on these topics, aimed at readers with backgrounds in physics and deep learning.
  arXiv  Detail & Related papers  (2024-05-01T15:59:00Z)
• A Novel Approach in Solving Stochastic Generalized Linear Regression via Nonconvex Programming [1.6874375111244329]
  This paper considers a generalized linear regression model as a problem with chance constraints. The results of the proposed algorithm were over 1 to 2 percent better than the ordinary logistic regression model.
  arXiv  Detail & Related papers  (2024-01-16T16:45:51Z)
• High-dimensional analysis of double descent for linear regression with random projections [0.0]
  We consider linear regression problems with a varying number of random projections, where we provably exhibit a double descent curve for a fixed prediction problem. We first consider the ridge regression estimator and re-interpret earlier results using classical notions from non-parametric statistics. We then compute equivalents of the generalization performance (in terms of bias and variance) of the minimum norm least-squares fit with random projections, providing simple expressions for the double descent phenomenon.
  arXiv  Detail & Related papers  (2023-03-02T15:58:09Z)
• Vector-Valued Least-Squares Regression under Output Regularity Assumptions [73.99064151691597]
  We propose and analyse a reduced-rank method for solving least-squares regression problems with infinite dimensional output. We derive learning bounds for our method, and study under which setting statistical performance is improved in comparison to full-rank method.
  arXiv  Detail & Related papers  (2022-11-16T15:07:00Z)
• Robust Regularized Low-Rank Matrix Models for Regression and Classification [14.698622796774634]
  We propose a framework for matrix variate regression models based on a rank constraint, vector regularization (e.g., sparsity), and a general loss function. We show that the algorithm is guaranteed to converge, all accumulation points of the algorithm have estimation errors in the order of $O(sqrtn)$ally and substantially attaining the minimax rate.
  arXiv  Detail & Related papers  (2022-05-14T18:03:48Z)
• Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression [35.78863301525758]
  We study a localized notion of uniform convergence known as an "optimistic rate" Our refined analysis avoids the hidden constant and logarithmic factor in existing results.
  arXiv  Detail & Related papers  (2021-12-08T18:55:00Z)
• 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)
• Learning Probabilistic Ordinal Embeddings for Uncertainty-Aware Regression [91.3373131262391]
  Uncertainty is the only certainty there is. Traditionally, the direct regression formulation is considered and the uncertainty is modeled by modifying the output space to a certain family of probabilistic distributions. How to model the uncertainty within the present-day technologies for regression remains an open issue.
  arXiv  Detail & Related papers  (2021-03-25T06:56:09Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)

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.