On Learning and Refutation in Noninteractive Local Differential Privacy
Authors: Alexander Edmonds
Aleksandar Nikolov
Toniann Pitassi
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
local privacy
agnostic learning
refutation
non-interactive

Abstract: We study two basic statistical tasks in  non-interactive local differential privacy (LDP): *learning* and *refutation*: learning requires finding a concept that best fits an unknown target function (from labelled samples drawn from a distribution), whereas  refutation requires distinguishing between data distributions that are well-correlated with some concept in the class, versus distributions where the labels are random. Our main result is a complete characterization of the sample complexity of agnostic PAC learning for non-interactive LDP protocols. We show that the optimal sample complexity for any concept class is captured by the approximate $\gamma_2$ norm of a natural matrix associated with the class. Combined with previous work, this gives an *equivalence* between agnostic learning and refutation in the agnostic setting. 

Learning versus Refutation in Noninteractive Local Differential Privacy
Alexander Edmonds University of Toronto
Aleksandar Nikolov University of Toronto anikolovecs. toronto. edu
alex. edmonds@@torontoo.co
Toniann Pitassi
Columbia University & University of Toronto toniêcs. toronto.
Abstract
We study two basic statistical tasks non-interactive local differential privacy (LDP): learning and refutation: learning requires finding concept that best fits an unknown target function (from labelled samples drawn from distribution), whereas refutation requires distinguishing between data distributions that are well- correlated with some concept in the class, versus distributions where the labels are random. Our main result is complete characterization of the sample complexity agnostic PAC learning for non-interactive LDP protocols. We show that the optimal sample complexity for any concept class is captured by the approximate 1/2 norm of a natural matrix associated with the class. Combined with previous work, this gives equivalence between agnostic learning and refutation in the agnostic setting.
Introduction
We study two related basic statistical tasks, learning and refutation, in the setting of distributed data, and under strong privacy constraints. For both tasks, we have an unknown distribution on labeled data points in the universe U x {+1}. and we receive samples from X. We are also given concept class S [+1]*, which, hopefully, capable of capturing the labels given by A. We define our two tasks as follows.
Learning requires finding a concept that best fits A. Lee. using the usual binary loss function Lx(h) E (a) * yl]. the goal of agnostic learning with accuracy a is to produce (a.b)~>
some ht which, with probability 1 3, satisfies (h) S mineec Lx(c) + If an algorithm solves this problem for any distribution X, then we say it (a, Be--msss agnostically.
Refutation requires distinguishing between data distributions À that are well correlated with some concept C, vs. data distributions where the labels are random. Le., the goal of agnostic refutation with accuracy is to distinguish, with probability - 3, between the following cases: (i) mingee (x(c) < versus (ii) for all h {#1]4, Lx(h) If an algorithm solves this problem for any distribution X, then we say it (a, -))-tes agnostically.
The definition of agnostic learning above is classical. Refutation is more recent notion, and was studied by Kothari and Livni 2018 (and in a realizable setting by Vadhan (017)) where was
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

shown that computationally efficient refutation is equivalent to computationally efficient agnostic learning. Refutation captures an extreme version of the problem of evaluating the choice of model in supervised learning, i.e., of estimating the best achievable loss minlee (c) by the concept class C. While agnostic learning is well-defined for any concept class, it is less meaningful when the best achievable loss is trivially large, which may be an indication that we need to choose a different model, ie.. a different concept class. For this reason, ideally we would like our learning algorithm to also tell us what loss it is able to achieve. Refutation is a more basic version of this problem, in which we merely want to distinguish data distributions for which our model is good from distributions with random labels, for which model can achieve good results. Certainly being able to solve the refutation problem is at least as hard as estimating mincec Lx(c).
In this paper, we study learning and refutation in the model of non-interactive local differential privacy (LDP) (Kaiivisaantthan et al. 2008]. LDP applies in a distributed setting in which each data point represents one person, and, in order to protect privacy, the person retains ownership of their data point. In particular, the data is never centrally collected, and, instead, the data owners communicate differentially private randomized message
central server. The differential privacy [Dwork et al., 2006] constraint ensures that the distribution on messages sent by one participant does not change dramatically if that participant's ss data point is changed. Thus, the central server or outside observer cannot learn much about any particular data point, guaranteeing a strong form of privacy protection (as long the privacy parameter is small enough). Nevertheless, with enough participants. the combination of all private messages can reveal enough statistical information in aggregate in order to solve statistical task, such as learning. LDP is the model of choice of many industrial deployments of differential privacy [Erlingsson et al. 2014| Thakurta et al.) 2017 7 Apple 2016 Ding et al., 2017]. Here focus on non-interactivve LDP protocols, i.e., protocols in which each participant simultaneously sends a single message to the server. Non-interactive protocols are much easier to implement than multi-round interactive protocols, particularly considering the large number of data points which are typically necessary for LDP to be useful.
Our main goal is to characterize, for any given concept class C, the sample complexity of learning and refutation under the constraints of non-interactive LDP. Moreover, we aim to understand how these two problems are related to each other.
In many settings, it trivial to take an algorithm for learning and use it to obtain an algorithm for refutation, by executing the learning algorithm for accuracy a/4, and estimating the loss of the returned hypothesis within a /4. converse of this simple reduction was established by Kothari and Livni 2018), and by Vadhan 2017]. Unfortunately, neither of these reductions applies to the setting of non-interactive LDP, since they rely on interacting with the distribution À adaptively.
This leaves open the question of whether or not learning and refutation in the non-interactive LDP setting are equivalent tasks with respect to sample complexity. In the forward (typically easier) direction, can non- non-interee interactive learning algorithms solve non- -on-interactive refutation (by estimating the minimum loss achievable by the model) without a significant increase in sample complexity, and conversely, can the reductions from refutation to learning from Kothari and Livni (0188 and Vadhan
2017 be extended to the setting of non-interactive protocols?
We note that, by the equivalence proved in Kasiviswanathan et al. 2011 between LDP and the statistical queries (SQ) model of Kearns [1933.. this also means that the relationship between the query complexity of non-adaptive SQ learning versus refutation is open. Similarly, all our results extend the non-adaptive SQ model. Adaptive SQ learning has been characterized by [eldmann [017]. and this in turn implies the same characterization for sequential LDP (LDP protocols in which each participant sends one message, which can depend on the messages of previous participants).
An overview of our main results follows. The derivation of our results will be presented in Section for the agnostic setting and in Section B for realizable. See Appendix A for notation and standard definitions. See Appendix E for a discussion of open problems.
1.1 Characterization of agnostic learning
Our first theorem resolves the open problem for agnostic learning, by showing that non-interactive LDP learning and refutation are equivalent (up to a logarithmic approximation) in the agnostic setting. We do so by the following theorem, which gives characterization of the sample complexity of both

---

problems in terms of the approximate 7/2 norm of natural matrix associated with the concept class C 5 (=1)".
Theorem 1. Let C {+1}4 be finite concept class with concept matrix W e (=1]exu given by Definition 3 L O, a. 3 E (0, 1/2|. Then, to either (2ox -le-aam C agnostically, or (2a, ---refute C agnostically under non-interactivee s-LDP, it suffices to have sample of size
1/ (W, a)²
IoW, log((c1/33)
n= 0
e2o2
Conversely, for 3 = Q(1), for some a' Q Tog(1/a} the number of samples required to either (a', -e-aar agnostically or ( refutte C agnostically under non-interactio e-LDP is at least
())(W,a)-11
n= Ω
E2
In Theorem [ denote by (2 the approximate "22 norm of the matrix W, i.e., the minimum 722 norm of a matrix that approximates W up to an additive a entrywise. (For a definition of the 72 norm, see Appendix A The theorem shows that the sample complexity of both learning and refutation under non-interactive LDP can be characterized in terms of 72 (W, a). Moreover, the sample complexities of both problems are equal, up factor Ollog (1/x)) loss in the accuracy parameter, and a factor Ollog (C) loss in the sample complexity.
The main new result in Theorem is the lower bound on the sample complexity of learning. The upper bound for both learning and refutation, as well as the lower bound for refutation were previously shown by Edmonds et al. [2019). We close the gap by proving the lower bound for learning. Combined with the previous results, this proves the equivalence of non-interactive LDP sample complexity for learning and refutation. As in the previous proofs,
prove the lower bound for agnostic learning via the (dual formulation) of the approximate 72 norm. In order to give a family of distributions that is hard against learning algorithms, we define new difference matrix, D, associated with the concept class C, which is more suitable for the learning lower bound. Then we show that (2(D,,o) and 7/2 W, a) are approximately equal.
1.2 Characterization of realizable refutation
The results above do not apply to the realizable setting, in which the underlying distribution À on u {+1} is guaranteed to be labelled by concept E C, i.e., (x(c) 0. In particular, the lower bounds we prove in terms of the approximate "/2 norm utilize distributions that may not be realizable. It is worth noting that some concept classes may require exponentially fewer samples to learn in the realizable case than to learn agnostically, as may be seen with Kearns
[193) and Feldman 20099.
While we are not able to characterize realizable learning, we give a characterization of realizable analog of the refutation problem, and show that realizable learning is no harder than realizable refutation. In our formulation of realizable refutation with accuracy a, are given samples from some distribution over U x {+1), and the goal to distinguish the cases:
mincec (x(c) 0, i.e, some concept in C exactly gives the labels under A;
for all h { (h) 2 a.
The case is equivalent to the definition of refutation introduced by Vadhan [017]
Daniely and Feldman 2018 showed that (for closed under negation) the sample complexity of
realizable learning under non-interactive LDP is bounded from below by the margin complexity of
C. They left open the question whether one can prove a matching upper bound. This question was resolved in the negative by Dagan and Feldman 2019). The problem of characterizing the sample complexity of realizable learning under non- con-inteeec LDP thus remains open.
In this work, we give non-interactive LDP protocol which may be applied towards both realizable learning and realizable refutation. This gives a sample complexity upper bound for these problems in terms of new efficiently computable quantity r)(C, ax) that we define. This quantity combines elements of both the 7/2 norm and of margin complexity, and sandwiched between them. Further, derive lower bound for realizable refutation in terms of ry(C, a), showing that our protocol is

---

nearly optimal for realizable refutation, and that the sample complexity of realizable refutation is an upper bound on the sample complexity of realizable learning under non-interacttiv LDP. Our main theorem for realizable learning is stated next. See Section B for the definition of ry(C..).
Theorem 2. Let C S { be a finite concept class. Let > O, a, 3 E (0, 1/2]. Then, to either (2a, 3y-learn C realizably, or (2a, re-ffut C realizably under non non-interactive s-LDP, it suffices to have a sample of size
= n),,,))
ax -log((C///))
E?O?
Conversely, for 3 - for some a' = S2 a the number of samples required to (a',8) refftte C realizably under non con-interactive e-LDP is at least
== a)²
E2a2
2 Refutation versus Learning: Agnostic Case
As mentioned in the introduction. Edmonds al. 2019] (Theorems 24 and 25) gave sample complex- ity upper bounds for both agnostic learning and refutation for non-interactive LDP in terms of the approximate 72, well nearly tight lower bound for agnostic refutation. However, it left open the question of lower bounds for agnostic learning under non-interactive LDP. Our main theorem, stated next, resolves this by giving nearly tight lower bound in terms of the approximate 7/2 norm of the natural matrix associated with C. Theorem thus follows by combining Theorems 24 and 25 from Edmonds al. [2019] together with Theorem
Definition 3.
Let C S [+1]u l be concept class. The concept matrix We E [+1]Cxu of is the matrix with entries given by We.a = c(a).
Theorem 4. Let C S {=1]² be a concept class with concept matrix W E {+1)exu as given by Definition Let > 0, a, E (0, 1]. Assume B = (11). Then, for some a' St [og([/a>)
under non-inteructive s-LDP, the number of samples required (a', BB)-laar C agnostically is at least
n Ω (72(W,,)) 1)3 )
E2a²
2.1 Difference matrix
Theorem 4 is given in terms of the concept matrix associated with the concept class; however, our proof of this result will focus instead on the difference matrix associated with the concept class, defined below.
Definition 5. The difference matrix of concept class C: u + {+1} } is the matrix D E (+1) with entries given, for e, EC,a U, by
ifc(a) d'(a)
d (cla)-((a))
if((a) - c,)((a) = +1
+1 ifc(a) = +1, cl,c((a) = -1
The difference matrix is one of the key ideas that enables the proof of Theorem We will use a dual formulation of 7/2 (D, a) to construct pairs of hard distributions for our lower bound, each pair of concepts c, c' E C. The structure of the difference matrix will help us ensure that no correct agnostic learning algorithm can output, with high probability, the same hypothesis for both distributions in pair. It is not apparent how to guarantee this property when working directly with the concept matrix W. Nevertheless, the following lemma shows that a)) and 72(W; a) are essentially the same. (See Appendix B for the proof.)
pair corresponding
'hile Theorems 24 25 from Edmonds al. 2019 are stated terms of agnostic learning, their definition of agnostic learning is mon-standart and requires the learner to output hypothesis as well as the loss it achieves. Thus the upper bounds hold for the standard definition of agnostic learning. while the lower bound only holds for refutation.

---

Lemma 6. Let C be a concept class with concept matrix W E RCxU and difference matrix D E Ree xu, Then "22 a) S (2 a). Conversely, 72 a) 272(D, a/2) 1, and if is closed under negation then (2(W, a S a))
The next Lemma is the same as Theorem M but with W replaced by the difference matrix D. Theorem 4 is an immediate consequence of Lemma together with Lemma C
Lemma 7. Let C S {=1}4 be concepr class with concept matrix D E [=1]ex as given by
Definition Then Theorem holds with W replaced by the difference matrix, D.
The of this section devoted the proof of Lemma
2.2 KL-divergence bound
For mechanism M X Z in the local model, and probability distribution on X", (M()) to denote the distribution of the mechanism's 's transcript when its input is sampled from v.
Lemma 8. |Edmonds et al. 2019) Let E (0, 1), and let M : x + 2 be non-interactive E-LDP protocol. Then, for families :i....,Aa; and (pI....,.., of distributions on X, together with distribution π over [k].
27
E Da((T(())ITMMU ViT
O(ns²)
E SER* :1/1l $1 VNn
max
E
[s]]
E xmpaa
[Sa))
(Bndy
In matrix notation, define the matrix M [ by mu.a (Ao(x) Mo(x))) Then
E VeT
(T (XN())I S O(ns?) || 1| -12(())
Note that the statement of Lemma is slightly different than the statement given in Edmonds et al. (2099), but the result as stated here is an immediate consequence of the original proof.
Our lower bound against agnostic learning will construct families {AI...., AR and {ui..... pR of distributions on 24 x {+1}, as well as a distribution æ over [k:]. The idea will be to construct these distributions so that, when M is agnostic learner for C, then, for any fixed v E [k].
DKL
2 2dIv TM<)))) 20122)1111 2(11,
where the first inequality is just Pinsker's inequality, and the second one will follow from our construction A and po. Then the lower bound will follow by Lemma g long we can make sure that [ - is small.
2.3 Duality and Hard Distributions
For the construction of hard families of distributions, it will be convenient to make use of the following dual formulation, shown in Edmonds et 2019
Lemma 9, Let D CCa xu be the difference matrix of a concept class C, as given by I Then,
22 (D, max {
DOU (D.U-alUIl] alU U x u, U 0
(U)
For an arbitrary concept class C C {#1)4, let E x witness 2 so that
(D() D UU
(3)
(U)
By normalizing U, we may assume, without loss of generality, that ||U|| 1. Moreover, we can assume that, for any c, E C, Eoeu " 2 0. Otherwise, cannot achieve 2. since we can multiply the row of U indexed by (c,ee) by -1, which increases D U and does not change ||U]]] or (UU)
5

---

We will consider the matrices U+ U- -* E Ie with non non-negttive entries which satisfy U U UT so that U+ and U correspond to the positive and negative entries of U respectively. We define the distribution on C² by
[(c,)= = Σ "ic,c'),a
(4)
DELL
Then, for d' C, consider the distribution Aeee on {+1} given by
"toee' c(c,
ut
" "(ce'),
(a, 1)
de, ( -1)=
(5)
π T(C,
Similarly, let Pe,e' be the distribution onl x { given by
+ (c,c') x(c.c')
Pe.e (a, 1) "(c,e',, c')'
(a.
(6)
Since U has unit l norm, the above distributions are well-defined. Note that de,e' and Me,e" have the Meanwhile, Aa,
same marginal on 2/ which we denote K(c,e"). In particular, (K),e)(aa) [
#(c,c")
always gives a the label b b= sign( (u((e")))) while fe,,r always gives a the label -iinnsiinnua. (c.e))
will be useful have notation for one of these labelling functions, so define sc,e' u [=1} by sc,e' (a) sign(M(c.e)).l)
Consider the following relationship between U and the distributions we have constructed.
M(a,e') = T(c, c') (No 1) -o,e (a, 1)) = <(c, (a)se.
Note that
Σ aEll
=((c)) Σ
Keo (a) (c(a)sac - (a))scc(a)
aEll
= =x(cd)) (c) - (c))
(7)
Similarly,
E Madd) I(C,c)) (Imad (c) aEM
(8)
Hence,
(
[L - Lp (c,e
-mm (d))
D U
E (c
E
(D( Whenever C contains at least two distinct concepts, 72 [D, at) > 0, and then implies D U >
By the equations above, this implies that, on average with respect to (c, c') ग., the loss of is greater by a than the loss of c' on Xe,e'. Likewise, on average, the loss of c' is greater by a than the loss of on Pe.et We will see later that, if we can obtain these properties in worst case over (c, c'), rather than only average, then no hypothesis can fit both Ao.e' and pe,et for any c' E C. The following section modifies the distributions we have constructed so to obtain the required properties.
2.4 Lower bound derivation
The following lemma gives a modification of the hard distributions we constructed, giving us the properties we need for our lower bound. The proof is deferred to Appendix C
Lemma 10.
Let C be concept class. Let D be the matrix given by 1 Let U C xu |[]]]
satisfy Then there exist probability distributions Xe and oe over {+1), and a distribution over C² such that:
1. For all (c,c') in the support of I (c) - Lxx (c) 2 (loo(()/a)
2. For all (c,ce) in the support of Ian (c)) La. (c) 2 [[oo[[/a]]

---

3. The matrix Ü E RR2x with entries M(a,)) ((c, - Pe (a)) satisfies (U) 25 (Ū) - DaU
We also want bound the operator norm, which appears in Lemma in terms of (5()). To do so, we use the following lemma from Edmonds et al. [2019].
Lemma ((Edmonds et al., 2019)). Let U and be k x T matrices, and let x. be a probability distribution [k] such that, for any i E [k], [T], we have Us.j. x())ma... Then there exists probability distribution on [b], with support contained in the support of n. such that || (a)()) S (
Recall that we also want to obtain a lower bound on dTv(TM( (TTMmTIITMMM when M is learning algorithm for C. For this purpose, we apply the following lemma, whose proof is also deferred to Appendix C The main observation in the proof is, for any hypothesis h C - [=1], and any distributions and μ satisfying the conditions of the lemma, we have Lx + (h) =
Lemma 12. Let À and μ. be distributions U {+1}. Assume that X and y have the same marginal on U. Also assume that X is labelled by some s U + { while is labelled by -s. Finally, assume
that for some e, C, Ly(c') Ly(c) > a. If U + {=1} satisfies (x) < Lx(e') + a/4,
then Lu (h) > L,(c) + 3a/4. Hence, if M is an algorithm which (a/4, B)-eaams C from n samples, 23.
then dry (MM())"") M(""))
Finally, with these results at our disposal, we may obtain the lower bound of Lemma
Let E Re xu ||U||| = 1, satisfy Let म, together with Ar.e and Paae be the distributions guaranteed to exist by Lemma 10 and let U E RC² xll be the corresponding matrix with entries
Proof of Lemmal 7
"(c,"')aa = H(c,c)) (Rea (a, -iee 1)) = -7(e,c)) (a, -1) -
- - (a, -1)
Let M be the matrix with entries m(c,e'),a "a ( c'). By Lemma 11 there exists some distribution ă with support contained in that of मे such that
40r)(U)
M M
S 4 -
<
D
where the last inequality follows from Lemma gives
10 Combining Lemma with the dual formulation
E (c,c')
(TM
(7 (1 - Onn)²)
||M (L)
2 (n)(())
2
<((n=?)
= =((ne))
D D
72(D,a)
Now let
1 ( min Lice (c') Lucd (c)
a'
4
O (log(L/a))
where the last inequality is by Lemma 10 By Lemma
12 if M (3',3)-laamms C for some B =
211. This implies n = Ω (>2(D.a)) 2
(1), then (c,e)) (Ta (TT
E.
as to be proved.
3 Refutation versus Learning: Realizable Case
In this section, we present our algorithm for realizable learning and refutation for non -nterrtreee LDP. For concept class U4 {=1}, we define a quantity ryC a) and argue that it gives an upper bound on the sample complexity for realizable learning of C.
Definition 13. Let ::u + {+1} be a concept class. Let
Ke = W E (x)xxx(=)))
|We,(a,((a)l S a and We, (c,(a.-c(o)) 2 1 Ve E C,a Eu)
9
7

---

Let
KC = -w e (exux(LII) ME E Ke, E W = W + +011
(10)
where 1s the all-ones row vector indexed over C, so that W + 01 is the matrix obtained by shifting each row of W in each entry by O-.
Then define
n(C, min (2(W) (
W E KE).
The idea is that each row of W defines a statistical query corresponding to a concept, (a b) = We. The statistical query corresponding to the true concept that was used to label the data will have a small value, whereas any query corresponding to a concept with large loss will have a large value. The next theorem formalizes this argument.
Theorem 14. Let C S {=1]" be a concept class. Let E > O, a E (0, 1]. Then there exists an E-LDP mechanism which may be used both (3a, -le-m C realizably and (3a, 3) re-fuee realizably with n samples, where
(CCCa)) log(1c1/B)
=
6202
Proof. As per Definition 13 let W K2 be the matrix that witnesses n/C,, a) and let W Ke and 0 E Rº be the matrix and vector which witness W E Kg. If we can answer the statistical queries given by W, then we can answer the queries given by W with the same accuracy by subtracting 0g from the answer the query for concept
By the definition of W, if, for some c C, À is supported on on those (a, b) u x {+1} which satisfy c(a) b, then the value of the query corresponding to e is bounded
[We,(a,)]] = (a,b)~>
[We.(a.((a))] S
(a.b)~A
Meanwhile, for arbitrary distribution À on u {+1), the value of the query corresponding to c E may be bounded as
E
[we,(a.r)] 2 P(a,bjnx (b c(a)] P(a,b)as Ib c(a)) 2 Lx(c)
(a.b)~>
In particular, if (x(c)= 2 30, then E
2 2a.
(a,b)~>
follows that, by approximating the statistical queries given by W with worst-case error d we can distinguish the case where À agrees with some E C from the case where, for all concepts E C, (x(c) 3a. In the former case, returning some c' C where our estimate of E [Wa[(a,b)] is (a.b)~
strictly less than 2a guarantees (c) 3a.
To complete the proof, suffices to apply the upper bound from Edmonds al. 2019 which says that, to answer the collection of statistical queries given by W under non-interactive s-LDP, with accuracy a/4 4 and probability failure at most 3, the number of samples required is most
(2(W) log((CI/3)
17(C, a) an(C,a)
log(((1)))
eaa2
3.1
Lower bound
Our lower bound will follow similar strategy as in the agnostic case. However, our construction of hard distributions will be tailored to 17(C, a) and its dual.
3.1.1 Duality
We will again use convex duality in our lower bound. We will express ry,C,a) as maximum over dual matrices U, and we will use an optimal U to construct 'hard distributions' for realizable refutation. To this end, consider the following duality lemma, proved in Appendix D

---

Lemma 15. For any concept class C S {=1} and any a.
DeEC, (Me(a,)(a)) a alMc,(a.((a)))
T(C,,a) = -ax UESC
(11)
72(U)
where we define
{ U (eXxX(x(())) Vce E (ucl(a,((a) + ua,(a-e(a))
Sc =
aetl
and, Ve C, Va U, Va(aa-c(a)) 2 0)
3.1.2 Hard distributions
Let U E [ex((x((1)) witness I1 By normalizing, we may assume without loss of generality that We will consider the matrices U-, - E 12mxN with non-negative entries which satisfy U --= U so that U and U correspond to the positive and negative entries of U respectively, We define the distribution æ on C given by (Tc)) ((. Me,(a.)). Then, for each E C, let A₂ and Me be the distributions on ll {=1} given by
||0|| =
be(a,b) = ((.,h)
2ut
and Mo(a, b) = 2u
(c))
T(c)
Since the rows of each sum to zero and have unit l norm, the distributions d and fe are well- defined. Moreover, since (c.(a.-e(a)) 2 for all C, E U, the only negative entries of U those of the form (c,(x, This implies that the distribution pe always labels samples a E U by c(a).
3.1.3 Warm-up: single-concept case
Consider the case where C consists of single concept Since (), > 0, then implies
Σ acdl
(alla,c((a))
a al
(12)
aell
Hence,
((a,b)~x. (c(a) + b] Plass)ne (c(a) + bj > a. (P(a.b)as (c(a) b] + P P(a,b)nm (c(a) = bl)
Using
P PlaMM)e (e(a) = =1
(13)
and rearranging, this gives
2a LA,(C) (c) (a.t))~A [c(a) # bj >
1 a
In other words, if we distinguish distribution on U x {+1) which labels samples according to
from one which disagrees with e with probability greater than 2a Ita'
then we can distinguish between
Ae and Pe-
3.1.4 General case
Appendix D.2 generalizes the lower bound of the previous section to the general case where the concept class is not restricted to a single concept.
The first issue which needs to be addressed in the general case is that rather rather than holding in worst case over all concepts, holds on average for concept E C' drawn from the distribution This issue is handled by applying the binning result of Lemma 19
The second issue which needs to be addressed is that, while each is guaranteed not to fit the corresponding distribution >,. as with (13). it may hold that some other U - {+1} has small loss on Aç- This is remedied by mixing distribution a, which agrees with into the distribution X This guarantees that every h : - {+1} has large loss on de-
Altogether, obtain the lower bound of Theorem

---

References
Apple. Apple previews ios 10, the biggest ios release over, 2016. URL bR:p com/
Y. Dagan and V. Feldman. Interaction necessary for distributed learning with privacy communi- cation constraints. CoRR, abs/1911..04011 2019. URL
A. Daniely and V. Feldman. Learning without interaction requires separation. CoRR, abs/1809.09165, httgg/bbs/889.....
2018. UtLptt:::/ org/ h//g//bb//// aaaaaass//aa 110./.00...0 09165
B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 3571-3580. Curran Associates, Inc., 2017. URL http://papees mips httpppppppe/o--coollleetteeeeeee
pdf
C. Dwork, McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryplography, TCC "06, pages 265-284, Berlin, Heidelberg, 2006. Springer.
A. Edmonds, A. Nikolov, and J. Ullman. The power of factorization mechanisms in local and central differential privacy. CoRR, abs/1911 2019. URL http://a:/ http://aaaiiv...g/bbbss/// wwwg/aa/////a//eeee. 1911.08339
U. Erlingsson, V. Pihur, and A. Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM Conference on Computer and Communications Security, CCS' 14. ACM, 2014.
A. V. Evfimievski, J. Gehrke, and R. Srikant. Limiting privacy breaches in privacy preserving data mining. In PODS, pages 21 2122 ACM, 2003.
V. Feldman. A complete characterization of statistical query learning with applications to evolvability. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 375-384. IEEE Computer Society, 2009. doi: 10.1109/ FOCS. ROCSS2000.33. URL httpt:ttttp/.o..ooo org/ 10. 1109/F0CSS 2009 35
V. Feldman. A general characterization of the statistical query complexity. S. Kale and O. Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 785-830. PMLR, 2017, URL http::/pproceeddnggg mlr. press/v65/feeeeeeeeeeeeee wttp///dddeede/eeeeccmmmmm html
S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In FOCS, pages 531 IEEE, Oct 25-28 2008.
S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793-88 826, 2011. doi: 10.1137/990756090. URL 2tgg/.../... 10. 1137 1137/090756090 https://doi org
M. J. Kearns. Efficient noise-tolerant learning from statistical queries. In STOC, pages 392-401. ACM, May 16-18 1993.
P. K. Kothari and R. Livni. Improper learning by refuting. In A. R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018. January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPlcs, pages 55:1-55:10, Schloss Dagstuhl Zentrru für Informatik. 2018. doi: 10.4200 URL https://t:://d ha0p://///ooologg///oo002/1///s 2018.58
4230/LIPICS. ITCS
A. G. Thakurta, A. H. Vyrros, U. S. Vaishampayan, G. Kapoor, J. Freudiger, V. R. Sridhar, and D. Davidson. Learning new words, May 2017. US Patent 9,645,998.
S. P. Vadhan. On learning vs. refutation. In S. Kale and O. Shamir, editors, Proceedings of the 30th Conference on Learning Theory. COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017. volume 65 of Proceedings of Machine Learning Research, pages 1835-1848, PMLR, 2017. URL http://proceedinge mlr. .tt..m.............. https///6//aahaaaan html
10

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "jy_Fnz6vafD", "reviewer": "Reviewer_eniG", "summary": "This paper studies the sample complexity of learning and refutation in the model of non-interactive local differential privacy (LDP). In a non-interactive LDP protocol, all users sends a message to the server once, simultaneously and independently. In the agnostic setting, the authors show that learning and refutation are equivalent (up to a logarithmic approximation) wrt sample complexity. The main result gives a lower bound on the sample complexity in terms of the \"approximate $\\gamma_2$ norm\" of a matrix associated with the concept class, which in conjunction with earlier work by Edmonds et al. (2019) shows this equivalence. In the realizable setting, the authors show that refutation implies learning.\n", "questions": "* Why is the approximate $\\gamma_2$ norm not defined in the main text? Given that this norm features extensively, a definition in the main text is desirable.\n\n* In Lemma 9,  the $\\bullet$ operator is not defined.\n\n* Why is the realizable refutation setting more difficult than the agnostic case?\n\n* What is a good intuition for the definition of the quantity $\\eta(\\mathcal{C},\\alpha)$ in Definition 13 that features in the bounds in Theorem 2 for the realizable case?\n\n\n\n", "limitations": "The authors do not address any potential negative societial impact of the work and I reckon there is none.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper resolves an open question for lower bounds in the agnostic case in the non-interactive LDP setting. The presentation in certain parts can be improved. In particular, deferring some of the full proofs to the appendix and including some intuition for the two main quantities that appears in the statements of theorems, viz., $\\gamma_2$ and $\\eta$ can make the presentation better. Also the reader can benefit from a separate Contributions section with pointers to the main statements.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9t4FhAwJnSM", "reviewer": "Reviewer_kF1C", "summary": "This paper studies two tasks, learning and refutation, in non-interactive local differential privacy. It proves the same lower bounds of the sample complexity of agnostic PAC learning for both tasks, which matches the upper bound proved in the previous work. Consequently, the paper shows the equivalence between learning and refutation in the agnostic setting.", "questions": "As the paper is studied for the finite concept class, one question is whether the result could be extended to the infinite concept class setting.", "limitations": "Yes, the paper describes several open problems as the future work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe result is solid and complete. It closes the gap between upper bound and lower bound of sample complexity for learning and refutation, in the setting of agnostic PAC learning and non-interactive local differential privacy.\n\n### Weaknesses\nThe proof could be more hierarchical.\n\nMinor issue:\n1. Typo: In lemma 8, m_{v, x} -> m_{a, x}", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9-c3DK2lgnq", "reviewer": "Reviewer_3PmZ", "summary": "This paper studies the issue of learning and refutation in the setting of non-interactive local differential privacy. It provides a characterization of the sample complexity of agnostic PAC learning for non-interactive LDP protocols and shows the equivalence of learning and refutation in the setting of agnostic learning. \n", "questions": " I have some one major concern:\n\n(1)What is the relation of the refutation in this paper to that in Vadhan [2017]? I found that they are different but could not see the direct equivalence.\n", "limitations": "It needs some more detailed explanation of the relationship to the similar issues in the literature. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in this field.  I believe that the results in this paper are mathematically sound.  The presentation is well-organized and also the topic about learning and refutation in the LDP setting is very interesting. \n\nOne minor: some mistakes in the definition of learning problem Page 1", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "75e4VtJpwJi", "reviewer": "Reviewer_d2S2", "summary": "Setting and main contributions:\nThe paper is about the tasks of learning and refutation concept classes in the local differential privacy (LDP) model (which is a model with strong privacy guarantees for users, even from the central party).\n\nThe first main result is closing an open question of showing a lower bound on the sample complexity for agnostic learning. This gives a full characterization of these models, as upper bounds for learning and refutation, and a lower bound for refutation were obtained by Edmonds, Nikolov, and Ullman (STOC20).\n\nThe second main contribution is in the realizable model: an LDP protocol with upper bounds on the sample complexity for learning and refutation, and also a lower bound on refutation.", "questions": "-", "limitations": "-", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies fundamental questions regarding learning for the important privacy model - LDP.\nThe contributions are significant.\n\nThe first contribution closes the gap in the literature on learning and refutation in the agnostic model. \nSpecifically, I find the technique for proving the lower bound very elegant. \nThe idea of working with the difference matrix seems interesting and may be of independent interest, in my opinion.\n\nIn the second contribution, the authors define a quantity, eta(C,alpha), that quantifies the sample complexity in the realizable case. The lower bound idea is similar to the agnostic case when working with the \"right\" quantity eta(C,alpha).\n\nI recommend accepting the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept