Timezone: »

 
Poster
On the Robustness of CountSketch to Adaptive Inputs
Edith Cohen · Xin Lyu · Jelani Nelson · Tamas Sarlos · Moshe Shechner · Uri Stemmer

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #624
in Poster Session 3 »
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.
Keywords: T: Everything Else · MISC: Scalable Algorithms · SA: Privacy-preserving Statistics and Machine Learning

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)

More from the Same Authors