Bounds on the sample complexity for private learning and private data release

No abstract is available for this paper.

• Publication year

  2010

• Venue

  Machine-mediated learning

• Publication date

  2010-02-09

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/s10994-013-5404-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A learning theory approach to noninteractive database privacy

  2013cited by this paper
• Characterizing the sample complexity of private learners

  2013cited by this paper
• Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression.

  2012cited by this paper
• A firm foundation for private data analysis

  2011cited by this paper
• Sample Complexity Bounds for Differentially Private Learning

  2011cited by this paper
• On projective planes

  2010cited by this paper
• The Differential Privacy Frontier (Extended Abstract)

  2009cited by this paper
• On the complexity of differentially private data release: efficient algorithms and hardness results

  2009cited by this paper
• Differentially Private Empirical Risk Minimization

  2009cited by this paper
• A learning theory approach to non-interactive database privacy

  2008influential reference
• Privacy-preserving logistic regression

  2008cited by this paper
• A Note on Differential Privacy: Defining Resistance to Arbitrary Side Information

  2008cited by this paper
• What Can We Learn Privately?

  2008influential reference
• Pseudorandom Bits for Polynomials

  2007cited by this paper
• Privacy via pseudorandom sketches

  2006cited by this paper
• Calibrating Noise to Sensitivity in Private Data Analysis

  2006cited by this paper
• Practical privacy: the SuLQ framework

  2005influential reference
• Foundations of Cryptography: Volume 1, Basic Tools

  2001influential reference
• The Foundations of Cryptography - Volume 1: Basic Techniques

  2001cited by this paper
• Efficient noise-tolerant learning from statistical queries

  1998cited by this paper
• Eecient Noise-tolerant Learning from Statistical Queries

  1998cited by this paper
• An Introduction to Computational Learning Theory

  1994cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Learnability and the Vapnik-Chervonenkis dimension

  1989cited by this paper
• A general lower bound on the number of examples needed for learning

  1988cited by this paper
• Computational limitations on learning from examples

  1988cited by this paper
• A theory of the learnable

  1984influential reference
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper
• private communication

  1969cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

  2026cites this paper
• DP-FedPUAC: Federated learning with differential privacy via adaptive gradient clipping and local iteration optimization

  2026cites this paper
• Towards User-level Private Reinforcement Learning with Human Feedback

  2025cites this paper
• Differentially Private Federated Learning With Time-Adaptive Privacy Spending

  2025cites this paper
• Optimal Client Sampling in Federated Learning with Client-Level Heterogeneous Differential Privacy

  2025cites this paper
• An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

  2025cites this paper
• Statistical Inference for Differentially Private Stochastic Gradient Descent

  2025cites this paper
• Efficient Public Verification of Private ML via Regularization

  2025cites this paper
• ImprovDML: Improved Trade-off in Private Byzantine-Resilient Distributed Machine Learning

  2025cites this paper
• Optimal Pure Differentially Private Sparse Histograms in Near-Linear Deterministic Time

  2025cites this paper
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings

  2025cites this paper
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning

  2025cites this paper
• Differentially Private Federated Learning Model with Second-Order Optimization

  2025cites this paper
• Private Learning of Littlestone Classes, Revisited

  2025cites this paper
• Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time

  2025cites this paper
• Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity

  2025cites this paper
• Not All Learnable Distribution Classes are Privately Learnable

  2024cites this paper
• Investigating Privacy Attacks in the Gray-Box Setting to Enhance Collaborative Learning Schemes

  2024cites this paper
• Federated Transformer: Multi-Party Vertical Federated Learning on Practical Fuzzily Linked Data

  2024cites this paper
• Private PAC Learning May be Harder than Online Learning

  2024cites this paper
• Alternating minimization differential privacy protection algorithm for the novel dual-mode learning tasks model

  2024cites this paper
• DP-MTFL: Differentially Private Multi-Tier Federated Learning for IoT applications

  2024cites this paper
• Dp-graph2vec: Learning Differential Privacy Representations of Graphs

  2024cites this paper
• Efficiently Computing Similarities to Private Datasets

  2024cites this paper
• Replicability in High Dimensional Statistics

  2024cites this paper
• Dimension-free Private Mean Estimation for Anisotropic Distributions

  2024cites this paper
• The Limits of Differential Privacy in Online Learning

  2024influential citation
• On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

  2024cites this paper
• Subsampling is not Magic: Why Large Batch Sizes Work for Differentially Private Stochastic Optimisation

  2024cites this paper
• Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy

  2024cites this paper
• Learning with Impartiality to Walk on the Pareto Frontier of Fairness, Privacy, and Utility

  2023cites this paper
• Have it your way: Individualized Privacy Assignment for DP-SGD

  2023cites this paper
• From Robustness to Privacy and Back

  2023cites this paper
• Local differentially private federated learning with homomorphic encryption

  2023cites this paper
• Differentially-Private Deep Learning With Directional Noise

  2023cites this paper
• Challenges towards the Next Frontier in Privacy

  2023cites this paper
