Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning

• URL: http://arxiv.org/abs/2303.07152v1
• Date: Mon, 13 Mar 2023 14:26:27 GMT
• Title: Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning
• Authors: T. Tony Cai, Yichen Wang, Linjun Zhang
• Abstract summary: We propose a novel approach called the score attack, which provides a lower bound on the differential-privacy-constrained minimax risk of parameter estimation. It can optimally lower bound the minimax risk of estimating unknown model parameters, up to a logarithmic factor, while ensuring differential privacy for a range of statistical problems.
• Score: 8.760651633031342
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Achieving optimal statistical performance while ensuring the privacy of personal data is a challenging yet crucial objective in modern data analysis. However, characterizing the optimality, particularly the minimax lower bound, under privacy constraints is technically difficult. To address this issue, we propose a novel approach called the score attack, which provides a lower bound on the differential-privacy-constrained minimax risk of parameter estimation. The score attack method is based on the tracing attack concept in differential privacy and can be applied to any statistical model with a well-defined score statistic. It can optimally lower bound the minimax risk of estimating unknown model parameters, up to a logarithmic factor, while ensuring differential privacy for a range of statistical problems. We demonstrate the effectiveness and optimality of this general method in various examples, such as the generalized linear model in both classical and high-dimensional sparse settings, the Bradley-Terry-Luce model for pairwise comparisons, and nonparametric regression over the Sobolev class.

Related papers

• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• On the design-dependent suboptimality of the Lasso [27.970033039287884]
  We show that the Lasso estimator is provably minimax rate-suboptimal when the minimum singular value is small. Our lower bound is strong enough to preclude the sparse statistical optimality of all forms of the Lasso.
  arXiv  Detail & Related papers  (2024-02-01T07:01:54Z)
• Differentially Private Sliced Inverse Regression: Minimax Optimality and Algorithm [16.14032140601778]
  We propose optimally differentially private algorithms designed to address privacy concerns in the context of sufficient dimension reduction. We develop differentially private algorithms that achieve the minimax lower bounds up to logarithmic factors. As a natural extension, we can readily offer analogous lower and upper bounds for differentially private sparse principal component analysis.
  arXiv  Detail & Related papers  (2024-01-16T06:47:43Z)
• On the Statistical Complexity of Estimation and Testing under Privacy Constraints [17.04261371990489]
  We show how to characterize the power of a statistical test under differential privacy in a plug-and-play fashion. We show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence.
  arXiv  Detail & Related papers  (2022-10-05T12:55:53Z)
• Debiasing In-Sample Policy Performance for Small-Data, Large-Scale Optimization [4.554894288663752]
  We propose a novel estimator of the out-of-sample performance of a policy in data-driven optimization. Unlike cross-validation, our approach avoids sacrificing data for a test set. We prove our estimator performs well in the small-data, largescale regime.
  arXiv  Detail & Related papers  (2021-07-26T19:00:51Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning [78.83598532168256]
  Marginal-likelihood based model-selection is rarely used in deep learning due to estimation difficulties. Our work shows that marginal likelihoods can improve generalization and be useful when validation data is unavailable.
  arXiv  Detail & Related papers  (2021-04-11T09:50:24Z)
• Minimax Off-Policy Evaluation for Multi-Armed Bandits [58.7013651350436]
  We study the problem of off-policy evaluation in the multi-armed bandit model with bounded rewards. We develop minimax rate-optimal procedures under three settings.
  arXiv  Detail & Related papers  (2021-01-19T18:55:29Z)
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient [62.24615324523435]
  This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient.
  arXiv  Detail & Related papers  (2020-11-08T16:48:02Z)
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds [8.760651633031342]
  We show that the proposed algorithms are nearly rate-optimal by characterizing their statistical performance. The lower bounds are obtained via a novel technique, which is based on Stein's Lemma and generalizes the tracing attack technique for privacy-constrained lower bounds.
  arXiv  Detail & Related papers  (2020-11-08T04:27:21Z)
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation [49.502277468627035]
  This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history.
  arXiv  Detail & Related papers  (2020-02-21T19:20:57Z)

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.