Multiclass versus Binary Differentially Private PAC Learning
Authors: Satchit Sivakumar
Mark Bun
Marco Gaboardi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
PAC Learning
Online Learning
Multiclass Learning

Abstract: We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning. We apply this transformation to a recently proposed binary private PAC learner to obtain a private multiclass learner with sample complexity that has a polynomial dependence on the multiclass Littlestone dimension and a poly-logarithmic dependence on the number of classes. This yields a doubly exponential improvement in the dependence on both parameters over learners from previous work. Our proof extends the notion of $\Psi$-dimension defined in work of Ben-David et al. [JCSS, 1995] to the online setting and explores its general properties.

Multiclass versus Binary Differentially Private PAC Learning
Mark Bun
Marco Gaboardi
Department of Computer Science
Department of Computer Science
Boston University Boston, MA 02215
Boston University
Boston, MA 02215
mbun@bu.c edu
gaboardi @irr.di@uu.... edu
Satchit Sivakumar
Department of Computer Science
Boston University Boston, MA 02215 satchit@bu. edu
Abstract
We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning. We apply this transformation recently proposed binary private PAC learner to obtain private multiclass learner with sample com- plexity that has a polynomial dependence on the multiclass Littlestone dimension and a poly-logari dependence on the number of classes. This yields doubly exponential improvement in the dependence on both parameters over learners from previous work. Our proof extends the notion of V-dimension defined in work of S to the online setting and explores general properties.
Ben-David et
Introduction
P Machine learning and data analytics are increasingly deployed on sensitive information about individuals. Differential privacy [10] gives mathematically rigorous way to enable such analyses while guaranteeing the privacy of individual information. The model of differentially private PAC learning [17] captures binary classification for sensitive data, providing simple and broadly appli- cable abstraction for many machine learning procedures. Private PAC learning is now reasonably well-understood, with host of general algorithmic techniques, lower bounds, and results for specific fundamental concept classes
12
15 2 [6].
Beyond binary classification, many problems in machine learning are hetter modeled as multiclass learning problems. Here, given training set of examples from domain X' with labels from [k] (0, 1o..,,,,,,,, k). the goal is to learn a function h : X' - [k] that approximately labels the data and generalizes the underlying population from which was drawn. Much less is presently known about differentially private multiclass learnability than is known about private binary classification, though it appears that many specific tools and techniques can be adapted one at time. In this work. we ask: Can we generically relate multiclass to binary learning as to automatically transfer results from the binary setting to the multiclass setting?
To illustrate, there is simple reduction from given multiclass learning problem to sequence of binary classification problems. (This reduction was described by Ben-David et al. [5] for non-private
'The full version of this paper with all of the details can be found at https//arrci.orgabb/2212.0.0.0
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

learning, but works just as well in the private setting.) Intuitively, one can learn a multi vulli- label one bit at a time. That is, to learn an unknown function f : X - [kt], it suffices to learn the [logg(k + 1)1 binary functions ft X + [k], where each f. the 7th bit f.
Theorem 1.1 (Informal). Let H be a concept class consisting of [k]]vel functions. If all of the binary classes H, = (fe: f E ] are privately learnable, then H is privately learnable.
Beyond its obvious use for enabling the use of tools for binary private PAC learning the classes H5, we show that Theorem h.T strong implications for relating the private learnability of И to the combinatorial properties of H itself. Our main application of this reductive perspective is improved sample complexity upper bound for private multiclass learning in terms of online learnability.
1.1 Online vs. Private Learnability
A recent line of work has revealed an intimate connection between differentially private learnability and Icarnability in Littlestone's 's mistake- model of online learning [18]. For binary classes, the latter is tightly captured by combinatorial parameter called the Littlestone dimension; class H is online learnable with mistake bound at most d' if and only if its Littlestone dimension is at most d. The Littlestone dimension also qualitatively characterizes private learnability. If class H has Littlestone dimension d, then every private PAC learner for H requires at least 2(log" d) samples M.. Mcanwhile, Bun et al. (7) showed that H is privately Icarnable using 220(0) samples, and Ghazi et al. [13 gave an improved algorithm using (d²) samples. (Moreover, while quantitatively far apart, both the upper and lower bound are tight up to polynomial factors as functions of the Littlestone dimension alone
[15].)
Jung et al. 14 recently extended this connection from binary to multiclass learnability. They gave upper and lower bounds on the sample complexity of private multiclass learnability in terms of the multiclass Littlestone dimension 9. Specifically, they showed that if multi-valued class H has multiclass Littlestone dimension d, then it is privately learnable using 2 ((4) samples and that every private learner requires (2llog d) samples.
Jung et al.'s upper bound [4] directly extended the definitions and arguments from Bun et al.'s 7 earlier 22 -sample algorithm for the binary case. While plausible. it is currently unknown and far from obvious whether similar adaptations can be made to the improved binary algorithm Ghazi et al. [3). Instead of attacking this problem directly, we show that Theorem I.I together with additional insights relating multiclass and binary Littlestone dimensions, allows us to generically translate sample complexity upper bounds for private learning in terms of binary Littlestone dimension into upper bounds in terms of multiclass Littlestone dimension. Instantiating this general translation using the algorithm of Ghazi et al. gives the following improved sample complexity upper bound.
Theorem 1.2 (Informal). Let H be a concept class consisting of [k]-valued functions and let d be the multiclass Littlestone dimension of H. Then H is privately learnable using Ö(d log. (k 1)) samples.
In addition to being conceptually simple and modular, our reduction from multiclass to binary learning means that potential future improvements for binary learning will also automatically give improvements for multiclass learning. For example, if one were able to prove that all binary classes of Littlestone dimension d are privately learnable with (dd samples, this would imply that every [k]-valued class of multiclass Litttlestone dimension d is privately learnable with Ö(d log (A: + 1)) samples
1.2 Techniques
Theorem I.I shows that a multi-valued class is privately learnable if all of the binary classes H, are privately learnable, which in turn holds long we can control their (binary) Littlestone dimensions. So the last remaining step in order to conclude Theorem 1.2 is to show that if H has bounded multiclass Littlestone dimension, then all of the classes H, have bounded binary Littlestone dimension. At first glance, this may seem to follow immediately from the fact that (multiclass)
2 "The nearly cubic dependence on log(k + 1) follows from the fact that the accuracy of private learners can be boosted with sample complexity blowup that nearly inverse linear in the target accuracy 6

---

Littlestone dimension characterizes (multiclass) online learnability mistake bounded learner for a multiclass problem is, particular, able learn each individual output bit of the function being learned. The problem with this intuition is that the multiclass learner is given more feedback from each example, namely the entire multi-valued class label, than a binary learner for each H2 that is only given a single bit. Nevertheless, we are still able to use combinatorial methods to show that multiclass online learnability of a class H implies online learnability of all of the binary classes Hy
Theorem 1.3. Let H be a [k]]valued concept class with multiclass Littlestone dimension d. Then every binary class H; has Littlestone dimension at most 6d 6nl + +1).
Moreover, this result is nearly tight. In the full version of the paper, we show that for every k, d 2 1 there is a [ki]-vllued class with multiclass Littlestone dimension d such that at least one of the classes H2 has Littlestone dimension at least ((d + 1))-
In addition, turns out that online learnability of the binary classes H, implies multiclass online learnability of H. In the full version of the paper, we show that if the multiclass Littlestone dimension of H is d, then there is at least one binary class H; with Littlestone dimension larger than d log(k++ 1)
This result is also tight.
Theorem L.3 the main technical contribution of this work. The proof adapts techniques introduced by Ben- David et al. [5] for characterizing the sample complexity of (non-private) multiclass PAC learnability. Specifically, Ben- David et al. introduced a family of combinatorial dimensions, param- eterized by collections of maps V and called V V-dimensions, associated to classes of valui- functions. One choice of V corresponds to the "Natarajan dimension" " [19], which was previously known to give lower bound on the sample complexity of multiclass learnability. Another choice corresponds to the "graph dimension" [19] which was known to give an upper bound. Ben-David et al. gave conditions under which V-dimensions for different choices of V could be related to each other, concluding that the Natarajan and graph dimensions are always within an Oloog(k + 1)) factor, and thus characterizing the sample complexity of multiclass learnability up to such factor.
Our proof of Theorem 1.3 proceeds by extending the definition of V-dimension online learning. We show that one choice of T corresponds to the multiclass Littlestone dimension, while a different choice corresponds to the maximum Littlestone dimension of any binary class H,. We relate the two quantities up to logarithmic factor using new variant of the Seeee--heeah-Pebbeeee Lemma for the "0- cover numbers" of class of multi-valued functions. While we were originally motivated by privacy, we believe that Theorem 1.3 and the toolkit we develop for understanding online V-dimensions may be of broader interest in the study of (multiclass) online learnability.
Finally, we remark that Theorem 1.3 implies a qualitative converse to Lemma I.1 If multi-valued class H is privately learnable, then the lower bound of (14) implies that H has finite multiclass Littlestone dimension. Theorem I.3 then shows that all of the classes H; have finite binary Littlestone dimension, which implies via 7 that they are also privately learnable.
Societal Impact Our work is motivated by privacy-reppecting data analysis. Our focus is on theoretical questions aimed uncovering general principles about when private learning is feasible. As such, it does not negatively impact the way privacy-respecting techniques are used, but rather it clarifies their potential.
2 Background
Differential privacy. Differential privacy is property of randomized algorithm guaranteeing that the distributions obtained by running the algorithm on two datasets differing for one individual's data are indistinguishable up multiplicative factor e and an additive factor 8. Formally, it is defined as follows:
Let n. E N. A randomized algorithm M X + is (c, differereettl private for all subsets S y of the output space, and for all datasets X and X" containing elements of the universe X and differing in at most one element (we call these neighbouring datasets), we have that
Definition 2.1 (Differential privacy, 10
Pr(M(X) E S) e E $6+
3

---

One useful property of differential privacy that we will use is that any output of a differentially private algorithm is closed under post-processing that is, its cannot be made less private by applying any data-independent transformations.
Lemma 2.2 protessoosssing of differential privacy, (O).. If : NT - Y is (e, ( differentiaal private, and B : y + Z is any randomized function, then the algorithm B o M (c. diffferrnntt private.
PAC learning. PAC learning 21 aims at capturing natural conditions under which an algorithm can approximately learn an hypothesis class.
Definition 2.3 (Hypothesis class). A hypothesis class H with input space X and oulput space y (also called the label space) a set of functions I mapping X to y.
Where it is clear, we will not explicitly name the input and output spaces. We can now formally define PAC learning.
Definition 2.4 (PAC learning, (21).. A learning problem is defined by a hypothesis class H. For any
distribution P over the input space X, consider independent draws 22, In from distribution
P. A labeled sample of size n is the set f(I1)((1)) (22, (x2)). ....)...... (In, f(xn)) }}} where f E H. We say an algorithum A taking labeled sample X of size is (a, -cccurate PAC learner for the hypothesis class H for all functions f E H and for all distributions P over the input space, A on being given labeled sample of size drawn from P and labeled by f, outputs hypothesis h H such that with probability greater than or equal to 1 3 over the randomness of the sample and the algorithm.
Pr(h(x) * S..
The definition above defines PAC learning in the realizable setting, where all the functions f labeling the data are in H. Two well studied settings for PAC learning are the binary learning case, where y = {0, 1} and the multiclass learning case, where y = [k] = {0,1, ..k for natural numbers >> 2. The natural notion of complexity for PAC learning is sample complexity.
Definition 2.5 (Sample complexity). The sample complexity Sh o. (A) of algoritimm A with respect to hypothesis class H is the minimum size of the sample that the algorithm requires in order to be an (a, ))-ccurrate PAC learner for II The PAC complexity of the hypothesis class I
inf (())
In this work, we will be interested in generic learners, that work for every hypothesis class. Definition 2.6 (Generic learners). We say that an algorishm A that additionally takes the hypothesis class as an input, is a generic (a, -accuureeee private PAC learner with sample complexity function SCHH, a, B), if for every hypothesis class H. an (a, 3)-accuraate private PAC learner for H with sample complexity SC(H, 3)
Differentially private PAC learning. We can now define differentially private PAC learning, by putting together the constraints imposed by differential privacy and PAC learning, respectively.
Definition 2.7 (Differentially private PAC learning [7].. An algorithm A is an (c, 8) (..)))iffeeentiie private and (a, -)accuraeee private PAC learner for the hypothesis class H with sample complexity if and only if:
1. A is an (a,, B)-ccuruteeee PAC learner for the hypothesis class H with sample complexity n.
2. A is (c, dddifferrettiall private.
In this work, we study the complexity of private PAC learning. Our work focuses on the multiclass realizable setting.
Multiclass Littlestone dimension. We recall here the definition of multiclass Littlestone dimen- sion 19) which we will use extensively in this work. Unless stated otherwise, we will use the convention that the root of a tree is at depth 0. As a first step, we define class of labeled binary trees, representing possible input-output label sequences over an input space X' and the label space [k].

---

Definition 2.8 (Complete io-labeled binary tree). A complete io-labeled binary tree of depth b with input set X' and output set [k] consists of complete binary tree of depth b with the following properties:
1. Every node of the tree other than the leaves is labeled by example E X.
2. The 2 edges going from any parent node to its two children are labeled by two different labels in [k].
3. The leaf nodes of the tree are unlabeled.
We are interested in whether the input- labelings defined by the complete io-labeled tree can be achieved by some function in the hypothesis class; to this end, we define realizability for root-to-leaf paths.
Definition 2.9. Given complete io-labeled binary tree of depth b, consider root-to-leaf path described as an ordered sequence S = {(I, ys) l E [b]], where xs is a node label and yi is the label of the edge between D; and 1, and where zo the root. We say that the root-to-leaf path is realized by a function J E H for every Me) in S, we have 24 E X and = f(xx))
Using this definition we can now define what it means for hypothesis class of functions to shatter a complete io-labeled binary tree, which helps to capture how expressive the hypothesis class is. Definition 2.10 (Shattering). We say that a complete io-labeled binary tree of depth b with label set [k] is shattered by hypothesis class H if for all 2 root-to-leaf sequences S of the tree, there exists function f E H that realizes S.
Using this definition of shattering
finally define the multiclass Littlestone dimension.
Definition 2.11 (Multiclass Littlestone dimension, ()). The multiclass Littlestone dimension of hypothesis class H, denoted M (H), defined to be the maximum b such that there exists complete io-labeled binary tree of depth that is shattered by H. If no maximum exists, then we say that the multiclass Littlestone dimension of H is cc.
3
Main results
3.1 Reduction from multiclass private PAC learning to binary private PAC learning
Our first main result is a reduction from multiclass private PAC learning to binary private PAC learning. Informally, the idea is that that every function f mapping examples to labels in [K] can be thought of as vector of binary functions (fi, fiog(t= 1)). Here, each binary function predicts bit of the binary representation of the label predicted by f. Then, we can learn these binary functions by splitting the dataset into log(k (k + 1) parts, and using each part to learn different f.. We can learn the binary functions using an (c. 8DP binary PAC learner. Then, we can combine the binary hypotheses obtained to get hypothesis for the multiclass setting, by applying a binary to decimal transformation. This process, described in Figure preserves privacy since changing a single element of the input dataset changes only one of the partitions, and we apply an (e, -DP learning algorithm to each partition. The binary to decimal transformation can be seen as post-processing.
Next, we formalize this idea. Given a hypothesis class H with label set [k). construct the following log(A= + 1) hypothesis classes 11, .... ,H hog(k+1). For every function f E H, let ft f X - {0, 1} be the function defined such that fa(x)) is the ęth bit of the binary expansion of f(x). Let the hypothesis class H]; be defined as [ ʃ E H}. We will call these the binary restrictions of H. Theorem 3.1. Let H be a hypothesis class with label set [k] and let H|.. H blogk++1) be its binary restrictions. Assume we have (c, diffferrrtel private, (a, acc-uraee PAC learners B¹ Bi...., Blog(k+1) B,,..,,BBoo(kk+)) for H|.,..., "lla....,HHuuutt (log(t+1) with sample complexities upper bounded Then, there exists an (e, (dife-lliferytniaally private, (ox, B)- accurate PAC learner A for the hypothesis class H that has sample complexity upper bounded
by SCL. a.8: SCC..... ""."..""",""""""" SS
a.
by Eleg( log(k+1) SC,, log(k+1).9) log(k+1y
The proof of this lemma can found in the full version of the paper. Next, we recall that the sample complexity of privately learning binary hypothesis classes is characterized by the Littlestone
5

---

Algorithi
Dalaset
Binary Hypothesis Hi
Algorthm
brt
Dataset
Hypothesis Class H
bindtecly ....ghhh-ty
bit log/k=1)
Dalaset Xlopiett
Binary Hypothesis
Algorithm
ghate!l
Class Hisphhl))
Figure 1: Algorithm the (c, 5DD PAC learner for hypothesis classes with label set [k]. The algorithm B used as subroutine is an (c, 6)DP PAC learner for binary hypothesis classes. bin2dec represents a binary to decimal conversion.
dimension of the hypothesis class ① 77]. That is, there exists an (a, acccuureeee (c. 8)-DP PAC learning algorithm for any binary bypothesis class H with sample complexity upper and lower bounded by a function only depending on a, B, e, ô and d where d is the Littlestone dimension of H. Using this characterization, we obtain the following corollary to Theorem 3.1 Corollary 3.2. Let H be a hypothesis class with label set [k] and HI,,"., llogkk+1) be its binary restrictions. Let the Littlestone dimensions of H....., " [log(k+1) be di,-.. chog(k+1)- Assume we have generic (e, differerrntt private, (ax -a-ccuraeee PAC learner B for binary hypothesis classes G that has sample complexity upper bounded by function SCe,a(d', a, a,,8) 8) where d' is the Littlestone dimension of G. Then, there exists an (c, (d.f private, (a, B))-acuraate -log(k+1) SCe,5(d,, a/ log(k PAC learner for H that has sample complexity upper bounded by > Liml 1), B/ log(k + 1)).
Corollary 3.2 shows that the sample complexity of privately PAC learning hypothesis class in the multiclass setting can be upper bounded by function depending on the Littlestone dimensions of its binary restrictions. However, as described earlier, Jung et al. [14] showed that the sample complexity of private multiclass PAC learning could be characterized by the multiclass Littlestone dimension. Hence, an immediate question is what the relationship between the multiclass Littlestone dimension of class and the Littlestone dimensions of binary restrictions
Connection between multiclass and binary Littlestone dimension
We show that the multiclass Littlestone dimension MLS(H) of hypothesis class is intimately connected the maximum Littlestone dimension over its binary restrictions.
Theorem 3.3. Let H by a hypothesis class with input X and output set [k]. Let the multiclass Liulestone dimension of H be d. Let H),, ...,..., loog()+1) be the binary restrictions of H. Let the Littlesonee dimensions of H1, 2. ................................ boggkk+1) be di, ... chog(k+1)- Then,
max d, S 6d 1=1,- (1g(
similar-looking theorem relating the Natarajan dimension of hypothesis class with the maximum
VC dimension over its binary restrictions proved in Ben-David et al. (5) using the notion of V-dimension. Our proof of Theorem 3.3 is inspired by this strategy. It will proceed by defining and analyzing notion of dimension that call v W--ittlestone dimension. It will also use the O-cover function of a hypothesis class defined in Rakhlin et al. [20). The details of the proof are described in obtain the following corollary
Section 5 Finally, combining Theorem 3.3 and Corollary 3.2,
to Theorem 3.1
Corollary 3.4. Assume we have generic (e, (e, -ddifferrent private, (a, 8)-accurate PAC learner B for binary hypothesis classes G that has sample complexity upper bounded by function

---

(d', a. where d' is the Littlestone dimension of G. Then, there exists a generic (c, 6)- differentially private. (a, 3) -accuraeee PAC learner for multi-valued hypothesis classes (label set [k) that has sample complexity upper bounded by log(k= + 1)SC (66 log(k + 1), or/ log(k 1), log(I: + 1)) where d is the multiclass Littlestone dimension of H.
We now consider an application of this result. The best known sample complexity bound for (c, 6)-DP binary PAC learning is achieved by a learner described in Ghazi al. [33. We state a slightly looser version of their result here.
Theorem 3,5 (Theorem 6.4 13 ). Let G be any binary hypothesis class with Littlestone dimension dz. Then, for any e, 8, a, 3 E [0, for some
d
(oog(
ea2
there is an diffferrnnnt private, (a, B)- PAC learning algorithm B for G with sample complexity upper bounded by n.
The above learner can be boosted via technique of Bun al. 66 to improve the dependence to nearly inverse linear. The details of this boosting are discussed in the full version of the paper. Applying the reduction described in Theorem 3.1 with this boosted learner as a subroutine, and using Corollary 3.4 we get the following theorem.
Theorem 3.6. Let H be concept class over X with label set [k] and multiclass Littlestone dimension d. Then, for any e, E, at, B E [0, for some
n = 0 d (log(k + 1))8 log²(
(
dlogg
c0c33
ea²
there is an (c, --dffeferentially private, (o,, -accurreeee PAC learning algorithm A for H with sample complexity upper bounded by
4
V-Littlestone dimension
4.1
Definition
In this section, define online analogue to the V-dimension [5] that will help prove Theo- rem 3.3. The main intuition is that similar to in the definition of V-dimension, we can use what we term collapsing maps reason about the multiclass setting while working with binary outputs. Let é : [k] + {0, 1,*) represent a function that maps labels to {0, 1, +}. which we term a collapsing map. We define family of collapsing maps V/ set of collapsing maps. The definitions of labeled trees will be the only distinction from the regular definition of multiclass Littlestone dimension; and every node addition an example will also have a collapsing map assigned to it.
Definition 1 (V-lldeled binary tree). A complete Vi llleeee binary tree of depth b with label set [k] and mapping set on input space X' consists of complete binary tree of depth b with the following labels:
1. Every node of the tree other than the leaves is labeled by an example x E X, and collapsing map V.
2. The left and right edges going from any parent node to its two children labeled by 0 and respectively.
3. The leaf nodes of the tree are unlabeled.
Where the input space, label space and mapping are obvious, will omit them and simply refer to complete W-labeled binary tree.
Definition 4.2. Consider a root-wo-leaf path in a complete V-labeled binary tree described as an ordered sequence S = ([xo, dn, y0). ... (2b-1, Φb-1, 1,-111 1)h- where each x; E X is inpul, Φs is a collapsing map, and yJs E {0, 1] is an edge label. We say that this path is realized by a function f e H if (x.)) for every triple in the ordered sequence S.
7

---

We can now define what it means for a class of functions to 4-shatter a complete V-labeled binary tree.
Definition 4.3 (V-shattering). We say that a complete y Y-labeled binary tree of depth b with label set [k] is V-shattered by a hypothesis class H for all 2 root-to-leaf sequences of the tree, there exists a function f E H that realizes S.
Finally, we are in position to define the V-Littlestone dimension.
Definition 4.4 WV-Littlestone dimension). The V-Littlesooee dimension VP WLD(H H) of a hypothesis class H is defined to be the maximum depth b such that there is complete V--lablled binary tree of depth b that is Y-shattered by H. If no maximum exists, then we say that the V V-Littlestone dimension of H is d =
4.2 Properties of V-LLittlestone dimension
In this section, begin our investigation of the V--Littlestone dimensions by discussing few simple and useful properties that they have.
We define three important families of collapsing maps y.,, yoin and 4 that will play important role in our results. Consider a collapsing map Rw,wr defined by (w, = 0 if = w. ww (e) = 1 if f = w', and dw.wn (f) = * otherwise. Then, V. defined to be (ou ww + w', w, w E [+]]] Similarly, let Φb be collapsing map that maps a label to the 7th bit of its log(k: + 1) bit binary expansion. Then, yrbin is defined to f i 1,............... log(k + 1)}. Finally, y is defined as the family of all collapsing maps from [k] to {0, 1]
For any hypothesis class H, we show the following properties of W. Whbn (H) and V.D (H).
1. For all hypothesis classes H, MLS(H) (H).
2. For all hypothesis classes H. the hee Littlestonee dimension upper bounds the maximum Littlestone dimension over its binary restrictions.
3. For all hypothesis classes H, (H) s (H) VLD
The proofs of these facts can be found in the supplementary material. These facts show the expressive power of the W--Lttlestone dimension.
Proof of Theorem 3.3
In this section, we use the concept of V-LLitllestone dimension prove Theorem 3.3
5.1 Sauer's lemma for multiclass Littlestone dimension
In this section, we will describe a version of Sauer's Lemma that will suffice for our application. This argument is essentially due to Rakhlin et al. [20]. Theorem 7 in that paper states Sauer's ' lemma style upper bound for quantity they introduce called 'O-cover function', for hypothesis classes with bounded 'sequential fat-shattering dimension'. We show that this argument applies almost verbatim for hypothesis classes with bounded multiclass Littlestone dimension.
5.1.1 0-Cover function
We start by recalling the definition of O-cover from Rakhlin et al.
Definition 5.1 (output-labeled) trees, input-labeled trees). A complete output-labeled binary tree of depth with label set [k:] is complete binary tree of depth such that every node of the tree is labeled with an output E [k)) A complete input-labeled binary tree of depth b with input set X is complete binary tree of depth b such that every node of the tree is labeled with an input in X.
The convention we will use is that output and input-labeled binary trees have root at depth 1 (as opposed io-labeled trees and V-labeled trees, where we use the convention that root has depth 0). Consider set V of complete output-labeled binary trees of depth b with label set [k). Consider a hypothesis class H consisting of functions from input space X' label set [kt). Fix complete input-labeled binary tree of depth b with input space X and complete output-labeled tree E V.
8

---

Definition 5.2. We say that root-to-leaf path A in corresponds to a root-to-leaf path B in ffr all S if node i in the left child of node in A, then node + 1 in is the left child of node in B and likewise for the case where node + is the right child of node
Definition 5.3. Let A be a root-to-leaf path in 2 and let the the labels of the nodes in A be (z1,... .bb where zi X. The function f E H applied to A, denoted by [A), is the sequence (f(zi), .. (( ((xa))
Definition 5.4 (0-cover, (0]). We say that forms O-cover of hypothesis class H on tree z if. for every function f E H and every root-to-leaf path A in Z, there exists complete output-labeled tree v E V. such that for the corresponding root-to-leaf path E with the labels of nodes in denoted by a tuple C' [k]* (call this the label sequence of B), have that f(A) =C
Definition 5.5 (0-cover function, (20). We will use N(0, H, z) to denote the size of the smallest O-cover of hypothesis class H on tree z. Let T be the of all complete input-labeled binary trees of depth with input space X. Then, the O-cover function N0, H, b) of hypothesis class H is defined as supzerg N(, H)
5.1.2 Statement theorem
The following theorem is essentially Theorem 7 in Rakhlin al. (with multiclass Littlestone Dimension instead of Sequential Fat Shattering Dimension).
Theorem 5.6. Let hypothesis class H set of functions f - [k:]. Let the multiclass Littlstonee Dimension of H be d. Then, for all natural rumbers 2 d,
ekn d
N(0, Hn S
k2 s
2=0
and for all natural numbers n < d, NO, H, H, S (I: + 1)"
The proof of this theorem proceeds via an inductive argument, and can be found in the full version of the paper.
5.2 Lower bound for O-cover function
To complement the upper bound given by our variant of Sauer's Lemma, we give lower bound showing that the O-cover function must grow exponentially in the ByB-Littlestone dimension of class.
Lemma 5.7. Let the v -Litleestone Dimension of hypothesis class H be d. Then,
N(0, H,d) 2 2d
The proof can be found in the full version of the paper.
5.3 Putting the pieces together
In this section, we prove Theorem 3.3 using the techniques we have built up.
Let // be hypothesis class with MLS(H) = d and let H|1, H. llo((--) be its binary restrictions with Littlestone dimensions dy,... dlog(k+1)- Let the & (H) be d Then by the discussion in
Section 4.2 we have that d S dg. Additionally, using Lemma 5.7 and Theorem T5e n = dg 2 d.
we have that
ekdB d d
2dg < <NO,, H, <
(I)

---

We will use the fact that for all positive real numbers 2, y, In. S -y--n(ey)) Fix some constant y In 2 be chosen later. We can simplify equation| Wwith the following chain of inequalities.
2da
( d
(ekda
dB 1nln25 d
Im
dB
+ In(ek)
dB
dø 1n2 S d
y
In(ey) In(ck)
d
k dln
dB
In y
Setting y In 2, we get that
dg S 6d + 1).
Finally, by the discussion in Section 4.2 lower bounded by the maximum Littlestone dimension of the binary restrictions H. Then,
know that the 1 (H) is upper bounded by da and
max
dj S 1 bin
LD
H)) I dB I ln + 1).
1og(k+1)
This proves the theorem.
Mark Bun partially supported by NSF grants CCF-1947889 and CNS-2046425. Satchit Sivakumar was partially supported by NSF grant CNS-2046425. Marco Gaboardi was supported by the National Science Foundation under awards CNS2040249 and CNS2040215. In addition, this work was partially supported by Cooperative Agreement CB20ADRO1600U with the Census Bureau. The views expressed in this paper are those of the authors and not those of the U.S. Census Bureau or any other sponsor.
Funding and acknowledgements:
10

---

References
[1] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private pac learning implies finite littlestone dimension. In Proceedings of the SIst Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019, page 852 860, New York, NY, USA, 2019, Association for Computing Machinery.
[2] Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 269-282 PMLR, 2019.
[3] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and samitization: Pure vs. approximate differential privacy. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization,, and Combinatorial Optimization. Algorithms and Techniques, pages 363-378, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[4] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learners. J. Mach. Learn. Res., 20:146:1-146:31 2019.
[5] Shai Ben-David, Nicolò Cesa- Bisa-BBanchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, .... va-vulued functions. J. Comput. Syst. Sci., 50(1):74-86, 1995.
[6] Mark Bun, Marco Leandro Carmosino, and Jessica Sorrell. Efficient, noise-tolerant and private learning via boosting. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 1031-1077. PMLR, 2020.
[7] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 389 402. IEEE, 2020.
(8) Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 634-649. IEEE Computer Society, 2015.
[9] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai and the erm principle. In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 207-232, Budapest, Hungary, 09-11 Jun 2011. PMLR.
Multiclass learnability
[10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[11] Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51-60. IEEE Computer Society, 2010.
[12] Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 1000-1019, Barcelona, Spain, 13-15 Jun 2014. PMLR.
[13] Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC 21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. Virtual Event, Italy, June 21-25, 2021, pages 186-196. ACM, 2021.
11

---

[14] Young Hun Jung, Backjin Kim, and Ambuj Tewari. On the equivalence between online and pri- vate learnability beyond binary classification. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[15] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2263-2285. PMLR, 2020.
[16] Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Private learning of halfs- paces: Simplifying the construction and reducing the sample complexity. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Flowe Florina Balcan, and Ssuan-Tien Lin, editors, Ad- vances in Neural Information Processing Systems 33; Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[17] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova and A. Smith. What can we learn privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science pages 531-540, 2008
[18] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2(4))285-318) 1987.
[19] B. K. Natarajan. On learning sets and functions. Mach. Learn., 4(1):67-97, October 1989.
[20] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161(1):111-13,, 2015.
[21] I. Valiant. A theory of the learnable. Commun. ACM, 27(11):1 134-1142, 142, November 1984.
12


Reviews:
[{"review_id": "hPF9QDopGR0", "reviewer": "Reviewer_8M5o", "summary": "This work studies the connection between the differential privacy of binary learning and multiclass learning. The authors first show a simple reduction from multiclass to binary to private learning, meaning that they show that for any $f$ if there is an algorithm that private learns each binary function of $f$ (meaning learns each bit of $f$) then there is a private algorithm for $f$. Furthermore, the authors show tight bounds on Littlestone of multiclass and binary learning. They prove that if a multiclass hypothesis class has Littlestone dimension $d$ then each binary restriction of the same class has Littlestone dimension bounded by $\\sim 6d\\log k$. The authors provide upper and lower bounds for this claim. Moreover, the authors provide an upper bound to the sample complexity or privately learning a multiclass hypothesis relatively to the Littlestone dimension of this class.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "First of all, this work is well-organized and well-written and establishes very basic and fundamental results in differential privacy in the multiclass regime. The multiclass setting is a natural generalization from binary learning and providing upper bounds can be very challenging even in the simple PAC learning. Providing bounds on the binary restriction of a class $H$ is sometimes more difficult than proving for the multiclass problem (i.e., for linear classifiers the problems become non-separable in the binary restriction). Therefore, I find Theorem 1.3 very interesting. A weakness of this work is as the authors acknowledge, their strategy is similar to [5]. Overall, I recommend for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adress the societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "OlL6tn0KyhQ", "reviewer": "Reviewer_ErcE", "summary": "This paper studies the problem of multiclass differentially private PAC learning. It provides a generic reduction from multiclass differentially private PAC learning to binary private PAC learning, that is intuitively based on the decomposition of an integer $k$ into $\\log(k)$ bits. As a result, the contribution of the paper is a private multiclass learning algorithm (with sample complexity polynomial in the multiclass Littlestone dimension and poly-logarithmic in the number of labels-classes). This work is closely related to recent progress in the binary classification regime towards the connections between differentially private learnability and online learning.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This work studies multiclass differentially private PAC learning. The main question asked in this work is whether one can obtain multiclass DP learning results based on the existing binary DP learning results.\n\nAt a technical level, the paper relies on two known facts: a (simple) reduction from multiclass learning to binary and recent advances on (binary) DP PAC learning. Specifically, it is based on a well-known reduction from a given multiclass learning problem to a collection of binary sub-problems (that intuitively corresponds to the decomposition of an integer $k$ into $\\log(k)$ bits) and on a recent result that a binary class is privately learnable using $\\tilde{O}(d^6)$ samples, where $d$ is the Littlestone dimension of the class.\n\nUsing the aforementioned reduction, the authors obtain that if all the binary sub-classes are privately learnable, then the original multi-label class is privately learnable too. The main technical contribution of this work is the statement that if a multi-valued class has bounded multiclass Littlestone dimension, then all of its binary sub-classes have bounded binary Littlestone dimension (recall that the finiteness of the (binary) Littlestone dimension of a binary class implies that the class is privately learnable). The authors provide a tight quantification of this statement. \n\nThe tools behind the proof lie mainly in the well-known work on standard multiclass PAC learning and the $\\Psi$-dimension. Specifically, this work provides an extension of this capacity measure to the online setting: they show that one can choose a mapping $\\Psi$ so that the $\\Psi$-dimension corresponds to the multiclass Littlestone dimension while another choice of mapping can yield the maximum Littlestone dimension of the binary associated classes.\n\nStrengths: The problem studied in this paper is a natural extension of the existing literature. The connection with the previous results is clear and the provided technical result between multiclass and binary Littlestone dimension is nice. The sample complexity result has the additional advantage of being modular, in the sense that future improvements for the binary classification task can be directly applied to the multiclass case. The online analogue of the $\\Psi$-dimension is novel and seems natural and useful.  \n\nWeaknesses: The main novel technical contribution lies only in the introduction of the online version of the $\\Psi$-dimension in order to obtain the result that finite multiclass Littlestone dimension implies control to the Littlestone dimension of the binary sub-classes. The other two results (the reduction and the sample complexity improvement) are based on existing results: the reduction is essentially similar to the non-private setting and the proof has the additional privacy part (which is not technically challenging) and the sample complexity bound is a direct application of the binary $\\tilde{O}(d^6)$ result thanks to the reduction.\n\nPrevious Work: It is clearly presented how this work differs from the existing results and how existing results are used.\n\nCorrectness: As far as I can tell, yes.\n\nClarity: The paper is well-written and the results are clearly stated.\n\nSignificance: The results of the paper are interesting; this work is based on recent advances in (mainly binary and DP) learning theory and provides understanding towards the multiclass classification case.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors propose some potential future directions which correspond to some limitations of the existing work and hence address adequately this task. I do not think there is any potential negative societal impact as a byproduct of this work.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6"}, "extra_text": {}}, {"review_id": "ClqGtEIorVo", "reviewer": "Reviewer_T8vG", "summary": "The paper gives a generic reduction from from private binary PAC learning to private multi-class PAC learning. This paper improves the previous known results for multi class PAC learning in terms of both the dependence on the multi class Littlestone dimension (parameter which characterizes private PAC learning) and the number of classes. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper gives a generic reduction from from private binary PAC learning to private multi-class PAC learning and gets exponential improvement compared to previous results in terms of both number of classes and multi class Littlestone dimension. Private learning has been gaining considerable interest and is an important topic. This paper not only gets improved bounds but also since it generically converts guarantees from binary classification to multi-class classification for private learning and would also hold for future private binary classification results. The main technical contribution of the paper is to show that Littlestone dimension of the function class consisting of each bit of the function class is upper bounded by the multi class Littlestone dimension of the class. I think this result is interesting in itself and might be more useful generally. As the paper claims, the techniques in proving this result mostly follows from previous work in the supervised learning setting but, the generic reduction and using this connection is quite interesting and useful. \n\nThe paper is generally well written and easy to follow. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an elegant paper establishing fundamental results for multiclass differentially private PAC learning.  The reviewers found the paper well written and the results interesting.
Decision: Accept (Poster)