Uniformity Testing in the Shuffle Model: Simpler, Better, Faster
Uniformity testing, or testing whether independent observations are uniformly distributed, is the prototypical question in distribution testing. Over the past years, a line of work has been focusing on uniformity testing under privacy constraints on the data, and obtained private and data-efficient algorithms under various privacy models such as central differential privacy (DP), local privacy (LDP), pan-privacy, and, very recently, the shuffle model of differential privacy. In this work, we considerably simplify the analysis of the known uniformity testing algorithm in the shuffle model, and, using a recent result on "privacy amplification via shuffling," provide an alternative algorithm attaining the same guarantees with an elementary and streamlined argument.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Connecting Robust Shuffle Privacy and Pan-Privacy
In the \emph{shuffle model} of differential privacy, data-holding users send randomized messages to a secure shuffler, the shuffler permutes the messages, and the resulting collection of messages must be differentially p…
$\ell_p$ Testing and Learning of Discrete Distributions
The classic problems of testing uniformity of and learning a discrete distribution, given access to independent samples from it, are examined under general $\ell_p$ metrics. The intuitions and results often contrast with…
FairnessTesting RadiX-Nets: Advances in Viable Sparse Topologies
The exponential growth of data has sparked computational demands on ML research and industry use. Sparsification of hyper-parametrized deep neural networks (DNNs) creates simpler representations of complex data. Past res…
Whitening-based Contrastive Learning of Sentence Embeddings
This paper presents a whitening-based contrastive learning method for sentence embedding learning (WhitenedCSE), which combines contrastive learning with a novel shuffled group whitening. Generally, contrastive learning …
Contrastive LearningDiversitySemantic Textual SimilaritySentence+4Random Shuffling Beats SGD after Finite Epochs
A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to…