• Universal Neural-Cracking-Machines: Self-Configurable Password Models from Auxiliary Data

  2023cites this paper
• Confidence Intervals for Private Query Processing

  2023cites this paper
• Federated Learning with Reduced Information Leakage and Computation

  2023cites this paper
• DP-NMT: Scalable Differentially Private Machine Translation

  2023cites this paper
• On the Computational Complexity of Private High-dimensional Model Selection via the Exponential Mechanism

  2023cites this paper
• Privately Estimating a Gaussian: Efficient, Robust, and Optimal

  2023cites this paper
• Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD

  2023cites this paper
• Differentially Private Low-Rank Adaptation of Large Language Model Using Federated Learning

  2023cites this paper
• Federated Learning Privacy-preserving Method Based on Bregman Optimization

  2023cites this paper
• Less is More: Revisiting Gaussian Mechanism for Differential Privacy

  2023cites this paper
• Differential Privacy has Bounded Impact on Fairness in Classification

  2022cites this paper
• Private and Online Learnability Are Equivalent

  2022cites this paper
• Differentially Private Shapley Values for Data Evaluation

  2022influential citation
• PGPregel: an end-to-end system for privacy-preserving graph processing in geo-distributed data centers

  2022cites this paper
• Continual and Sliding Window Release for Private Empirical Risk Minimization

  2022cites this paper
• Fairness Certificates for Differentially Private Classification

  2022cites this paper
• Differential privacy: Review of improving utility through cryptography‐based technologies

  2022cites this paper
• Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization

  2022cites this paper
• How unfair is private learning? (Supplementary material)

  2022cites this paper
• How unfair is private learning ?

  2022cites this paper
• Algorithms with More Granular Differential Privacy Guarantees

  2022cites this paper
• Privacy-Enhanced Federated Learning: A Restrictively Self-Sampled and Data-Perturbed Local Differential Privacy Method

  2022cites this paper
• Privacy Amplification by Subsampling in Time Domain

  2022cites this paper
• DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy

  2022cites this paper
• Differential Privacy for Tensor-Valued Queries

  2022cites this paper
• Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning

  2022cites this paper
• A Deep Generative Model for Trajectory Modeling and Utilization

  2022cites this paper
• Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization

  2022cites this paper
• Privately Estimating a Gaussian: Efficient, Robust and Optimal

  2022cites this paper
• Private learning implies quantum stability

  2021cites this paper
• Is Private Learning Possible with Instance Encoding?

  2021cites this paper
• Quantum Private Distributed Learning Through Blind Quantum Computing

  2021cites this paper
• Universal Private Estimators

  2021cites this paper
• Analysis of Application Examples of Differential Privacy in Deep Learning

  2021cites this paper
• Shuffled Model of Differential Privacy in Federated Learning

  2021cites this paper
• Littlestone Classes are Privately Online Learnable

  2021cites this paper
• Differentially Private Nonparametric Regression Under a Growth Condition

  2021cites this paper
• Quantum federated learning through blind quantum computing

  2021cites this paper
• On the Sample Complexity of Privately Learning Axis-Aligned Rectangles

  2021cites this paper
• Private learning implies quantum stability

  2021cites this paper
• Differentially-Private Clustering of Easy Instances

  2021influential citation
• Privacy Amplification Via Bernoulli Sampling

  2021influential citation
• Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability

  2021cites this paper
• Matrix Gaussian Mechanisms for Differentially-Private Learning

  2021cites this paper
• Shuffled Model of Federated Learning: Privacy, Accuracy and Communication Trade-Offs

  2021cites this paper
• LDP-Fed: federated learning with local differential privacy

  2020cites this paper
• Near Instance-Optimality in Differential Privacy

  2020cites this paper
• Privacy Preserving Detection of Path Bias Attacks in Tor

  2020cites this paper
• Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling

  2020cites this paper
• Differential Privacy: a Survey

  2020cites this paper
• Adaptive Distributed Differential Privacy with SGD

  2020cites this paper
• An Attack on InstaHide: Is Private Learning Possible with Instance Encoding?

  2020cites this paper
• How to Democratise and Protect AI: Fair and Differentially Private Decentralised Deep Learning

  2020cites this paper
• Closure Properties for Private Classification and Online Prediction

  2020influential citation
• Differentially Private Deep Learning with Smooth Sensitivity

  2020cites this paper
• An Equivalence Between Private Classification and Online Prediction

  2020cites this paper
• Privately Learning Markov Random Fields

  2020cites this paper
• Quantum statistical query learning

  2020cites this paper
• Differentially Private Weighted Sampling

  2020cites this paper
• TiFL: A Tier-based Federated Learning System

  2020cites this paper
• Privacy Profiles and Amplification by Subsampling

  2020cites this paper
• Efficient and Privacy-Enhanced Federated Learning for Industrial Artificial Intelligence

  2020cites this paper
• A Computational Separation between Private Learning and Online Learning

  2020cites this paper
• On the Round Complexity of the Shuffle Model

  2020cites this paper