On the Robustness of CountSketch to Adaptive Inputs

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer

نتاج البحث: نشر في مجلةمقالة من مؤنمرمراجعة النظراء


The last decade saw impressive progress towards understanding the performance of algorithms in 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 CountSketch, a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering l2-heavy hitters of a vector (entries with (Eqaution presented)). 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 √k (for k heavy hitters) over prior "blackbox" approaches.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)4112-4140
عدد الصفحات29
دوريةProceedings of Machine Learning Research
مستوى الصوت162
حالة النشرنُشِر - 2022
الحدث39th International Conference on Machine Learning, ICML 2022 - Baltimore, الولايات المتّحدة
المدة: ١٧ يوليو ٢٠٢٢٢٣ يوليو ٢٠٢٢

All Science Journal Classification (ASJC) codes

  • !!Artificial Intelligence
  • !!Software
  • !!Control and Systems Engineering
  • !!Statistics and Probability


أدرس بدقة موضوعات البحث “On the Robustness of CountSketch to Adaptive Inputs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا