The Sampled Gaussian Mechanism's noise level decreases with larger subsampling rates, improving privacy-utility trade-offs.
problem Improving privacy-utility trade-offs in differentially private stochastic optimization.
method Proof of a conjecture about the Sampled Gaussian Mechanism's noise level and subsampling rate relationship.
result A rigorous proof of the conjecture, completing the proof of Theorem 6.2 in the original paper.
The paper improves privacy accounting for discrete-valued mechanisms and the subsampled Gaussian mechanism.
problem Improving the accuracy and efficiency of differential privacy accounting for discrete outputs.
method Uses fast Fourier transform (FFT) for rigorous error analysis and accounting of privacy loss.
result Provides strict lower and upper bounds for (ε,δ)-values, demonstrating up to 75% reduction in noise variance. We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the Rényi Differential Privacy (RDP) (Mironov, 2017) parameters for algorithms that: (1) subsamp…
New method audits DP guarantees without noise or subsampling info.
problem Auditing DP guarantees of ML models without prior info.
method Histogram-based density estimation for lower bounds.
result Natural generalization of membership inference auditing.
Unified framework for subsampling mechanisms with tighter privacy guarantees.
problem Improving privacy in machine learning models through subsampling.
method Conditional optimal transport for deriving mechanism-specific subsampling guarantees.
result Tighter privacy bounds for subsampled mechanisms compared to traditional methods.
New insights into privacy guarantees for subsampled mechanisms under composition.
problem Tight privacy guarantees for the composition of subsampled differentially private mechanisms.
method Addressed confusion points in privacy accounting for subsampled mechanisms, providing examples and counterexamples.
result Privacy guarantees for subsampled mechanisms differ significantly between Poisson subsampling and sampling without replacement.
The Sampled Gaussian Mechanism (SGM)---a composition of subsampling and the additive Gaussian noise---has been successfully used in a number of machine learning applications. The mechanism's unexpected power is derived from privacy amplification by sampling where the privacy cost of a single evaluation diminishes quadr…
A new Gaussian mechanism for differential privacy in the shuffle model is introduced.
problem Improving differential privacy in distributed learning environments.
method Characterization and upper-bounding of Rényi differential privacy (RDP) for the shuffle Gaussian mechanism.
result The shuffle Gaussian mechanism provides improved privacy guarantees compared to existing methods.
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.
In this paper we demonstrate that tempering Markov chain Monte Carlo samplers for Bayesian models by recursively subsampling observations without replacement can improve the performance of baseline samplers in terms of effective sample size per computation. We present two tempering by subsampling algorithms, subsampled…
In this paper, we study random subsampling of Gaussian process regression, one of the simplest approximation baselines, from a theoretical perspective. Although subsampling discards a large part of training data, we show provable guarantees on the accuracy of the predictive mean/variance and its generalization ability.…
Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guaran…
A two-stage GPR framework with automatic kernel search and subsampling improves prediction accuracy and efficiency.
problem Inaccurate predictions due to misspecified mean and kernel functions in Gaussian Process Regression.
method Two-stage GPR, automatic kernel search, subsampling for hyperparameter initialization.
result Competitive or better performance compared to full dataset training, robust on real-world datasets.
In this work we address the practical challenges of training machine learning models on privacy-sensitive datasets by introducing a modular approach that minimizes changes to training algorithms, provides a variety of configuration strategies for the privacy mechanism, and then isolates and simplifies the critical logi…
A new method tests independence for causal discovery on discrete data.
problem Inferring causal directions on discrete and categorical data.
method Subsampling-based method to test independence between cause and mechanism.
result Our method works for both discrete and categorical data without functional model assumptions.
A new Markov subsampling strategy based on Huber criterion improves data processing from noisy full data.
problem High noise level in data leads to poor performance of subsampling procedures.
method Design a Markov subsampling strategy based on Huber criterion to construct an informative subset from noisy full data.
result The estimator based on HMS is statistically consistent with a sub-Gaussian deviation bound.
Enhances random forest performance with exogenous randomness.
problem Improving random forest performance through exogenous randomness.
method Developed non-asymptotic MSE expansions for individual trees and forests, identified two types of randomness, and conducted simulations.
result Exogenous randomness, particularly feature subsampling, reduces both bias and variance of random forests.
New insights into how randomization affects greedy model selection.
problem Understanding the impact of feature subsampling on greedy model selection.
method Investigated greedy forward selection with feature subsampling, proving effects on bias and variance.
result Ensembling with feature subsampling reduces both bias and variance, unlike convex base learners.
A new method detects outliers using ensembles of Dirichlet process mixtures.
problem Challenges in unsupervised outlier detection using Dirichlet process mixtures.
method Ensembles of Dirichlet process Gaussian mixtures with random subspace and subsampling.
result Empirically outperforms existing approaches in unsupervised outlier detection.
We develop an iterative subsampling approach to improve the computational efficiency of our previous work on solution path clustering (SPC). The SPC method achieves clustering by concave regularization on the pairwise distances between cluster centers. This clustering method has the important capability to recognize no…
Proposes a new method for nonlinear Bayesian updates using ensemble kernel regression.
problem Nonlinear and non-Gaussian Bayesian updates for complex systems.
method Combines Kalman filtering for observed components and kernel density estimation for unobserved components, with subsampling and clustering.
result Reduces estimation errors in highly nonlinear scenarios compared to standard linear updates.
Statistical machine learning models should be evaluated and validated before putting to work. Conventional k-fold Monte Carlo Cross-Validation (MCCV) procedure uses a pseudo-random sequence to partition instances into k subsets, which usually causes subsampling bias, inflates generalization errors and jeopardizes the r…
Optimizes survey design for private mean estimation with reduced variance.
problem Minimizing variance in private mean estimation with privacy constraints.
method Formulates optimal survey design as an optimization problem, determining optimal subsampling sizes to minimize variance.
result Identifies the first privacy-aware stratified sampling scheme that minimizes variance under different privacy mechanisms.
Enhances privacy in federated learning with Laplacian smoothing.
problem Protecting data privacy in federated learning while maintaining model accuracy.
method Laplacian smoothing for differentially private federated learning (DP-Fed-LS).
result Improves model accuracy with differential privacy guarantee and membership privacy.
Differentially private (DP) machine learning has recently become popular. The privacy loss of DP algorithms is commonly reported using (ε,δ)-DP. In this paper, we propose a numerical accountant for evaluating the privacy loss for algorithms with continuous one dimensional output. This accountant can be appl…
A scalable algorithm for GP regression selects relevant covariates efficiently.
problem Scalable variable selection in large GP regression models.
method VGPR algorithm using Vecchia approximation for sparse precision matrix, mini-batch subsampling.
result Improved scalability and accuracy in selecting relevant covariates.
A fast algorithm for K-means clustering using subsampled SDP.
problem Efficiently solving large-scale K-means clustering problems. method Sketch-and-Lift (SL) approach for approximating SDP relaxed K-means. result SL method achieves similar exact recovery threshold as full SDP on full dataset.
This paper investigates the approximation power of three types of random neural networks: (a) infinite width networks, with weights following an arbitrary distribution; (b) finite width networks obtained by subsampling the preceding infinite width networks; (c) finite width networks obtained by starting with standard G…
Combines public and private data for better statistical estimation.
problem Estimating aggregate statistics from mixed data with varying privacy needs.
method Mixed estimators optimized for minimizing variance or median, using differential privacy techniques.
result Our mechanisms often outperform baseline methods in empirical tests.
The paper discusses a pooling mechanism to induce subsampling in graph structured data and introduces it as a component of a graph convolutional neural network. The pooling mechanism builds on the Non-Negative Matrix Factorization (NMF) of a matrix representing node adjacency and node similarity as adaptively obtained …
Ensemble methods that average over a collection of independent predictors that are each limited to a subsampling of both the examples and features of the training data command a significant presence in machine learning, such as the ever-popular random forest, yet the nature of the subsampling effect, particularly of th…
A new method selects a representative subsample for efficient kernel density estimation.
problem Selecting a representative subsample without model assumptions.
method Optimal transport techniques for model-free subsampling with an efficient algorithm.
result The selected subsample can be used for efficient density estimation with derived convergence rates and optimal bandwidth.
New mechanisms improve differential privacy for scalar queries.
problem Improving differential privacy for scalar, real-valued query functions.
method Mixing multiple Gaussian distributions to satisfy differential privacy.
result Mechanisms yield lower noise amplitudes and variances compared to the analytic Gaussian mechanism.
This paper optimizes subsampling for large datasets using Poisson distribution.
problem Efficiently subsample large datasets for quasi-likelihood estimation.
method Derives optimal Poisson subsampling probabilities and develops a distributed subsampling framework.
result Consistent and asymptotically normal estimators are obtained.
The Gaussian mechanism is an essential building block used in multitude of differentially private data analysis algorithms. In this paper we revisit the Gaussian mechanism and show that the original analysis has several important limitations. Our analysis reveals that the variance formula for the original mechanism is …
Expands differential privacy mechanisms to include the Generalized Gaussian mechanism for improved private machine learning.
problem Improving privacy in machine learning algorithms while maintaining utility.
method Introduces and analyzes the Generalized Gaussian (GG) mechanism for differential privacy.
result The GG mechanism provides better performance than the Laplace and Gaussian mechanisms across various values of β.
Large sample size brings the computation bottleneck for modern data analysis. Subsampling is one of efficient strategies to handle this problem. In previous studies, researchers make more fo- cus on subsampling with replacement (SSR) than on subsampling without replacement (SSWR). In this paper we investigate a kind of…
A significant hurdle for analyzing large sample data is the lack of effective statistical computing and inference methods. An emerging powerful approach for analyzing large sample data is subsampling, by which one takes a random subsample from the original full sample and uses it as a surrogate for subsequent computati…
New coherence parameter for GNNs with Fourier measurements improves signal recovery.
problem Characterizing generative compressed sensing with Fourier measurements.
method Subspace counting arguments and high-dimensional probability theory.
result First known restricted isometry guarantee for generative compressed sensing with subsampled isometries.
A new model-free subsampling method using uniform designs is proposed.
problem Model-based subsampling methods are often dependent on model assumptions.
method Developed a criterion (GEFD) and a model-free subsampling method based on uniform designs.
result The proposed method outperforms random sampling and is robust under diverse model specifications.
A new method reduces variance in SGMCMC by preferentially subsampling data.
problem High variance in stochastic gradient estimates impacts sampler performance.
method Use a non-uniform probability distribution to preferentially subsample data points and adaptively adjust subsample size.
result Maintains accuracy while substantially reducing average subsample size.
For massive data, the family of subsampling algorithms is popular to downsize the data volume and reduce computational burden. Existing studies focus on approximating the ordinary least squares estimate in linear regression, where statistical leverage scores are often used to define subsampling probabilities. In this p…
Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) is a momentum version of stochastic gradient descent with properly injected Gaussian noise to find a global minimum. In this paper, non-asymptotic convergence analysis of SGHMC is given in the context of non-convex optimization, where subsampling techniques are used o…
This paper assesses Gaussian and Exponential mechanisms for certifying adversarial robustness.
problem Certifying adversarial robustness using randomized smoothing mechanisms.
method Proposes a generic framework to assess the appropriateness of randomized smoothing mechanisms.
result Gaussian mechanism is an appropriate option for certifying both ℓ2-norm and ℓ∞-norm robustness. Group-equivariant subsampling layers improve CNNs' equivariance.
problem Non-translation equivariance in subsampling operations.
method Translation and group-equivariant subsampling/upsampling layers.
result Group-equivariant autoencoders learn equivariant representations.
Develops a method to optimize hyperparameters for subsampling methods.
problem Optimizing hyperparameters for subsampling methods to improve estimator efficiency.
method Careful theoretical analysis leading to an optimal choice of hyperparameters.
result Improves the statistical efficiency of subsampling estimators without extra CPU time.
New equivalences found between subsampling and ridge regularization methods.
problem Establishing precise structural and risk equivalences between subsampling and ridge regularization.
method Proved structural and risk equivalences between subsample ridge estimators and different ridge regularization levels and subsample aspect ratios.
result Optimally tuned ridge regression exhibits a monotonic prediction risk in the data aspect ratio.
Optimal Gaussian noise mechanisms achieve nearly optimal error in unbiased mean estimation.
problem Efficiently estimating the mean of high-dimensional data while preserving privacy.
method Differential privacy mechanisms with Gaussian noise, focusing on optimal covariance.
result Gaussian noise mechanisms achieve nearly optimal error among all private unbiased mean estimation mechanisms.