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 »
\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.
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