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

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications. Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility. We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Optimal Sampling for Generalized Linear Model under Measurement Constraint with Surrogate Variables [3.5903555216741405]
  In some cases, surrogate variables are accessible across the entire dataset and can serve as approximations to the true response variable. We propose an optimal sampling strategy that effectively harnesses the available information from surrogate variables.
  arXiv  Detail & Related papers  (2025-01-01T22:41:52Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines. We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• 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)
• 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)

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.