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.
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.
This work studies differential privacy in the context of the recently proposed shuffle model. Unlike in the local model, where the server collecting privatized data from users can track back an input to a specific user, in the shuffle model users submit their privatized inputs to a server anonymously. This setup yields…
Simpler, faster algorithm for uniformity testing in the shuffle model.
problem Testing uniformity of data in the shuffle model with privacy constraints.
method Simplified analysis and use of privacy amplification via shuffling.
result An algorithm with the same guarantees but simpler and more streamlined.
Develops shuffling gradient-based methods for nonconvex-concave minimax optimization.
problem Nonconvex-concave minimax optimization problems.
method Two shuffling gradient-based algorithms for nonconvex-linear and nonconvex-strongly concave settings.
result Achieves state-of-the-art oracle complexity in nonconvex optimization and best-known complexity bounds for nonconvex-strongly concave setting.
New shuffling methods improve convergence without Lipschitz smoothness.
problem Lack of convergence guarantees for shuffling methods under non-Lipschitz conditions.
method Revisit shuffling methods, prove convergence under general bounded variance condition.
result Matched current best-known convergence rates without Lipschitz smoothness.
New protocols improve privacy in counting and selection problems with multiple messages.
problem Improving privacy in counting and selection problems with multiple messages.
method Analyzed frequency estimation and selection problems in the shuffled model with multiple messages per user.
result Protocols with multiple messages achieve exponential improvements in error compared to single-message protocols.
SMG combines shuffling and momentum for non-convex optimization.
problem Non-convex finite-sum optimization problems.
method Shuffling Gradient-based method with momentum.
result Established state-of-the-art convergence rates for SMG.
A new algorithm improves convergence rates for convex optimization problems.
problem Convex optimization problems with finite-sum structure.
method Nesterov Accelerated Shuffling Gradient (NASG) integrating Nesterov's acceleration with different shuffling schemes.
result Improved convergence rate of O(1/T) for unified shuffling schemes.
When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then perform several epochs of training on the re-shuffled (either locally or globally) data. The above …
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 ε.
Unified analysis for shuffling-type gradient methods in optimization.
problem Optimization of finite-sum problems using shuffling strategies.
method Unified convergence analysis for various shuffling methods.
result Improved convergence rates for nonconvex problems and matching rates for convex problems.
A new method resolves permutation issues in shuffled linear regression for large-scale applications.
problem Estimating latent features through linear transformation with unknown permutations.
method Spectral matching method to align spectral components of measurement and feature covariances.
result Achieves accurate estimates in shuffled LS and LASSO settings with sufficient samples.
New neural model processes 2D data with long-range dependencies efficiently.
problem Limited receptive field of convolutions for complex 2D tasks.
method Proposes Matrix Shuffle-Exchange network with O ( log n ) \mathcal{O}( \log{n}) O ( log n ) layers and O ( n 2 log n ) \mathcal{O}( n^2 \log{n}) O ( n 2 log n ) complexity. result Exceeds convolutional and graph neural network baselines in long-range dependency modeling.
BUDS balances privacy and utility by shuffling data, achieving strong privacy with minimal loss.
problem Balancing privacy and utility in crowd-sourced statistical databases.
method One-hot encoding, iterative shuffling, loss estimation, risk minimization.
result Achieves ε = 0.02 ε= 0.02 ε = 0.02 for privacy, maintaining a privacy bound of ε = l n [ t / ( ( n 1 − 1 ) S ) ] ε= ln [t/((n_1 - 1)^S)] ε = l n [ t / (( n 1 − 1 ) S )] . New convergence rates for shuffling gradient methods without strong convexity.
problem Theoretical gap between shuffling gradient methods' empirical success and established convergence rates.
method Proved last-iterate convergence rates for shuffling gradient methods using function value gap.
result First last-iterate convergence rates for shuffling gradient methods without strong convexity.
Optimal SGD rates achieved with shuffling, covering non-convex and convex cases.
problem Optimizing finite-sum optimization problems with shuffling strategies.
method RandomShuffle and SingleShuffle algorithms for SGD, analyzing convergence rates.
result Minimax optimal convergence rates established, generalizing to non-convex costs.
SGD with random shuffling achieves lower optimization error than repeated shuffling.
problem Optimization of smooth and strongly-convex finite-sum problems.
method Lower bounds on SGD with random shuffling and repeated shuffling.
result Lower bounds on SGD with random shuffling and repeated shuffling reveal performance gaps.
In recent work, Cheu et al. (Eurocrypt 2019) proposed a protocol for n n n -party real summation in the shuffle model of differential privacy with O ε , δ ( 1 ) O_{ε, δ}(1) O ε , δ ( 1 ) error and Θ ( ε n ) Θ(ε\sqrt{n}) Θ ( ε n ) one-bit messages per party. In contrast, every local model protocol for real summation must incur error Ω ( 1 / n ) Ω(1/\sqrt{n}) Ω ( 1/ n ) , and there exist …
Power of network tests degrades when vertices are misaligned.
problem Power loss in network hypothesis testing due to vertex shuffling.
method Theoretical analysis and simulations of Frobenius norm differences in random dot product and stochastic block models.
result Shuffling vertices can significantly reduce the power of network tests.
Federated learning promises to make machine learning feasible on distributed, private datasets by implementing gradient descent using secure aggregation methods. The idea is to compute a global weight update without revealing the contributions of individual users. Current practical protocols for secure aggregation work…
Random shuffle method boosts HF dataset size 10-21 times.
problem Narrow dataset cardinality in HF clinical studies.
method Random shuffle method to enhance dataset size.
result Enhanced HF dataset size 10-21 times.
A novel RNN model with shuffled hidden states.
problem Improving recurrent neural network performance.
method Permuting hidden states and applying learned functions.
result Competitive results compared to literature baselines.
New convergence bounds for shuffling-based SGD methods in distributed learning.
problem Analyzing the performance of shuffling-based variants of SGD in distributed learning.
method Study of minibatch and local Random Reshuffling methods, proving convergence bounds and lower bounds.
result Shuffling-based variants converge faster than with-replacement sampling methods, and the bounds are tight.
We consider the problem of inference in a linear regression model in which the relative ordering of the input features and output labels is not known. Such datasets naturally arise from experiments in which the samples are shuffled or permuted during the protocol. In this work, we propose a framework that treats the un…
New method uses exponential family priors to handle shuffled data problems.
problem Handling mismatch errors in record linkage of two data files.
method Flexible exponential family prior on the permutation group for regularization.
result The proposed method outperforms competing methods in synthetic and real data.
Proposes methods to recover labels from shuffled networks using graph averages.
problem Recovering labels from a shuffled network using graph averages.
method Cluster networks into classes, then match the new graph to cluster-averages, minimizing the graph matching objective function.
result Higher fidelity matching performance when clustering networks into different classes.
New method to rank metrics on non-shuffled traffic.
problem Position bias in ranking metrics due to item display order.
method Leverage stochasticity of recommendation policy to mitigate position bias.
result Improved ranking metrics without shuffling recommendations.
Improved shuffling gradient methods converge faster for nonsmooth convex optimization.
problem Improving convergence rates for nonsmooth convex optimization problems.
method Analysis of shuffling gradient methods, focusing on Random Reshuffle and Single Shuffle strategies.
result Shuffling gradient methods, particularly Random Reshuffle and Single Shuffle, converge faster than Proximal Gradient Descent for nonsmooth convex optimization.
Balls-and-Bins sampling improves DP-SGD privacy and utility.
problem Improving privacy and utility in DP-SGD implementations.
method Introducing Balls-and-Bins sampling as an alternative to shuffling in DP-SGD.
result Balls-and-Bins sampling achieves utility comparable to shuffling while offering better privacy amplification.
Is it possible to perform linear regression on datasets whose labels are shuffled with respect to the inputs? We explore this question by proposing several estimators that recover the weights of a noisy linear model from labels that are shuffled by an unknown permutation. We show that the analog of the classical least-…
Enhanced financial reward with shuffled feature CNN-DRL.
problem Improving reward in financial data using CNN-DRL.
method Applying shuffled features to financial data for CNN-DRL.
result Substantial enhancement in reward attainment.
Paper improves privacy bounds for shuffle model using novel numerical techniques.
problem Improving privacy guarantees in the shuffle model of differential privacy.
method Develops and evaluates numerical techniques for tighter ( ε , δ ) (\varepsilon,δ) ( ε , δ ) -differential privacy bounds. result Accurately evaluates privacy loss distribution for adaptive compositions of shufflers.
New algorithms for private generalized linear contextual bandits.
problem Private estimation and optimization for generalized linear models under differential privacy.
method Developed algorithms for stochastic and adversarial contexts under shuffle and joint differential privacy.
result Achieved private regret bounds for generalized linear models, differing from non-private rates by factors of d / ε \sqrt{d/\varepsilon} d / ε and d / ε \sqrt{d/\varepsilon} d / ε respectively. Sampling without replacement speeds up optimization in minimax problems.
problem Optimizing minimax problems with faster convergence rates.
method Analysis of gradient descent ascent and proximal point method with two sampling strategies.
result Sampling without replacement leads to faster convergence rates in minimax optimization.
Paper proves privacy guarantees for shuffled and online PNSGD, reducing noise over time.
problem Privacy amplification in shuffled and online PNSGD settings.
method Iterative analysis of PNSGD with hidden updates, proving privacy guarantees for shuffled and online settings.
result Privacy guarantees for shuffled and online PNSGD with reduced noise over time.
This paper improves privacy bounds for DP algorithms using f f f -DP.
problem Difficulty in analyzing randomness in DP algorithms due to mixture distributions.
method Derives a closed-form expression for trade-off functions and analyzes f f f -DP. result Enhances privacy of DP-GD with random initialization and shuffling models.
The paper analyzes the variance of different shuffling methods in stochastic gradient descent.
problem Understanding the variance of different shuffling methods in stochastic gradient descent.
method Power spectral density analysis to study the noise sequences of stochastic gradients.
result The stationary variances of iterates decrease in the order of SGD, SGD-RR, and SGD-SO.
ShuffleNet is a state-of-the-art light weight convolutional neural network architecture. Its basic operations include group, channel-wise convolution and channel shuffling. However, channel shuffling is manually designed empirically. Mathematically, shuffling is a multiplication by a permutation matrix. In this paper, …
Proof of injection from double shuffle to Kashiwara-Vergne Lie algebra.
problem Injecting double shuffle Lie algebra into Kashiwara-Vergne Lie algebra.
method Inclusion of brunnian braids group on different genus 0 surfaces, using lower central series of brunnian Lie algebras, and explicit links between maps.
result Injection of double shuffle Lie algebra into symmetric Kashiwara-Vergne Lie algebra.
FLAME improves privacy in federated learning without trusted parties.
problem Ensuring privacy in federated learning without trusted parties.
method FLAME uses the shuffle model of differential privacy to achieve better accuracy and privacy.
result FLAME protocols improve testing accuracy by 60.7% compared to local model FL.
The paper explores how low-degree polynomials can detect shuffled linear regression models.
problem Detecting multivariate shuffled linear regression models from independent Gaussian random matrices.
method Investigates the effectiveness of low-degree polynomial algorithms for distinguishing the model from independent Gaussian random matrices.
result Establishes a phase transition phenomenon in the performance of low-degree polynomial algorithms for distinguishing the model.
WASH trains ensembles with shuffled weights to improve accuracy and reduce communication.
problem Training ensembles for weight averaging leads to models converging to different loss basins.
method WASH randomly shuffles a small percentage of weights during training to keep models within the same basin.
result WASH achieves state-of-the-art image classification accuracy with lower communication costs.
New method improves privacy of machine learning models using shuffling.
problem Maintaining privacy in machine learning models trained on large datasets.
method Recovering privacy guarantees for cyclic Stochastic Gradient Descent (SGD), a faster alternative to traditional SGD.
result Privacy guarantees for cyclic SGD are competitive with those for sampling with replacement.
Paper proposes a method to handle linear regression with partially shuffled data.
problem Linear regression with mismatched predictors and responses.
method Pseudo-likelihood approach based on two-component mixture densities with EM optimization.
result The method can tolerate larger fractions of mismatches and estimate noise level.
Study phase transitions in shuffled regression problems.
problem Phase transitions in shuffled regression problems.
method Transformed permutation recovery into probabilistic graphical model, used message passing (MP) algorithm and branching random walk process.
result Characterized impact of signal-to-noise-ratio ( $\snr$ ) on permutation recovery, proposed Gaussian approximation method.
Random Reshuffling outperforms Stochastic Gradient Descent in smooth convex optimization.
problem Theoretical limitations of Random Reshuffling in smooth convex optimization.
method Random Reshuffling (RR) as a variant of Shuffling Stochastic Gradient Descent (Shuffling SGD).
result Random Reshuffling (RR) dominates Stochastic Gradient Descent (SGD) in smooth convex optimization under any reasonable stepsize after any finite number of epochs.
Paper proposes protecting DNN models with secret key preprocessing.
problem Protecting deep learning models from unauthorized access.
method Block-wise pixel shuffling with secret key for preprocessing.
result Protected models maintain close performance to non-protected models with correct key, but accuracy drops significantly with incorrect key.