What can we learn privately?
From MaRDI portal
Abstract: 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 contexts where aggregate information is released about a database containing sensitive information about individuals. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (non-private) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private PAC learner for the class of parity functions. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms.
Recommendations
Cites work
- A learning theory approach to noninteractive database privacy
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- Improved boosting algorithms using confidence-rated predictions
- Interactive privacy via the median mechanism
- On the complexity of differentially private data release, efficient algorithms and hardness results
- PAC-Bayesian stochastic model selection
- Pcps and the hardness of generating private synthetic data
- Theory of Cryptography
- Tracing traitors
- What can we learn privately?
Cited in
(only showing first 100 items - show all)- Differentially private nearest neighbor classification
- SPEED: secure, private, and efficient deep learning
- The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy
- Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint
- An incentive mechanism for trading personal data in data markets
- Distributionally-robust machine learning using locally differentially-private data
- Streaming submodular maximization under differential privacy noise
- Efficient and secure outsourcing of differentially private data publication
- Learning privately with labeled and unlabeled examples
- Locally differentially private item-based collaborative filtering
- Differentially private distance learning in categorical data
- Bounds on the sample complexity for private learning and private data release
- Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms
- Statistical active learning algorithms for noise tolerance and differential privacy
- Inferring ground truth from crowdsourced data under local attribute differential privacy
- Differentially private high dimensional sparse covariance matrix estimation
- A survey of privacy-preserving mechanisms for heterogeneous data types
- Submodular maximization over data streams with differential privacy noise
- Concurrent composition of differential privacy
- Covert learning: how to learn with an untrusted intermediary
- Order-revealing encryption and the hardness of private learning
- Simultaneous private learning of multiple concepts
- Learning with differential privacy: stability, learnability and the sufficiency and necessity of ERM principle
- Differentially-private learning of low dimensional manifolds
- Authentication in constrained settings
- Buying data from privacy-aware individuals: the effect of negative payments
- Large margin multiclass Gaussian classification with differential privacy
- What can we learn privately?
- Separating computational and statistical differential privacy in the client-server model
- Bounds on the sample complexity for private learning and private data release
- Sample complexity bounds on differentially private learning via communication complexity
- Distributed Private Data Analysis: Simultaneously Solving How and What
- A complete characterization of statistical query learning with applications to evolvability
- Fingerprinting codes and the price of approximate differential privacy
- Learners that use little information
- scientific article; zbMATH DE number 6860834 (Why is no real title available?)
- On the Power of Learning from k-Wise Queries
- Minimax Optimal Procedures for Locally Private Estimation
- Rejoinder
- Practical locally private heavy hitters
- Differential privacy on finite computers
- Finite sample differentially private confidence intervals
- Predictive learning on hidden tree-structured Ising models
- The complexity of differential privacy
- Private sequential learning
- On the measurement complexity of differentially private query answering
- scientific article; zbMATH DE number 7626777 (Why is no real title available?)
- Differentially private learning of geometric concepts
- HDDA: DataSifter: statistical obfuscation of electronic health records and other sensitive datasets
- Empirical risk minimization in the non-interactive local model of differential privacy
- scientific article; zbMATH DE number 7415075 (Why is no real title available?)
- Locally private \(k\)-means clustering
- Private selection from private candidates
- Private PAC learning implies finite Littlestone dimension
- Simultaneous private learning of multiple concepts
- scientific article; zbMATH DE number 7164746 (Why is no real title available?)
- Privacy aware learning
- Private data release via learning thresholds
- Submodular functions are noise stable
- Topics and Techniques in Distribution Testing: A Biased but Representative Sample
- Private and Online Learnability Are Equivalent
- Differentially-private learning of low dimensional manifolds
- An accurate, scalable and verifiable protocol for federated differentially private averaging
- Distribution-invariant differential privacy
- Adversarial manifold estimation
- Community detection in decentralized social networks with local differential privacy
- PAC learning halfspaces in non-interactive local differential privacy model with public unlabeled data
- Privacy amplification for wireless federated learning with Rényi differential privacy and subsampling
- Interactive versus noninteractive locally differentially private estimation: two elbows for the quadratic functional
- A novel privacy-preserving graph convolutional network via secure matrix multiplication
- Post-selection inference via algorithmic stability
- Differentially private inference via noisy optimization
- Differential privacy: getting more for less
- Local differentially private frequency estimation based on learned sketches
- Stochastic privacy-preserving methods for nonconvex sparse learning
- Optimal differentially private learning of thresholds and quasi-concave optimization
- Differentially private reinforcement learning
- Realizable learning is all you need
- Selective privacy-preserving framework for large language models fine-tuning
- On the privacy of noisy stochastic gradient descent for convex optimization
- General inferential limits under differential and pufferfish privacy
- On the impact of multi-dimensional local differential privacy on fairness
- Privacy-preserving Frank-Wolfe on shuffle model
- Locally covert learning
- Fine-filter: an effective defense against poisoning attacks on frequency estimation under LDP
- Enhancements of communication-efficient distributed statistical inference and its privacy preservation
- Private distribution testing with heterogeneous constraints: your epsilon might not be mine
- Adaptive conformal classification with noisy labels
- Tangent differential privacy
- Derivative-free optimization with transformed objective functions and the algorithm based on the least Frobenius norm updating quadratic model
- Differentially private sampling from distributions
- Private PAC learning may be harder than online learning
- Estimating smooth GLM in non-interactive local differential privacy model with public unlabeled data
- Differentially private Assouad, Fano, and Le Cam
- Infinitely divisible noise in the low privacy regime
- Channel simulation: theory and applications to lossy compression and differential privacy
- Noninteractive locally private learning of linear models via polynomial approximations
- Versatile differentially private learning for general loss functions
- Federated learning on Riemannian manifolds with differential privacy
- On distributed differential privacy and counting distinct elements
This page was built for publication: What can we learn privately?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3093624)
