What Can We Learn Privately?

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in the contexts where aggregate information is released about a database containing sensitive information about individuals. We present several basic results that demonstrate general feasibility of private learning and relate several models previously studied separately in the contexts of privacy and standard learning.

• Publication year

  2008

• Venue

  2008 49th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2008-03-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/090756090arXiv 0803.0924
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Privacy Preserving Data Mining

  2015cited by this paper
• Differential privacy with compression

  2009cited by this paper
• Differential privacy and robust statistics

  2009cited by this paper
• On lattices, learning with errors, random linear codes, and cryptography

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

  2008influential reference
• A Statistical Framework for Differential Privacy

  2008cited by this paper
• Efficient, Differentially Private Point Estimators

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

  2008cited by this paper
• The Boundary Between Privacy and Utility in Data Publishing

  2007cited by this paper
• The price of privacy and the limits of LP decoding

  2007cited by this paper
• Pseudorandom Bits for Polynomials

  2007cited by this paper
• Stability of k -Means Clustering

  2007cited by this paper
• Towards Sharp Inapproximability For Any 2-CSP

  2007influential reference
• Privacy, accuracy, and consistency too: a holistic solution to contingency table release

  2007cited by this paper
• Smooth sensitivity and sampling in private data analysis

  2007cited by this paper
• A Sober Look at Clustering Stability

  2006cited by this paper
• Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol

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

  2006cited by this paper
• Our Data, Ourselves: Privacy Via Distributed Noise Generation

  2006cited by this paper
• Differential Privacy

  2006cited by this paper
• Privacy via pseudorandom sketches

  2006cited by this paper
• Stability of Randomized Learning Algorithms

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

  2005influential reference
• On lattices, learning with errors, random linear codes, and cryptography

  2005cited by this paper
• Toward efficient agnostic learning

  2004cited by this paper
• Generalization bounds for averaged classifiers

  2004cited by this paper
• A framework for high-accuracy privacy-preserving mining

  2004cited by this paper
• Bounded-concurrent secure multi-party computation with a dishonest majority

  2004cited by this paper
• Privacy-Preserving Datamining on Vertically Partitioned Databases

  2004influential reference
• More on Average Case vs Approximation Complexity

  2003cited by this paper
• Limiting privacy breaches in privacy preserving data mining

  2003cited by this paper
• Cryptographic Randomized Response Techniques

  2003cited by this paper
• Revealing information while preserving privacy

  2003cited by this paper
• New lower bounds for statistical query learning

  2002cited by this paper
• Almost-everywhere Algorithmic Stability and Generalization Error

  2002cited by this paper
• Stability and Generalization

  2002cited by this paper
• Randomized Response, Statistical Disclosure Control and Misclassificatio: a Review

  2002cited by this paper
• Privacy

  2002cited by this paper
• Stability and generalization

  2002cited by this paper
• On using extended statistical queries to avoid membership queries

  2002influential reference
• On the design and quantification of privacy preserving data mining algorithms

  2001influential reference
• On Using Extended Statistical Queries to Avoid Membership Queries

  2001cited by this paper
• Secure Human Identification Protocols

  2001cited by this paper
• Noise-tolerant learning, the parity problem, and the statistical query model

  2000cited by this paper
• Neural Network Learning: Theoretical Foundations

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

  1998influential reference
• Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation

  1997cited by this paper
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

  1994influential reference
• Efficient noise-tolerant learning from statistical queries

  1993influential reference
• On Learning Ring-Sum-Expansions

  1992cited by this paper
• Toward Efficient Agnostic Learning

  1992cited by this paper
• Learning Integer Lattices

  1992cited by this paper
• Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications

  1992cited by this paper
• Learning integer lattices

  1990cited by this paper
• Occam's Razor

  1987cited by this paper
• A theory of the learnable

  1984cited by this paper
• Distribution-free performance bounds for potential function rules

  1979cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper
• Randomized response: a survey technique for eliminating evasive answer bias.

  1965cited by this paper
• Probability inequalities for sum of bounded random variables

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

  1952cited by this paper
• on Lattices.

  year unknowncited by this paper

• Information Bottleneck-Based Subgraphs Defending Against Inference Attacks in Federated Graph Learning Systems

  2026cites this paper
• Fine-Grained Manipulation Attacks to Local Differential Privacy Protocols for Data Streams

  2026cites this paper
