New method for private density estimation of high-dimensional Gaussian mixtures.
problem Private density estimation for mixtures of unrestricted high-dimensional Gaussians.
method Exploits list global stability to prove upper bound on sample complexity.
result First upper bound on sample complexity for agnostic private density estimation.
Improved private agnostic learning with near-optimal sample complexity.
problem Private agnostic learning with arbitrary privacy parameters.
method Near-optimal sample complexity construction.
result Near-optimal extra sample complexity of \(\widetilde{O}(\mathrm{VC}(\mathcal{C})/α^2)\) for any \(\varepsilon \leq 1\).
We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC …
We consider learning problems where the training set consists of two types of examples: private and public. The goal is to design a learning algorithm that satisfies differential privacy only with respect to the private examples. This setting interpolates between private learning (where all examples are private) and cl…
Differentially private ensemble classifiers adapt to data streams while protecting privacy.
problem Adapting to evolving data characteristics while protecting private information.
method Unbounded ensemble updates, model agnostic approach.
result Outperforms competitors on various privacy, drift, and distribution settings.
Bounds on Littlestone dimension for private learning and online prediction.
problem Understanding the Littlestone dimension of composed classes for private learning.
method Deriving bounds on Littlestone dimension and transforming private learners.
result Improved bounds on sample complexity for private learning.
Study shows realizable learnability doesn't imply agnostic learnability for distributions.
problem Learnability and robustness of distribution classes.
method Analyzes the relationship between learnability and robustness for distribution learning.
result Realizable learnability does not imply agnostic learnability for distributions.
A framework for private causal effect estimation without structural assumptions.
problem Estimating causal effects from private observational data.
method Model-agnostic framework that privatizes predictions and aggregation steps.
result Maintains competitive performance under realistic privacy budgets.
Private distribution learning with public data, leveraging sample compression schemes.
problem Private distribution learning with public and private samples under differential privacy constraints.
method Connection to sample compression schemes and list learning.
result At least d public samples are necessary for private learnability of Gaussians in R^d.
New bounds for private learning of high-dimensional Gaussian distributions.
problem Learning high-dimensional Gaussian distributions under differential privacy constraints.
method Analytic tools for constructing global covers from local covers, modified hypothesis selection techniques.
result Near-optimal sample complexity bounds for general Gaussians, conjectured to be near-optimal in the general case.
New privacy-preserving learning model for mixtures of private and public data.
problem Learning from datasets with both private and public data, where privacy concerns differ.
method Designing a differential privacy-preserving learning algorithm for a mixture of private and public sub-populations.
result Linear classifiers can be learned with sample complexity comparable to non-private PAC-learning, even when privacy status correlates with labels.
Adversarial CCA improves representation learning by allowing more flexible priors.
problem Improving representation learning through more flexible priors.
method Adversarial techniques applied to Deep Variational CCA (VCCA and VCCA-Private).
result Adversarial CCA offers stronger and more flexible priors for representation learning.
Paper improves DP-ERM for binary linear classification with large-margin subsets.
problem Differentially private binary linear classification with large-margin subsets.
method Efficient (ε,δ)-DP algorithm with empirical zero-one risk bound. result Improved empirical zero-one risk bound for binary linear classification.
Privacy-preserving GNNs for graph data with sensitive node data.
problem Privacy concerns in learning node representations for graphs with sensitive data.
method Developed a privacy-preserving GNN learning algorithm based on Local Differential Privacy (LDP). Proposed an LDP encoder, an unbiased rectifier, and a denoising mechanism (KProp).
result Our method maintains a satisfying level of accuracy with low privacy loss.
Paper tightens privacy and generalization bounds for iterative learning.
problem Balancing privacy and generalization in iterative learning algorithms.
method Established alignment between generalization and privacy, derived composition theorems for iterative algorithms.
result Generalization bounds for iterative learning algorithms are strictly tighter than existing works.
New algorithms for privately learning decision lists and halfspaces.
problem Private learning of decision lists and halfspaces.
method Differentially private algorithms for PAC and online models.
result Private algorithms match or surpass non-private guarantees.
This paper studies trade-offs in private prediction methods.
problem Leakage of training data information in machine learning predictions.
method Private training and private prediction methods with trade-offs.
result Private training methods outperform private prediction methods in various settings.
First proper learning algorithm for Gaussian halfspaces with matching sample and computational complexity.
problem Agnostically learning halfspaces under Gaussian distribution.
method First proper learning algorithm with matching sample and computational complexity.
result First proper learning algorithm for agnostically learning halfspaces under Gaussian distribution with matching sample and computational complexity.
Private learning of Gaussian Mixture Models without boundedness assumptions.
problem Private estimation of parameters of Gaussian Mixture Models with unbounded components.
method Reduction to non-private problem, blackbox privatization, Moitra and Valiant's algorithm.
result First sample complexity upper bound and polynomial time algorithm for privately learning GMMs.
Private learning needs more data or better features.
problem Improving differentially private machine learning performance.
method Demonstrates the need for either more private data or better features.
result Private learning requires either more data or better features.
We study the relationship between the notions of differentially private learning and online learning in games. Several recent works have shown that differentially private learning implies online learning, but an open problem of Neel, Roth, and Wu \cite{NeelAaronRoth2018} asks whether this implication is {\it efficient}…
New findings show limitations in converting private learning to online learning efficiently.
problem Limitations in converting private learning to online learning efficiently.
method Assuming one-way functions, we show an efficient conversion from pure-private learners to online learners is impossible.
result Efficient conversion from pure-private learners to online learners is impossible under certain assumptions.
FedZKT enables resource-constrained devices to participate in federated learning with heterogeneous models.
problem Inequality in resource allocation hinders participation from resource-constrained devices in federated learning.
method Zero-shot knowledge transfer through a server-assigned distillation process.
result FedZKT effectively transfers knowledge across heterogeneous on-device models without requiring comparable local training efforts.
Efficiently learns private models using public data.
problem Improving private learning performance with public data.
method Proves computationally efficient algorithms for private learning with public data.
result First computationally efficient algorithms for private learning with public data.
Improved differentially private deep learning with group-wise clipping techniques.
problem Efficiency and privacy trade-offs in deep learning models.
method Group-wise clipping techniques (per-layer and per-device) to reduce compute time and memory overhead.
result Private learning with group-wise clipping achieves similar or better performance than non-private learning with less wall time.
Algorithm selects public datasets for private machine learning.
problem Choosing the most suitable public dataset for private machine learning.
method Measures gradient subspace distance between public and private datasets.
result Excess risk scales with the subspace distance between gradients.
Private learning can perform well in high dimensions, contrary to known results.
problem When does differentially private learning not suffer in high dimensions?
method Introduced a condition called restricted Lipschitz continuity to derive improved bounds for excess empirical and population risks.
result Gradients in private fine-tuning of large models are mostly controlled by a few principal components, similar to conditions for convex settings.
Public pretraining improves private model training even in extreme distribution shift scenarios.
problem Improving private model training accuracy in settings with large distribution shift.
method Empirical evaluation and theoretical explanation of public representations improving private training accuracy.
result Public representations can improve private training accuracy by up to 67% over private training from scratch in settings with large distribution shift.
Private PGB boosts synthetic data quality using GANs and privacy techniques.
problem Differentially private GANs struggle with convergence and poor output quality.
method Combines reweighted samples from GAN training using Private Multiplicative Weights method.
result Improves synthetic data quality across various datasets and tasks.
Study privacy and robustness in learning halfspaces, proving hard trade-offs.
problem Balancing privacy and robustness in learning halfspaces.
method Proves nearly tight bounds on sample complexity for robust private learning of halfspaces.
result Robust and private learning is harder than robust or private learning alone.
Paper develops a private algorithm for multi-agent learning in bandits.
problem Private cooperative learning in decentralized systems.
method Developed extsc{FedUCB} algorithm for multi-agent learning.
result Improves pseudoregret bounds and empirical performance.
New private algorithms for online learning improve regret in high privacy regimes.
problem Private online learning from experts and convex optimization.
method Transformed lazy algorithms for differential privacy.
result Improved regret bounds for DP-OPE and DP-OCO.
New private learning algorithms improve utility in tasks with public features.
problem Private learning with public features in recommendation and ad prediction.
method Developed algorithms that protect only certain sufficient statistics, improving utility for linear regression and private recommendation benchmarks.
result Achieved state-of-the-art performance on private recommendation benchmarks.
We establish a tight characterization of the worst-case rates for the excess risk of agnostic learning with sample compression schemes and for uniform convergence for agnostic sample compression schemes. In particular, we find that the optimal rates of convergence for size-k agnostic sample compression schemes are of…
The study optimizes polynomial regression for learning under Gaussian distributions.
problem Agnostic learning of Boolean and real-valued functions under Gaussian distributions.
method LP duality and polynomial degree analysis for L1-regression. result Optimal SQ lower bounds for various function classes.
Differentially private hyperparameter tuning improves privacy in machine learning.
problem Hyperparameter tuning leaks private information through selected configurations.
method Local Bayesian optimization using Gaussian Process surrogate for private gradient approximation.
result DP-GIBO converges to locally optimal hyperparameters with polynomial dimensional dependence.
Dynamic model considers private asset markets' complexities.
problem Understanding and optimizing private asset allocation.
method State-of-the-art dynamic model with machine learning.
result Optimal investment policies quantified over fund life.
New algorithm learns disjunctions faster than previous methods.
problem Learning Boolean disjunctions in the agnostic PAC model.
method Developed an agnostic learner with complexity 2ildeO(n1/3). result First separation between SQ and CSQ models in distribution-free agnostic learning.
DP-RandP improves privacy-utility tradeoff in DP-SGD by learning priors from random processes.
problem Improving the performance of differentially private stochastic gradient descent (DP-SGD) on private data.
method A three-phase approach that learns priors from images generated by random processes and transfers these priors to private data.
result New state-of-the-art accuracy on CIFAR10, CIFAR100, MedMNIST, and ImageNet for various privacy budgets.
New algorithms save computation in agnostic learning with membership queries.
problem Efficiently learning touchstone classes with membership queries.
method Designing agnostic learning algorithms for circuits with sublinear gates.
result Agnostic learning algorithms for circuits with sublinear gates achieve significant computational savings.
PriMORL trains private RL policies on offline data.
problem Private reinforcement learning on offline data.
method PriMORL learns DP models of the environment and optimizes a policy on the penalized private model.
result PriMORL enables training of private RL agents on complex tasks.
PILLAR improves SP learning with less private data.
problem Efficiently learning with semi-private data under privacy constraints.
method Uses pre-trained public data features to reduce private data requirements.
result Significantly lower private labelled sample complexity achieved.
Private learning is hard when data is long-tailed.
problem Achieving both privacy and fairness in machine learning with long-tailed data.
method Theoretical analysis and experimental validation on various datasets and algorithms.
result Relaxing overall accuracy can lead to good fairness even with strict privacy requirements.
We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension~d requires Ω(log∗(d)) examples. As a corollary it follows that the class of thresholds over N can not be learned in a private manner; this resolves open qu…
Paper introduces algorithms for private decision tree learning.
problem Private decision tree learning in distributed settings.
method Proposes DP-TopDown, NoisyCounts, and LocalRNM.
result First utility guarantees for private decision tree learning.
Optimizes differentially private kernel learning with random projection.
problem Privacy-preserving learning algorithms with optimal performance.
method Differentially private kernel ERM algorithm based on random projection in reproducing kernel Hilbert space.
result Achieves minimax-optimal excess risk rates for various loss functions.
Improved private learning of halfspaces with reduced sample complexity.
problem Private learning of halfspaces with reduced sample complexity.
method Iterative algorithm for solving linear feasibility problem, improving state-of-the-art results.
result Sample complexity reduced to d2.5⋅2log∗∣G∣, improving d2 factor. Motivation: Human genomic datasets often contain sensitive information that limits use and sharing of the data. In particular, simple anonymisation strategies fail to provide sufficient level of protection for genomic data, because the data are inherently identifiable. Differentially private machine learning can help b…