Private Federated Frequency Estimation: Adapting to the Hardness of the Instance
Authors: Jingfeng Wu
Wennan Zhu
Peter Kairouz
Vladimir Braverman
Venue: NeurIPS 2023 poster (2023)
Keywords: sketch
federated analytics
privacy

Abstract: In federated frequency estimation (FFE), multiple clients work together to estimate the frequency of their local data by communicating with a server, while maintaining the security constraint of $\mathtt{secsum}$ where the server can only access the sum of client-held vectors. For FFE with a single communication round, it is known that count sketch is nearly information-theoretically optimal [Chen et al., 2022]. However, when multiple communication rounds are allowed, we propose a new sketch algorithm that is provably more accurate than a naive adaptation of count sketch. Furthermore, we show that both our sketch algorithm and count sketch can achieve better accuracy when the problem instance is simpler. Therefore, we propose a two-phase approach to enable the use of a smaller sketch size for simpler problems. Finally, we provide mechanisms to make our proposed algorithm differentially private. We verify the performance of our methods through experiments conducted on real datasets.

Private Federated Frequency Estimation: Adapting to the Hardness of the Instance
Jingfeng Wu* Johns Hopkins University uuujfQjhu.c edu
Wennan Zhu Google Research wennanzhu0google.o com
Peter Kairouz
Vladimir Braverman
Google Research kairouz@google, com
Rice University vb21@rice.
Abstract
In federated frequency estimation (FFE), multiple clients work together to estimate the frequencies of their collective data by communicating with server that respects the privacy constraints Secure Summation (SecSum), a cryptographic multi- party computation protocol that ensures that the server can only access the sum client-held vectors. For single-round FFE, it is known that count sketching is nearly information- -hhoreeinttoortiically optimal for achieving the fundamental accuracy- communication trade-offs (Chen et al.] [022]. However, we show that under the more practical multi-rouse multi-round FEE setting, simple adaptations of count sketching are strictly sub-optimal, and we propose a novel hybrid sketching algorithm that is provably more accurate. We also address the following fundamental question: how should practitioner set the sketch size in way that adapts to the hardness of the underlying problem? We propose two-phase approach that allows for the use of smaller sketch size for simpler problems (e.g. near-sparse or light-tailed distributions). We conclude our work by showing how differential privacy can be added to our algorithm and verifying its superior performance through extensive experiments conducted on large- scale datasets.
Introduction
In many distributed learning applications, server seeks to compute population information about data that is distributed across multiple clients (users). For example, consider distributed frequency estimation problem where there are n clients, each holding local data from a domain of size d, and server that aims to estimate the frequency of the items from the n clients with the minimum communication cost. This task can be done efficiently by letting each client binary encode their data and send the encoding the server, a local communication bandwidth cost of log(d) bits. With the binary encoding, the server can faithfully decode each local data and compute the global frequency vector (i.e., the normalized histogram vector).
However, the local data could be sensitive or private, and the clients may wish to keep it hidden from the server. The above binary encoding communication method, unfortunately. allows the server to observe each individual local data, and therefore may not satisfy the users' privacy concerns. Federated Analytics (FA) [Ramage and Mazzocchi 2020 Zhu et al. 2020) addresses this issue by developing new methods that enable the server to learn population information about the clients while preventing the server from prying any individual local data. In particular, cryptographic
Work done during intersship at Google Research
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

multi-party computation protocol, Secure Summation (SecSum) [Bonawitz et al. 2016]. has become a widely adopted solution to provide data minimization guarantces for FA [Bonawitz al., 202T]. Specifically, SecSum sets up a communication protocol between clients and the server, which injects carefully designed additive noise to each data that cancels out when all of the local data are summed together, but blurs out (information theoretically) each individual local data. Under SecSum, the server is able to faithfully obtain the correct summation of the data from all clients but is unable to read single local data. The federated frequency estimation (FFE) problem refers to the distributed frequency estimation problem under the constraint of SecSum. Clearly, the binary encoding method is not compatible with SecSum, because when the binary encoding is passed to the server through SecSum, the server only gets the summation of the binary encodings of the users' data, which does not provide sufficient information for computing the global frequency vector.
naive approach to FFE can be accomplished by employing one-hot encoding: each client encodes its local data into a d-dimensional one-hot vector that represents the local frequency vector and sends it to the server through SecSum. Then the server observes the summation of the local frequency vectors using SecSum and scales it by the number of clients to obtain the true frequency vector. However, this one-hot encoding approach costs O (n)) bits of communication per client. This is because SecSum adds noise from a finite group of size (log n)) to each component of the d-dimensional local frequency vector (Bonawitz et al.) 2016) to avoid overflows. With a linear dependence on domain size d, the one-hot encoding approach is inefficient for large domain problems, which is common setting in practice. In what follows, we focus on the regime where d > n.
Recently, linear compression methods were applied to mitigate the high communication cost issue for FFE with large domains [Chen et al. 2021 2022]. The idea is to first linearly compress the local frequency vector into a lower dimensional vector before sending it to the server through SecSum; as linear compression operators commute with the summation operator, the server equivalently observes a linearly compressed global frequency vector though SecSum (after rescaling by the number of clients). The server then applies standard decoding methods to approximately recover the global frequency vector from the linearly compressed one. In particular, Chen et al. [022] show that CountSketch [Charikar et al. 2002] (among other sparse recovery methods) can be used as a linear compressor for the above purpose, which leads to communication bandwidth cost of (n log(d) lo)( bits. Therefore when d' > n, CountSketch achieves a saving in local communication bandwidth compared to the one-hot encoding method that requires (dd log(n)) bits. Moreover, Chen et al. (2022) show that for FFE with a single communication round, an 20 log(d)) (d)) local communication cost information information-theoretiaall -heoretically unavoidable for worst-case data distributions, i.e, we cannot do better without making additional assumptions on the global frequency vector.
Contributions. In this work, we make three notable extensions to CountSketch for FFE problems.
1. We show that the way Chen al. 2022] set up the sketch size (linear in the number of clients 7) is often pessimistic (see Corollary (2.4). In fact, in the streaming literature, the estimation eтror induced by CountSketch is known adapt to the tail norm of the global frequency vector [Minton and Price 2014), which is often sub-linear in n. Motivated by this, we provide an casy-to-use, two-phase approach that allows practitioners determine the necessary sketch size by automatically adapting to the hardness of the FFE problem instance.
2.
We consider FFE with multiple communication rounds, which better models practical deploy- ments of FA where aggregating over (hundreds of) millions of clients in a single round is not possible due to device availability and limited server bandwidth. We propose a new multi-round sketch algorithm called Hybr idSketch that provably performs better than simple adaptations of CountSketch in the multi-round setting, leading to further improvements in the communication cost. Surprisingly,
show that HybridSketcl ch adapts to the tail norm of a heterogeneity vector (see Theorem 3.2).. Moreover, the tail of the heterogeneity vector is always no heavier, and could be much lighter. than that of the global frequency vector, explaining the advantage of HybridSketon cSketch. For instance, on the C4 dataset [Bowman et al.) 2020) with a domain size of d = 150, 868 and 150, 000 users, we show that our method can reduce the sketch size by 83% relative simple sketching methods when the number of sketch rows is not very large.
We extend the Gaussian mechanism for CountSketch proposed by Pagh and Thorup (0022) Zhao et al. 2022 to the multi-round FFE setting to show how our sketching methods can be made differentially private [Dwork et al. 2006). We also characterize the trade-offs between accuracy and privacy for our proposed method.
2

---

