论文标题
关于Countsketch的鲁棒性自适应输入
On the Robustness of CountSketch to Adaptive Inputs
论文作者
论文摘要
Countsketch是一种流行的维度降低技术，它使用随机线性测量将向量映射到较低的维度。该草图支持恢复向量的$ \ ell_2 $ -heavy击球手（带有$ v [i]^2 \ geq \ frac {1} {k} {k} {k} {k} \ | \ boldsymbol {v} \ |^2_2 $）的条目。我们研究了在自适应设置中草图的鲁棒性，其中输入向量可能取决于先前输入的输出。自适应设置在反馈或对抗攻击的过程中出现。我们表明，经典的估计器不健壮，可以通过草图大小的多个查询来攻击。我们提出了一个强大的估计器（对于稍微修改的草图），该估计器允许在草图大小中进行二次查询，这是$ \ sqrt {k} $（对于$ k $ heavy heaters）在先前工作中的改进因子。
CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized 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 study the robustness of the sketch in adaptive settings where input vectors may depend on the output from prior inputs. Adaptive settings arise in processes with feedback or with adversarial attacks. 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 work.
