36 citations · 176 across the 38 of their papers we have counts for
54 papers
Simpler Distribution Testing with Little Memory
Clément L. Canonne, Joy Qiping Yang
We consider the question of distribution testing (specifically, uniformity and closeness testing) in the streaming setting, \ie under stringent memory constraints. We improve on th…
Learning bounded-degree polytrees with known skeleton
Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya +1
We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesi…
Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine
Clément L. Canonne, Yucheng Sun
Private closeness testing asks to decide whether the underlying probability distributions of two sensitive datasets are identical or differ significantly in statistical distance, w…
Tight Bounds for Machine Unlearning via Differential Privacy
Yiyang Huang, Clément L. Canonne
We consider the formulation of "machine unlearning" of Sekhari, Acharya, Kamath, and Suresh (NeurIPS 2021), which formalizes the so-called "right to be forgotten" by requiring that…
Private Distribution Learning with Public Data: The View from Sample Compression
Shai Ben-David, Alex Bie, Clément L. Canonne +2
We study the problem of private distribution learning with access to public data. In this setup, which we refer to as public-private learning, the learner is given public and priva…
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, Jerry Li +2
We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samp…
Near-Optimal Degree Testing for Bayes Nets
Vipul Arora, Arnab Bhattacharyya, Clément L. Canonne +1
This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution over , given sample access to .…
Concentration Bounds for Discrete Distribution Estimation in KL Divergence
Clément L. Canonne, Ziteng Sun, Ananda Theertha Suresh
We study the problem of discrete distribution estimation in KL divergence and provide concentration bounds for the Laplace estimator. We show that the deviation from mean scales as…
Lemmas of Differential Privacy
Yiyang Huang, Clément L. Canonne
We aim to collect buried lemmas that are useful for proofs. In particular, we try to provide self-contained proofs for those lemmas and categorise them according to their usage.
Near-Optimal Bounds for Testing Histogram Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane +1
We investigate the problem of testing whether a discrete probability distribution over an ordered domain is a histogram on a specified number of bins. One of the most common tools…
Private independence testing across two parties
Praneeth Vepakomma, Mohammad Mohammadi Amiri, Clément L. Canonne +2
We introduce -test, a privacy-preserving algorithm for testing statistical independence between data distributed across multiple parties. Our algorithm relies on privately estim…
Robust Testing in High-Dimensional Sparse Models
Anand Jerry George, Clément L. Canonne
We consider the problem of robustly testing the norm of a high-dimensional sparse signal vector under two different observation models. In the first model, we are given i.i.d.…
Optimal Closeness Testing of Discrete Distributions Made (Complex) Simple
Clément L. Canonne, Yucheng Sun
In this note, we revisit the recent work of Diakonikolas, Gouleakis, Kane, Peebles, and Price (2021), and provide an alternative proof of their main result. Our argument does not r…
Independence Testing for Bounded Degree Bayesian Network
Arnab Bhattacharyya, Clément L. Canonne, Joy Qiping Yang
We study the following independence testing problem: given access to samples from a distribution over , decide whether is a product distribution or whether it is…
The Role of Interactivity in Structured Estimation
Jayadev Acharya, Clément L. Canonne, Ziteng Sun +1
We study high-dimensional sparse estimation under three natural constraints: communication constraints, local privacy constraints, and linear measurements (compressive sensing). Wi…
A short note on an inequality between KL and TV
Clément L. Canonne
The goal of this short note is to discuss the relation between Kullback--Leibler divergence and total variation distance, starting with the celebrated Pinsker's inequality relating…
Uniformity Testing in the Shuffle Model: Simpler, Better, Faster
Clément L. Canonne, Hongyi Lyu
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…
Optimal Rates for Nonparametric Density Estimation under Communication Constraints
Jayadev Acharya, Clément L. Canonne, Aditya Vikram Singh +1
We consider density estimation for Besov spaces when each sample is quantized to only a limited number of bits. We provide a noninteractive adaptive estimator that exploits the spa…
The Price of Tolerance in Distribution Testing
Clément L. Canonne, Ayush Jain, Gautam Kamath +1
We revisit the problem of tolerant distribution testing. That is, given samples from an unknown distribution over , is it -close to or $\varepsi…
Identity testing under label mismatch
Clément L. Canonne, Karl Wimmer
Testing whether the observed data conforms to a purported model (probability distribution) is a basic and fundamental statistical task, and one that is by now well understood. Howe…
Information-constrained optimization: can adaptive processing of gradients help?
Jayadev Acharya, Clément L. Canonne, Prathamesh Mayekar +1
We revisit first-order optimization under local information constraints such as local privacy, gradient quantization, and computational constraints limiting access to a few coordin…
Inference under Information Constraints III: Local Privacy Constraints
Jayadev Acharya, Clément L. Canonne, Cody Freitag +2
We study goodness-of-fit and independence testing of discrete distributions in a setting where samples are distributed across multiple users. The users wish to preserve the privacy…
Unified lower bounds for interactive high-dimensional estimation under information constraints
Jayadev Acharya, Clément L. Canonne, Ziteng Sun +1
We consider distributed parameter estimation using interactive protocols subject to local information constraints such as bandwidth limitations, local differential privacy, and res…
Interactive Inference under Information Constraints
Jayadev Acharya, Clément L. Canonne, Yuhan Liu +2
We study the role of interactivity in distributed statistical inference under information constraints, e.g., communication constraints and local differential privacy. We focus on t…