Timezone: »
Poster
On the Robustness of CountSketch to Adaptive Inputs
Edith Cohen · Xin Lyu · Jelani Nelson · Tamas Sarlos · Moshe Shechner · Uri Stemmer
The last decade saw impressive progress towards understanding the performance of algorithms in {\em adaptive} settings, where subsequent inputs may depend on the output from prior inputs. Adaptive settings arise in processes with feedback or with adversarial attacks. Existing designs of robust algorithms are generic wrappers of non-robust counterparts and leave open the possibility of better tailored designs. The lowers bounds (attacks) are similarly worst-case and their significance to practical setting is unclear. Aiming to understand these questions, we study the robustness of \texttt{CountSketch}, a popular dimensionality reduction technique that maps vectors to a lower dimension usingrandomized linear measurements. The sketch supports recovering $\ell_2$-heavy hitters of a vector (entries with $v[i]^2 \geq \frac{1}{k}\|\boldsymbol{v}\|^2_2$). We show that the classic estimator is not robust, and can be attacked with a number of queries of the order of the sketch size. We propose a robust estimator (for a slightly modified sketch) that allows for quadratic number of queries in the sketch size, which is an improvement factor of $\sqrt{k}$ (for $k$ heavy hitters) over prior "blackbox" 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 Room 309
More from the Same Authors
-
2023 Poster: Efficient Graph Field Integrators Meet Point Clouds »
Krzysztof Choromanski · Arijit Sehanobish · Han Lin · YUNFAN ZHAO · Eli Berger · Tetiana Parshakova · Qingkai Pan · David Watkins · Tianyi Zhang · Valerii Likhosherstov · Somnath Basu Roy Chowdhury · Kumar Avinava Dubey · Deepali Jain · Tamas Sarlos · Snigdha Chaturvedi · Adrian Weller -
2023 Poster: Concurrent Shuffle Differential Privacy Under Continual Observation »
Jay Tenenbaum · Haim Kaplan · Yishay Mansour · Uri Stemmer -
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 »
Aryeh Kontorovich · Menachem Sadigurschi · Uri Stemmer -
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 »
Aryeh Kontorovich · Menachem Sadigurschi · Uri Stemmer -
2022 Poster: Differentially Private Approximate Quantiles »
Haim Kaplan · Shachar Schnapp · 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 »
Haim Kaplan · Shachar Schnapp · 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