Study learning and refutation in non-interactive LDP, showing sample complexity equivalence.
problem Characterize sample complexity for learning and refutation in non-interactive LDP.
method Characterize sample complexity for agnostic PAC learning in non-interactive LDP protocols.
result Optimal sample complexity for any concept class is captured by the approximate γ 2 γ_2 γ 2 ~norm of a natural matrix associated with the class. Interactive privacy mechanisms improve spectral density estimation under local differential privacy.
problem Estimating spectral density of Gaussian time series with local differential privacy constraints.
method Two-stage process: Laplace mechanism followed by privatized sample analysis.
result Interactive mechanisms achieve faster rates for spectral density estimation.
This work refines grid size selection for non-interactive private K K K -means clustering.
problem Choosing the optimal number of grids for privatized K K K -means clustering. method Proposes a refined grid-size selection rule to minimize expected deviation in the K-means objective function.
result The proposed strategy results in more accurate clustering compared to prior work, even under tight privacy budgets.
New methods test discrete distributions faster with local privacy constraints.
problem Testing discrete distributions under local differential privacy constraints.
method Efficient randomized algorithms and test procedures, both non-interactive and interactive.
result Faster separation rates in interactive privacy mechanisms.
Study local differential privacy methods for estimating power sums of discrete distributions.
problem Estimating non-linear functionals of discrete distributions under local differential privacy constraints.
method Interactive and non-interactive mechanisms for estimating power sums, with lower bounds provided.
result Achieves faster rates of estimation under certain conditions.
Paper addresses ERM in LDP, reducing sample complexity for smooth and convex losses.
problem Achieving error α in ERM with non-interactive LDP, especially for high-dimensional data.
method Developed algorithms using Bernstein polynomial and polynomial approximation techniques.
result For smooth and convex losses, sample complexity is linear in dimensionality.
New study shows non-interactive privacy model requires exponentially more data.
problem Privacy constraints limit data analysis efficiency.
method Developed new technique to prove lower bounds on data samples needed.
result Exponential lower bound on samples needed for learning tasks.
In this paper, we study the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. In the case of constant or low dimensionality ( p ≪ n p\ll n p ≪ n ), we first show that if the ERM loss function is ( ∞ , T ) (\infty, T) ( ∞ , T ) -smooth, then we can avoid a dependence of the sample complexity, to achieve e…
New method reduces communication in distributed learning, improving privacy and utility.
problem Distributed learning with minimal communication and privacy protection.
method Non-interactive blind model averaging (BlindAvg) with output perturbation.
result BlindAvg converges to centralized learning with strong L2-regularization and SoftmaxReg for better privacy-utility tradeoff.
New method uses public data to achieve optimal nonparametric classification with privacy constraints.
problem Optimal nonparametric classification under local differential privacy constraints.
method Locally differentially private classification tree with data-driven pruning.
result Achieves mini-max optimal convergence rate with public data.
Optimal testing for densities under local differential privacy constraints.
problem Testing goodness-of-fit for densities under privacy constraints.
method Estimation of quadratic distance and minimax separation rates.
result First minimax optimal test under local differential privacy constraints.
The paper addresses hypothesis selection with local differential privacy, requiring more samples than non-private methods.
problem Hypothesis selection under local differential privacy constraints.
method Develops algorithms for hypothesis selection with local differential privacy, achieving near-optimal sample and round complexities.
result Non-interactive algorithms for k k k -wise simple hypothesis testing require O ~ ( k ) \tilde O(k) O ~ ( k ) samples and O ( log log k ) O(\log \log k) O ( log log k ) rounds of interaction. Paper improves GLM estimation in NLDP model with public unlabeled data.
problem Estimating smooth GLMs in NLDP model with public unlabeled data.
method Presented ( ϵ , δ ) (\epsilon, \delta) ( ϵ , δ ) -NLDP algorithms for GLMs using Stein's lemma and public/unlabeled data. result Significant improvement in sample complexity for GLM estimation.
We consider learning under the constraint of local differential privacy (LDP). For many learning problems known efficient algorithms in this model require many rounds of communication between the server and the clients holding the data points. Yet multi-round protocols are prohibitively slow in practice due to network …
The paper explores privacy-preserving methods for counting unique elements in distributed settings.
problem Counting unique elements in a distributed setting while maintaining privacy.
method Analyzes and proves lower bounds for differentially private protocols in various settings.
result Achieves optimal error bounds for multi-message shuffle protocols in estimating distinct elements.
Novel compression method preserves privacy while reducing communication costs.
problem Reducing communication costs in differential privacy mechanisms.
method Poisson private representation (PPR) for compressing and simulating local randomizers.
result Achieves compression within a logarithmic gap from theoretical lower bound.
Optimal locally private hypothesis selection with interactive rounds.
problem Locally private hypothesis selection under i.i.d. samples.
method Developed an ε-LDP algorithm using critical queries for hypothesis selection.
result Achieved optimal sample complexity of Θ(k/α²ε²) for hypothesis selection.
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.
Improves privacy amplification by shuffling for differential privacy.
problem Enhancing privacy guarantees in systems with anonymous data contributions.
method Theoretical and numerical analysis of Rényi differential privacy parameters and privacy amplification by shuffling.
result First asymptotically optimal analysis of Rényi differential privacy parameters for shuffled outputs.
Differential privacy has emerged as a gold standard in privacy-preserving data analysis. A popular variant is local differential privacy, where the data holder is the trusted curator. A major barrier, however, towards a wider adoption of this model is that it offers a poor privacy-utility tradeoff. In this work, we add…
New method recovers graph latent positions under edge differential privacy.
problem Recovering latent graph information from privatized graphs.
method Applying geometric insights to adjust statistical inference for privatized graphs.
result Achieves consistent recovery of latent positions under local edge differential privacy constraints.
Paper tackles privacy-preserving data density issues using deconvolution.
problem Privacy-preserving noise affects data density, leading to under/over-estimation.
method Develops deconvoluting kernel density estimators and regression models.
result Demonstrates improved accuracy in estimating heavy-hitters with locally differential data.
Data processing inequalities link Fisher information to local differential privacy constraints.
problem Understanding how Fisher information scales with local differential privacy constraints.
method Developed data processing inequalities for Fisher information under local differential privacy.
result Implications for private estimation with optimal bounds and error rates.
This work improves local differential privacy by considering context to make it more effective.
problem Local differential privacy often sacrifices utility, especially for sensitive data.
method Introduces context-aware local differential privacy, optimizing privacy and utility.
result Contextual information can reduce the number of samples needed for privacy compared to classical LDP.
This paper improves privacy accounting in decentralized FL using f-Differential Privacy.
problem Challenges in accurately quantifying privacy budget in decentralized FL.
method Develops two new f-DP-based accounting methods for decentralized FL.
result Yields tighter (ε,δ) bounds and improved utility compared to existing methods.
LDP is equivalent to contraction of E_γ-divergence, impacting privacy and utility.
problem Analyzing trade-offs between privacy and utility in estimation problems.
method Equivalence of LDP constraints to contraction coefficients of E_γ-divergence, using f-divergences and estimation-theoretic tools.
result LDP guarantees can be expressed in terms of contraction coefficients of arbitrary f-divergences.
Noise-aware Bayesian inference framework for locally private data collection.
problem Privacy-preserving data collection with non-trustworthy aggregators.
method Noise-aware probabilistic modeling framework for Bayesian inference under LDP.
result Demonstrated efficacy in parameter estimation for various distributions and regression models.
Paper tackles federated learning with privacy, enhancing target data analysis.
problem Heterogeneity and privacy of distributed data in federated learning.
method Formulates federated differential privacy, studies statistical problems under privacy constraints.
result Federated differential privacy offers a balance between privacy and knowledge transfer.
Locally private reinforcement learning protects individual environments from reverse engineering.
problem Protecting private information in distributed reinforcement learning environments.
method Locally differentially private algorithms that protect local agents' models from adversarial reverse engineering.
result Demonstrated that the proposed algorithm performs well under local differential privacy (LDP).
New bounds for LDP with heterogeneous privacy levels guaranteeing high probability of accuracy.
problem Statistical estimation under LDP with users having varying privacy levels.
method Developed finite sample upper bounds in ℓ_2-norm with high probability, complemented by lower bounds.
result Optimal guarantees for heterogeneous LDP in terms of probability and constants.
An exciting new development in differential privacy is the shuffled model, in which an anonymous channel enables non-interactive, differentially private protocols with error much smaller than what is possible in the local model, while relying on weaker trust assumptions than in the central model. In this paper, we stud…
New federated f f f -differential privacy for collaborative learning.
problem Privacy in federated learning.
method Introducing federated f f f -differential privacy and proposing a generic private federated learning framework. result Proves federated f f f -differential privacy provides privacy guarantee on each record of one client's data. Improved shuffling technique amplifies privacy guarantees for anonymous data contributions.
problem Enhancing privacy in systems where data is contributed anonymously.
method Developed a new approach to random shuffling that amplifies differential privacy guarantees.
result Achieved asymptotically optimal privacy amplification with nearly optimal dependence in ε.
Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe…
New method estimates discrete distributions while protecting privacy.
problem Estimating discrete distributions with local differential privacy.
method Combining robust learning and local differential privacy.
result Minimax estimation rate of ε d / α 2 k + d 2 / α 2 k n ε\sqrt{d/α^2 k}+\sqrt{d^2/α^2 kn} ε d / α 2 k + d 2 / α 2 k n under privacy constraint. The paper studies MAB problems with LDP to balance privacy and service quality.
problem Balancing privacy and service quality in multi-armed bandit systems.
method Investigates regret minimization for MAB with LDP guarantee, proving lower bounds and proposing matching upper bounds algorithms.
result Regret upper bounds match lower bounds up to constant factors for MAB algorithms with LDP guarantee.
We study E γ E_γ E γ -divergence contraction and its privacy implications.
problem Analyzing privacy in data processing and algorithms.
method Generalizing Dobrushin's coefficient to E γ E_γ E γ -divergence and deriving contraction coefficients. result Local differential privacy can be expressed in terms of E γ E_γ E γ -divergence contraction, leading to precise sample size reductions. Paper addresses privacy and robustness in stochastic linear bandits.
problem Stochastic linear bandits with differential privacy and adversarial robustness.
method Logarithmic batch queries, arm elimination algorithm, two privacy models.
result First algorithms providing differential privacy and adversarial robustness.
Paper proposes a federated learning method for quantile inference with local differential privacy.
problem Federated learning of quantile inference under local differential privacy constraints.
method Local stochastic gradient descent with randomized mechanism for privacy and efficiency.
result Asymptotic normality and functional central limit theorem for the proposed estimator.
This paper benchmarks privacy-preserving machine learning on medical images.
problem Ensuring privacy in medical image analysis while maintaining model accuracy.
method Comparing Local-DP and DP-SGD for differential privacy in medical imagery.
result Theoretical privacy guarantees do not fully align with real-world performance.
The paper proposes a fair and private decentralized deep learning framework.
problem Ensuring fairness and privacy in collaborative deep learning.
method A reputation system and differential privacy are used. FDPDDL framework is built with two stages: initialisation and update.
result FDPDDL achieves high fairness, comparable accuracy to centralised and distributed frameworks, and better accuracy than standalone.
Paper introduces input perturbation for privacy in machine learning models.
problem Protecting both training data and model parameters while maintaining privacy.
method Add noise to training data and train with perturbed data for differential privacy.
result Achieves (ε,δ)-differential privacy on the final model with privacy on original data.
New algorithm reduces privacy loss in SGD without learning rate tuning.
problem Locally differentially private stochastic optimization with high privacy loss.
method BANCO (Betting Algorithm for Noisy COins) for ε ε ε -LDP SGD. result Matches convergence rate of tuned SGD without learning rate tuning.
FedSel uses local differential privacy to protect data privacy in federated SGD.
problem Privacy leakage from gradients in federated SGD.
method Two-stage framework with top-k dimension selection and gradient accumulation.
result FedSel reduces privacy leakage by privately selecting important dimensions.
Paper improves privacy-accuracy balance in federated learning.
problem Privacy-accuracy tradeoffs in federated learning.
method Personalized federated learning with joint differential privacy.
result Coordination of local and centralized learning improves accuracy while maintaining privacy.
Paper optimizes privacy-preserving distribution estimation for sparse data.
problem Sparse distribution estimation under local differential privacy constraints.
method Compressive sensing approaches for privacy-preserving estimation.
result Significant reduction in sample complexity for approximately sparse distributions.
Paper addresses privacy in combinatorial semi-bandits with improved bounds.
problem Privacy-preserving learning in combinatorial semi-bandits with additional dimension dependence.
method Proposes novel algorithms and proves optimal regret bounds for LDP and DP settings.
result Achieves nearly optimal regret bounds for LDP and DP settings, matching non-private rates.
New methods protect privacy while providing accurate prediction sets.
problem Privacy-preserving conformal prediction for untrusted aggregators.
method Two LDP approaches: k-ary randomized response and binary search response.
result Finite-sample coverage guarantees and robust coverage under randomization.