We conclude by verifying the performance of our methods through experiments conducted on several large-scale datasets. All proofs and additional experimental results are differed to the appendices.
2 Adapting CountSketch to the Hardness of the Instance
In this part, we focus single-round FFE and show how CountSketch can achieve better results when the underlying problem is simpler. Motivated by this, we also provide a two-phase method for auto-tuning the hyperparameters of CountSketch, allowing it to automatically adapt to the hardness of the instance.
Single-Round FFE. Consider n clients, each holding an item from a discrete domain of size d. The items are denoted by xa E [d] for I,..., n. Then the frequency of item j is denoted by
f = -:= Ixe jl
We use to denote the one-hot representation of T4, i.e., x2 Cx, where (c+) refers to the canonical basis. Then the frequency vector can be denoted by
f= fa) = - - [0,
In single-round FFE, the n clients communicate with a server once under the constraint of SecSum, and aim to estimate the frequency vector f. Note that SecSum ensures that the server can only observe the sum of the local data.
Algorithm 1 COUNT SKETCH FOR FEDERATED FREQUENCY ESTIMATION
Require: n clients with local data 2; E [d] for f = 1.... n. Sketch length L and width W. The server prepares independent hash functions and broadcasts them to each client:
be
[d] [W], de [d] {+1}, for l [L].
2: for Client i 1...., , parallel do
3: Client encodes the local data æt E [d] to enc(x:) E R&XW where
(enc(x))) = [he( kt] oe(xx) for l [L], k [W].
4: Client sends enc(x;) E L SecSum.
5: end for
6: SecSum receives (enc(x:)))* t=1 and only reveals the summation Σ enc(x;) to the server.
7: for Item d in parallel do
8: Server produces I, estimators for fz:
dec(j; = ar(i) ET (nc(z))n)()))))) (mbe)) for l [4].
9: Server computes the median of the L estimators:
dec(j) == median(dec(j:() LE [[]]
10: end for
11:
return (dec(j)) estimate to (f))g
Count Sketch. CountSketch is classic streaming algorithm that dates back to [Charikar et al. 2002]. In the literature of streaming algorithms, CountSketch has been extensively studied and is known to be able to adapt to the hardness of the problem instance. Specifically, CountSketch of fixed size induces an estimation error adapting to the tail norm of the global frequency vector [Minton]
and Price 2014].
recent work by Chen et al. (2022 apply CountSketch to single-round FFE. See Algorithm for details. They show that CountSket ch approximately solves single-round FFE with communication cost of On log(d) log(n)) bits per client. Moreover, they show D(n log(d) bits of communication per client is unavoidable for worst-case data distributions (unless additional assumptions are made),

---

confirming its near optimality. However, the results by Chen et al. (2022) are pessimistic as they ignore the ability of CountSketch to adapt to the hardness of the problem instance. what follows, we show how the performance of CountSketch can be improved when the underlying problem becomes simpler.
We first present a problem-dependent accuracy guarantee for CountSketch of a fixed size, L X W, that gives the sharpest bound our knowledge. The bound is due Minton and Price [014 and is restated for our purpose.
Proposition 2.1 (Restated Theorem 4.1 in Minton and Price 20144). Let (fi) be estimates produced by CountSketch (see Algorithm 1y. Then each (0, 1). W 2 2 and L 2 log(1/p), holds that: for each j E [d], with probability least 1 p.
log(1/p)
If, fl
L
W
E>W
where (f1)z1 refers to (fi)21 sorted in non-increasing order, and
an absolute constant.
For the concreteness of discussion, we will focus on foo as a measure of estimation error in the remainder of the paper. Our discussions can be easily extended le or other types of error measures. Proposition 2 directly implies the following -eror bounds for CountSketch (by an application of union bound).
Corollary 2.2 (fao-erron bounds for CountSketch), Consider Algorithm) 7 (og(d/p) and W 2, it holds that: with probability at least p.
Then for each p E (0, 1),
[|dec(-) - fllce < <C
VW E >W
(1)
where C is absolute constant. In particular, implies that
||dec(.) fl C/W.
According to Corollary 2.2 the estimation error is smaller when the underlying frequency vector (2f))21 has lighter tail. In other words, CountSketch requires smaller communication bandwidth when the global frequency vector has a lighter tail. Our next Corollary 2.3 precisely characterizes this adaptive property in terms of the required communication bandwidth. To show this, we will need the following definition on the probable approximate correctness an estimate.
Definition 1 ((T, corr))/orreet An estimate = (fi) of the global frequency vector f = (f (T,p)-correc
P P(If fll=o max, 1f. - fil 7} <p.
Corollary 2.3 (Oracle sketch size). Fix parameters T,P E (0, 1). Then for CountSketch (see Algorithm to produce an (corect estimate, suffices the sketch size L log and
W = C min
Eeer
(2)
where C. > 0 is an absolute constant. In particular, the width W in satisfies W S W Wwors := m-minn (2/T, n).
(3)
Corollary 2.3 suggests that the sketch size can be set smaller if the underlying frequency vector has lighter tail. When translated to the communication bits per client (that is O(L W log(n)), where log(n) accounts for cost of SecSum), Corollary 2.3 implies that CountSketch requires
o( min [ 2 E,er f., n} log log(n)) < O0mnn(1m, n) log(d) log(n)) (4)
bits of communication per client to be (r, -coorrct.. In the worst case where (ft) is ((n) and T = (1/n). 4 nearly matches the Q( log(d) informatiinn-therrticc worst-case communica- tion cost shown in Chen et al. 2022 ignoring the log(n) factor from SecSum. However, in practice, (Jt) has fest-decaying tail, and (4 suggests that CountSketch can use less communication to solve the problem. We provide the following examples for better illustration of the sharp contrast. between the worst and typical cases.

---

Corollary 2.4 (Examples), Fix parameters T, E (0. Consider Algorithm 2 with sketch length log(d)) (dp).. Then in each case for Algorithm [ produce an (T,p)-corres estimate for 1/n:
1. When Ji x 2 it suffices to set W = (llog(/TT).
2. When fi X i i for > 1, it suffices to set W = (/a)
3. When ft x i-1 log (ii) for b > 1, it suffices to set W = ④ log (l/T))
4. When ft 10/n for ......................... n// 10, it suffices to set W ((1/T).
Two-Phase Method for Hyperparameter Setup. Corollary 2.3 allows to use CountSketch with smaller width for an easier single-round FFE problem, saving communication bandwidth. However, the sketch size formula given by (2) in Corollary 2.3 relies on crucial information of the frequency (ft) i.e., # (ff: : f: 2 r) and Ei<T f². which are unknown who sets the sketch size. Thus, it is unclear if and how these gains can be realized in practical deployments.
We resolve this quandary by observing that in practice, the frequency vector often follows Zipf's law [Cevher] 2009 Powerss 1998). This motives us to conservatively model the global frequency vector by a polynomial with parameters. By doing so, we can first run a small CountSketch to collect data from a (randomly sampled) fraction of the clients for estimating the parameters. Then based on the estimated parameter, we can set up an appropriate sketch size for a CountSketch to solve the FFE problem. This two-phase method is formally stated as follows.
We approximate the (sorted) global frequency vector (/7)(= by a polynomial two parameters a > 0 and 3 > 0, such that
Ceeherr 2009 with
is0; fi = poly B): poly (t: = 10, 1>1,
[B.00
3 where 1" == max EE=
< 1) is set such that poly (i; o, B) is a valid frequency vector. Here's 's an exccutive summary of the proposed approach for setting the sketch size.
1. Randomly select subset of clients (e.g., 5, 000 out of 10
2. Fix small sketch (e.g., 16 x 100) and run Algorithm I with the subset of clients to obtain an estimate (fi).
3. Use the top-k values (e.g., top 20) from f. to fit a polynomial with parameter a and | (under squared error).
Solve Equation
4 under the approximation that f =s B -1th and output W according to the result.
Experiments. We conduct three sets of experiments to verify our methods. In the first set of experiments, we simulate single-round FFE problem with the Gowalla dataset (Cho et al. 201 The dataset contains 6, 442, 892 lists of location information. We first construct a domain of size == 175, 000, which corresponds to grid over the US map. Then we sample n = d/10 = 17, 500 lists of the location information (that all belong to the domain created) to represent the data of n clients, uniformly at random. This way, we set up a single-round FFE problem with n 17,500 500 clients in a domain of size d = 175, 000. In the experiments, we fix the confidence parameter to be In In(2/p))
p = 0.1 and the sketch length to be from (10-3, 1). We only test 7 > 20/n n. because it is less important to estimate frequencies over items with small counts (say, 20). For CountSketch, we compute sketch width with three strategies, using (2) (called "instance optimal"), using 3 (called "minimax optimal"), and using the two-phase method. We emphasize that the "instance optimal" method is not a practical algorithm as requires access to unknown information about the frequency; we use it only for demonstrating the correctness of our theory. We set all constant factors to be 2. The results are presented in Figures ( and (b). We observe that the "minimax optimal" way of hyperparameter choice is in fact suboptimal in practice, and is improved by the "instance optimal" and the two-phase strategies.
16. The targeted -eroor T is chosen evenly
In the second set of experiments, we run simulations on the "Colossal Clean Crawled Corpus" (C4) dataset [Bowman et al.) 2020). which consists of clean English text scraped from the web. We treat each domain in the dataset as user and calculate the number of examples each user has. The domain size d = 150, 868, which the maximum example count per user. We randomly sample 150, 000 users from the dataset. We fix the sketch length to be L, 5. Other parameters are the same as the Gowalla dataset. The results are presented in Figures d() and (e), and are consistent with what we have observed in the Gowalla simulations.
5

---

Shared design
achieved 7. atror
minimax optimal optimal
fresh design
hybrid design
wwo-phase-methan
minimax optimal
Instance optimal
6014
two phase method
60m
com
f.
target
on
width
(a) Gowalla, single round
(b) Gowalla, single round
(c) Gowalla, multi-round
shared design
achlevad arror
fresh design
seatch hh wioh
hybrid design
minimax optimal optimal
minimax optimal
instance optimal
two-phase-methee
www-phase--eeee phase-methhd
ur target
target
width
(d) C4, single round
(c) C4, single round
(f) C4, multi-round
shared design desi hybrid design
ochieved f. arror
minimax optimal
achieved c. error
instance optimal
6.015
0.012
minimax optimal optimal two-phase-methhod
0.003
330
200
300
400
502
000
target f. errer
target
sketch width
(g) Setiment- 140,, single round
(h) Setiment- 140, single round
(i) Setiment- multi-round
Figure 1: Single-round and multi-round FFE simulations. Subfigures (a) and (b) compare different hyperpa-
rameter strategies for Sketch in single-round FFE problem on the Gowalla dataset [Cho et al. 2011 Subfigure (c) compares three sketch methods in multi-round FFE problem on the Gowalla datasct. Subrigures (d), (c), and (f) are counterparts subfigures (a), (b), and (c), respectively, but the C4 [Bowman al. 2020 dataset. Similarly, subfigures (g), (h), and (i) are counterparts of subfigures (a), (b), and (c), respectively, but on the Sentiment-1-44 [Go et al. 2009] dataset.
In the third set of experiments, we run simulations on a Twitter dataset Sentiment-144 [Go al. 2009]. The dataset contains d = 739, 972 unique words from N = 659, 497 users. We randomly sample one word from each user construct our experiment dataset. The number of rounds M 10. and in each round, N/10 65, 949 clients participate. The algorithm setup is the same as in the Gowalla experiments. Results are provided Figures [ () and (h), and are consistent with our prior understandings.
3 Sketch Methods for Multi-Round Federated Frequency Estimation
practice, having clients participate in a single communication round usually infeasible due to the large number of devices, their unpredictable availability, and limited server bandwidth (Bonawitz ctt al. 2019). This motivates us to consider a multi-round FFE setting.
Multi-Round FFE. Consider a FFE problem with M rounds of communication. In each round, clients participate, each holding an item from universe of size d. The items are denoted by
(m) E [d]. where t [n]] denotes the client index and m [M]] denotes the round index. For simplicity, we assume in each round a new set of clients participate. So in total there are N Mn
z;
clients. Then the frequency of item j is now denoted by
1
(m) Jt
f
=
Mn
For the m-th round, the local frequency is denoted by (( = -
=i] .Clearly, denote the one-hot representation of (m) i.c.,
(m) 1t
have fz 3I Em= f(mm). Similarly, we use x; (m)

---

shared design hybrd design
shared design hybri design
shared design fresh hybrd design
5. ereer in expectation
2. eroor expectation
in expectatoon
120
(a) fi x
(b) fi x
(c) f
Figure 2: Shared vs. Hybrid vs. Fresh Sketches. We refer the reader to Section 3 for the definitions of the three methods. We compute the expected for error for shared/hybridffresh sketches for a homogeneous, multi round-round FFE problem. The domain size is d = 10 The number of rounds is M = 10. In all setups, the sketch length is fixed to I. 5. In every setting, the foe error is averaged with 1, 000 random repeats for simulating the expectation. In the similarly to fresh sketch, and both are hetter than shared sketch. As long as the global frequency vector a slightly higher degree polynomial (e.g., with a degree higher than 3), then hybrid sketch is significantly better than both shared and fresh sketches.
The
when the global frequeney vector is low-degree polynomial, hybrid sketch performs
Xi (m) =e,(m) where (ee) refers to the canonical basis. Then the frequency vector be denoted by f -fi......ff fa)T. The aim is to estimate the frequency vector f in manner that is compatible with SecSum.
Baseline Method 1: Shared Sketch. A multi-round FFE problem can be reduced to single-round FFE problem with a large communication. Specifically, one can apply the CountSketch with the same randomness for every round; after collecting all the sketches from the M round, one simply averages them. Due to the linearity of the sketching compress method, this is equivalent to a single round setting with N Mn clients. We refer to this method count sketch with shared hash design (SharedSketch).
Thanks to the reduction idea, we can obtain the error and sketch size bounds for SharedSketch via applying Corollaries 2.2 and 2.3 to SharedSketch by replacing n by N Mn,
Baseline Method 2: Fresh Sketch. A multi-round FFE problem can also be broken down to M independent single-round FFE problems. Specifically, each round, and decode M local estimators for the M local frequency vectors. As the CountSketch produces an unbiased estimator, one can show that the average of the M local estimators is an unbiased estimator for the global frequency vector. We call this method count sketch with fresh hash design (FreshSketch). We provide the following bound for FreshSketch, The proof of which is motivated by] Huang et al. 2202T.
can apply independent CountSketch in
Theorem 3.1 cestance-specife bound for FreshSketch). Let (fz))= be estimates produced by FreshSketch. Then for each p (0, 1), W 2 and log(1/p), , it holds that: for each j E [d]. with probability at least 1
log(1/p) MM/(
1 W
- T
L
E>
where C' is an absolute constant, and (FF)) are defined in Theorem
3.2
Hybrid Sketch. Both SharedSketch and FreshSketch reduce multi-round FFE problem into single-round FFE problem(s). In contrast, we show more comprehensive sketching method, called that solves multi-round FFE problem as count sketch with hybrid hash design (lybridSketoh) Specifically, HybridSketor generates M a whole. HybridSketch sketches that share set of bucket hashes but use independent sets of sign hashes. Then in the m-th communication round, participating clients and the server communicate by the CountSketch algorithm based the m-th sketch, so the server observes the summation of the sketched data through SecSum, After collecting M summations of the sketched local data, the server first computes averages over different rounds for variance reduction, then computes the median over different repeats
presented as Algorithm 2
7

---

Algorithm 2 HYBRID SKETCH FOR FEDERATED FREQUENCY ESTIMATION
The number of rounds M. N Mn clients with local data xi (m) E [d] for [M] and I E [m]. Sketch length I. and width W.
Require:
The server prepares independent hash functions and broadcasts them each client:
h
[d]
> [W] ot (m)) [d] - {+1} for l [Z], E [M]
2: for Round 1, ..... M in parallel do
3: for Client L= = .,.... n in parallel do
4: Client (m, t) encodes the local data (mm) to (x) E RR where (m))
(enc(() (m) (ir (())))
[Ma(ot = ki o (xt (m)) for E [L], e [W].
e.k
5: Client (m, .) sends enc (x((m) to SecSum.
6: end for
7: SecSum receives (enc(m) (z) (mm) (z/ )) and reveals the sum Σ (
(m)) to the server.
8: end for
9: for Item j = ..... d in parallel do
Server produces M estimators for fz:
dec(j:m,l):= = o (f)
1 E emc(m) (z(mM))
for m E [M], & [L].
11: Server computes the median over E [L] of averages over m [M] of the estimators:
dec(j) median
M7 ΣM dec(j; l [4]].
12: end for
13:
return (dec())) as estimate to (fz)
(or sketch rows) for success probability amplification. We provide the following groblem-dependeed bound for HybridSket.o
Theorem 3.2 (Instance-specific bound for HybridSketch). Let (fz) be estimates produced by HybridSketch (see Algorithu 2. Define a heterogeneity vector (F:) by
M
1
(m)
F
i= i=
M
m=1
Clearly, it holds that F; S fs for every i E [d.. Let (F)' (F2) (Fi)sz1 sorted in non-increasing
order. Then for each p E (0, 1). W 2 and L ()p() it holds that: for each j E [d]. with
probability at least P.
log(1/p)
If, - fyl
Σ SW
L
W
where C' is an absolute constant.
We would like point out that, although our HybridSketch algorithm is developed for multi-round frequency estimation problems, it can be adapted to multi-round vector recovery problems as well. Hence it could have broader applications in other federated learning scenarios.
Hybrid Sketch vs. Fresh Sketch. By comparing Theorem 3.2 with Theorem 3.1 we see that, with the same sketch size, the estimation error of HybridSketch smaller than that of FreshSketch by factor of / /log(M/p). This provides theoretical insights that Hybri dSketch is superior to FreshSketch in terms of adapting to the instance hardness in multi-round FFE settings. This is also verified empirically by Figure

---

Hybrid Sketch vs. Shared Sketch. We now compare the performance of HybridSketch and SharedSketch by comparing Theorem 3.2 and Proposition 2.1 (under revision of replac- ing with N = Mn). Note that
items error 0.1/ width
10
shared design fresh design
hybrid design
10t
F
1 M
Σ
mJ)
1 M
mm)
ft.
10
m=
So with the same sketch size, HybridSketch achieves an error that is no worse than csc in every case. Moreover, in the homogeneous case where all local frequency vectors are equivalent to the global frequency vector, i.e., f(m) = f for all m, then it holds that F; = f./ M. So in the homogeneous case, HybridSketch achieves error that is smaller than that of esc by a factor of 1/VM. the general cases, the local fre- quency vectors are perfectly homogeneous, then the improvement of Hybr HybridSketch over SharedSketch will depend on the heterogeneity of these local frequency vectors.
10
200
400 600 aãc
1000
1200
sketch width
The number of items with error greater than 0.1/width for Shared. Hybrid, and Fresh Sketches with C4 dataset. HybridSketch with width 200 achieves roughly the same emorr as SharedSketch with a width of 1200 and Fresh sketch with width of 600.
Figure 3:
Experiments. We conduct three sets of experiments to verify our understandings about these sketches methods for multi-round FFE.
In the first sets of experiments, we simulate a multi-round FFE problem in homogeneous settings, where in every round the local frequency vectors are exactly the same. More specially, we set domain size d 10S, number of rounds M local frequency vectors are the same and (hence also the global frequency vector) are proportional to (i-1-1) 1- L= 5. In each experiment, we measure the expected -erorr of each method with the averaging over 1, 1,000 independent repeats. The results are plotted in Figure 2 We can observe that: for low-degree polynomials, HybridSketch is nearly good as FreshSketch and both are better than SharedSketch. But for slightly high degree polynomials (with a degree of 3), HybridSketch already outperforms both FreshSketch and SharedSketch. The numerical results consistent with our theoretical analysis.
and test three different cases, where all the
(i=)) and (i (i= respectively. In all the settings, we fix sketch length to
In the second sets of experiments, we simulate multi-round FFE problem with the Gowalla dataset [Cho al.] [01 Similar previously, we construct domain of size d 175, 000, which corresponds grid over the US map. Then we sample N = d 175, 000 lists of the location information (that all belong to the domain created) to represent the data of N clients, uniformly at random. We set the number of rounds to be M = 10. In each round, n N/M = 17, 500 clients participate. The results are presented in Figure Ttc. Here, the frequency and heterogeneity vectors have heavy tails, HybridSketch and FreshSketch perform similarly and both are better than SharedSketch. This is consistent with our theoretical understanding.
In the third sets of experiments, we run simulations on the C4 [oowman et al. 2020 dataset. Similar to the single round simulation, the domain size 150, 868. We randomly sample N 150, 000 users from the dataset. The number of rounds M = 10, and in each round, N/10 = 15, 000 clients participate. The results are provided in Figures f[()) and Here, the frequency and heterogeneity vectors have moderately light tails, and Figure 3 alaredy suggests that Hybri produces an estimate that has better shape than that produced by FreshSketch and SharedSketch, verifying the advantages of HybridSketch.
4 Differentially Private Sketches
While SecSum provides security guarantees, it does not provide differential privacy guarantees. In this part, we discuss simple modifications to the sketching algorithms to make them provably differentially private (DP).

---

Definition 2 6)-DP [worr et al. 2006) ). Let alg(-) be randomized algorithm that takes dataset D its input. Let I' be its probability measure. alg(-) is (e, if: for every pair of neighboring datasets D and 'D', it holds that
P(alg(D) E) <e. .(faag((D) E +
In case, a dataset corresponds to all participated clients (or their data), and two neighboring datasets should be regarded as two sets of clients (local data) that only differ in a single client (local data). The algorithm refers to all procedures before releasing the final frequency estimate, and all the intermediate computation is considered private and is not released.
We work with central DP, that is, server releases data in a differentially private way while clients do not release data. We focus on Hybrid as representative algorithm. The DP mechanism a DP mechanism that
can also be extended to the other sketching algorithms. Specifically, adds independent Gaussian noise to each entry of the sketching matrix, which is initially proposed for making CountSkete differrnniillyy private by Pagh and Thorup 2022 Zhao et al. [2022].
We provide the following theorem characterizing the trade-off between privacy and accuracy. Theorem 4.1 (DP-hy -hyrid sketch). Consider a modified Algorithm [ where we add to each entry of the sketching matrix an independent Gaussian noise, (O, Co /Llog(1/6)/e) where co > is known constant. Suppose that L = log(d/p) and W 2 2. Then the final output of the modified Algorithm 2 denoted by (fo)z= is (c, ().P) for 1 and 5 < 0.1. Moreover, with probability at most 1 p. it holds that
max 15, - (V (V Vlog(d/p) log()
W
nVMe
where C >>0 O is an absolute constant and (FF) are as defined in Theorem 3.2
It is worth noting that if the number of clients per round (n) is fixed, then a larger number of rounds M improves both the estimation error and the DP error in non-worst cases, e-g.. when the local frequency vectors are nearly homogenous. However, if the total number of clients (N Mn) is fixed, then a larger number of rounds M improves the estimation error but makes the DP error worse.
When M- = 1. Theorem 4. recovers the bounds for differentially private CountSketch in Pagh and Thorup 2022]. Zhao al. [2022] and Theorem 5.1 in Chen et al. 2022]. Moreover, Chen et al. 2022 shows that in single-round FFE, for any algorithm that achieves an lo -error smaller than T == ((Vlog(d) log (og(1/6)/(nne)) in the worse case. each client must communicate Ω(
minf / logg dd/ / (10)), log(d))) bits (see Their Corollary 5.1). In comparison, According to Theorem 4.1 and Corollary 2.3 the differentially private CountSketch can achieve an loo -erorr smaller than F with length L log(d) and width
(
((f 22 1 E)) JIST
- n S
W = C min
min(2/T,
resulting in a per-client communication of O(W L log(n)) bits, which matches the minimax lower bound in Chen al. (2022) ignoring log(n) factor, but could be much smaller in non-worst cases where (f) decays fast.
5 Concluding Remarks
We make several novel extensions to the count sketch method for federated frequency estimation with one or more communication rounds. In the single round setting, we show that count sketch can achieve better communication efficiency when the underlying problem is simpler. We provide a two-phase approach to automatically select a sketch size that adapts to the hardness of the problem. In the multiple rounds setting, we show a new sketching method that provably achieves better accuracy than simple adaptions of count sketch. Finally, we adapt the Gaussian mechanism to make the hybrid sketching method differentially private.
We remark that the improvement of the instance -eeeeneed method relies on the assumptions that the underlying frequency has a lighter tail, which might be unverifiable a priori due to constraints, e.g., limited communication and privacy budget. Finally, this work focuses frequency is considered to be fixed. Extending our results to an online setting where the frequency varying is an interesting future direction.
offline setting where the
10

---

Acknolwdgement
We thank the anonymous reviewers for their helpful comments. We thank Brendan McMahan for insightful discussions during the project. VB has been partially supported by National Science Foundation Awards 2244899 and 2333887 and the ONR award N000142312737.
References
Kallista Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning on user-held data. arXiv preprint 1.Ii:6611.004500 2016.
Kallista Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In MLSys. mlsys.org, 2019.
Kallista Bonawitz, Peter Kairouz, Brendan McMahan, and Daniel Ramage. Federated learning and privacy: Building privacy-preserving systems for machine learning and data science on decentralized data. Queue, 19(5):77-114, 2021.
Samuel R. Bowman, Gabriel Angeli, Siddharth Jain, Jared Kaplan, Prafulla Dhariwal, Saurabh Neelakantan, Jonathon Shlens, and Dario Amodei. C4: Colossal clean crawled corpus. arXiv preprint arXiv:2005. 14165, 2020.
Volkan Cevher. Learning with compressible priors. Advances in Neural Information Processing Systems, 22, 2009.
Moses Charikar, Kevin Chen, and Martin International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
Finding frequent items in data streams, In
Wei-Ning Chen, Christopher A Choquette-Choo, and Peter Kairouz. Communication efficient federated learning with secure aggregation and differential privacy, In NeurlPS 2021 Workshop Privacy in Machine Learning. 2021.
Wei-Ning Chen, Ayfer Özgür, Graham Cormode, and Akash Bharadwaj. The communication of security and privacy in federated frequency estimation. arXiv preprint arXiv:22 2022.
Eunjoon Cho, Seth A Myers, and Jure Leskovec. Friendship and mobility: user movement in location- based social networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1082-1090, 2011.
Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N Project Report. Stanford, 1(12), 2009.
Ziyue Huang, Yuan Qiu, Ke Yi, and Graham Cormode. Frequency estimation under multiparty differential privacy: One-shot and streaming. arXiv preprint arXiv:2104.07808 2021.
Gregory T Minton and Eric Price. Improved concentration bounds for count-sketch. In Proceedings of the twent--ffth annual ACM-SIAM symposium on Discrete algorithms, pages 669-686. SIAM, 2014.
Rasmus Pagh and Mikkel Thorup. Improved utility analysis of private countsketch. arXiv preprint arXiv:2205.0883 083977 2022.
David M. W. Powers. Applications and explanations of Zipf's law. In New Methods in Language Pro- cessing and Computational Natural Language Learning, 1998. URL htttps://aaee hatp///ccaanntooggyyo org/W98- 1218

---

Daniek Ramage and Stefano Mazzocchi.
Federated analytics:
Collaborative
data
science without data collection. https: /ttp://:/aaaogggg//// googleblog...oooooooooooooooooo. wom/2020/055
federated anw.lyttii--lllllorrttttoooooaea
html 2020.
Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. arXiv preprint 00%/:: 2022.
Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li. Federated heavy hitters discovery with differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 3837-3847. PMLR, 2020.
12

---

A Missing Proofs for Section 2
A.1 Proof of Proposition 2.1
Proof of Proposition
2.1
We refer the reader to Theorem 4.1 in Minton and Price 2014
A.2 Proof of Corollary 2.2
Proof of Corollary
2.2
From Proposition 1 we know that
log(1/6)
for every j [d].
I
[dec(()) - fyl c.
E(ft)
<
L
W
&W
By union bound we have
log(1/5)
PP there cxists j [d], |dec(j) ful > C.
Σ(Ar
dô.
W
Replacing d with 8/d, setting L (og(d/)). and using the definition of lo norm, we obtain
P dec(.))
ol > C.
Σ
<6
W
OW
We next show that:
W EOP W
To this end, first show that fi W. If not, must have for i 1, W, f. W as (fZ) is sorted in non-increasing order. Then Σ J 2 E J > 1, which contradicts to the fact that (Jz ) is frequency vector. We have shown that fw S W and this further implies that for any i 2 W, ft S fw S w. Then we can obtain
1 W
EOPS
EE
W
W
&W
since (fi))m) is frequency vector. We have completed all the proof.
A.3 Proof of Corollary 2.3
Proof of Corollary 2.3
Define
1 W
E(W) = V
E(ft).
We will show the following:
1. IF 2 2 # Ejer f then F(W) ST.
2. Moreover, if E(W) r. then W 2 | 7} Ener f7)
Then Corollary 2.3 follows by combining Corollary 2.2 with the above claims.
We first show the first part. First note that W # 2 r} and that (Sr) is sorted in non- increasing order, so for all 2 W holds that f < r. Therefore,
F(W)
Σ
Σ l?.
W
VW
SW
JUST
Moreover, note that W>
2 1 Eher fc further have E(W) T.
13

---

To show that second part, we first note that, by definition, E(W I 7 is equivalent to
2W 2 W
Σ (.
72
1>W
Consider the following function
F(k):= =
Ei: k
one can directly verify that F(k) minimized at ki* = # : fi 2 T}: moreover,
F(k") = k=" = + 7/2 Er.
72
FiCT
Therefore, we have
2W F(W) 2 F(k') #If 7)
Σ f..
72
fict
This completes our proof.
B Missing Proofs for Section 3
B.1 Proof of Theorem
3.1
Proof of Theorem 3.1 The proof is motivated by Huang et al. 2021
Define the following events
1m C
1
((m))
log(1/p)
(m!
s m E [M]. E [d].
L
W
i>
Then by Proposition 2.1 we have
P(E,
2 -
Then by union bound, we have
M
F.
2 1p
Conditional on the event of 0mm F. (m)) we know that every random variable ffm)) - is bounded within
(- pptm), f(()),
where
(fm) C.
(1g()/))
Σ (m))
L
W
iW
So by Hoeffding inequality, we have
m
1
Σ
mm))
log(2/p1)
M (F(m))
p
M
M
2M2
Then we have
1
(m)
M
f(m))
log(2/p1)
Σ (F(m))2
M
2 P1 Mp.
M
2.2
14

---

Note that
log(2/p1)
Σ (F(m))²= 2= 1og(2/p1)
M
M
C²
log(1/p)
1
(1!m))
2M
2M
I.
m=1
m=1
i>
C². log(2/p1) (og((1p))
(P))
21.
So we have
P
Σ m)
(m)
C
log(2/p1) log(1/p)
(F))
(Fi)
M
M
2L
W
WsW
P1 Mp.
Note replace P1 = p' 2 and == p/ (2M) we have that
M
f(m)
M
mm)
C²
log(1/p")ogg
(M/v))
Σ
(Fi)
21-p p/.
M
M
L
W
m=
m==
W
B.2 Proof of Theorem 3.2
Proof of Theorem 3.2 Let us consider the hybrid sketch approach in Algorithm 2 Recall that within a round, clients use the same set of hash functions to construct their sketching matrices. Across different rounds, clients use the same set of location hashes but a fresh set of sign hashes. Denote the hash functions by:
he [d] + [w),
t= L;
(m) [d] - -+,, t= L......, Lg m 1..., M.
Recall the local frequency in each round is defined by
(17) Σ (mm.))
m 1,..., M.
And the global frequency vector is defined by
p(m)
M
Then according to the communication protocol, the server receives M sketching matrices (each corresponds to a summation of clients' sketches within the same round). From the m-th sketch, we can extract L estimators for each index j E i...
(m.
Σ 1 (1) he(i) (mm) (j) (m) (i) m
of
j [d. E [M], e [4]
rf()) + Σ (1a he(i) of (mm) (j) (m))
(t) p(m))
For each index, we will first average the estimators from different rounds to reduce the variance, then take the median over different rows to amplify the success probability. In particular, denote the round-wise averaging by
M
Σ
j [d] Le [L]
M
m=1
M
M
(he(1) he(5) (m) (m) (1)- 0m (i) (m))
(m))
M
M
m=
m=
15

---

M
f
[he(i) = hoO)
Σ
o
(m))
(j) oi (m)) (i) p!
signal
if}
m=1
M
Σ
1 [be(1) = h₂)
(m) (j).0) oe (m) r!!m
M
signal
m=1
headNoize
M
+ M
E [brlt))
he)
Σ
(m) (i) ot (i) p! of
(5)
tailNoise
Then take the median over these estimators to obtain
= median (1)0)
[L]}, j E [d].
Head Noise. The only randomness comes from the algorithm. Note that the head noise contains at
most |W] s 0.1W independent terms, and each is zero with probability 1/W. Thus the head
noise is zero with probability at least (1 - 1/W)I 2 (1 1/W)0.1W 2 0.9 provided that W 10.
Tail Noise. Now consider the second noise term in Fixing l' and j. Define
< (m))
di (m)
(j)
oi
(m)
p!
M
& = Σ {m) Σ
(m)
(j) of (m) (i) r((m)
7/ 1 (i) h(1)1
1
tailNoise = M
Σ Ths E
First notice that (5(
(())
m=1 are independent random variables and
EiS!" = 0. Varle!m)] (f/m²) 2
These imply that
M
[ = O, Var[g:] = Σ (?(m))?
m==
Moreover, notice that (m,, Edii are independent random variables, and
Ein²1 W
we then have
E|mAS = 0;
Var(n:S Einr] Var(G:] Var[n]] (E(c.))
M
1
( m))
W
m=1
Therefore conclude that
EftailNoise]
Σ
E[n = 0:
M
Var[tailNoise]
Σ
Var[n&]]
M
16

---

M Σ
(1!
M
if W
m=
)
M2W
N m=
Then by Chebyshev that: for fixed [d] and & [L] it holds that
M ( 2
10
P
tailNoisel|
0.1.
M2W
W m=1
By union bound we see that: for fixed j E [d] and & E [L] it holds that
P
f/
10
Σ
> 0.8 > 0.5.
M
NEW
Probability Amplification. Fixing Recall that (Z)) i.id. random variables and that median :LE [L]]. By Chernoff over l and union bound over j that:
pf for each [d],
[[,
fyl
10
ΣΣ
(r!
2d exp(I(()))
M2W
N
By choosing I. 0(log(2d/8)) obtain that, with probability least 5,
M
for each j E [d],
[f - fy x
10
(r. ) 2
M2W
W m==1
C Missing Proofs for Section
C.1 Proof of Theorem 4.1
Proof of Theorem 4.1 We follow the method of Pagh and Thorup [2022
Zhao et [2022] add
DP noise to all M sketches. Suppose F = (f(m) and f (f(m M7 frequencies for two neighboring datasets respectively, then
are the sets of local
|F -F F12 1
n Denote the sketches to be released by S F = (S(m)) p(m)) M fz-sensitivity:
m= One can then calculate the
- VL
where (d/() is the sketch length. Therefore the sketching will be (c, by adding Gaussian noise No0, o?) to each bucket of each sketch, where
log((1)))
me
The final released frequency estimator is obtained by post-processing the sketch, it also (c, 8)-D. We then calculate the error for the noisy sketch matrix. For each row estimator, we have that with probability least 2/3:
M Σ
f (8) F3 tti GaiiNe +
radm NN(0,
M
m=

---

tailNoise - /M)
(r. (r) 2 +
v I. log(11/))
M
VMne
m=
By taking median over I, ~ log(d/6) repeats, we see that with probability at least 6, it holds that
Mog(d/0) log(1/6)
for each j E [d],
[f, fyl x
(m/m)))²
M
VMne
18


Reviews:
[{"review_id": "Lw6y5dEoax", "reviewer": "Reviewer_2XAM", "summary": "This paper explores several variants of the count sketch method for federated frequency estimation (FFE).\n- With only one communication, they provide a refined instance-dependent analysis for CountSketch and find that the sketch size depends on unknown problem-dependent quantities.\nThey then propose a two-phase approach to first learn these quantities first and then perform FFE.\n- They also consider the case where multiple communication is available, they explore several variants of count sketch methods to utilize the multiple communication rounds, provide theoretical analysis, and conduct numerical experiments to verify their findings.\n- They also explore a differential private extension.\n\n======= after rebuttal =======\n\nI have read the author's rebuttal which addresses most of my concerns.\n\nThe remaining issue from my perspective is the lack of an instance-dependent lower bound which is left as a future work, as claimed in the rebuttal.\n\nHence, I tend to increase the point.", "questions": "1. From Figure 1 (a)(d), I find that given a target $\\ell_{\\infty}$ error, the minimax optimal curve often achieves a smaller $\\ell_{\\infty}$ error than the instance optimal one, though the latter aligns with the straight line $y=x$ better. It seems that the minimax optimal one is better than the instance optimal one in the achieved accuracy, which is quite counterintuitive. Is there anything I missed? Could the author provide some explanation?\n2. Could the author provide some intuitive explanation about why Hybrid Sketch could be better than Fresh Sketch? Note that Hybrid Sketch shares a set of bucket hashes but uses independent sets of sign hashes. Why this dependence on shared bucket hashes is better than independent bucket hashes? What about independent bucket hashes and shared sign hashes?\n3. Is it possible to provide any lower bound to show the instance-dependent upper bounds are tight?\n4. Line 316, when $n$ is fixed, why increasing $M$ improves the estimation error? In Theorem 4.1, the estimation error $\\sqrt{\\frac{\\sum_{i>W}\\left(F_i^*\\right)^2}{W}}$ seems to have nothing to do with $M$ in the worst case.\n5. Is it possible to extend the methods developed in this paper to empirical risk minimization where gradients of nonconvex models (such as neural networks) are used?", "limitations": "N/A.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "They conduct a systematic investigation of FFE problems and provide theoretical analysis.\n\nThe paper is well-written and easy to follow.", "weaknesses": "The paper tries to study a lot of stuff, which, however, left many questions untouched. See the Questions part.\n\nThere seems not much novelty in the theoretical analysis. \n\nThe benefit of instance dependence on the estimation guarantee is not well illustrated.\n\nThough the author provides a lot of numerical experiments to validate their theoretical predictions, it is still unclear how the proposed method would affect practical training where (overparameterized) neural networks are used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions. We address your concerns as follows. \n\n---\n**Q1**. “From Figure 1 (a)(d), … It seems that the minimax optimal one is better than the instance optimal one in the achieved accuracy, which is quite counterintuitive. Is there anything I missed? Could the author provide some explanation?”\n\n**A1**. We respectfully point out that Figures 1(a) and (d) imply that the minimax optimal curve is **worse** than the instance optimal curve in terms of computing a minimal necessary sketch size. Observe that the minimax optimal curve archives a smaller error than the instance optimal curve, while both are smaller than the targeted error. Note that Count Sketch with a larger sketch size archives a smaller error. So Figures 1(a) and (d) show that the minimax optimal method (eq. (3)) computes an unnecessarily large sketch size to achieve a targeted error, causing a waste of bandwidth, while the instance optimal method (eq. (2)) computes a more accurate sketch size. This is also illustrated in Figures 1(b) and (e).\n\n---\n**Q2**. “Could the author provide some intuitive explanation about why Hybrid Sketch could be better than Fresh Sketch? Note that Hybrid Sketch shares a set of bucket hashes but uses independent sets of sign hashes. Why this dependence on shared bucket hashes is better than independent bucket hashes? What about independent bucket hashes and shared sign hashes?”\n\n**A2**. Fresh Sketch computes an “average of medians”, that is, produces well-concentrated estimates of each local frequency independently and then takes the average to produce an estimate of the global frequency. In comparison, Hybrid Sketch computes a “median of averages”, that is, 1) produces high-variance estimators for each local frequency, then 2) averages them to obtain low-variance estimators for global frequency, and finally 3) uses the median trick to amplify success probability. \n\nFresh Sketch is less effective than Hybrid Sketch because the average of independent well-concentrated estimates is less well-concentrated compared to the median of independent low-variance estimates. This is because, for a good event (where the error is small) to happen in the former method, multiple independent good events have to happen simultaneously, which leads to an invocation of the union bound. In contrast, the good event in the latter method only fails with at most exponentially small probability.\n\nIn Step 2) of Hybrid Sketch, we use fresh sign hashes and shared bucket hashes to reduce estimation variance. The fresh sign hashes allow cancellation of errors when averaging the (high-variance) local estimators, which leads to an error bound that depends on the heterogeneity vector rather than the global frequency vector. The shared bucket hashes allow the error cancellation to happen in the same bucket, avoiding interface from other buckets, which leads to an error bound that depends on only the tail of the heterogeneity vector rather than the entire vector. \n\n---\n**Q3**. “Is it possible to provide any lower bound to show the instance-dependent upper bounds are tight?”\n\n**A3**. Minimax lower bound exists in the literature that justifies the sharpness of the upper bound in the worst case, see, e.g., Theorem 8.1 in [13]. However, whether or not there is an instance-dependent lower bound that matches the best-known instance-dependent upper bound is still an open problem to the best of our knowledge, and we will leave that for future work. Our conjecture is that the current instance-dependent upper bound (e.g., Proposition 2.1) can be improved. \n\n---\n**Q4**. “Line 316, when $n$ is fixed, why increasing $M$ improves the estimation error? In Theorem 4.1, the estimation error $ \\sqrt{ \\frac{\\sum_{i>M} (F_i^*)^2} {M} } $ seems to have nothing to do with $M$ in the worst case.”\n\n**A4**. Thank you for pointing out this typo. We will revise line 316 to “... a larger number of rounds M improves the estimation error **in non-worst cases, e.g., when the local frequency vectors are nearly homogenous**...”\n\n---\n**Q5**. “Is it possible to extend the methods developed in this paper to empirical risk minimization where gradients of nonconvex models (such as neural networks) are used?”\n\n**A5**. Good question. Our focus in this work is a federated frequency estimation problem. However, our analysis for Count Sketch and Hybrid Sketch can be applied to general vector recovery problems as well. Therefore, we expect our methods can be applied to estimate the gradient vectors in the ERM problem. We will comment on this in the revision. \n\n---\n**Q6**. “There seems not much novelty in the theoretical analysis.”\n\n**A6**. We use some standard techniques to derive our bounds. However, we’d like to emphasize that both the considered multi-round FFE problem settings and results are new. It also requires non-trivial efforts to establish new effective algorithms such as Hybrid Sketch, to allow the sketching method to adapt to the hardness of the instance, and to make the algorithm differentially private. \n\n---\n**Q7**. “The benefit of instance dependence on the estimation guarantee is not well illustrated.”\n\n**A7**. We hope our explanations about Figure 1 in **A1** have clarified the benefits of instance-dependent methods over the minimax optimal method. We are happy to improve our presentation further if you have specific suggestions! \n\n---\n**Q8**. Though the author provides a lot of numerical experiments to validate their theoretical predictions, it is still unclear how the proposed method would affect practical training where (overparameterized) neural networks are used.\n\n**A8**. We’d like to emphasize that our focus in this work is the federated frequency estimation problem and neural network training is beyond the scope of this work. We agree that extending our methods to neural network training is an interesting future direction. \n"}, {"review_id": "pPoUv2A131", "reviewer": "Reviewer_gbH4", "summary": "This paper tackles the problem of Federated Frequency Estimation (FFE) by leveraging the Federated CountSketch algorithm (Algorithm 2 in this paper). Compared to previous FFE methods the authors argue that if the tail of the underlying frequencies is light or small (\\emph{i.e., } the smaller frequencies have considerably smaller values). Furthermore, such a lighter tail provides two benefits, (1) The FFE error decreases and (2) A smaller width can be afforded in the Federated CountSketch algorithm that leads to a direct reduction in the client communication costs. Under a Federated setting, both advantages are meaningful. In the first half of the paper, the authors provide ways to leverage this lighter tail in the Federated setting. While in the second half, the authors provide FFE algorithms that work for a large number of clients by running CountSketch over multiple groups of clients. Finally, the paper also provides a Differential Privacy (DP) guarantee and estimation error while running the FFE algorithm over multiple rounds.\n\nOverall, the authors provide a clear and unique analysis that furthers the FFE literature by reduction of the estimation error and sketch width when leveraging the (almost optimal) CountSketch algorithm. The empirical evaluations provide a complete picture of the impact of the suggested method. Minor comments regarding the two-phase method, empirical evaluations, and DP section have been provided below.\n", "questions": "The paper is well-written and conveys interesting results for performing Federated Frequency estimation over various scenarios. I do not have major concerns regarding the paper. A few minor suggestions have been pointed out in the weaknesses section.\n\n", "limitations": "The primary limitation of the proposed method has been provided in point 3 of the weaknesses section. The authors can consider including a limitations/discussion section that highlights such challenges.\n\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper tackles several challenges in the FFE literature. Primarily the authors demonstrate FFE algorithms for the cases when (1) the number of clients is low to moderate and (2) for a high number of clients. They also tackle the case when Differential Privacy (DP) is introduced in FFE deployments.\n\n1. The core idea that the authors leverage is the reduction in the estimation error while using the CountSketch algorithm when the underlying frequencies have a lighter tail. The authors argue that when the data is distributed in such a (lighter-tail) fashion, the previous estimation error bounds are unable to leverage these tighter bounds to provide real-world benefits. Using Corollaries 2.2-2.4 the authors demonstrate a reduction in the estimation error and the sketch width and thus the communication cost of the clients.\n2. Furthermore, the paper suggests that when the clients are high in number, simply computing CountSketch over a single round might not be feasible. They demonstrate that the naive application of CountSketch in the multi-round setup is not enough. Thus, they suggest a new algorithm “Hybrid Sketch, \" extending CountSketch for the multi-round setup. The Hybrid Sketch algorithm by maintaining the same hash buckets can combine the analysis of frequency estimation across rounds rather than analyze each separately. \n3. Finally, a DP alternative of Hybrid Sketch is provided that follows similarly to previous approaches.\n", "weaknesses": "1. For the two-phase method in section 2, the authors suggest that frequencies follow the Zipf law; thus, they estimate the polynomial coefficients by a kind of pilot study on a small number of clients. It is however unclear how the instance optimal method can leverage Eqn. (2) with the unknown frequencies to estimate the sketch width. Is the two-phase method employed for the instance optimal method as well? Please consider adding relevant clarification for all three methods.\n2. For the DP analysis consider mentioning the exact mechanism used to add noise. At first glance, it might not be clear if the method employs local DP or central DP.\n3. In certain cases, the idea that the frequencies have a lighter tail might not be verifiable (before running the sketching algorithm). Such an instance may occur if the communication or DP budget is constrained or if there are not enough clients to handle both the pilot and the actual sketching algorithm under DP constraints. Thus, adding this limitation clearly toward the end of the article will add clarity. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper! We will address your comments as follows. \n\n---\n**Q1**. “For the two-phase method in section 2, the authors suggest that frequencies follow the Zipf law; thus, they estimate the polynomial coefficients by a kind of pilot study on a small number of clients. It is however unclear how the instance optimal method can leverage Eqn. (2) with the unknown frequencies to estimate the sketch width. Is the two-phase method employed for the instance optimal method as well? Please consider adding relevant clarification for all three methods.”\n\n**A1**. In the instance optimal method, the sketch size is computed based on eq. (2) by an oracle. The instance optimal method is for demonstrating the correctness of our theoretical understanding and is not a practical method. We will provide detailed clarifications for all three methods in the revision.  \n\n---\n**Q2**. “For the DP analysis consider mentioning the exact mechanism used to add noise. At first glance, it might not be clear if the method employs local DP or central DP.”\n\n**A2**. We employ central DP. We will clarify this in the revision. \n\n---\n**Q3**. “In certain cases, the idea that the frequencies have a lighter tail might not be verifiable (before running the sketching algorithm). Such an instance may occur if the communication or DP budget is constrained or if there are not enough clients to handle both the pilot and the actual sketching algorithm under DP constraints. Thus, adding this limitation clearly toward the end of the article will add clarity.”\n\n**A3**. We agree with this limitation and will clarify this in the revision.\n"}, {"review_id": "MEPlxVhzsG", "reviewer": "Reviewer_vZGP", "summary": "The paper considers the problem of federated frequency estimation under the Secure Summation constraint. Motivated by the tail-bound analysis of CountSketch, the authors propose a two-round communication approach that can significantly reduce the sketch size and improve the overall communication size. Later, the authors extend the algorithm to a multi-round HybridSketch algorithm and improve the protocol's scalability. This paper also carefully analyzed their proposed method's trade-offs between accuracy and privacy. The proposed algorithm shows performance improvements in real-world datasets (Gowalla and Colossal Clean Crawled Corpus).", "questions": "What is the difference in communication latency between the proposed algorithm vs. baselines?\n\nUse different ticks or line styles to better distinguish between the lines in figures.\n", "limitations": "No limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Federated frequency estimation is a very important task in federated analytic and has many applications. The main idea is intuitive. Many real-world data distributions exhibit skewness, while the chen et al. showcases the lower bound for this task is $nlogd$ bits of communication per client, this work takes the distribution into account to reduce the communication costs.", "weaknesses": "The experiments showcase good estimation accuracy improvement. One may wonder how the communication latency changes between the baselines and hybrid sketch. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive evaluation! Please find our answers to your specific questions below. \n\n---\n**Q1**. “What is the difference in communication latency between the proposed algorithm vs. baselines?”\n\n**A1**. In our experiment, the client/server communication is simulated so the latency is ignorable. In practice, we expect that the communication latency is proportional to the sketch size (which determines the message length). So the difference between our proposed method vs. baselines in the sketch size vs. error plots (see Figure 1(b)(c)(e)(f), Figure 2, and Figure 3) reflects their communication latency difference in practical applications. For example, in Figure 3, the dashed gray lines show that for a fixed error, the hybrid sketch size is much smaller than the fresh and shared design.\n\n---\n**Q2**. “Use different ticks or line styles to better distinguish between the lines in figures.”\n\n**A2**. We will revise the plots as you suggested.\n"}, {"review_id": "MWRJjRSu7S", "reviewer": "Reviewer_q1hW", "summary": "In the nascent area of 'federated analytics', the canonical problem is frequency estimation: each client holds a label (or a collection of labels), and the aim is to recover the frequency distribution of these labels, or at least information on the most frequent labels (heavy hitters).  Prior work has demonstrated that this problem can be tackled by making use of 'sketch' data structures designed over the last few years.  The question is now to understand how to optimize the accuracy-communication tradeoff, while meeting various security and privacy guarantees.  This paper builds on prior work in this direction, by arguing that better bounds can be achieved due to the skewed nature of the input data: essentially, the worst case for sketches is when the data is uniform, and better accuracy is seen when most mass is in the head of the label frequency distribution.  Results for this case follow in part due to prior analysis of such data structures, adapted to the parameters of the federated setting. The second results apply to the case when data is collected in multiple rounds, by comparing the effect of using the same randomly chosen sketch parameters versus varying some.  The results show that this achieves improved bounds in the case that the frequency distribution changes between rounds.  Experiments based on simulated data allocations quantify this further.   ", "questions": "Are there any good data sets or references that can help to argue that the heterogeneity vectors F are substantially smaller (in Euclidean norm) than the frequency vectors? ", "limitations": "No limitations in the send of negative societal impact\nCould say more about technical limitations of the work, or future work -- the conclusion just summarizes the results. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a foundational problem for the area of federated computing, and the paper shows some improved results which could be of use to practitioners. \n\nThe algorithms proposed are clear and suitable to be implemented.  It is straightforward to achieve differential privacy by noise addition to the sketch (under secure aggregation), with bounded impact on accuracy. ", "weaknesses": "The novel contribution is not extremely high.  The first set of results are shown by plugging parameters into theorems from prior work, and some manipulation of probabilities. The second set of results are more involved, but can still be viewed as adaptations of prior proofs.  From a technical perspective, there is not much excitement.  The potential practical implications could elevate this work, but this would require more effort to demonstrate that the real world scenarios where this is needed map on to the assumptions in this work. \n\nThe results separate best from the single sketch approach when the data is 'heterogenous'.  The paper could do more to define the exact model of heterogeneity assumed, and to test these on real data.  The main opportunity for hybrid sketch to shine (P8) is when the frequency vectors are heterogenous -- that is, when the frequency distribution is different during each round of data collection.  (Note that most commonly, in the federated setting, heterogenous is used to refer to the case when the allocating of data to each client can vary a lot.  However, the definition of the frequency estimation problem is oblivious to the allocation of labels to clients: it just asks for the global frequency distribution). It would be helpful to know what kind of scenarios expect to have different frequency distributions per round, and what are the implications of this for the frequency estimation problem -- when the data is constantly shifting, what should the ground truth frequency distribution be? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions. In the following, we will address your questions. \n\n---\n**Q1**. “The novel contribution is not extremely high. The first set of results are shown by plugging parameters into theorems from prior work, and some manipulation of probabilities. The second set of results are more involved, but can still be viewed as adaptations of prior proofs. From a technical perspective, there is not much excitement. The potential practical implications could elevate this work, but this would require more effort to demonstrate that the real world scenarios where this is needed map on to the assumptions in this work.”\n\n**A1**. We use some standard techniques to derive our bounds. However, we’d like to emphasize that both the considered multi-round FFE problem settings and results are new. It also requires non-trivial efforts to establish new effective algorithms such as Hybrid Sketch, to allow the sketching method to adapt to the hardness of the instance, and to make the algorithm differentially private.\n\n---\n**Q2**. “The results separate best from the single sketch approach when the data is 'heterogenous'. The paper could do more to define the exact model of heterogeneity assumed, and to test these on real data. The main opportunity for hybrid sketch to shine (P8) is when the frequency vectors are heterogenous -- that is, when the frequency distribution is different during each round of data collection. (Note that most commonly, in the federated setting, heterogenous is used to refer to the case when the allocating of data to each client can vary a lot. However, the definition of the frequency estimation problem is oblivious to the allocation of labels to clients: it just asks for the global frequency distribution). It would be helpful to know what kind of scenarios expect to have different frequency distributions per round, and what are the implications of this for the frequency estimation problem -- when the data is constantly shifting, what should the ground truth frequency distribution be?”\n\n**A2**. We'd like to make two clarifications regarding our results. \n\nFirstly, Hybrid Sketch separates best from Shared Sketch when the multi-round dataset is *homogenous* rather than heterogenous (see the discussions in lines 247-264). Therefore, the main opportunity for Hybrid Sketch to shine is when local frequency vectors are closer to homogenous rather than heterogeneous. \n\nSecondly, our definition of (single-round) frequency estimation problems only asks for a frequency vector. However, our definition of multi-round frequency estimation problems asks for local frequency vectors in each round instead of only a global frequency vector (this can be seen from Theorem 3.2). So the latter problem is *not* oblivious to data allocation. \n\nWe hope we have clarified the questions. Please let us be aware if there are any further concerns. \n\nThe online setting where data is constantly shifting is very interesting. However, our main focus in this work is an ‘’offline’’ setting where the number of rounds $M$ is fixed (and known). We will comment on the online setting as a future work. \n\n---\n**Q3**. “Are there any good data sets or references that can help to argue that the heterogeneity vectors F are substantially smaller (in Euclidean norm) than the frequency vectors?”\n\n**A3**. In an ideal case where the local frequency vectors are perfectly homogenous, we can show that (see lines 247-264)\n$$ F_i = \\frac{1}{\\sqrt{M}} f_i,$$ \nwhere $M$ is the number of rounds. So the heterogeneity vector is only $1/\\sqrt{M}$ of the global frequency vector, pointwise, hence also in Euclidean norm. In practice, the multi-round datasets are often *approximately* homogeneous, so we expect the heterogeneity vector to be substantially smaller than the global frequency vector. \n"}]

Author rebuttal:

Meta-review: All reviewers felt that this paper made a solid contribution to the growing body of literature on private frequency estimation, even though the novelty of the theoretical analysis was perhaps a bit limited. The paper was well written and should be of interest to the broad NeurIPS community.
Decision: Accept (poster)