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, ארצות הברית
משך הזמן: 17 יולי 202223 יולי 2022
https://proceedings.mlr.press/v162/

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1702???
  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2200.2207???
  • ???subjectarea.asjc.2600.2613???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the Robustness of CountSketch to Adaptive Inputs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי