Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
Authors: Edith Cohen
Mihir Singhal
Uri Stemmer
Venue: ICML 2025 poster (2025)
Keywords: Sketching
cardinality sketches
robustness to adaptive inputs
adaptive data analysis
differential privacy
Primary area: social_aspects->robustness
TL;DR: Design and analysis of cardinality sketches that are robust to adaptive inputs

Abstract: Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and computational costs. However, recent research has shown that these sketches can fail under {\em adaptively chosen queries}, breaking down after approximately $\tilde{O}(k^2)$ queries, where $k$ is the sketch size.
In this work, we overcome this \emph{quadratic barrier} by designing robust estimators with fine-grained guarantees. Specifically, our constructions can handle an {\em exponential number of adaptive queries}, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries {\em sharing the same element}, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
Edith Cohen 12
Mihir Singhal 31 Uri Stemmer 2
Abstract
V [n]] to their sketches S(V), and an estimator that processes the sketch S(U) and returns an approximation of the cardinality [U]. An important property of sketching maps is composability: The sketch S(U J V) of the union of two sets U and V can be computed directly from the sketches S(U) and S(V). Composability is crucial for most applications, particularly in distributed settings where data is generated and analyzed across multiple locations and times. To intuit why composition is necessary, note that it is not possible to obtain a cardinality estimate of U U V from separate cardinality estimates of U and V, since the sets may or may not overlap (the same key might occur in both sets). Therefore we must compose the sketches before applying an estimator.
Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimiz- ing storage, communication, and computational costs. However, recent research has shown that these sketches can fail under adaptively cho- sen queries, breaking down after approximately Ó(k²) queries, where is the sketch size. In this work, we overcome this quadratic barrier by de- signing robust estimators with fine- ann-ggri guar- antees. Specifically, our constructions can han- dle exponential number of adaptive queries, provided that each element participates in at most Ō(k²) queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries sharing the same ele- ment, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.
It is known that any sublinear composable cardinality sketch that is statistically guaranteed for all inputs must be random- ized (Kane et al., 2010). By this, we mean that the sketching map cannot be predetermined and must instead be sampled from a distribution. The guarantees are expressed in terms of the sketch size k: for any sequence of 20(k) queries, with high probability over the sampling of the map, all queries are estimated within small relative error.
1. Introduction
Cardinality sketches are extensively used in practice. Min- Hash sketches are composable sketches based on hash map- pings of keys to priorities, where the sketch of a set is determined by the minimum priorities of its elements (Fla- jolet & Martin, 1985; Flajolet et al., 2007: Cohen, 1997; Broder, 2000; Rosén, 1997; Cohen, 1997; Broder, 1997; Bar-Yossee Yossef et al., 2002)'. Most practical implementations" use MinHash sketches of various types, particularly bottom- k: and HyperL sketches (Flajolet et al., 2007; Heule et al., 2013). In many applications, a sketch is computed for each part of the data that reside in different locations and occurs in different time periods. The original data is often discarded. The estimates used for localized anal- ysis, where cardinality estimates are computed for disjoint datasets, but also for analysis that spans multiple locations and time horizons, which requires composability. To ensure composability, the same map must be used to sketch all
When dealing with massive datasets, compact summary structures (known sketches) allow us to drastically re- duce storage, communication, and computation while still providing useful approximate answers.
Cardinality sketches are specifically designed to estimate the number of distinet elements in a query set (Flajolet & Martin, 1985; Flajolet et al., 2007: Cohen, 1997; Alon et al., 1999; Bar- Yossef et al., 2002; Kane et al., 2010; Cohen, 2015; Blasiok, 2020). For ground set [n] of keys, sketch is defined by sketching map S that maps subsets
'Google Research "School of Computer Science, Tel Aviv University, Israel 'School of Computer Science, UC Berkeley, Berkeley, CA, USA. Correspondence to: Edith Cohen <edith @ wohenwang.com. hir.a.iinghal @ gmmil.com>, Uri Stemmer <u@uri.co.l>>.
Mihir Singhal <mi-
'For survey see (Cohen. 2008; 2023).
Proceedings of the 12nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
SSee, e.g., (Apache Software Foundation, Accessed: 2024; Google Cloud, Accessed: 2024).

---

Breaking the Quadratic Barrier
queries, and the guarantees of 20(k) queries hold provided that the queries do not depend on the sampled sketching map, which is known as the non-adaptive setting.
estimator.
For cardinality sketches, Reviriego & Ting (2020) and Pater- son & Raynal (2021) constructed Okk) attacks on the popular HLL sketch with its standard estimator. Ahmadian & Cohen (2024) constructed -kk))ssize attacks for popular MinHash sketching maps with their standard estimators, as well as a Ó(k2) )-ize universal attacks. Gribelyuk et al. (2024) presented polynomial
1.1. The adaptive setting
In the adaptive setting, we assume that the sequence of queries may be chosen adaptively based on previous interac- tions with the sketch. This arises naturally when a feedback loop causes queries to depend on prior outputs.
universal attacks on all linear sketching maps for cardinality estimation. Finally, Cohen et al. (2024) presented optimal D(k")-size univer- sal attacks on broad classes of union-composable or linear sketching maps." 3
The main challenge in the adaptive setting (compared to the non-adaptive setting) that the queries become correlated with the internal randomness of the sketch. This would not be an issue if the sketching algorithm were deterministic, but unfortunately, randomness is necessary.
To summarize, there are, essentially, matching upper and lower bounds of @(k²) on the number of adaptive cardinality queries that can be approximated using a sketch of size k. The upper bound is obtained from the generic wrapper of Hassidim et al. (2020), while the lower bound arises from the universal attack of Cohen et al. (2024). We refer to this limitation as the quadratic barrier.
Specifically, we consider a black-box interaction model, where the sketching map S is sampled once at the beginning and then fixed but hidden. The responder answers queries using this fixed map, but the map itself is not revealed. The adversary interacts with the sketch by submitting queries U and observing the corresponding cardinality estimates that the responder computes from S(U), and may adapt future queries based on previous outputs. This captures realistic settings where the sketch is reused across queries, and its internal randomness can potentially leak over time.
1.2. Per-key participation
Nevertheless, we can still hope for stronger data-dependent guarantees, and since cardinality sketches are widely used in practice, achieving this under realistic conditions im- portant. Specifically, we seek common properties of input queries such that, if these properties hold, we can guarantee accurate processing of t >>>>> k2 adaptive queries.
Hassidim al. (2020) presented a generic robustness wrap- per that transforms non-robust randomized sketch into more robust one. Informally, this wrapper uses differential privacy (Dwork et al., 2006) to obscure the internal ran- domness of the sketching algorithm, effectively breaking correlations between the queries and the internal random- ness.
We consider parameter r that is the per-key participation in queries. Current attack constructions are such that most keys are involved in large number of the queries and therefore r s t. However, in many realistic scenarios, the majority of keys participate in only a small number of queries and < 1. This pattern emerges when the distribution over the key domain shifts over time. For instance, the popu- larity of watched videos or browsed webpages can change over time, leading to changing set of access frequencies of keys. Additionally, even when the query distribution is fixed, this pattern is consistent with Pareto-distributed frequencies, where a small fraction of keys (the "heavy hit- ters") appear in most queries, while most keys appear in only limited number of queries. We therefore pose the following question:
In more detail, to support & adaptive queries, the wrapper of Hassidim et al. (2020) maintains approximately vi indepen- dent copies of the non-robust sketch and answers each query by querying all (or some) of these sketches and aggregating their responses. As Hassidim et al. (2020) showed, this results in a more robust (and composable) sketch, that can support queries in total at the cost of increasing the space complexity by a factor of s VT. Instantiating this wrapper with classical (non-robust) cardinality sketches results in sketch for cardinality estimation that uses space A R vi/a², where a is the accuracy parameter.
Lower bounds. Lower bounds on robustness are established by designing attacks in the form of adaptive sequences of queries. The objective of an attack to force the algorithm to fail. An attack is more efficient if it causes the algorithm to fail using smaller number of adaptive queries. We refer to the number of queries in the attack as the size of the attack, which is typically a function of the sketch size k. Some attacks are tailored to particular estimator, while others are universal in the sense that they apply to any
Question 1.1. Can we shift the quadratic barrier from the total number of queries i to the typically much smaller pa- rameter r. that is, can we design a robust (and composable) sketch of size k R3 /r instead of se VB?
'hhese attacks apply to any sketching map that satisfies some certain reasonability conditions and suggest that the quadratic bound is likely to apply generally.
2

---

Breaking the Quadratic Barrier
1.3. Results overview
map from keys to i.i.d. random priorities. The sketch BkSketcchV) of subset V includes the i keys with lowest priorities and their priority values. The standard car- dinality estimator for this sketch returns function of the highest priority in the sketch, which is a sufficient statistic for the cardinality. A sketch size of At = Max yields with high probability a relative error of + a. The standard estimator, however, can be compromised using an attack with &' Ō(k) queries (Ahmadian & Cohen, 2024). We present two robust estimators for the bottom-k sketch that are analyzed using our fine-grained SQ framework:
We provide an affirmative answer to Question I.1. Specifi- cally, we design sketch and estimator capable of handling an exponential number of adaptive queries provided that each key participates in at most = Ól2)) queries. We further provide an extension which maintain the guarantee even if this condition fails for a small fraction of the keys in each query.
Reformulating the robustness wrapper (Section 3). As we mentioned, the generic wrapper of Hassidim al. (2020) transforms non-robust sketches into more robust ones by ob- scuring their internal randomness using differential privacy. This effectively "reduces" the problem of designing a robust sketch to that of designing a suitable differentially private aggregation procedure. Our first contribution is to reformu- late this wrapper so that the reduction is not to differential privacy, but rather the problem of adaptive data analysis (ADA).
Basic Robust Estimator (Section 4). We present a stateless estimator and show that for a E (0, and ( all estimates are accurate with high prob- ability provided that all keys participate in no more than query sketches. In particular, since it always holds that r 2 t. this implies a guarantee of t = $2(k=aa)) on the number of adaptive queries. Note that the sketch size "budget" of can be used to trade off accuracy and robust- ness.
In the ADA problem, we get an input dataset S sampled from some unknown distribution D, and then need to answer a sequence of adaptively chosen statistical queries (SQ) w.r.t. D. This problem was introduces by Dwork et al. (2015) who showed that it is possible to answer ss [S|2 statistical queries efficiently. The application of differential privacy tool for the ADA problem predated its application for robust data structures.
Tracking Robust Estimator (Section 5). We present another estimator that tracks the exposure of keys based on their participation in query sketches. Once a limit of is reached, the key is deactivated and is not used in future queries. The tracking estimator allows for smooth degra- dation and continues to be accurate as long as at most an a fraction of entries in the sketch are deactivated. Note that the tracking state is maintained by the query responder (server-side) and does not effect the computation or size of the sketch.
Our reformulated wrapper has two benefits: (1) It allows us to augment the generic wrapper with the gramularity needed to address Question 1.1, whereas the existing wrapper lacks this flexibility. (2) Even though our construction ultimately solves the ADA problem using differential privacy, other known solutions to the ADA problem now exist, and it is conceivable that future applications might need to leverage properties of these alternative solutions.
Experiments. Finally, in Section 6, we demonstrate the benefits of our fine-grained analysis using simulations on query sets sampled from uniform and Pareto distributions and observe 12x to x gains.
To this end, in Section 3 we introduce a tool: an SQ frame- work with fine-grained generalization guarantees. This framework addresses an analogous version of Question 1.1 for the ADA problem, where k represents the sample size and is the maximum number of query predicates that are satisfied by given key x. To adapt this tool for sketch- ing, we need to represent the randomness determining the sketching map as a sample from a product distribution and express the query response algorithm in terms of appropriate statistical queries. This tool generalizes the analysis of the robust version of CountSketch introduced by Cohen et al. (2022a).
1.4. Additional related work
The adaptive setting has been studied extensively across multiple domains, including statistical queries (Freedman, 1983; loannidis, 2005; Lukacs et al., 2009; Hardt & Ullman, 2014; Dwork et al., 2015; Bassily et al., 2021), sketching and streaming algorithms (Mironov et al., 2008; Hardt & Woodruff, 2013; Ben-Eliezer et al., 2021 Hassidim et al., 2020; Woodruff & Zhou, 2021; Attias et al., 2021; Ben- Eliezer et al., 2021a; Cohen et al., 20226; 2023; Ahmadian & Cohen, 2024), dynamic graph algorithms (Shiloach & Even, 1981; Ahn al., 2012: Gawrychowski et al., 2020; Gutenberg & Wulff-Nilsen, 2020; Waje, 2020; Beimel et al., 2021), and machine learning (Szegedy et al., 2013; Good- fellow et al., 2014; Athalye et al., 2018; Papernot et al., 2017).
Robust estimators for bottom-k sketch. We use our fine- grained SQ framework in order to design a robust version for the popular bottom-k MinHash cardinality sketch (Rosén, 1997: Cohen, 1997; Broder, 1997; Bar- Yossef et al., 2002). The randomness in the bottom-k sketch corresponds to
Lower bounds. For the ADA problem, Hardt & Ullman
3

---

Breaking the Quadratic Barrier
(2014); Steinke & Ullman (2015) designed quadratic- size universal attack, using Fingerprinting Codes (Boneh & Shaw, 1998). Hardt & Woodruff (2013) designed polynomial-sizz universal attack on any linear sketching map for f2 norm estimation. Cherapanamjeri & Nelson (2020) constructed an (kk) attack on the Johnson Lin- denstrauss Transform with the standard estimator. Ben- Eliezer et al. (2021b) presented an -size attack on the AMS sketch (Alon et al., 1999) with the standard estima- tor. Cohen et al. (2022b) presented an O(k)-size attack on Count-Sketch (Charikar et al., 2002) with the standard esti- mator. Cohen et al. (2023) presented Ö(k²) size universal attack on the AMS sketch (Alon et al., 1999) for &g norm estimation and on Count-Sketcl (Charikar et al., 2002) (for heavy hitter or inner product estimation).
the same privacy parameters (Kaplan et al., 2021; Feld- man & Zrnce, 2021; Cohen et al., 2022a; Cohen & Lyu, 2023b). The algorithm maintains a set A of active indices that is initialized to all of [n] and maintains charge coun- ters (Ci)eetx), initialized to 0. For each query (h, 7), the response is AboveThresholdd" (h, T) test result that is f Eie h(i,))) + Lap]1/e] if å T and is 1 other- wise. Note that AbcveThreshold evaluates the query only over active indices. For each query with positive (above) response, the algorithm increases the charge counts on all the indices that contributed to the query, namely, h(i, x3) = 1. Once C. r, index i is removed from the active set A of indices.
The appeal of Algorithm is a fine-grained analysis that can only result in an improvement - the privacy bounds have the same dependence on the parameter r. that in the basic approach bounds the total number of tests with positive outcomes and in the fine-grained one bounds the (potentially much smaller) per-index participation in such tests:
2. Preliminaries
2.1. DP tools:
linear queries with per-unit charging
Differential privacy (Dwork et al., 2006) (DP) is Lipschitz- like stability property of algorithms, parametrized by (e, 6). Two datasets x, x' E X" are neighboring if they differ in at most one entry. Two probability distributions 'D and 'D' satisfy D 25 D' if and only if for any measurable set of events E, (r) I e Prax(E) + 8 and Pr (E)= I ef Pro(E) + 5. A randomized algorithm A is (e, 6) if for any two neighboring inputs a and x', A(x)) Re.8 A(x'). DP algorithms compose in the sense that multiple applications of a DP algorithm to the dataset are also DP (with composed parameters).
Theorem 2.1 (CCohen & Lyu, 2023a) Privacy of Algo- rithm 1). For any < and 5 (0, 1), Algorithm I is (O(Vrlog() (og(1)))))) + 5)-DP (see Theorem A. for more precise expressions).
Algorithm 1: Linear Queries with Individual Pri- vacy Charging
Input: Sensitive data set (I1,...,, v.)) E privacy
budget r >> 0; Privacy parameter E >> 0.
foreach i [n] do C, + 0 // Initialive counters // critializa the active set Function AboveThresholdd" (h,
A
[m]
Given a dataset æ :- (5 (#1,..., I.) X of items from domain X. counting query is specified by predicate f [n] x X + [0, 1] and has the form f(x) : Lie(n] f(i, For 8 > 0, an algorithm that returns a noisy count f(xr) := f(x) + Lap[1/s]. where Lap is the Laplace distribution, satisfies (e, O)-DP. When multiple such tests are performed over the same dataset, the privacy parameters compose to (re, DD or alternatively /orrlog(1//8 re?, 8)DP for any 5= >00 0.
11 AboveThccahhold quezy
Input: predicate h |m]] x X - {0, 1) and
threshold T' E R
- noige
(EEEA ((), + Lap(1/E)
/1 Taplaca
if h > T then
11 Teat against Chresheld
foreach i A such that h(i, 1 do C. C.+C. C.+1
if = then + A (1)
return h
The Sparse Vector Technique (SVT) (Dwork et al., 2009; Roth & Roughgarden, 2010; Hardt & Rothblum, 2010; Vad- han, 2017) is a privacy analysis technique for a situation when an adaptive sequence of threshold tests on counting queries is performed on the same sensitive dataset æ. Each test AboveThreshold. (f. T) is specified by a predicate f and threshold value T. The result is the noisy value f(x) if f > T and is I otherwise. The appeal of the technique is a privacy analysis that only depends on the number r of queries for which the test result is positive.
else
return
on input (S,T) // Main Loop: process queries return AboveThrehhhh (f.1)
2.2. ADA tools
The generalization property of differential privacy applies when the dataset æ is sampled from a distribution. It states that if a predicate h is selected in a way that preserves the privacy of the sampled points then we can bound its generalization error: the count over æ is not too far from
We will use here an extension of (a stateless version of) SVT, described in Algorithm 1, that improves utility for
4

---

Breaking the Quadratic Barrier
the expected count when we sample from the distribution. We will use the following variant of the cited works (see Appendix B for a proof):
Proof. The first claim of the sampling and generalization error, follows from Theorem 2.1 and Theorem 2.2
For the privacy parameters in Theorem 2.1 we set ò 8/n² and obtain & = V (og Eo < a/2v2. From Theorem 2.2 we get that, for each query h, the additive error Ey-D hzy) - h(xx)] is at most
Theorem 2.2 (Generalization property of DP (Dwork et al., 2015; Bassily et al., 2021; Feldman & Steinke, 2017)). Let A X + 2* be an (e, -iifffrrrettilllyyy private algorithm that operates on a dataset of size n and outputs predicate h. X + {0, J.. Let 'D D1 x ... Du be a product distribution over X let
(x1, (.1...... Inn) 'D be sample from D, and let c- A(x)) Then for any T 2 it
(e -1 E h(v) + log(T T + 1) + 2Tnő, y-D
holds that
with probability least 1 2/T. Note that we have c < a. Thus, setting T = 2m/3 3 (so that a union bound over all queries gives a failure probability of 1 - -), the result follows.
4 log(T + +1 27
1
Pr awDD, A(-)(
E
26
W-D
h(y)
h(x)=
> 8
<
T
4 > log(T + +11 (og(T+1)))
1
Pr anDD A+a)
h(x²)
E h(y)
27nó
ydD
T
Claim 3.2 (Noise and deactivation error bounds). Under
the conditions of Lemma 3.1, with probability at least 1 - B, for all m query predicates h, for h = Eien h(i, 25)) + Lap(1/Eo).
where hyy) denotes the total value of h over elements of y.
When applying Theorem 2.2, will assume that h also takes the index i as argument (so, we write h(i,x,) instead of h(z;)). This is equivalent because we can re- place D; with distribution that samples the tuple xi. for v2 ~ D..
h(x:) - h h> logg(mmm (22m33//000
h(x)) - h < log(2m/33/Eo + Σ h(i,
<E(M]]A
Proof. Each Laplace noise Lap(1/Eo) is bounded by = log(2mm log(2m/B)/Ee /)/cs, with probability at least 1- - 3/mm, so by a union bound, with probability at least - 33, it bounded as such for all queries, and the result follows immediately.
3. ADA with Fine-Grained Analysis
We now consider a variation of the ADA framework where we sample a dataset DD from a product distribution D and then process adaptive linear threshold queries as in Al- gorithm I over the dataset œ. The benefit of this is obtaining bounds in terms of the per-key participation in queries (that the number of queries h for which 1(6,, x;) = 1), which always lower than the total number of queries. Moreover, the approach tolerates small fraction of deactivated indices in each query. which simply contribute proportionally to the error.
The total error of h with respect to the expectation Ey-D h(y) is bounded by the sum of errors in Lemma 3.1 and Claim 3.2:
Corollary 3.3. For some constants CI. C2 > O, under the conditions of Lemma 3.1, with probability at least 1 - B, for all m queries h,
- - < E E - yoD
Σ A(i, xE|m|AA
We bound the error due to generalization and sampling and due to the privacy noise and the deactivation of keys that reached the charging limit r:
where
==a- E (b)) + +O(a 1/ (mm (mm/B)) B)). y
Lemma 3.1 (Generalization and sampling error bound). Let D= Di x.. x Dr, be a product distribution over X". Let x ~ D be a sampled dataset. Let a > 0 be sufficiently small (i.e., smaller than some absolute constant). Consider an execution of Algorithm I on dataset x with adaptive queries, parameter >> log(n/3), and
We can apply this fine-grained ADA to analyze the robust- ness of randomized data structures (or algorithms) that sam- ple randomness p and process adaptive queries M; that depend on the interaction till now and the randomness p. To do so, we need to specify a product distribution D = D1 x D2x.... x D, so that
a
ED = A/rlog(n//)
Then it holds that with probability at least - B. all of the m query predicates h,
The distribution of p is D.
2.
The queries in the original problem can be specified in terms of linear queries over p and have statistical guarantees of utility over p ~ D.
<a- E [[y)] + loo((m/8)) DnD
E [Mv) -((x)) D
5

---

Breaking the Quadratic Barrier
Algorithm 2: Bottom-k: Cardinality Sketch and
Algorithm 3: Basic Robust Cardinality Estimator
Standard Estimator
function RobustEstu(S)
// Estimate [V] from
Sample ~ U'Oo 1] for i [w].// Randomness for the
BkSketchp(V)
Sketching Map
Input: A bottom-k: sketch S, E 0.50.5
function BkSketcch(V))
// Botton-k k sxetching
if [S] < then Return exact value when return [S]
map ua uning P
Input: Set V C [n]]
else
if V S & then
T k/2n, = =1 (1-a)h while (T 1) and
return ((, 1iEV]
else
(h + E(ioDES ((re)) + Lap(1/so)) <T do
return (() lie Vips < // where Puka is the kth smallest in the multiset Jollen V)
L (1 + a/4)r
return T/T
function StdEstt(S)
/1 Standard estimator
Input: Parameters k, 2 1 and a, 3
Input: A bottom-k sketch
if [S] < k then
60 4/rlog(n/(//0)
Temma 3.1 with g+
return [S]
imput S L return RobustEste,,(S)
// Main Toop
clse
T (AX
11 kth smallest P
return (k- 1)/T
on input
// Xain Loop
to optimally use the information in the sketch S but can be attacked with linear number of queries (Ahmadian & Cohen, 2024).
return StdEstx(S)
When applying this to sketching maps which do not contain all the information of p. we will need to ensure that the linear queries we use can be evaluated over the sketch.
4.2. Basic robust estimator
Algorithm 4 describes robust estimator RobustEst that is applied to bottom-k sketch.
We analyze this estimator under the assumption that the query set sequence (Vg))e(4 has the property that each key E [n] appears in at most r sketches in (aksketch(VVi)ieee
4. The Bottom-k Cardinality Sketch
4.1. Sketch and standard estimator
The bottom-k cardinality sketch and standard estimator are described in Algorithm 2. Let the ground set of keys be [n]. We sample a vector of random values p [0, 1]" That is, for each key E [nx] there is an associated i.i.d. Ps ~ D. The vector P specifies the bottom-k sketching map (k) that maps a set V C [m] to its sketch. The sketch consists of the pairs (i, p.) for the values of i V such that P; is smallest. When VV| S k. the sketch contains all elements of V. Note that, though n and also [V| can be very large, the size of the sketch is at most k. This sketching map is clearly composable.* 4
Vi E [n], Σ (eexxskesch, Sr. jEM
(I)
Note that for this to hold it suffices that each key is included in at most r query sets. That is, Vi E [n], Σ}E(h Lev, S r. Theorem 4.1 (Basic robust estimator guarantee). If the query sequence Algorithm 3 satisfies for some >> log(n/ (), then for value of k 00002222200 /olg ( every output will be (1 + a) accurraee with probability at least 8.
For a query set V C [n], we apply an estimator to the sketch : BkSketch, (V)) to obtain an estimate of the cardi- nality of V. The standard estimator StdEst (S) computes which is the kth order statistics of the Pe values in the sketch, which is sufficient statistic of the cardinality. It then returns the value (k- - 1)/T. The estimate is unbiased, has variance at most [V]/(k - 2). and an exponential tail (see e.g. (Cohen, 2015)). This standard estimator is know
4.3. Analysis of basic robust estimator
In this section we prove Theorem 4.1.
Before we start, we make some basic assumptions on the parameters which we will use throughout the proof. First, we pick
== Ca 2 /rlog//2(n//)))
where the constant C' is chosen to be sufficiently large. Fur- thermore, note that if 2 n then we are always storing the whole set V in the sketch, so we may assume that & < n (and therefore n² and a 1/vn).
"The analysis uses a common assumption of full i.i.d. randomness in the specification of the sketching maps. Note that Ollog k) bits of representation random hash maps + Pi-
sufficient. Implementations use pseudo-
6

---

Breaking the Quadratic Barrier
We map Algorithm to the framework of Algorithm 1, where the dataset is p.
Algorithm 4: Tracking Robust Estimator
function IRobustEste,.(9) // Rabust Cardinality
First, we show that we can consider the sum of 1 perer to be over the entire set V, rather than just those that are included in the bottom-k sketch S:
Estimate of V from Bksketcāp(V)
Input: A bottom-k sketch S
if [S] < k then // Return exaot value when k return [S]
Lemma 4.2. Suppose that, in Algorithm 3. h Eiiness (p(eT) + Lap(1/Eo)) is replaced by h = Diey ((pee)) + [ap(1/eo)) (where the two Laplace ran- dom variables are coupled to be the same value). Then, the sequence of outputs of Algorithm 3 changes with probability at most 8/4.
else
7 k/2n, T + k/4 while
(T < A + Eunnes (()))))(()))))) + Lap(1/so) do
L 7 +- (1+ (1+)/
foreach (i,z;) E S do // Per-key tracking if < then Clil + Cii +1
return T/T
Proof. Since S contains the & values of such that pi is minimal, the only way to have h * h is to have the sum over S be equal to k and the sum over V to be greater than k. The outputs may then only differ if h < T, but the probability that k + Lap(1/Eo) < (1 a)k is at most e e-ookk < B/ poly(n) (n), where the polynomial in n can be made as large as we like (by setting the constant on k).
Input: Parameters k, 2
// initializa:ion C 0 o/16
// Dictionzry with default value 0 Leams 3.1 with ft. g
eo f (n/ //
on input S L return (Robust
1/ Main Loop
Now, note that the total number of queries to Algorithm 3 cannot exceed nr S poly(n) by (I). Furthermore, the total number of iterations of the while loop per call is most O(a log n-) (n)y
Claim 4.3.
E (u), = =-/V.
The lemma follows by taking a union bound over all it- crations of the while loop and over all queries to Algo- rithm 3.
Proof. Observe that for i E V. ll,, (i, = 0 for all y and for E V, E(vv,,, (0 (i. y:)] = T.
LI
Finally, recall from the proof of Lemma 4.2 that the total number of iterations of the while loop (and thus the overall total number of calls to Algorithm is most poly so in Corollary 3.3 we can take = poly(n).
With this lemma in mind, we will henceforth assume through this entire section that Algorithm 3 uses h instead of h. introducing a failure probability of at most 3/4.
Now, we will show that the execution of Algorithm can be performed via queries to Algorithm 1, rather than accessing p directly. Indeed, note that the counting query i takes the same form (except for the check being over [n] instead of A) as its analog in Algorithm 1, where the query function is
Now, by Corollary 3.3, we have with probability at least - 3/4 that
à < <1+ + ak/8,
(3)
i, (1 (01-a/8)711 a/8)T|V| ak/8,
(4)
(1, pt) = LEVAART.
where we have used that
A = 0(a - 3/2 (n/3) < ok//8.
Observe that for any query sketch S, there is at most one positive test in Algorithm 3. Therefore, per assumption (1) on the input, each index appears in at most r positive tests. Therefore, if we were to instead perform these tests using Algorithm 1, all indices would remain active and nothing would ever be removed from A. Thus, we would have that A = [n].. so indeed the values of h are identical in Algorithm 1 and Algorithm 3. Thus, Algorithm 3 can be simulated by queries to Algorithm 1, so we may apply the results of Section 3.
by the choice of k. (Recall also that [n] \ A is always empty, so the sum term in Corollary 3.3 vanishes.) We assume henceforth that this probability-11 (1- BB/4) event does in fact occur.
Proposition 4.4. Whenever T < (1- (1-a/2]T/[V] the while loop in Algorithm continues to the next value of T.
Proof. Note that ak/8 < aT/4 since T > k/2. Thus, by (3), when 7 < (1 (llaa/22TT|V// we have < (1+a/8) a/2)T + aT/4 < T (for sufficiently small a), so we are done.
In order to apply Corollary 3.3, we need to first compute the expectation of by, on D:
7

---

Breaking the Quadratic Barrier
Proposition 4.5. Whenever T > (1 (1+a/2)T/IVV, the while
6. Empirical Demonstration
loop in Algorithm 3 terminates.
We demonstrate the effectiveness of our fine-grained ap- proach by comparing the number of queries that can be guaranteed compared with the baseline per-query analysis. We use synthetically generated query sets sampled from Uniform and Pareto distributions with or E (1.5, 2) and
Proof: Again, by (4), when >> / we have h > (L-a//S(4+a//TT-cc///4 T, so are done. n
Now, Proposition ensures that the output of the algorithm is always at least (1 a a/2)]V|. Moreover, since is incre- mented by factors of 1 + //4, there will be some value of r tested that is between (1 + a/227/ / | and (1 + T)T/IVI (note that since [V] 2 k. we have (1 + / < 1). By Proposition 4.5, this value will cause the while loop to ter- minate, yielding an output that is at most (1 + aa]V). This completes the proof of Theorem 4.1.
Im = 1, support size of 10 and query set size of 5 x 10", For each sketch size k, we match a value of the parameter r = 0.0024² (with RobustEst and TRobustEst and respectively / = 0.002 with baseline analysis.
With RobustEst we stop as soon as there is a key that appeared in r queries. With IRobustEst, number of queries for which at most 10% of sketch entries are deactivated and stop when there is a sketch with 50% of entries deactivated. Figure 1 reports the number of queries with the baseline and fine-grained estimators. The respective gain factor is measured by the ratio of the number of queries that can be effectively answered with per-key analysis to the baseline. We observe gains of two orders of magnitude for uniformly sampled query sets. This hold even without tracking using RobustEst. For Pareto query sets, we only TRobust Est, as tracking is necessary because some keys appear in many query sketches. We observe gains of 12x for the very skewed a 1.5 and 40x with a 2.
count the
When assumption (1) does not hold, that is, when some keys get maxed (have participated in more than r query sketches), the guarantees are lost even when there are no maxed keys in the query set. The universal attack constructions of (Ah- madian & Cohen, 2024; Cohen et al., 2024) show this is unavoidable. The attack fixes a ground set U and identi- fies keys with low priorities (these are the keys that tend to be maxed). The query sets that is U with the identified keys deleted has cardinality close to [U] but the estimates of RobustEst would be biased down. In the next section we introduce tracking estimator that allows for smooth degradation in accuracy guarantees as keys get maxed.
Conclusion
5. Robust Estimator with Tracking
Our work raises several compelling follow-up questions. While our fine-grained robust estimators are tailored to the bottom-k cardinality sketch, we conjecture that similar ro- bustness guarantees can achieved for other MinHash- based sketches, including the k-partition (also known as PCSA or Stochastic Averaging) sketches (Flajolet & Martin, 1985; Flajolet al., 2007). Achieving this would likely require extending the fine-grained ADA framework beyond its current restriction to linear queries.
We next propose and analyze the estimator ERobustEst in Algorithm 3 that is an extension of RobustEst that includes tracking and deactivation of keys that appeared in the query sketches more than r times. This estimator offers smooth degradation in estimate quality that depends only on the number of deactivated keys present in the sketch and this is guaranteed as long as there are no queries where most of the sketch is deactivated.
Another open direction concerns robustness for other norms, settings where inputs are sparse and only a small subset of entries are aanyyaappearnng frequently across queries. When sketching methods assign independent randomness per key and each key appears in only one query, full robust- ness trivially holds. This scenario applies to many popular sketching methods. However, robustness becomes more subtle when keys may appear in multiple r > 1 queries or when only a small number of keys appear in many queries. For & norm estimation with the popular AMS sketch (Alon et al., 1999), existing quadratic-size attacks succeed even when all inputs have disjoint support except for single shared key (Cohen et al., 2023). The guarantees we can provide under the weaker condition that each key appears in at most r > 1 queries remains an open question.
Theorem 5.1 (Analysis of TRobustEst), For a value kf = = - (2 suppose that an adaptive adversary provides at most m inputs to Algorithmm 4 such that the sketch of every input has at most k/22 deactivated keys. Then, with probability at least - for every input whose sketch has at most ak/ /4 deactivated keys, the output is (1 + approximaaio of the true cardinality.
This theorem guarantees that, as long as no query has too many (more than k/2) deactivated keys, the results of Al- gorithm 4 will continue to be accurate even for queries that have few (at most (4k/4) deactivated keys. This allows the algorithm to continue guarantecing accuracy even if a few keys are subject to many queries. We discuss the nu- merical advantages of this further in Section 6. The proof is analogous to Section 4.3 and provided in Appendix C.
Finally, we conjecture that analogous robustness results
8

---

Breaking the Quadratic Barrier
Lnfomile-50,,
Faratoo Je-dfi, See inactive
beeethe
Ieternet
400
220
275
25
Figure 1. Number of guaranteed queries for sketch size k. The gain factor of IRobustEst baseline over two orders of magnitude with the Uniform distribution, x for Pareto with a = 2, and 12x for Pareto with a = 1.5.
may be achievable for a broader class of sublinear statis- tics-such as capping statistics (Cohen, 2018; Cohen & Geri, 2019), whose sketching techniques extend generalized cardinality sketches.
thesizing robust adversarial examples. In International conference on machine learning, pp. 284-293. PMLR, 2018.
Attias, I., Cohen, E., Shechner, M., and Stemmer, U. A framework for adversarial streaming via differential pri- vacy and difference estimators. CoRR, abs/2107.14527. 2021.
Acknowledgments
Edith Cohen was partially supported by Israel Science Foun- dation (grant 1156/23). Uri Stemmer was Partially sup- ported by the Israel Science Foundation (grant 1419/24) and the Blavatnik Family foundation.
Bar- Yossef, Z., Jayram, S., Kumar, R. Sivakumar, D., and Trevisan, L. Counting distinct elements in data stream. In RANDOM. ACM, 2002.
Impact Statement
Bassily, R., Nissim, K., Smith, A. D., Steinke, T., Stemmer, U., and Ullman, J. R. Algorithmic stability for adap- tive data analysis. SIAM J. Comput., 50(3), 2021. doi: 10. 1111/61/11 103646 URL httph::/t//eet //ooi: org/10. 1 1 1 6M1 1 6466.6
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must specifically highlighted here.
Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., and Stemmer, U. Dynamic algorithms against an adap- tive adversary: Generic constructions and lower bounds. CoRR, abs/211 1.03980, 2021.
References
Ahmadian, S. and Cohen, Unmasking vulnerabili- ties: Cardinality sketches under adaptive inputs. In ICML, 2024. URL aattps:///olfe org/ 48550/
Ben-Eliezer, O., Eden, T., and Onak, K. Adversarially robust streaming via dense-sparse trade-offs. CoRR, abs/2109.03785, 2021a.
arXiv.2405.0 24051.2200...780.
Ahn, K. J., Guha, S., and McGregor, A. Analyz- ing graph structure via linear measurements. In Proceedings of the 2012 Anmual ACM-SIAM Sym- posium on Discrete Algorithms (SODA), pp. 459- 467, 2012. doi: 10.113771.788661119339999 URL. https:tt///c...... http://pwssssaa.rrrgoeee.eee
Ben-Eliezer, O., Jayaram, R., Woodruff, D. P., and Yogev, A framework for adversarially robust streaming algo- rithms. SIGMOD Rec., 50(1):6-13, 2021b.
Blasiok, J. Optimal streaming and tracking distinct elements with high probability. ACM Trans. Algorithms, 16(1):3:1- 3:28, 2020.
Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58: 137-177, 1999.
Boneh, D. and Shaw, Collusion secure fingerprinting for digital data. IEEE Trans. Inf. Theory, 44(5): 1905, 1998. doi: 10. 1011000810706666 URL https:
Apache Software Foundation. DataSketches, Accessed: 2024. URL https:/ /ddaaaaaaeeettaaae wettrassktcche..apachh.. apache. org. Apache Software Foundation Documentation.
//doi. o0c/00.0gg11.... 1119/18.1111111 11111/..1111911..755.....
Broder, A. Z. On the resemblance and containment of documents, In Proceedings of the Compression and Com- plexity of Sequences, pp. 21-29. IEEE, 1997.
Athalye, A., Engstrom, L., Ilyas, A., and Kwok, K. Syn-

---

Breaking the Quadratic Barrier
Broder, A. Z. Identifying and filtering near-duplicate docu- ments. In Proc.of the 1thh Annual Symposium on Com- binatorial Pattern Matching, volume 1848 of LNCS. pp. 1-10. Springer, 2000.
Cohen, E., Lyu, X., Nelson, J., Sarlós, T.,, Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022a. URL https: /tle://arxxie http///wxvv.rggg/......../ abs 2202. 13736.
Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. In Proceedings of the 29th International Colloquium on Automata, Languages and Programmiing, ICALP '02, pp. 693-703. Springer- Ppringer-Verlag, 2002. ISBN 3540438645.
Cohen, E., Lyu, X., Nelson, J., Sarlós, T.,, Shechner, M.. and Stemmer, U. On the robustness of countsketch to adaptive inputs. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 41 4112-4140, PMLR, 2022b.
Cherapanamjeri, Y. and Nelson, J. On adaptive distance es- timation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Cohen, E., Nelson, J., Sarlós, T., and Stemmer, U. Trick- ing the hashing trick: A tight lower bound on the ro- bustness of countsketch to adaptive inputs. In Pro- ceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023, doi: 10.1609/aaii v3766 25882. URL https::///// /ttp::s://ojs.aaeeeeseee org/ index. php/AAAI
Cohen, E. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55:441-452 1997.
Cohen, E., Nelson, J., Sarlós, T., Singhal, M., and Stemmer, U. One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches. arXiv preprint arXiv:241 1.Xx::241..063700 1.06370, 2024.
Cohen, E. Hanh Sketches, pp. 1-7. Springer US, Boston, MA, 2008. ISBN 978-3-642-278488-88 doi: 10. 10077978-33-602-27848-----77777- URL
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrat- ing noise sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cohen, E. All-distances sketches, revisited: HIP estimators for massive graphs analysis. TKDE, 2015. URL http: ht/arxiv.org//aaee.e abs ablaaabs..11... 1t/.//1666000 3284.
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, On the complexity of differentially pri- vate data release: Efficient algorithms and hardness re- sults. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pp. 381-390, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 978 600585502. doi: 10. 1145/1536414.15366611 URL https: /tt.: 10.1145/153644 15364677.
Cohen, E. Stream sampling framework and application for frequency cap statistics. ACM Trans. Algorithms, 14 (4):52:1-52:40, 2018. ISSN 1549-6325. doi: 10.1145/ 3234338.
Cohen, E. Sampling big ideas in query optimization. In Geerts, F., Ngo, H. Q. and Sintos, S. (eds.), Proceedings Symposium
of the 42nd ACM on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023, pp. 361-371. ACM, 2023. URL https:/t:
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. L. Preserving statistical validity in adaptive data analysis. In STOC, pp. 117-126. ACM, 2015.
doi: 10. 1 0..1145//584432235599955 org / 10. 11 15 / 3589933
Cohen, and Geri, O. Sampling sketches for concave sublinear functions of frequencies. In NeurlPS, 2019.
Feldman, V. and Steinke, Generalization for adaptively- chosen estimators via stable median. In COLT, volume 65 of Proceedings of Machine Learning Research, pp. 728- 757. PMLR, 2017.
Cohen, E. and Lyu, X. The target-charging technique for privacy analysis across interactive computations. In Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023a. URL https: /wt.cci.oooooooooooooooo org/ 10. 48550/ arxiv 2330211044
Feldman, V. and Zrnic, T. Individual privacy account- ing via a rényi filter. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances Neural Information Processing Systems, 2021. URL https: // //openreview net/ http///ormmmmmmptaaeaae __
Cohen, E. and Lyu, X. The target-charging technique for privacy accounting across interactive computations.
CoRR, abs/2302. 1044, 2023b. doi: 10.48550/arXiv.
Flajolet, P. and Martin, G. N. Probabilistic counting algo- rithms for data base applications. Journal of Computer and System Sciences, 31:182-2099 229209 1985.
2004.11044. URL https:: http::/t::////e http:://dooo...........o 48550/ arxiv. 2302. 11044.
10

---

Breaking the Quadratic Barrier
Flajolet, P., Fusy, E., Gandouet, O., and Meunier, Hy- perloglog: The analysis of near-optimal cardinality estimation algorithm. In Analysis of Algorithms (AofA). DMTCS, 2007.
Hardt, M. and Woodruff, D. P. How robust are lin- ear sketches to adaptive inputs? In Proceedings of the Forty-Fifth Annual ACM Symposium The- ory of Computing, STOC '13, PP. 121-130, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10.1145/ 248862.. URL https://doi. org/10. 1145/2488608 2488624.
Freedman, D. A. A note on screening regression equa- tions. The American Statisticion, 37(2):152-155, 1983. doi: 10.1080/000011005. 104822277 URL https://ww.. http::/wwwaaaffffonnoooo wtt http///oo//aaa/// abs/ 10. 10.1080/0003130330 10488772...
Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. Adversarially robust streaming algo- rithms via differential privacy. In Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2020.
Gawrychowski, P., Mozes, S., and Weimann, O. Minimum cut in o(m log" n) time. In ICALP, volume 168 of L/PIcs, pp. 57:1-57:15. Schloss Dagstuhl- SrgstuhllLLeinni--eenmm Leibniz-Zentrum für Informatik, 2020.
Heule, S., Nunkesser, M., and Hall, A. HyperLogLog in practice: Algorithmic engineering of state of the art cardinality estimation algorithm. In EDBT, 2013.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explain- ing and harnessing adversarial examples. arXiv preprint arXiv: 14/65772 2014.
loannidis, J. P. A. Why most published research findings are false. PLoS Med, (2):8, 2005.
Google Cloud.
BigQuery Documentation: Ap- proximate Aggregate Functions, Accessed:
Kane, D. M., Nelson, J., and Woodruff, D. P. An optimal algorithm for the distinct elements problem. In PODS, pp. 41-52. ACM, 2010.
2024. URL https://cloud. google. com/ hwwpee/rw//dssseeeeeeeee////////
Google
Cloud Documentation.
Kaplan, H., Mansour, Y., and Stemmer, U. The sparse vector technique, revisited. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 2747- 2776. PMLR, 2021. URL http: / httpp//ecceeee.n..o// mir mir. mir.spres/ v114/v133444// 2213///kalla /kapla22plaaaaaa html.
Gribelyuk, E., Lin, H., Woodruff, D. P., Yu, H., and Zhou, S. A strong separation for adversarially robust to esti- mation for linear sketches. In Proceedings of the 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024. URL https:// /ttp://aavvv.////a///ieeeeeeiaaa org/ / 2409. 6153.
Kontorovich, A., Sadigurschi, M., and Stemmer, U. Adap- tive data analysis with correlated observations, 2022.
Gutenberg, M. P. and Wulff-Nilsen, C. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the Thirty-First Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pp. 2542-2561, USA, 2020. Society for Industrial and Applied Mathematies.
Lukacs, P. M., Burnham, K. P., and Anderson, D. Model selection bias and Freedman's paradox. Annals of the Institute of Statistical Mathematics, 62(1):117, 2009.
Mironov, I., Naor, M., and Segev, G. Sketching in ad- versarial environments. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC *08, pp. 651-660, New York, NY, USA, 2008. Associa- tion for Computing Machinery. ISBN 978 97816055888 1055800777. doi: 10. 10.1144/13344376 1374471. URL ht https: /oii. org /1g
Hardt, M. and Rothblum, G. N. A multiplicative weights mechanism for privacy-preserving data analysis. In 51th Annual IEEE Symposium on Foundations of Com- puter Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pp. 61-70. IEEE Computer Soci- ety, 2010. doi: 10.1109/FOCS 2010.88. URL https: //doi. org/ 10. 19 /FOCS. 2010.85 85.
Papernot, N., McDaniel, P., Goodfellow, I., Jha, S., Celik, Z. B., and Swami, A. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications secu- rity, pp. 506 506-519, $19,2017.
Hardt, M. and Ullman, J. Preventing false discov- ery in interactive data analysis is hard. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 454-463. IEEE Com- puter Society, 2014. doi: 10.1109/FOCS.214.
Paterson, K. G. and Raynal, M. Hyperloglog: Ex- ponentially bad in adversarial settings. Cryptology ePrint Archive, Paper 2021/1139 2021. URL https:
55. URL htRh:: /oii. htwp:ttpp://ab...eecompeeeeesss ieecomptersooclety org/10.1109/Foce. 2014..55........................

---

Breaking the Quadratic Barrier
//eprint.iactee wtt....o.r.r/////11333/333 eprint. facr. saaerrorg wacr..rgg/22//1133/
https://
Reviriego, P. and Ting, D. Security of hyperloglog (HIL)) cardinality estimation: Vulnerabilities and pro- tection. IEEE Commun. Lett., 24(5):976-980, 2020. doi: 10. 11000//..OMM22000027998890099990 URL https: //doi. wwtp./.../////.........////
2020 2 2972895.
Rosén, Asymptotic theory for order sampling. Statisti- cal Planning and Inference, 62(2):135-158, 1997.
Roth, A. and Roughgarden, T. Interactive privacy via the median mechanism. In Schulman, J. (ed.), Proceed- ings of the 42nd ACM Symposium on Theory of Com- puting, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 765-774. ACM, 2010. doi: 10. 1145/1806689.18067999 URL https: /tt...rg///ooooooooooo/o../ org/ 10.1145/1806688 1806794.
Shiloach, Y. and Even, S. An on-line edge-deletion problem. ACM, 28(1):1-4, jan 1981. ISSN 0004-5411, doi: 10. 10.11457322234.32223.. URL https: org/ 10. 18..145/3200 DT..1445/32224.322255
Steinke, T. and Ullman, J. Interactive fingerprinting codes and the hardness of preventing false discovery. In Grünwald, P. Hazan, E., and Kale, S. (eds.), Proceed- ings of The 28th Conference Learning Theory, vol- ume 40 of Proceedings of Machine Learning Research, pp. 1588-1628, Paris, France, 03-06 Jul 2015. PMLR. URL https: http:///d/occggpeeee//ee mlr press/v4D/ Steinke15 htmml.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. arXiv preprint arXiv: 2013.
Vadhan, S. P. The complexity of differential pri- vacy. In Lindell, Y. (ed.), Tutorials on the Foun- dations of Cryptography, pp. 347-450. Springer International Publishing, 2017. doi: 1007/ 978-3-319-57048-8|1 URL https:://////t /dog.org///////o/////o/oo 10. 10.1007//788 000000099777331--5700800 3--1---70-9----77777
Waje, D. Rounding Dynamic Matchings against an Adaptive Adversary. Association for Computing Machinery, New York, NY, USA, 2020. URL https: ///////ooi.. /////o.ooog//..//// org/10. 1145/3357713 3384258.
Woodruff, D. P. and Zhou, S. Tight bounds for adversarially robust streams and sliding windows via difference estima- tors. Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021.
12

---

Breaking the Quadratic Barrier
A. Fine-grained SVT privacy bounds
More precise bounds for Theorem I and for standard SVT throught the target charging technique (TCT).
Theorem A.1 (Privacy of Barget-Charging (Cohen & Lyu, 2023a) ). Algorithm I (and per-query SVT) satisfy the following
approximate DP privacy bounds:
(1 + ae, 01;a))
for any >> 0;
q [ [1
+ a1 =s² +e / (1+
log(11))))) (o
for any 6 > 0, > 0.
2
where (r, a) S e "रं and q e=+I
B. Proof of extended generalization
Here will prove Theorem 2.2:
Theorem 2.2 (Generalization property DP (Dwork et al., 2015; Bassily et al., 2021; Feldman Steinke, 2017)). Let A: X T 2 be (e, -iifferrent privale algorithm that operates on a dalasel of size and oulputs predicate h: + 10. Let D2 ... D, be product distribution over X", let x ( Fnd 'D be sample from D, and let h t A(x). Then for any T 2 it holds that
1
Pr a>D h=-A(s))
20 E y-D
h(w) 1((x)
log + +1) nT
T
1
Pr k(m)(mm)
hi(x))
20
E (()) W-D
log(T + +1) 2Tnd
T
The proof is obtained by transforming the following expectation bound into high probability bound.
Lemma B.1 (Expectation bound (Kontorovich et al., 2022)). Let B be an (e, O-iffferreetllllllyy private algorithm that operates on T sub-databases and outputs predicate h X + [0, 1] and an index t E ...,...., .T. Let D = D2 ... Dn, be product distribution over X be distribution over X, let ø = (I1..... xT) where every 2j ~ DD is sampled independently, and let (h,, 1) +- B (T). Then,
E 1e-s.ho0 h(()) - -Tnd S
E B~D
[ax))
S
E (..((D) + Tnôô
HND
E~D (h.t)+B((a)
(b.t)eB(aa))
(b()))
(Here, we use h(D) as shorthand to denote Ey-D h(y)-)
Proof. The proof is identical to that of Lemma 3.1 of (Kontorovich et al., 2022) with v/r 0, and omitting the final inequality in the last chain of inequalities.
Proof of Theorem 2.2. We prove the first inequality; the second follows from similar arguments. Fix product distribution D on X. Assume towards contradiction that with probability at least 1 I/T algorithm A outputs a predicate h such that 22 - M(D)- - h(x) > log(T - 1) + 27nd. We now use A and 'D to construct the following algorithm B that contradicts Lemma B. We remark that algorithm B "knows" the distribution D. This will still lead to contradiction because the expectation bound of Lemma B.I holds for every differentially private algorithm and every underlying distribution.
Observe that B only accesses its input through A (which is (e, 8) ddiffrrentially private) and the exponential mechanism (which is (e, 0)ddifferenntillly private). Thus, by composition and post-processing. B is (2e, diffferrrtyy private. Now consider applying B on databases き = (It..... #T) containing i.i.d. samples from D. By our assumption on A. for every t we have that e 2e, hD( - hx( 2 4 log(T + 1) + 2Tn with probability at least 1/T. We therefore get
4
Pr
max {e-22 he(D) ha()))) 2 log(T + 11 + 27 nd [E[T]
2 11- (1-11-17 1/T)² 2 2
(()
13

---

Breaking the Quadratic Barrier
Algorithm 5: B
Input: T' databases of size each: ह = (01...... .T
Define h = 0 and set F t {(h, 1)}-
for / 1.... T
Let f4 < A(x)), and set F = F ([h,,t)}
Sample (h", from F with probability proportional to exp (5 (c-2e hh² - h² (x )))
return (*))
The probability is taken over the random choice of the examples in ø according to D and the generation of the predicates fa according to ( Thus, by Markov's inequality.
2 max max { 25 h2(D) --(( 2 log(T + Tnó.
E
END
[E[T]
B(a)
Recall that the set F' (constructed step of algorithm B) contains the predicate ha and hence,
E max {e-2s -,((D) - he(2x)) = E aw D (
max (0, max fc- -h(DD) - -h((z))) 2 log(T + 1) + Tná. (5)
(h,
LE[T]
So, in expectation, the set F contains pair (h, 1) with large difference e 25, h(D) - (. In order to contradict the expectation bound Lemma B.I, we need to show that this also the case for the pair (h", (*) that is sampled in Step 3. Indeed, by the properties of the exponential mechanism, we have that
2 log(? (T + 1).
2: (D) h² (zxe)) 2 max fe- 2e -h(D) h(x;)} (h+ (>>D")nEE
(6)
(h.))P
E
Taking the expectation also over t and ((x) we get that
E $<D
l hD( - h² hxxx))))
2
max fe- - - h(zx))
log + 1)
d~D ((a))
(h,t)F
(())
2
2 8
log(? (T' + + T'd
log(? [T' 1) T'no.
This contradicts Lemma B.I.
C. Analysis of the tracking estimator
Here we will prove Theorem 5.1:
suppose that an adaptive adversary provides most m inputs Algorithm such that the sketch of every input has at most k/2 deactivated keys. Then, with probability at least 3. for every input whose sketch has at most ak/4 deactivated keys, the output is (1 + cpppprooxiimaion of the true cardinality.
Theorem 5.1 (Analysis of TRobustEst). For value of (oog2
The analysis is analogous to Section 4.3; indeed, we will reuse most of the results from that section. We may make the same assumptions on k, a as at the start of Section 4.3, Again, we begin with an analog of Lemma 4.2:
Lemma C.1. If h = Eisppes (p)cr))(C(()rr)) + Lap(1/Eu) is replaced by = ΣiEv (pver))(C()e))) + Lap(1/so) then the outputs of Algorithm 4 change with probability at most B/4.
Proof. In order for not to equal h, the maximum value of P: in S must be below т. However, in that case, by assumption, most k/2 of these elements may be inactive, so the sum in h is at least k/2. order for the output to change in any given step, we must then have h < < h. However, this would require Lap(1/e0) < -k/4, which has probability at most - < m/ B. By union bound (as in the proof of Lemma 4.2), we are done.
14

---

Breaking the Quadratic Barrier
Again, assume henceforth that Algorithm 4 uses h instead of h. We now show once again that Algorithm 4 can be simulated by calls to Algorithm 1, with the same function hy, as in Section 4.3. Indeed, the only difference from Algorithm is that C' can only increment elements of the sketch S rather than the whole set V, so we need to ensure that there are never keys i V such that < T and i & S. We show this, along with the analogs of Proposition 4.4 and Proposition 4.5, by induction:
Claim C.2. The following holds with probability at least 1 8/2. Let d be the number of deactivated elements in the sketch S. Then, whenever < (1 - - the while loop in Algorithm continues to the next value of т, and whenever T ((1 + a/4)T + d)/ it terminates. Moreover, the values in C' always match the values that Algorithm would have.
Proof. We proceed by induction; suppose the statement has held true on all previous inputs and iterations of the while loop. We show that it holds on the current iteration - note that we must have T < (1 + / + dd/[V] by the inductive hypothesis, since otherwise the loop would have terminated in the previous step. Recall by assumption that d < k/2, and we set T k/4, so this means that T < k/lV/.
We first show that the current input, the keys V with Ps are all in the sketch S. Indeed, by the inductive hypothesis, we may apply Lemma 3.1 on hv.;
| - hv;+
<
T|V| 0llo(mm33///
32
0
ak
32
8
Since 7|V| < 7k/8, this means that we have hy, (p) < k. However, hv. (p) is just the count of E V such that Pt < T, so this count is less than k; then all such E are included in the sketch (since is a bottom-k: sketch).
Therefore, we have shown the second part of Claim C.2, since every value that would need be incremented is actually in the sketch C. remains show the first part.
We now apply Corollary 3.3 (again using the inductive hypothesis that our algorithm has matched Algorithm 1), to obtain that
< (1++//16)-V1++ >> -akk)))///kkk1166,
d,
(7)
(8)
where again, the value of is at most akk by the choice of k; and the sum in Corollary 3.3 is bounded by the number of deactivated elements satisfying hy.r (i, pt) = 1, which is at most d (since we just showed that all such elements are in S). The remainder of this proof is now identical to that of Proposition 4.4 and Proposition 4.5.
From Claim C.2, we deduce (identically to the previous analysis) that whenever ak 4, the output of the algorithm is (1 + apprroxxxintooon of [V.
15


Reviews:
[{"review_id": "ALXplOkxBr", "reviewer": "Reviewer_f3xR", "summary": "The paper addresses the problem of sketching under the additional constraint that each key appears in at most $r$ queries. This setting generalizes prior work by introducing a finer-grained robustness notion based on per-key participation rather than the total number of queries. The main result establishes that, under this assumption, the required sketch size should be proportional to $\\sqrt{r}$, rather than the sqrt of the number of queries that can be answered accurately. The authors provide theoretical justification for this claim and propose a robust estimation procedure based on per-key tracking.\n\n## update after rebuttal\n\nI believe the paper still requires substantial revision, including the overall structure of the paper, clarity of exposition, problem formulation, and experimental depth. I will maintain my original score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and comments.\n\n**> The paper lacks a rigorous, self-contained problem formulation, making it difficult for those unfamiliar with sketching literature to follow the argument effectively. The definition of \"query\" is ambiguous in the introduction and should be clarified.**\n\nWe will make sure to define the model more clearly in the introduction. To clarify here, the model is that there is an adversary selecting a set V (the \"query\"), and the algorithm receives the sketch S(V) and must compute an estimate of the cardinality |V| and return this to the adversary. This process is repeated over multiple rounds.\n\n**> a more extensive comparison with standard adaptive sketching techniques would strengthen the argument.**\n\nWe will survey additional related results. Prior to our work, all existing approaches to adaptive cardinality sketching obtained worst-case bounds, supporting at most a quadratic number of queries. The blue line in our plots (\"baseline\") captures the best prior result, showing our improvements. \n\n**> The experiments are conducted on toy datasets, which provide some intuition for the effectiveness of the approach but lack depth.**\n\nWe agree that we used synthetic datasets for our evaluations. The overall goal of this paper is to present a theoretical framework and provide proven guarantees, which we consider to be the main contribution of our work.\n\n**> The exposition is convoluted... does not provide sufficient background... Providing a clear high-level overview would be beneficial...**\n\nThank you for the feedback. For the revised version we will make sure to make the explanations, especially in the introduction, more clear and accessible, and properly define what a query is.", "claims_and_evidence": "The primary claim made by the paper is that the sketch size should be order of $\\sqrt{r}$ rather than a sqrt of the total number of queries. This result is formalized in Theorem 4.1. The theorem appears well-supported, and the authors provide proofs and an empirical evaluation. However, the paper lacks a rigorous, self-contained problem formulation, making it difficult for those unfamiliar with sketching literature to follow the argument effectively. The definition of \"query\" is ambiguous in the introduction and should be clarified.", "methods_and_evaluation_criteria": "The proposed methods involve a modification of bottom-$k$ sketches by introducing per-key participation tracking and a robust estimation procedure. While the techniques seem reasonable, the exposition is convoluted, making it difficult to assess the practical implications. The evaluation is based on synthetic data and demonstrates the improvement over prior methods in terms of the number of adaptive queries the sketch can support. However, a more extensive comparison with standard adaptive sketching techniques would strengthen the argument.", "theoretical_claims": "Theorem 4.1 states that robustness in the per-key participation model requires a sketch size of $\\sqrt{r}$. While the proof structure appears correct at a high level, I have not verified the details rigorously. Given the importance of this result, providing a clear high-level overview would be beneficial while having proof details in the appendicies.", "experimental_designs_or_analyses": "The experiments are conducted on toy datasets, which provide some intuition for the effectiveness of the approach but lack depth.", "relation_to_broader_scientific_literature": "he paper situates itself within the literature on cardinality estimation and sketching but does not provide sufficient background for readers unfamiliar with the area.", "essential_references_not_discussed": "I am not familiar with sketching literatures.", "other_strengths_and_weaknesses": "A major weakness of the paper is its organization and clarity. The structure is unfriendly to readers unfamiliar with sketching. A more rigorous and formal problem definition should be included early on. The term \"query\" is not well-defined in its initial usage, making the motivation unclear.", "other_comments_or_suggestions": "see the Strengths and Weaknesses section.", "questions_for_authors": "see the Strengths and Weaknesses section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "G6hf56RF0g", "reviewer": "Reviewer_hTkY", "summary": "Cardinality sketches support computing a small sketch/summary of a set of keys S from a universe U. The sketch supports estimating |S|. This problem is trivial without further requirements as one can merely store |S| in log(|U|) bits. A cardinality sketch thus further requires that given sketches of two sets A and B, one can compute the sketch of their union and intersection from the sketches themselves. When analysing the performance of a sketch, the authors considers how many adaptively chosen queries (cardinality estimates) that a sketch of size k can process without making a mistake. The paper designs sketches that can handle more than O(k^2) queries with sketch size k. Compared to previous work, the guarantee they give depend on the number of queries that share an element in U, instead of just the number of queries.\n\nSpecifically, they claim to design a sketch and an estimator that can handle an exponential number of adaptive queries if each key participates in at most \\tilde{O](k^2) queries. They also claim to extend this result to the case where this condition fails on a small fraction of keys.\n\nThey also state that one of their contributions is arguing that one can reduce constructing robust sketches to \"adaptive data analysis (ADA)\" instead of reducing to differential privacy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and comments.\n\n**> The biggest weakness is the section with the simulated data and the plots, which I think would benefit from a better explanation.**\n\nWe will make sure to add a more clear explanation of the empirical evaluation for the full version of the paper. To explain briefly here, the plots show the gain of our \"tracking\" robust estimator (Algorithm 4, which keeps track of the number of times each key is used) over our \"basic\" robust estimator (Algorithm 3), and over the baseline from prior work. The plots show how long the theoretical guarantee of each algorithm lasts, in the case where the query sets are drawn from some selected natural distributions. The plots demonstrate that, indeed, for these distributions, Algorithm 4 is likely to maintain its guarantee for much longer than Algorithm 3, which in turn is likely to outperform the baseline from prior work.\n\n**> Reduce the problem to ADA instead of the usual DP... then solve using DP. So it's not clear to me that their approach is as novel as claimed.**\n\nBy now we know of several approaches to solve the ADA problem. DP is definitely one of the prominent approaches, but it is not the only approach. In particular, as Blanc (2023) showed, the ADA problem can be solved using \"subsampling\" (without adding noise to the responses directly). Even though in our paper we do use DP at the end of the day to solve the resulting ADA problem, our new reduction shows that if tomorrow someone will come up with yet another solution to the ADA problem (maybe with some additional properties / providing more fine-tuned guarantees) then this new solution could potentially be applied, via our reduction, to design new robust sketches.", "claims_and_evidence": "The claims are supported by theoretical proofs. The ones that I read seem correct. Additionally, there is a small simulation study. It is not clear to me how the simulations support their claims.\n\nFurthermore, they claim that it is among their contributions to reduce the problem to adaptive data analysis instead of reducing it to the usual differential privacy. However, they then solve the adaptive data analysis problem using differential privacy, so it's not clear to me that their approach is as novel as claimed.", "methods_and_evaluation_criteria": "The comparisons to theoretical results in the litterature are appropriate.\n\nThe emperical evaluation using simulated synthetic data however, is not sufficiently explaned. Hence, it is difficult to determine if it's appropriate or not.", "theoretical_claims": "I checked all the proofs on pages 1-8 except for the proofs of the following which I merely skimmed:\nlemma 3.1, claim 3.2, corollary 3.3.\n\nAll the proofs seem correct.", "experimental_designs_or_analyses": "As mentioned above, it is unclear to me what the \"emperical evaluation\" actually says about their results, so I cannot determine if they are valid or not.", "relation_to_broader_scientific_literature": "Their algorithm and analysis are based on the privacy of their Algorithm 1 (Cohen & Lyu 2023), and they claim to break the \"quadratic barrier\" given by Cohen et al. (2024).", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "The paper is relatively easy to follow and so are the proofs. I think the results are nice and seem like they could be useful.\n\nThe biggest weakness is the section with the simulated data and the plots, which I think would benefit from a better explanation.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X4Bxjul8sj", "reviewer": "Reviewer_qFNd", "summary": "This work revisits the problem of robust cardinality sketches for adaptive queries and provides improved results. In the classic cardinality sketch, the queries are independent of the sampled sketch, and the sketches can answer an exponential number of queries (in the sketch size $k$). In the adaptive queries setting, a query can be chosen based on the output of previous queries. Existing work shows that these sketches can fail after $\\tilde{O}(k^2)$ queries.  \n\nThe paper breaks this quadratic barrier. It presents an adaptive data analysis framework that builds on the generalization property of differential privacy. It shows that by limiting each element's participation to $\\tilde{O}(k^2)$ times, the framework can answer an exponential number of queries. The paper further fits the Bottom-k sketch into this framework, resulting in a cardinality sketch that can answer $\\Omega(k^2)$ adaptive queries.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and comments.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Experiments validate the theoretical findings.", "relation_to_broader_scientific_literature": "The paper broadens the toolkit for designing robust algorithms.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper is well presented. It introduces the problem and relevant background in a succinct and accurate manner and presents the algorithms in an organized way. The contribution is substantial and offers a clear improvement over previous work in this area.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I don't have any specific questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a theoretically strong contribution that breaks the quadratic barrier in adaptive cardinality sketching by introducing a per-key participation model. The approach expands the robustness framework for sketches and offers new insights by connecting adaptive sketching to adaptive data analysis (ADA).

The submission is borderline. While Reviewer qFNd strongly supports acceptance and Reviewer hTkY finds the results promising, Reviewer f3xR raises several concerns, particularly regarding clarity, accessibility, problem formulation, and experimental depth. The weaknesses they point out include that the exposition is dense, the definition of certain key terms are delayed, and the empirical evaluation is underdeveloped.

Given the soundness of the theoretical contributions and the potential impact on robust sketching, I recommend a weak accept. Note that this decision may be overridden by the SAC/program committee depending on the available room in the program. The authors are encouraged to significantly improve the clarity of the problem setup, refine the empirical section, and address accessibility issues in the final version.
Decision: Accept (poster)