Timezone: »
Poster
On the Robustness of CountSketch to Adaptive Inputs
Edith Cohen · Xin Lyu · Jelani Nelson · Tamas Sarlos · Moshe Shechner · Uri Stemmer
\texttt{CountSketch} is a popular dimensionality reduction technique that maps vectors to a lower-dimension usinga randomized set of linear measurements. The sketch has the property that the $\ell_2$-heavy hitters of a vector (entries with $v_i^2 \geq \frac{1}{k}\|\boldsymbol{v}\|^2_2$ can be recovered from its sketch. We study the robustness of the sketch in adaptive settings, such as online optimization, where input vectors may depend on the output from prior inputs. We show that the classic estimator can be attacked with a number of queries of the order of the sketch size and propose a robust estimator that allows for quadratic number of queries. We improve robustness by a factor of $\sqrt{k}$ (for $k$ heavy hitters) over prior approaches.
Author Information
Edith Cohen (Google Research and Tel Aviv University)
Xin Lyu (University of California, Berkeley)
Jelani Nelson (UC Berkeley)
Tamas Sarlos (Google)
Moshe Shechner (Tel Aviv University)
Uri Stemmer (Tel Aviv University and Google Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: On the Robustness of CountSketch to Adaptive Inputs »
Thu. Jul 21st 06:50 -- 06:55 PM Room None
More from the Same Authors
-
2022 Poster: From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers »
Krzysztof Choromanski · Han Lin · Haoxian Chen · Tianyi Zhang · Arijit Sehanobish · Valerii Likhosherstov · Jack Parker-Holder · Tamas Sarlos · Adrian Weller · Thomas Weingarten -
2022 Spotlight: From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers »
Krzysztof Choromanski · Han Lin · Haoxian Chen · Tianyi Zhang · Arijit Sehanobish · Valerii Likhosherstov · Jack Parker-Holder · Tamas Sarlos · Adrian Weller · Thomas Weingarten -
2022 Poster: Adaptive Data Analysis with Correlated Observations »
Menachem Sadigurschi · Uri Stemmer · Aryeh Kontorovich -
2022 Poster: Private frequency estimation via projective geometry »
Vitaly Feldman · Jelani Nelson · Huy Nguyen · Kunal Talwar -
2022 Spotlight: Private frequency estimation via projective geometry »
Vitaly Feldman · Jelani Nelson · Huy Nguyen · Kunal Talwar -
2022 Spotlight: Adaptive Data Analysis with Correlated Observations »
Menachem Sadigurschi · Uri Stemmer · Aryeh Kontorovich -
2022 Poster: Differentially Private Approximate Quantiles »
Shachar Schnapp · Haim Kaplan · Uri Stemmer -
2022 Poster: FriendlyCore: Practical Differentially Private Aggregation »
Eliad Tsfadia · Edith Cohen · Haim Kaplan · Yishay Mansour · Uri Stemmer -
2022 Spotlight: FriendlyCore: Practical Differentially Private Aggregation »
Eliad Tsfadia · Edith Cohen · Haim Kaplan · Yishay Mansour · Uri Stemmer -
2022 Spotlight: Differentially Private Approximate Quantiles »
Shachar Schnapp · Haim Kaplan · Uri Stemmer -
2021 Poster: Differentially-Private Clustering of Easy Instances »
Edith Cohen · Haim Kaplan · Yishay Mansour · Uri Stemmer · Eliad Tsfadia -
2021 Spotlight: Differentially-Private Clustering of Easy Instances »
Edith Cohen · Haim Kaplan · Yishay Mansour · Uri Stemmer · Eliad Tsfadia -
2020 Poster: Composable Sketches for Functions of Frequencies: Beyond the Worst Case »
Edith Cohen · Ofir Geri · Rasmus Pagh -
2020 Poster: Stochastic Flows and Geometric Optimization on the Orthogonal Group »
Krzysztof Choromanski · David Cheikhi · Jared Quincy Davis · Valerii Likhosherstov · Achille Nazaret · Achraf Bahamou · Xingyou Song · Mrugank Akarte · Jack Parker-Holder · Jacob Bergquist · Yuan Gao · Aldo Pacchiano · Tamas Sarlos · Adrian Weller · Vikas Sindhwani -
2019 Poster: Differentially Private Learning of Geometric Concepts »
Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2019 Poster: Matrix-Free Preconditioning in Online Learning »
Ashok Cutkosky · Tamas Sarlos -
2019 Oral: Differentially Private Learning of Geometric Concepts »
Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer -
2019 Oral: Matrix-Free Preconditioning in Online Learning »
Ashok Cutkosky · Tamas Sarlos -
2019 Poster: Self-similar Epochs: Value in arrangement »
Eliav Buchnik · Edith Cohen · Avinatan Hasidim · Yossi Matias -
2019 Oral: Self-similar Epochs: Value in arrangement »
Eliav Buchnik · Edith Cohen · Avinatan Hasidim · Yossi Matias