• Tighter privacy auditing of differentially private stochastic gradient descent in the hidden state threat model.

  2026cites this paper
• Enhancements of communication-efficient distributed statistical inference and its privacy preservation

  2026cites this paper
• Efficient privacy loss accounting for subsampling and random allocation

  2026cites this paper
• Secure, Verifiable, and Scalable Multi-Client Data Sharing via Consensus-Based Privacy-Preserving Data Distribution

  2026cites this paper
• How Entanglement Reshapes the Geometry of Quantum Differential Privacy

  2026cites this paper
• Learning with Locally Private Examples by Inverse Weierstrass Private Stochastic Gradient Descent

  2026cites this paper
• SoK: Enhancing Cryptographic Collaborative Learning with Differential Privacy

  2026cites this paper
• Randomized distributed function computation (RDFC): ultra-efficient semantic communication applications to privacy

  2026cites this paper
• Setup Protocols for Sender Anonymity

  2026cites this paper
• RAIN: Secure and Robust Aggregation under Shuffle Model of Differential Privacy

  2026cites this paper
• Your Privacy Depends on Others: Collusion Vulnerabilities in Individual Differential Privacy

  2026cites this paper
• PEGS: A Graph Synthesis Approach Based on Local Differential Privacy Preference

  2026cites this paper
• Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy

  2026cites this paper
• NOIR: Privacy-Preserving Generation of Code with Open-Source LLMs

  2026cites this paper
• Privacy Amplification for BandMF via $b$-Min-Sep Subsampling

  2026cites this paper
• SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics

  2026cites this paper
• Classification Under Local Differential Privacy with Model Reversal and Model Averaging

  2026cites this paper
• LabelDP Leaks Privacy — A Tightened Correlation-Aware Privacy Model for Labeled Training Data

  2026influential citation
• VPrivKV: Verifiable Local Differential Privacy for Key-Value Data

  2026cites this paper
• ALOG: Adaptive Longitudinal Grids for Geospatial Data using Local Differential Privacy

  2026cites this paper
• Hole-Free Differentially Private Multiparty Laplace Mechanism

  2026cites this paper
• LFS: A Locally Private Framework for Degree Statistic Estimation With Laplace Mechanism

  2026cites this paper
• We Should Separate Memorization from Copyright

  2026cites this paper
• Privately Learning Decision Lists and a Differentially Private Winnow

  2026cites this paper
• Concept-Aware Privacy Mechanisms for Defending Embedding Inversion Attacks

  2026influential citation
• Private Prediction via Shrinkage

  2026cites this paper
• Strategic Incentivization for Locally Differentially Private Federated Learning

  2025cites this paper
• Towards Privacy-preserving Photorealistic Self-avatars in Mixed Reality

  2025cites this paper
• Diffusion-Based Heterogeneous Graph Synthesis Under Local Differential Privacy

  2025cites this paper
• Estimating Group Means Under Local Differential Privacy

  2025cites this paper
• Communication-Efficient Publication of Sparse Vectors under Differential Privacy

  2025cites this paper
• Non-Asymptotic Analysis of Online Local Private Learning with SGD

  2025cites this paper
• PPFLQB: A Privacy-Preserving Federated Learning enhanced Quantum-secure Blockchain layered framework

  2025cites this paper
• Local Differential Privacy for Distributed Stochastic Aggregative Optimization with Guaranteed Optimality

  2025cites this paper
• An Attack-Agnostic Defense Framework Against Manipulation Attacks Under Local Differential Privacy

  2025cites this paper
• Analyzing and Enhancing LDP Perturbation Mechanisms in Federated Learning

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

  2025cites this paper
• Synthetic Tabular Data: Methods, Attacks and Defenses

  2025cites this paper
• Private List Learnability vs. Online List Learnability

  2025cites this paper
• Federated Learning for Heterogeneous Data Integration and Privacy Protection

  2025cites this paper
• SoK: Data Minimization in Machine Learning

  2025cites this paper
• Prink: ks-Anonymization for Streaming Data in Apache Flink

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

  2025influential citation
• A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPO

  2025influential citation
• Synopsis: Secure and private trend inference from encrypted semantic embeddings

  2025cites this paper
• Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation

  2025cites this paper
• Differentially Private Relational Learning with Entity-level Privacy Guarantees

  2025cites this paper
• Locally Differentially Private Trajectory Publication Based on Regional Popularity Awareness

  2025cites this paper
• Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates

  2025cites this paper
• Toward Multimodal Privacy in XR: Design and Evaluation of Composite Privatization Methods for Gaze and Body Tracking Data

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

  2025cites this paper
• Facility Location Problem Under Local Differential Privacy Without Super-Set Assumption

  2025cites this paper
• Bipartite Randomized Response Mechanism for Local Differential Privacy

  2025cites this paper
• Client Clustering Meets Knowledge Sharing: Enhancing Privacy and Robustness in Personalized Peer-to-Peer Learning

  2025cites this paper
• Practical and Accurate Local Edge Differentially Private Graph Algorithms

  2025cites this paper
• Private and Effective Range Counting Query Over Evolving Data in Internet of Things

  2025cites this paper
• Dynamic Data Release Based on Differential Privacy

  2025cites this paper
• Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy

  2025cites this paper
• Locally Differentially Private Thresholding Bandits

  2025cites this paper
• Necessity of Block Designs for Optimal Locally Private Distribution Estimation

  2025cites this paper
• Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy

  2025cites this paper
• Fine-grained Manipulation Attacks to Local Differential Privacy Protocols for Data Streams

  2025cites this paper
• Privacy-Preserving Conformal Prediction Under Local Differential Privacy

  2025cites this paper
• PrivFED: Protecting User Privacy in Federated Learning Systems Through Differential Privacy

  2025cites this paper
• Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation Under Differential Privacy

  2025cites this paper
• Differential Private Data Stream Analytics in the Local and Shuffle Models

  2025cites this paper
• PAUSE: Low-Latency and Privacy-Aware Active User Selection for Federated Learning

  2025cites this paper
• Differentially Private and Communication-efficient Decentralized Learning Using Deep Quantizers

  2025cites this paper
• Mitigating privacy risks in Retrieval-Augmented Generation via locally private entity perturbation

  2025cites this paper
• Multi-Class Item Mining Under Local Differential Privacy

  2025influential citation
• Verifiable Exponential Mechanism for Median Estimation

  2025cites this paper
• Leveraging Randomness in Model and Data Partitioning for Privacy Amplification

  2025cites this paper
• Revisiting Locally Differentially Private Protocols: Towards Better Trade-offs in Privacy, Utility, and Attack Resistance

  2025cites this paper
• Data Poisoning Attacks to Locally Differentially Private Range Query Protocols

  2025cites this paper
• Analysis, Design, and Implementation of a User-Friendly Differential Privacy Application

  2025cites this paper
• On Theoretical Limits of Learning with Label Differential Privacy

  2025cites this paper
• Poisoning Attacks to Local Differential Privacy Protocols for Trajectory Data

  2025cites this paper
• Privacy for Free: Leveraging Local Differential Privacy Perturbed Data from Multiple Services

  2025cites this paper
• PAUSE: Privacy-Aware Active User Selection for Federated Learning

  2025cites this paper
• PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors

  2025cites this paper
• Personalized Federated Training of Diffusion Models with Privacy Guarantees

  2025cites this paper
• Tree-based Models for Vertical Federated Learning: A Survey

  2025cites this paper
• Accelerating Differentially Private Federated Learning via Adaptive Extrapolation

  2025influential citation
• Improving Statistical Privacy by Subsampling

  2025cites this paper
• Dual Utilization of Perturbation for Stream Data Publication Under Local Differential Privacy

  2025cites this paper
• From Randomized Response to Randomized Index: Answering Subset Counting Queries with Local Differential Privacy

  2025cites this paper
• Heavy-Tailed Privacy: The Symmetric alpha-Stable Privacy Mechanism

  2025cites this paper
• Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems

  2025cites this paper
• Towards Trustworthy Federated Learning with Untrusted Participants

  2025cites this paper
• Cape: Context-Aware Prompt Perturbation Mechanism with Differential Privacy

  2025cites this paper
• Group fairness under obfuscated sensitive information

  2025cites this paper
• Locally Differentially Private Graph Clustering via the Power Iteration Method

  2025cites this paper
• Private Rate-Constrained Optimization with Applications to Fair Learning

  2025influential citation
• The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches

  2025cites this paper
• Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor

  2025cites this paper
• Differential Privacy Under Multiple Selections

  2025cites this paper
• PASS: Private Attributes Protection with Stochastic Data Substitution

  2025cites this paper
• Enhancing Metric Privacy With a Shuffler

  2025cites this paper