Study private query release with public data, reducing sample sizes.
problem Answering a wide range of statistical queries while maintaining privacy.
method Combines public and private samples to answer queries with differential privacy.
result Private and public sample complexities for different query classes.
Private estimation with public data reduces sample complexity.
problem Estimating private distributions with limited public data.
method Differentially private estimation with public data under constraints of pure or concentrated DP.
result Public data can significantly reduce private sample complexity for estimation.
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 method generates private synthetic data without domain size dependence.
problem Private synthetic data generation for unbounded query classes.
method Constructs a private synthetic data generator for privately PAC learnable query classes.
result Sample complexity independent of domain size for privately PAC learnable query classes.
Improved private sample complexity for answering classification queries.
problem Designing an algorithm to accurately answer classification queries while maintaining differential privacy.
method Formally studied in agnostic PAC model, derived new upper bound on private sample complexity.
result Improved private sample complexity bound for answering classification queries.
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.
We investigate the problems of identity and closeness testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing Differential Privacy to the individuals of the population. We describe an approach that yields sample-efficient differentially private testers for the…
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 d 2.5 ⋅ 2 log ∗ ∣ G ∣ d^{2.5} \cdot 2^{\log^*|G|} d 2.5 ⋅ 2 l o g ∗ ∣ G ∣ , improving d 2 d^2 d 2 factor. 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\).
Differentially private weighted sampling improves privacy while maintaining utility.
problem Ensuring privacy in datasets with key-value pairs while preserving analytical utility.
method Private Weighted Sampling (PWS) that ensures element-level differential privacy.
result Significant performance gains in key reporting and estimation accuracy compared to prior methods.
New private algorithms learn large-margin halfspaces efficiently.
problem Learning large-margin halfspaces with privacy constraints.
method Differentially private algorithms based on a new approach.
result Sample complexity depends only on the margin, not dimension.
The paper explores learning with a mix of private and public data while maintaining privacy.
problem Learning with a mix of private and public data while ensuring differential privacy.
method Designing a learning algorithm that satisfies differential privacy only with respect to private examples.
result A hypothesis class of VC-dimension d can be agnostically learned up to an excess error of α using only (roughly) d/α public examples and d/α^2 private labeled examples.
Improved locally private sparse estimation with multiple samples per user.
problem Challenges in high-dimensional locally private sparse estimation.
method Proposes a framework for user-level locally private sparse linear regression with multiple samples per user.
result Eliminates the dependency of dimensionality on error bounds, achieving tighter error bounds.
Private learner for halfspaces with efficient sample complexity.
problem Private learning of halfspaces over arbitrary domains.
method Differential privacy for center point location and its application to halfspace learning.
result Private halfspace learning with sample complexity p o l y ( d , 2 log ∗ ∣ X ∣ ) poly(d, 2^{\log^*|X|}) p o l y ( d , 2 l o g ∗ ∣ X ∣ ) . We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure ε ε ε -differential privacy [Dwork et al. TCC 2006] and approximate ( ε , δ ) (ε,δ) ( ε , δ ) -differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approxima…
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.
Proves exponential sample complexity separations in local differential privacy.
problem Sample complexity in locally private protocols.
method Connection between communication complexity and sample complexity, using specific lower bounds for two problems.
result Exponential separations between differentially private protocols.
Framework for private, noise-tolerant, and efficient learning algorithms.
problem Private and efficient learning of large-margin halfspaces in noisy environments.
method Simple framework using differential privacy and noise tolerance conditions.
result Noise-tolerant and private PAC learners for large-margin halfspaces with sample complexity independent of dimension.
Private optimization faster on interpolation problems with quadratic growth.
problem Private optimization in interpolation problems.
method Adaptive algorithm with improved sample complexity.
result Exponential improvement in private sample complexity for quadratic growth.
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.
PRESTIGE improves privacy in stochastic optimization by combining private sampling and CL.
problem Privacy leakage in stochastic optimizations for large-scale sensitive data.
method Introduces PRESTIGE, a robust stochastic optimization framework that combines private sampling and gradual curriculum learning.
result PRESTIGE achieves a good tradeoff between privacy preservation and robustness over baselines.
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.
Privacy affects how much data is needed for CVaR optimization.
problem Privacy constraints impact the effective sample size for CVaR optimization.
method Analyzes the privacy-relevant sample size and decomposes CVaR excess risk.
result The effective private tail sample size is εnτ, affecting CVaR learning rates.
New algorithm learns Gaussian mixtures privately with optimal sample complexity.
problem Learning parameters of Gaussian mixtures under differential privacy constraints.
method Differentially private algorithm based on Achlioptas and McSherry's approach.
result Sample complexity matches non-private algorithm up to lower order terms.
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 ALS method improves matrix completion with tighter rates and better privacy.
problem Differential privacy in matrix completion for user-level privacy.
method Joint differentially private ALS method with tighter sample complexity and privacy trade-offs.
result Achieves nearly optimal sample complexity and best privacy/utility trade-off.
Private method measures nonlinear correlations between data hosted across two entities.
problem Measuring nonlinear correlations between sensitive data hosted across multiple parties while preserving privacy.
method Differentially private estimator of distance correlation.
result First private estimator of nonlinear correlations in a multi-party setup.
New algorithm estimates Gaussian means and covariances efficiently and privately.
problem Estimating Gaussian parameters privately and efficiently.
method Differentially private preconditioner to transform arbitrary Gaussian samples.
result First polynomial-time, sample-efficient estimator for arbitrary Gaussian distributions.
Study differentially private methods for learning Hawkes processes.
problem Lack of thorough analysis on sample complexity for learning Hawkes processes parameters and releasing differentially private versions.
method Developed non-private and differentially private estimators for Hawkes processes parameters.
result Obtained sample complexity results for both private and non-private settings.
Private algorithms minimize population loss with optimal rate.
problem Private optimization of convex functions with stochastic samples.
method Differentially private algorithms based on algorithmic stability.
result Optimal rate of 1 / n 1/\sqrt{n} 1/ n for population loss. Optimal private tests for simple hypotheses are characterized.
problem Private testing of simple hypotheses under differential privacy constraints.
method Characterization of sample complexity and optimal tests using log-likelihood ratio tests.
result Optimal sample complexity achieved by a specific randomized and clamped variant of the log-likelihood ratio test.
New method for differentially private optimization with general Lipschitz conditions.
problem Differentially private optimization under general Lipschitz conditions.
method Generalized Lipschitz condition for per-sample gradients, tuning clip norm based on minimum per-sample Lipschitz constant.
result Efficacy of the recommended clip norm tuning method verified on 8 datasets.
Proposes a framework for private data augmentation in federated learning.
problem Privacy and performance issues in non-IID training datasets.
method Multi-hop federated augmentation with sample compression.
result Significantly improves privacy, transmission delay, and local training performance.
New lower bounds for private covariance estimation of Gaussian distributions are proven.
problem Proving tight lower bounds for private estimation tasks under differential privacy.
method Generalized fingerprinting method for exponential families and private Assouad method.
result Tight lower bounds for private covariance estimation in Frobenius and spectral norms.
Paper analyzes InstaHide's security, recovering all private images with provable guarantee.
problem Protecting privacy of training data in neural networks.
method Unified framework to understand and analyze attacks on InstaHide, presenting a new algorithm to recover all private images with provable guarantee.
result InstaHide is computationally secure but not information-theoretically secure when mixing two private images.
Differentially private statistical inference using β β β -divergence.
problem Achieving differential privacy without altering data generation.
method Sampling from a generalised posterior minimizing β β β -divergence. result More precise inference with broader applicability.
Improved sample efficiency for private learning of Gaussian mixtures.
problem Learning mixtures of Gaussians with differential privacy.
method Inverse sensitivity mechanism, sample compression, sumset volume bounds.
result Proved optimal sample complexity for private learning of mixtures of Gaussians.
Locally private Gaussian estimation tackles privacy in i.i.d. sample mean estimation.
problem Estimating the mean of an unknown Gaussian distribution while maintaining local differential privacy for each user.
method Adaptive two-round and nonadaptive one-round solutions for locally private Gaussian estimation.
result Upper bounds partially match with information-theoretic lower bounds, showing tightness up to logarithmic factors.
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.
Algorithm selects private hypothesis from unknown distribution.
problem Private selection of hypothesis from unknown distribution.
method Differentially private algorithm for hypothesis selection.
result Sample complexity of O ( log m α 2 + log m α ε ) O(\frac{\log m}{α^2} + \frac{\log m}{α\varepsilon}) O ( α 2 l o g m + α ε l o g m ) . 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.
Efficiently estimates Gaussian distributions privately and robustly.
problem Private and robust estimation of Gaussian distributions.
method Efficient algorithms for pure and approximate differential privacy models.
result Optimal sample complexity in both pure and approximate differential privacy settings.
Differentially private policy evaluation improves reinforcement learning efficiency.
problem Sample inefficiency in reinforcement learning.
method Differentially private actor-critic model initialization.
result Improves sample efficiency in control problems.
Study public-data assisted private stochastic optimization with labeled or unlabeled public data.
problem Limits and capability of public-data assisted differentially private (PA-DP) algorithms in stochastic convex optimization.
method Lower bounds for PA-DP mean estimation and novel methods for leveraging public data in private supervised learning.
result Achieved dimension independent rate for GLM with unlabeled public data, showing optimality.
Privacy-preserving binary classification using locally differential private data.
problem Classifying data while protecting individual privacy.
method Locally differential private mechanism followed by a universally consistent classifier.
result Minimax rates of convergence are slower when using private data.
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.
Efficiently private clustering algorithms with tight approximation ratios.
problem Differentially private clustering of various types.
method Efficient algorithms achieving tight approximation ratios for clustering problems.
result Achieves approximation ratios similar to non-private algorithms with small additive errors.
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.