Fast Rates for Bandit PAC Multiclass Classification
Authors: Liad Erez
Alon Cohen
Tomer Koren
Yishay Mansour
Shay Moran
Venue: NeurIPS 2024 poster (2024)
Keywords: bandit
classification
multiclass
Primary area: bandits
TL;DR: We establish optimal sample complexity bounds for agnostic PAC in bandit multiclass classification with finite hypothesis classes and Natarajan classes

Abstract: We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(\varepsilon,\delta)$-PAC version of the problem, with sample complexity of $O\big( (\operatorname{poly}(K) + 1 / \varepsilon^2) 
\log (|\mathcal{H}| / \delta) \big)$ for any finite hypothesis class $\mathcal{H}$. In terms of the leading dependence on $\varepsilon$, this improves upon existing bounds for the problem, that are of the form $O(K/\varepsilon^2)$. We also provide an extension of this result to general classes  and establish similar sample complexity bounds in which $\log |\mathcal{H}|$ is replaced by the Natarajan dimension.
This matches the optimal rate in the full-information version of the problem and resolves an open question studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011) who demonstrated that the multiplicative price of bandit feedback in realizable PAC learning is $\Theta(K)$. We complement this by revealing a stark contrast with the agnostic case, where the price of bandit feedback is only $O(1)$ as $\varepsilon \to 0$. Our algorithm utilizes a stochastic optimization technique to minimize a log-barrier potential based on Frank-Wolfe updates for computing a low-variance exploration distribution over the hypotheses, and is made computationally efficient provided access to an ERM oracle over $\mathcal{H}$.

Fast Rates for Bandit PAC Multiclass Classification
Liad Erez Tel-Aviv University
Alon Cohen Tel-Aviv University
Tomer Koren
Tel-Aviv University
1 laderez@mail. tau. ac. i1
Google Research
Google Research
alonco@tauex. tau. ac
tkoren@tauex tau, ac
Yishay Mansour Tel-Aviv University
Shay Moran
Technion
Google Research
Google Research
mansour.. wis.rrryyyyyyyymll..coom
thaymoran1@gmaill.
Abstract
We study multiclass PAC learning with bandit feedback, where inputs are classi- fied into one of possible labels and feedback limited to whether or not the predicted labels are correct. Our main contribution is in designing novel learn- ing algorithm for the agnostic (e, 6)-PAC version of the problem, with sample complexity of ((poly(K) + 1/E=) log( (IH)/5) log((7()))) for any finite hypothesis class H. In terms of the leading dependence on E, this improves upon existing bounds for the problem, that are of the form OK//²²) We also provide extension of this result to general classes and establish similar sample complexity bounds which log [H] is replaced by the Natarajan dimension. This matches the optimal rate in the full-information version of the problem and resolves an open question studied by Daniely, Sabato. Ben-David, and Shalev-Shwartz (2011) who demon- strated that the multiplicative price of bandit feedback in realizable PAC learning is O(K). We complement this by revealing stark contrast with the agnostic case, where the price of bandit feedback is only O(1) as & - O. Our algorithm utilizes stochastic optimization technique minimize log-barrier potential based on Frank-Wolfe updates for computing low-variance exploration distribution over the hypotheses, and is made computationally efficient provided access to ERM oracle over H.
Introduction
Multiclass classification is fundamental learning problem in which learner is tasked with clas- sifying objects into one of possible labels. In bandit multiclass classification [18], upon making a prediction, the learner does not observe the true label, but only whether not the prediction was correct. As a concrete example, consider the task of classifying images, say, from the ImageNet dataset, with the number of labels K being several thousands. After the learner predicts a label for particular image, both the image and the prediction are shown to a human rater who asked prediction is correct not, after which the answer is revealed to the learner. Thus, the learner faces a bandit multiclass classification instance as the true label is not revealed in case the prediction was deemed incorrect by the rater.
Much of previous work on the foundations of bandit multiclass classification focused on the online setting [18, 10, 9, 21, 23, 13), where the goal of the learner is to minimize the regret compared to a given hypothesis class H, namely, the learner's total number of correct predictions throughout the learning process compared to that of the best fixed hypothesis from H. A central line of work focused on studying the properties of H that allow for sublinear regret this context, and on char-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

acterizing the achievable regret rates in terms of K. |H] and the number of prediction rounds T. For instance, Auer et al. [4] show that for any finite H one can obtain a regret bound of O O(T log [H(), by casting the classification problem as (contextual) K K-armed bandit problem. Daniely and Hel- bertal [9] demonstrate that the dependence on log [']] can replaced by the Littlestone dimension of tH, which may potentially be smaller than log [H] and, in particular, may be finite even when H is infinite. Very recently, Erez et al. [13] establish a characterization of the optimal regret rates for finite hypothesis classes and show that it is of the form (min KT log [H[],, [H| + vT), which is tight even when the labeled examples are drawn i.i.d. from a fixed distribution.
Here we focus on a different, yet closely related version of multiclass classification, viewed as a learning problem in a PAC framework [25]. In this setting, the labeled examples are drawn from a fixed unknown distribution, and the learner's ' goal is to ultimately output a prediction rule which performs well, over this distribution, relative to the best hypothesis from the underlying class H. This problem has mainly been studied in the analogous full-information setting, that is, when the learner as access to training set of i.i.d. examples along with their true labels, where the number of samples required to learn an 8-optimal hypothesis was shown to be O((1/=)) log( (HH))) for finite classes [22, 5, 10, 6]. the bandit case, however-namely where the learner may repeatedly predict labels of drawn examples and obtain feedback only on whether the prediction was correct not-a comprehensive understanding of the achievable sample complexity rates is still missing.
On the surface, the PAC bandit multiclass problem might be deemed trivial: a straightforward ap- proach of uniformly approximating the losses of all hypotheses in H by drawing i.i.d. examples and predicting labels uniformly at random, already gives rise to O((K) (s))) log [H() sample complexity which appears to be optimal due to the bandit feedback. Furthermore, the simple underlying al- gorithm can be implemented efficiently. provided that empirical risk minimization (ERM) can be carried out efficiently over the hypothesis class. However, this view regards multiclass classification as generic K K-armed (contextual) bandit problem and neglects crucial aspect of the setting: each example has a single correct label, as opposed to a more general scenario where each label may be associated with its own loss, independently of other labels. And indeed, no non-trivial lower bounds can be found in the existing literature for this problem.'
The following questions thus remain:
(1) What is the optimal sample complexity of the bandit multiclass setting? In particular, can one improve upon the prototypical K/&² rate, representative of bandit problems?
(2) Can this sample complexity be attained by an efficient (polynomial time) algorithm, whenever ERM can be computed efficiently over the underlying hypothesis class?
1.1 Summary of contributions
In this work, we address the questions above and establish a nearly-tight characterization of the achievable sample complexity in the bandit multiclass problem, along with an efficient algorithm. Our main contributions are summarized as follows.
(i) For a finite hypothesis class H, we give an algorithm with sample complexity of ((pol((K) 1/6²) log( (o8()))))) for producing an 6-optimal classifier with probability at least 1 5: see Theorem 1 in Section 3. Further, our algorithm is proper learner and can be implemented efficiently provided a (weighted) ERM oracle for the class H. In terms of the leading depen- dence 8, this bound significantly improves over the previously mentioned O(K/ bound, and matches the optimal rate in the full-information version of the problem.
(ii) For more general, possibly infinite hypothesis classes H with finite Natarajan dimension d, we establish a generalized sample complexity bound of ((poly((K + 1/$²)d log(1/8)); see Theorem 2 in Section 4. This improves over the previous O(Kd/e") bound due to Daniely, Sabato, Ben-David, and Shalev-Shwartz [10], and matches the known rate in the full-information case [22] up to logarithmic factors for sufficiently small s.
These results bear some interesting consequences. First, and perhaps most surprisingly, they imply that there is no additional price for bandit feedback in PAC multiclass classification, as 8 - O:
We note that Daniely and Helbertal [9] do provide stochastic lower bound construction, but it pertains to multi-label multiclass rather to the standard single-label setting we consider here.

---

namely, that the ratio between the optimal sample complexity rates in the bandit and the full- information settings is (1), and not @(K) as one might expect. Indeed, the latter is often the multiplicative price of bandit information in multitude of scenarios (see, e.g., 19], and further, it is the tight price in the realizable case of bandit multiclass [10]. This phenomenon occurs already in the case of finite hypothesis class, and extends naturally to general Natarajan classes.
Second, the results reveal an unexpected gap between the attainable bounds in the online (i.e., regret minimization) and the PAC settings of the bandit multiclass problem. A recognized trademark of online learning is that online-to-bue to-batch conversions of regret bounds very often give sharp sample complexity rates in the i..d. PAC setting [see e.g.. 8, 7, 17]. In bandit multiclass classification, however, we exhibit a stark separation between the two settings, where for sufficiently large hypoth- esis classes an online-to- saine-tto-atchh batch conversion of the optimal regret rate results with sample complexity O(K/E) x2) [13], whereas the rate we establish here is (1/E8² + poly(K))-
The core novelty in our algorithmic approach is a stochastic optimization technique for efficiently recovering a low-variance exploration distribution over the hypotheses in H, with variance (1) rather than the OKK) obtained by simple uniform exploration of labels. We show that through minimization of stochastic objective akin a log-barrier (convex) potential over the induced label probabilities, such a distribution can be computed in a sample-efficient way and in turn be used to uniformly estimate the losses of all hypotheses in H via importance sampling. Moreover, we demonstrate how this stochastic optimization problem can be solved efficiently using a stochastic Frank- Wolfe method. More details about the algorithmic ideas and an overview of the analysis are given in Section 3.
1.2 Additional related work
Bandit multiclass classification. In agnostic online multiclass classification with bandit feed- back, regret bounds of the form O(yKT log (H)) can be obtained by viewing the problem as an
instance of contextual multi-armed bandits [4]; this bound has been recently improved by [13] to O(min KvKT log [H]. 17| + VTJ) for the classification setting. [9] show how to replace the log [H] dependence in the first bound by the Littlestone dimension of H, and [23] show how K can be replaced with a refined quantity which encapsulates the effective number of labels. Additional re- finements in the realizable setting include the Bandit Littlestone dimension which provides char- acterization of the optimal mistake bound for deterministic learning algorithms [10].
Contextual bandits. The PAC objective of the bandit multiclass classification problem can be seen special case of the problem of identifying an approximately optimal policy in contextual multi-armed bandits. In the more general contextual bandit framework, sample complexity lower bounds of 22(K' /²) are known [4]. with regret upper bounds of the form Ō (KV obtained in several previous works [4, 12, 1]. Reducing our problem to contextual bandits, however, ignores the special structure exhibited by the reward function in the classification setting, namely their sparsity (see [13] for a more detailed comparison), and indeed we establish improved sample complexity rates in this special case. In bit more detail, in the works of [12, 1], one of the main technical ideas is to compute a distribution over policies which induces reward estimator whose variance is bounded, uniformly over the policies, by O(K) (it is actually nontrivial to show that such distribution even exists). Our approach involves similar ideas the sense that we also aim to compute such a low-variance exploration distribution over the hypotheses, but the crucial difference is that in the classification setting, the sparse nature of the rewards allows us to uniformly bound the variance by 0(1) rather than OKK). Li et al. [20] also consider the PAC objective for contextual bandits and establish gap dependent sample complexity bound which never exceeds K/æ², but to our understanding does not imply improved bound for sparse rewards (or single-label classification), as even for the multi- armed bandit variant, in order to obtain improved sample complexity bounds which are instance dependent, one must leverage the variances of the arm rewards in addition to the gaps.
2A similar separation has been observed before, e.g., in the context of general online/stochastic convex optimization [24].
3

---

2 Problem Setup
Bandit multiclass classification. We consider a learning setting in which learner is tasked with classifying objects from a set of examples X with a single label from a set of K possible labels y (1.... K). A stochastic multiclass classification instance is specified by hypothesis class H m (X- -) and a joint distribution 2 over example-label pairs over X x y. We focus on finite hypothesis classes and denote N - |H] In the bandit setup, the learner interacts with the environment an iterative manner according to the following protocol, over 1, ....
(i) The environment generates a pair (xi, yi) D and the example x; is revealed to the learner;
The learner predicts label E y;;
(iii) The learner observes whether or not the classification of is correct, namely 1(;; = =>}}.²
Agnostic PAC model. In the PAC version of the problem, given parameters e, 8 0 the goal of the learner is to produce a hypothesis à X - M, such that with probability at least 1 - 6 (over the randomness of the environment as well as any internal randomization of the algorithm):
( - (D(h)) S
where here (h) - Pr[h(x) y] is the expected zero-one loss of h with respect to (x. D, and ht* - argmin (h) is the best hypothesis in H. That is, the learner needs to identify a hypothesis which is e-optimal in H with respect to the expected zero-one loss, with probability at least - 6. In this model, the learner's 's performance is measured in terms of sample complexity, which the number of interaction rounds with the environment as a function of ô required for satisfying the guarantee stated above.
Weighted ERM oracle. For computational results, will assume weighted empirical risk minimization (ERM) oracle access to the hypothesis class H. In more detail, we assume access oracle, denoted OH, defined as follows: given sequence of examples, labels and weights (xi, (1,0)),........ (., (t, E X x y x R as input, the oracle OH returns
Σ a, 1(h(x,) ys)-
argmin BeTH
We remark that this is version of the argmin oracle often considered in the more general contextual bandit setting [e.g.. 12, 1], specialized for the classification setting we focus on here. For our runtime results, we will assume that each call to OyH takes ((1) time.
EN P. 1} the N-dimensional simplex which corresponds to the set of all probability distributions over H. Given P e AN and h H we use the notation P(h) to denote the probability assigned to h by the probability vector P. Given an example-label pair (x. y) X we define the binary vector Fx,y {0, 1) by
Additional notation. We denote by AN & {PeRt R
rx,y (h) & 1(4() y) Vh E H.
that is, Fx,y (h) is the zero-one reward of the hypothesis h on the pair (x. y). Given P E AN and (x, y) E X y we denote the probability of choosing the label y when sampling a hypothesis from on by
W (P) & Σ P(h)(s((x) = = P k=T
and for y (0, 1) we let W (P) & (1- Wr, w.y + y/K, which corresponds mixing the distribution Wzy (P) with a uniform distribution over labels with weight factor y.
3 Note that in the bandit setting, the learner does not observe the true label yy directly. In this model we allow for improper learners, that is, the output hypothesis may not a member of H; we emphasize, however, that main algorithm below is proper leamner namely it returns hypothesis h H.

---

Algorithm Bandit PAC Multiclass Classification via Log Barrier Stochastic Optimization
Parameters: MI. M (0, }
Phase 1:
Initialize 5 < 0.
while [S] M1 do
Environment generates (x. ~ D, algorithm receives X.
Predict uniformly at random from y and receive feedback 1(8 y).
Update S - U (xx if otherwise S is unchanged.
end while
Solve the stochastic optimization problem defined in Eq. (2) to an additive error of /2 using the dataset S. Let P AN be its output.
Phase 2: for lo... M2
Environment generates (x), D, algorithm receives X7- With prob. y. pick y1 y uniformly at random; otherwise sample h, and set 5; h1 (x1))
Predict 8, and receive feedback 1(5; y:).
end for Return:
h= On ((xi fi.
where 0; = =1(y, = "4y:=8///2(xx..99
3 Algorithm and Analysis
In this section we present and analyze our main contribution: an efficient bandit multiclass classi- fication algorithm, detailed in Algorithm 1, which will be shown satisfy the following agnostic PAC guarantee.
Theorem 1. If we set = 1, M₁ O(K* log((N00), M2 = O[log(N/O))(//e++ 1/E²)/++++///))))))) and use Algorithm solve the optimization problem defined in Eq. (2) for T O((K /lgg// rounds with step sizes Ti 1/t and batch sizes b, (y/2K) for (2 1)ka1 and b, otherwise; then with probability at least 1 Algorithm outputs h H with Lo Lo)h)( s using a total sample complexity of
olxx2
log 8 E
Furthermore, Algorithm I makes total number of O OK* /log( (()) calls to the weighted ERM oracle Oz, and runs in total time polynomial in K, 1/8 and log (N/)).
phases. In the first phase, we construct dataset of Mi poly(K) log(N/5) i.i.d. samples from D by predicting labels uniformly at random and taking into the samples for which the correct label is predicted (and is thus known). We then feed these samples to stochastic optimization scheme which finds an approximate solution to the following stochastic optimization problem:
Algorithm operates in
min (PP) & Dl..))-(d((Px..)) where o(P:x.y) & é log( (P))
(2)
s.t. PEAN.
The approximate solution, م AN will be shown satisfy certain low-variance properties, which will allow us to repeatedly sample from P for M2 O((K) /e + 1/s²) log(N/8) and estimate the loss of hypotheses in H rounds such that are guaranteed to find approximately optimal policy with high probability. We again emphasize that our algorithm is a proper learner in the sense that the returned hypothesis h is member of the underlying class H.
3.1 Overview of analysis
We next outline the details and intuition behind the implementation of Algorithm 1.
5

---

Low-variance exploration distribution. The main goal of the first phase of Algorithm 1 is to compute an exploration distribution P E AN with the property that with probability at least 6//2, the following holds:
Ix,y (h) W? (P)
Vh E H:
E(xy))
SC
(3)
where is some predefined parameter and C is an absolute constant, which crucially does not depend on K. The intuition behind this property is that the quantity of the left-hand side of Eq. (3) constitutes an upper bound on the variance of the random variable
Fx,y ()) =
WZ,y (P)
which is an unbiased estimator of the expected reward of the hypothesis h, that is, of 1(hxx) = y} the label ÿ is chosen according to an hypothesis drawn from P and y) is drawn from D. Thus, we think of Eq. (3) as a property which guarantees that the exploration distribution P can be used to estimate rewards, uniformly for all hypotheses in H, with low (constant) variance. This in turn allows us make use of -uriiice-sensitive concentration bounds, namely Bernstein's 's inequality, in order to accurately approximate the optimal policy using a small number of samples (this is done in the second phase of the algorithm, described below).
Controlling variance via stochastic optimization. In some more detail, our approach for com- puting such low-variance exploration distribution P is via upproximately solving the stochastic convex optimization problem defined in Eq. (2). The reason for the choice of O as convex poten- tial be minimized is the fact that its gradient is, up to a constant factor, given by
(h) W (P)
Vh E H (Vo(P)); = E
(4)
so that finding a low-variance exploration distribution amounts to computing P e AN for which VPD(P) is bounded in Los norm. Indeed, we show that the optimal solution the optimization problem given in Eq. (2) satisfies such a property. This, together with the properties of O as a self- concordant function allows finding such P by approximately minimizing & over the simplex: the self-concordance of a acts as a "restricted strong convexity" property, which roughly implies that approximate minimizers of O must also have small (low norm) gradients.
Efficient optimization via Stochastic Frank- Wolfe. In order to compute an approximate mini- mizer of the convex potential @ defined in Eq. (2), we employ stochastic optimization procedure, formally described in Algorithm 2, which is based on a stochastic version of the Frank-Wold (FW) algorithm [15] with SPIDER gradient estimates [14]. The reason for choosing a FW based approach, is that it allows for efficient optimization of ④ in N d-dimensional space, with runtime essentially in- dependent of N, by exploiting the weighted ERM oracle at our disposal. Furthermore, the FW algorithm, when performed over the simplex, generates iterates P,. P2.... such that P, is supported on at most / coordinates (provided that P1 is initialized at an arbitrary vertex of the simplex), allow- ing us to maintain succinct representation of the FW iterates again, essentially independently of the ambient dimension N. Additionally, we remark that while existing analyses (e.g. [29]) of the stochastic FW algorithm rely on smoothness of the objective with respect to the Lz-norm, objec- tive of interest, namely & is not smooth in this classical sense, however is smooth with respect to the LI norm. Therefore, we crucially rely on different analysis of the FW algorithm with SPIDER gradient estimates, presented in Appendix C, which accommodates smoothness with respect to the L1 norm.
Final exploration phase. The second phase of Algorithm 1 is more straightforward, where we repeatedly predict labels using i.i.d. samples from distribution which mixes the distribution over labels induced by P (the exploration distribution computed in phase 1) with a uniform distribution over y. Using Bernstein's inequality and the uniform low-variance property of P. we show that M2 = ((KK/* 1/8²) log(N/8)) samples suffice in order to ultimately output an hypothesis h H being e-optiall with probability at least 1 - 6/2. With this in hand, the desired PAC guarantee follows by union bound over the failure probabilities of the two phases of the algorithm.

---

3.2 Stochastic Trank-Wolff with SPIDER Gradient Estimates
Next, we present the stochastic FW procedure used in our algorithm as subprocedure; see Algo- rithm 2. It is essentially the SPIDER FW algorithm of Yurtsever et al. [29], specialized for solving the stochastic optimization problem defined in Eq. (2). We remark that the algorithm makes calls to línear optimization oracle over the simplex denoted by LOO, that given an input IR com- putes (g) = a Q g. As we will show later, each of the calls Algorithm makes to LOO can be implemented by call to the weighted ERM oracle. We also remark that, as discussed before, existing analyses of the stochastic FW procedure with SPIDER gradient estimates relies on L2 smoothness of the objective [29], and here we provide an analysis with respect to L1 smoothness being crucial in our case. We defer further details about SPIDER FW and its analysis to Appendix C.
Algorithm Stochastic Frank- Frank-Wolfe with SPIDER gradient estimates
Parameters: Dataset S C X yy, step sizes {n: ), batch sizes (b,)-- Initialize P1 E Av and initial gradient estimate g1
Let rą 2* - for k 1,2,.... for r ... do
Draw b, fresh samples (x1,))).... ..... (Nb, yb,) from S; i {T)) then Set
81
V (P)))))))
D
else Set
b Vo(Prix),)) yd) Vo(P,-iix)
81 8r-11
[=1
end if
Compute Q, = Lg))
Update Pr+1 (1 - n; n:
end for
3.3 Proof of Theorem
We now turn to formally prove Theorem 1. For clarity notation, we henceforth use E[-] instead of E(c.y)-DD [-] to denote expectation of random variable with respect to D. We begin this section by analyzing the first phase of Algorithm The following lemma, which is proven in Appendix A, characterizes the optimal solution to the stochastic optimization problem defined in Eq. (2), and shows that the gradient of & at that optimum is bounded by constant in Les norm.
Lemma 1. Suppose S I and let P+ E argmin ((P), where @ AN - R. was defined in Eq. (2). Then for any AN have
W7
(P)
E
1
(5)
W
(P+)
In particular, letting be the delta distribution on some h H:
Ex.y(h)
E
2.
W (P+)
The next key lemma, whose proof is also in Appendix A ensures that a sufficiently approximate minimizer of ① is also point in which the gradient is bounded I-e-norm, establishing the property given in Eq. (3).
Lemma 2. Suppose S and assume that for all P. e AN the following holds for P which was computed in phase of Algorithm
-())) μ.
7

---

Then,
Ruk2
|Vo(P) 2
y2
In particular, setting y /2k gives ||V 3.
The fact that the property given in Eq. (3) can be guaranteed with high probability using as few as Mi (poly((K (og(N/6) samples relies on the following lemma, also proven in Appendix A, which follows from the analysis of the stochastic Frank-Wolfe procedure (see Appendix C for the detailed analysis).
k /ya) 1og(16N/6) and = /ldd then with probability least 6/2, for all P. E AN it holds that
Lemma 3. Suppose S 1- M = 58000 K$
y
< - (P+)) -(P))
2K
We are now in position to prove Theorem by analyzing the second phase of Algorithm We make use of the guarantee of the first phase given in Lemma 2 with respect to the exploration distribution P. which allows us to use Bernstein's concentration inequality order to compute an e-optimal hypothesis in high probability using only = K/E + 1/ samples.
Proof of Theorem I. We first show that we can in fact use Algorithm as specified in the theorem's 's statement. That is, we prove that the calls to the linear optimization oracle, denoted by LOO in Algorithm can be implemented using the weighted ERM oracle Oz. Indeed, we first note that for any 8 RN holds that
LOO(g) g) = a 8) argmin(gg))
PEAw
heH
so it suffices to show that this can represented the form given in Eq. (1) for the SPIDER gradient estimates used in Algorithm 2, which we denote by It is straightforward to see each is linear combination of terms of the form Vo(P.x, y) where P is either
P.-1. Thus, we show that for g = Σn Ve Xi. yr), LOO(g) can be computed by call to the weighted ERM oracle. Indeed,
LOO(g)= argmin hErH
-11 y)
1(((x; = yi)
= argmin hes
Σ cr 1(h(x)) # yr).
W Wx (P,)
where a; = (1 - Ne.yy (Pr). Now, assume that after phase I, Algorithm computed P e AN with
(h)
max E hCH
$ 3.
(P)
Fix some E H. For i E (l....,M., M2} define (i)h) Kapoy (x)
w2 Wa (P) Note that E[X((h)
Pr[h(x) = y] and that Xi (f)...., XM, (h) are i.i.d. Additionally, by the guarantee phase I:
Var[X,(h)] S [ Fx (h) = 9r)
=E Ex,y (h) 3.
(W Xy.y (P))²
(P)
Define X(h) M. MM and note that by the form of the weighted ERM oracle, argmaхлew (h). Therefore, by an application of Bernstein's 's inequality (see e.g. [19], page 86)
and union bound, we have with probability at least - 6/2 for all h H:
6 6lgg(2/0))
2K log(2N/0)
(1) Pr[h(x) yll s
M2
M2

---

Hence for h, with probability at least 1 - 6/2 we have
LD(h) - (h²h)) = Pr(h(x) * y] - (x) + y]
-Pr[h* (x) = y Pr(h(x) y
(x) =y1 X(h")+ X(h)) - Pr(h(x)) y
36 36log(2N/0) 4K 1og(2N/6)
M2
yM2
Choosing M₂ 2 max log 8K log(2N (2) /0) (yε)) gives (D (h*) E. Thus, using Lemma 2 and Lemma 3, we are only left with proving that with high probability, collecting Mj samples for takes at most O(K* log(N/o) (6)) steps. This essentially follows from the fact that a binomial random variables is smaller than half of its expected value with very small probability. Formally. we use lemma F.4 of [11] to deduce that if X Bin(4K M, 1/K) then with probability at least - 6 it holds that X 2 2M, log(1 (1/) 2 MI, which means that 4K M₁ trials suffice to guarantee that with probability at least
6, the dataset will contain at least Mj samples. Thus,
the proof of Theorem is complete once we make the observation that 2K/ z K² + 1/6² (using the AM-GM inequality) so that the K/8 term is lower order and can be dropped from the final bound.
4 Extension to Natarajan Classes
In this section we extend our result for finite classes given in Theorem I to general, possibly infinite hypothesis classes H with finite Natarajan dimension. The Natarajan dimension is an extension of the VC dimension to the multiclass setting, defined follows:
Definition (Natarajan dimension [22]). The Natarajan dimension of hypothesis class H S X y is the largest integer d for which there exist d points Xi. X and d pairs of distinct labels (y11, .1.2)..... (yd,1. yd,2] E (1y) ) such that all 2 sequences of the form (11, (xd. ya), with y; (yn.y1) are realizable by H.
Note that in the binary case, when {0. 1). the Natarajan dimension reduces to the VC dimension. Our main result in this case effectively replaces the [ term, relevant when H is finite, with the Natarajan dimension dN of H.
Theorem 2. A hypothesis class H X y is PAC learnable with bandit feedback if and only if (i) it has a finite Natarajan dimension, and (ii) there exists K E N such that [(h(x) : h E H)H s K for every E X.
Furthermore, let H x be a hypothesis class of finite Natarajan dimension dy- Then there exists bandit multiclass classification algorithm which outputs a hypothesis h with L. (h)=
inf (h) S E with sample complexity of O(KK* + 1l/EP)dx log(1/6)).
As discussed, this result improves the classical result of Daniely et al. [10], who provided an upper bound on the sample complexity of PAC learning with bandit feedback, given by O(Kdx/6") and left obtaining tighter bounds
open question. In particular, for small target excess loss (E - 0), our bound eliminates the linear dependence on the number of labels K, thereby matching the ((dx/e) bound from the full information setting [22].
Theorem 2 follows directly from the following technical result, which is proven in Appendix B, when put together with Theorem 1.
Proposition 1. Assume that the sample complexity of PAC learning with bandit feedback a finite class of size N over a label-space of size K is at most M(N, K, E, 8), where e, ö are the error and confidence parameters. Then, the sample complexity of learning infinite class H is at most s s+m(S, K, 6/2,6/2).
where
dN In(K) In In(1/8))
s = 0
dN
[
ees (esydv dN k2dN S
S
2
dN
1=0

---

and dN is the Natarajan dimension H.
The proposition is proven by using the first examples to construct a finite discretization of size of the class H, which is (e/2) in H in the sense that every h E H is (e/2)-close to some It' in the discretization. Then, we apply our algorithm for finite classes on this finite discretization. Most of the proof is dedicated to establishing that the discretization is dense and to upper bounding its size. similar result for discretizing binary classes, with the VC dimension replacing the Natarajan dimension, is well known. In the VC case, the proof is based on considering the class of all symmet- ric differences of hypotheses from H and analyzing the VC dimension of that class using standard techniques. In our proof, we follow similar argument, but the analysis of the VC dimension of the symmetric difference class, which remains binary even in the multiclass setting, is more nuanced.
Proof of Theorem 2. For the first part of the theorem, note that Item (i) is clearly necessary for learnability, as finite Natarajan dimension is required even in the case of full information feedback. Item (ii) is also necessary: if there exists a point x such that (h(x) ht H) contains more than K distinct labels, then in the realizable case, the sample complexity with bandit feedback has a lower bound of S2 (K), provided K is sufficiently large constant. This follows by setting the target distribution to assign probability to a single example yx,,,, y), where y is drawn uniformly in advance from K labels in (hxx) h E H). An elementary coupon collector argument yields lower bound of K k/2 indeed, if only m s K/2 examples are drawn, then the learner does not correctly guess the label during training with probability least 1/2. Conditioned this event, the population loss is 1/2 (in fact, 2 R72). leading
lower bound of 1/2 1/2 1/4 the population error.
For sufficiency, note that if Item (ii) holds, the class H effectively reduces to class over K total labels and is therefore learnable when its Natarajan dimension is finite, as follows from [9].
For the second part of the theorem, note that by Theorem 1, we have an upper bound on the sample complexity for PAC learning with bandit feedback over finite classes of size N of
m (N, K, e, 8) 0((K* 1/E²) log(N/0))-
Thus, the proof follows immediately from Proposition I together with the fact that:
S
es 2dN log K + log 8¹
log
s dN
log dx
where s and S are defined in the statement of Proposition 1 (note that log(s) only contributes loga- rithmic terms to the overall bound).
5 Conclusion and Open Problems
In this work, we establish a nearly-optimal sample complexity of (((ooy(K)++1s)) (og((())))) for the bandit multiclass classification problem and design an efficient algorithm achieving this bound. While the dominant term in our sample complexity bound (which depends s) is optimal, our bound exhibits a K additive dependence on the size of the label space. We conjecture that the optimal bound is of the form OK//= 1/ for which matching lower bound can be shown in a straightforward manner. One possible approach to improve the dependence on K is perhaps a more adaptive method which combines maximization of estimated rewards in tandem with lowering the variance of the sampling distribution gradually over time. We leave this as very interesting question for future research.
Acknowledgments
This project has received funding from the European Research Council (ERC) under the Euro- pean Union's Horizon 2020 research and innovation program (grant agreements No. 101078075; 882396). Views and opinions expressed are however those of the author(s) only and do not neces- sarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This project has also received
10

---

funding from the Israel Science Foundation (ISF, grant numbers 2549/19; 3174/23), the Yandex Initiative for Machine Learning at Tel Aviv University, the Tel Aviv University Center for Al and Data Science (TAD), the Len Blavatnik and the Blavatník Family foundation, and from the Adelis Foundation.
Shay Moran is a Robert J. Shillman Fellow; supported by ISF grant 1225/20, by BSF grant 2018385, by Azrieli Faculty Fellowship. by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not nec- essarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] A. Agarwal, D. Hsu, S. Kale, Langford, L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
[2] N. Alon, R. Bassily, and S. M. and. Limits of private learning with access to public data. In M. Wallach, H. Larochelle, Beygelzimer, F. d' A'Alché-Bus Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 10342-10352, 2019. URL https / pttpp/einceee.e.///e/ www.ips.r...... / 2019/hash// /ataa//aaaaaaaaa6767777777777280
www.rraattttaaa.e.... html.
[3] H. Asi, V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Opti- mal rates in 11 geometry. International Conference on Machine Learning, pages 593-403 PMLR, 2021.
[4] Auer, N. Cesa-Bianchi. Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[5] S. Ben-David, N. Cesa-Bianchi, and P. M. Long. Characterizations of learnability for classes of (O...., n} va-vuleed functions. In Proceedings of the fifth annual workshop on Computational learning theory, pages 333-340, 1992.
[6] N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff. characterization of multi- class learnability. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 943-955. IEEE, 2022.
[7] S. Bubeck, N. Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[8] N. Cesa- Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[9] A. Daniely and T. Helbertal. The price of bandit information in multiclass online classification. In Conference on Learning Theory, pages 93-104. PMLR, 2013.
[10] A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207- 232. JMLR Workshop and Conference Proceedings, 2011.
[11] C. Dann, T. Lattimore, and F. Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
[12] M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXiv:1106.233: 2369, 2011.
[13] I.. Erez, A. Cohen, T. Koren, Y. Mansour, and S. Moran. The real price of bandit information in multiclass classification, 2024.

---

[14] C. Fang, J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic eath-integrated differential estimator. Advances neural information processing systems, 31, 2018.
[15] M. Frank, P. Wolfe, et An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-100 1956.
[16] D. Haussler and P. M. Long. A generalization of sauer's lemma. J. Comb. Theory, Ser. A, 71 (2):219-240, 1995.
[17] E. Hazan et al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-32,, 2016.
[18] S. M. Kakade, S. Shalev-Shwartz, and A. Tewari. Efficient bandit algorithms for online mul- ticlass prediction. In Proceedings of the 25th international conference on Machine learning. pages 440-447, 2008.
[19] Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[20] Z. Li, L. Ratliff, K. G. Jamieson, L. Jain, et al. Instance-optimal pac algorithms for contextual bandits, Advances in Neural Information Processing Systems, 35:37590-37603,, 2022.
[21] M. Long. New bounds on the price bandit feedback for bouudee online multiclass learning. Theor. Comput. Sci., 19881159-63.. 2020. doi: 10.10160.TCS..019.111.
[22] B. K. Natarajan. On learning sets and functions. Machine Learning, 4(1):67-97, 1989.
[23] A. Raman, V. Raman, U. Subedi, and A. Tewari. Multiclass online learnability under bandit feedback. arXiv preprint arXiv:2308. 04620, 2023.
[24] O. Shamir. On the complexity of bandit and derivative- -eeea stochastic convex optimization. In Conference Learning Theory, pages 3-24. PMLR, 2013.
[25] L. G. Valiant. A theory of the learnable. Communications of the ACM, 17(11):13341114 1984.
[26] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. In Proc. USSR Acad. Sci., 1968.
[27] M. Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
[28] A. Yurtsever, S. Sra, and V. Cevher. Conditional gradient methods via stochastie path- integrated differential estimator. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Ma- chine Learning Research, pages 7282-7291. PMLR, 09-15 Jun 2019.
[29] A. Yurtsever, S. Sra. and V. Cevher. Conditional gradient methods via stochastic path- integrated differential estimator. In International Conference on Machine Learning, pages 7282-7291. PMLR, 2019.
A Proofs for Section
Proof of Lemma 1. First note that the gradient of d(-) is given by
(1 -1- r),
VO E
W (P)
Thus, using a first-order optimality condition for Px. the following holds that for any P E AN.
Vb((P)) (P- (P-P.)) P.) 2 0,
12

---

which amounts to
- (1 (P PPP) -xxy
S0.
W (Py
or equivalently,
W7 W (P) (Px)
$ 50
W (P+)
which rearranges to the first inequality proven. Letting P be the delta distribution on some h E H, we have proven that
Tx,y
E
(1 7)
$
W7, (P+)
and the second inequality follows since y
Proof of Lemma 2. Assume that É minimizes O up to an additive error of μ. that is, the assumption given in the statement of the lemma. Now, note that for every (x,y) X x M, using the explicit form of ((:x,,) y) and its gradient, holds that:
((P:x,)) ((Pxix,)) vo(Pxix,y) - co(x.y),
where w0z) = - log + 2 - and Rx,y = (K) (Px). Using the lower bound w(z) 2 min - 2)) (1 - } (see Lemma 4 in Appendix A; this is where the seff-concordance of
comes in) we obtain that for all E H.
y²
((P:x.y)- VO(P.i (P-P))
2K
W w
W W7,y
y²
Fx,y (h)
Fx,y (h)
2K
WV
W7, (P+)
Taking expectation of the inequality over (x, y) ~ D while using a first-order optimality condition for Ps with respect to and the fact that [E 2 [.]. we obtain
2 Tx.y (h)
y²
Ex.y (h)
# (PP)
E
2K
W2, (P)
W7 WT,y (P+)
and rearranging we obtain that for all h E H,
Tx,y (h)
2uk² y2
Tx,y W7 (Px)
E
$
+E
W
using Lemma and the form of V&D we obtain the desired bound.
Proof of Lemma 3. In order to invoke Theorem 3 on +(-), we prove that ((:x,, y) satisfies the re- quired Lipschitz and smoothness properties with K/y and B = k2/ /y² Indeed, the gradient of is given by
Fx.y W (P)
Vo(P,x,))
and since (P) 2 y/K and ||rx, s we obtain the required Lipschitz property, that is, [VV((P.x,)) x)ll G. For Lı smoothness, it suffices to show that for any P. Q AN and any
(x,y) E X x it holds that
[V vo(Q,x, B|I Qll
13

---

Indeed.
Fx.y (h)
(x,y
[V - vll =
y) max NET
W7 (P)
W (2)
(2, (P)
W2, (P)W
Fx.y 1x.y-
(1
(P),()
K2 P Ql1
where in the last step we used Hölder's inequality. Now, using Theorem 3, our choice of T' and Mi for which the batch sizes b, defined Theorem satisfy Σ b, S M1, the proof is complete.
Lemma 4, Let wxz))= = log z + 1. It holds that:
w<z) (1- -1-)) 4)²
The first lower bound is relevant,for for s and the second for 1.
Proof. Note that (2) - 1/2 and (1) = 0, hence w(2) fe²(1 11xxddx. When 0 z S 1 can bound 1/x for any $ x 1. Therefore,
(<z)) = (1/1//-11 1)dxxxxxx f (x 1)dr }(( (1-2)
When
the elementary inequality, for any 2 2 1:
)
-
= d
-
dx
to bound
((2)= S:¹ (1 (1-11/) 1/x)dxx (1(( -(000-111)))=-1111333)
B Proof of Proposition 1
Proof of Proposition I. Consider the following learning rule: first sample examples X1, ....... from the population (guess their label arbitrarily). Now for each pattern ((x, yr) y/ which is realiz- able by some function h H, pick representative h H such that h(x,) y for all í Define Hean to be the set of all such representatives. The Sauer-Shelah-Perles Lemma for the Natarajan dimension [16] implies that
Hrinl S.
Now, apply the assumed algorithm on the finite class Hti with error and confidence parameters 8/2, 5/2. Let h denote the hypothesis outputted by the algorithm. Thus, with probability at least 6/2 the excess loss (or regret) of h with respect to Hrin is at most 8/2. A union bound combined with the following lemma imply that with probability at least 8, the excess loss of h with respect to H is most
Lemma 5. With probability at least 1 - 6/2 over the sampling of X the finite class Hesn is an (e/2)-cover for H. That is, for every h H there exists h' Hesn such that the probability that h' (x) * h(x) for random point x drawn from the population is at most e/2.
14

---

Indeed, by union bound, with probability at least 1 ò, both (i) the excess loss of h is at most e/2, and (ii) Hii is an (e/2)-cover for H. Hence, the excess loss of h with respect to the best hypothesis in H is at most e/2 + s/2 E, as required.
Lemma 5 follows from a standard uniform convergence argument. In the case of binary labels K = 2, this lemma known and has been used e.g. in [2]. The general case is derived below using a similar argument like in [2].
Proof of Lemma 5. We need show that with probability least N1),1)..... .... (Ns, Ys) D, for every h E H, there exists h E Hein such that (((x)))-((((x) * (x)) e/2. For convenience, we use the notation d(h, ht) Prix.))-D(h(x) (x)]..
6/2 over
Let = (X)....,Xx) be the sequence of points in the random sample, and for a hypothesis h let h(7) (h(xi)..... h(x)). By construction, for every h H, there exists h Hein such that
(TT)) = h(T). We will show that d(h, ht) s 8/2.
Define the event
E = 3h1, h2 E H: d(hi, h2) 8/2 and (T) hT))
We prove that
2ess
2dx KAdv e
Pr[E] s
(6)
dN
Before we do so, we first show that this suffices to prove the lemma: indeed, d(h, h²) e/2 for some h E H and h' E Hein such that h' h'(T) = hT),, then the event E occurs because Hein C H. Now, via standard manipulation, this bound
most 6/2 for some = 0 dN In(K) ln(1/e) + In(1/0))
e
which yields the desired bound and completes the proof.
It remains to prove (6). To do so, we use standard VC-based uniform convergence bound on the class HA (An,, hn, h2 E H), where
(x) (x) A2
(x)=1(
(x(x) # h2(x),
h1(x) h2(x).
Let GA denote the growth function of Hy: that is, for any number m,
Ga(m)
max (V]VV==)
Halv
where Haly is the set of all restrictions (or projections) V of functions from HA. Note that
2e
2dv
(m(m)
Add
dN
This follows from the fact that for any set V of size we have HHalv & [H|v|?, since every binary vector Haly is determined by pair of functions Hly. Hence,
2e
2dv
GA (m) I max M|v]
Add
V =m
dN
where the last inequality follows from the extended Sauer's Lemma for Natarajan classes applied on H [16].
Now, by invoking a uniform convergence argument, we have
Pr[E] Pr(3h, h2 H d(h,, h2) > e/2 and (T) h2(T)) Pr[3b E HA d(b, s/2 and b(T) = bo(7)] (Here bo is the all-zero vector)
(2x(2s) -.3/4
(double-sample symmetrization argument)
2ess 2dN
2
Add e x/14
dN
15

---

The bound in the third line is non non-triival; it is known as the double-sampic argument which was used by Vapnik and Chervonenkis in their seminal paper [26]. The same argument used virtually all VC-based uniform convergence bounds. This proves inequality (6) and completes the proof of the lemma.
C Stochastic (SPIDER) Frank-Wolff in L1 Norm
In this section we present and analyze the stochastic Frank- Wolfe (FW) method used as a sub- procedure in main algorithm. Crucially, require specific variant of stochastic FW due to Yurtsever et al. [28]. called SPIDER-FW, that employs mini-batching and variance-reduced for stochastic gradient estimation.
SPIDER FW has been shown obtain the optimal 1/e² rate of convergence in a general stochastic setting that involves convex and smooth objective [28]. However, the existing analysis pertain to the Euclidean case, whereas we crucially require an Lı-L, analysis. provide such analysis here with a specialized argument for variance-reduction with respect to the Lı norm. (We note that optimization.)
similar arguments have appeared in [3] the context of differentially-prisen
Setup. The setup for this section is the following. We consider a stochastic optimization problem of the form
minimize
F(w)= E[f
S.t.
W.
where W is convex domain in Rd and the expectation is over drawn from underlying distribu- tion D. In the context this section, we think D as being unknown but assume that i.i.d. samples Z1, 22..... D are readily available.
We further make the following assumptions:
We assume that f convex. ß-smooth and G-Lipschitz (in its first argument) with respect the Li norm over W, that is,
B ||u vll Vz E Z.
fuu, z) & f(v, (v, (u -
and further, that fv, G for all z and W:
We assume that the feasible domain W has L1 diameter & D, that is, ||u l s D for all n. V E W. the algorithmic access to the set W is through a linear optimization oracle (LOO), that given any vector g Rdd computes
LOO(g) argmin g w. weW
C.1 Stochastic FW with SPIDER gradient estimates
The SPIDER FW algorithm is presented in Algorithm 3. The algorithm makes Frank-Woo type updates using "SPIDER" gradient estimates gr, that are computed from the raw stochastic gradients. The SPIDER estimates work mini-batches, but employ low-variance bias correction order to update the estimates without resetting them entirely from round to round, thus saving in the mini- batch sizes. The main result of this section is given in the following theorem. Theorem 3. Algorithm 3 with step sizes T) = 1/tt and batch sizes b, defined
(G/BD)2 ift (Tk)a2li otherwise,
b,
guarantees that, for all 2 and any > 0:
E[F(w,) - F(w")] 25BD2 Vlog d, and Pr F(w;) F(w") 25BD²
dt
log 2 1
Consequently, for convergence to within > 0 with probability at least the algorithu requires (oogB")e) calls LOO and O((G22 + /²D+) log(d/6)) stochastic gradient computations.
16

---

Algorithm Stochastic Frank-Wolfe with SPIDER gradient estimates
Parameters: step sizes {M/ hr batch sizes {b,).- Initialize W1 E W and initial gradient estimate 81
Let тą 2* for k 1,2....
for / = 1.2.... do
Draw fresh b, samples Eh. from D; if r {Tk k21 then Set
b vf(w,.z)
8: b
else
Set
b
81 = 81-1
V (V(W,, (i(W
b1
end if'
Compute = LgO(g:);
Update Wr+1 (1 1/r) W/ 17: end for
C.2 Analysis
To analyze Algorithm 3, we first record generic convergence guarantee for stochastic FW template with gradient estimates. The template operates as follows; starting from an arbitrary initialization Wi E W, for I,..,
get gradient estimator 8 at Wy;
use LOO to compute V, argmin wew 81 W";
(iii) update W,+1 7 n, V..
Lemma 6. Set for all and suppose that the gradient estimates satisfy. for some 0,
11 Ellg, FWw;) $ emp
Then the FW iterations guarantees for all 2 and w W that:
BD2 2cD
E[F(w,) F(w"))))))))))))))))))))))
Similarly, if the estimates satisfy
V121: Pr(lgg- VF c6m)) 56
for some E (0, 1) and c 0, then for any 2 2 and w E W, with probability at least - 16,
(wv))=(ww") 2D 2c&D
Proof. First, using B-smoothness (with respect to |!-Ilı) we have that F(Wrr) F(w.) VF(w;) (Wee1 w.) + f.ll ww wrll?
F(w,) + + VF(,)) (v, w,) BD?
Next, due to the minimality of vr, notice that for any w* E W.
VF(w,) (v, w,) (v, wy) + (VF(w,) 81) (v, w,)
8: (w" -w) +VF(w,)) 8,) (v, w,)
VF((w) -w)- (VF(w, - -g) (v, - w²) F(w") F(w,) + ((())(w,)) -grll...
'The claim of this particular theorem holds in fact for any pair of dual norms, but for consistency, is stated and proved here only for the L
17

---

where the final inequality follows from convexity and the diameter bound. equality and rearranging, we obtain
Plugging into the in-
F(w,+1) F(w" = (1 F(w"") "; gr -g lo=
Taking the expectation of both sides and using our assumption on the gradient estimates, we obtain the following progress inequality, that holds for all r 2 1:
E[F((r+1) F(w") ") $ (1- (1-m))E[F(w) - [(w")] 2 (BD2 2cD)..
We are now ready to prove the main claim by induction on / 2 2. First, plugging / and 7)1 into the progress inequality we have that E[F(w2) F(w")] & {BD2 + 2cD), that is, the claim holds for = 2. For the induction step, let assume that E[F(w,) F(w")] z (BD² 2cD)/t for some 2 2. Then by the progress inequality:
E[F(Wn)) - F(w") ) $ (1 11) E()()) F(w")( (DD +cD)
-
BDd +CD
+ BD + 2cD
21
BDd +cDD
This concludes the proof in expectation. The second claim regarding convergence with high proba- bility follows from the same arguments together with union bound.
The next lemma analyzes the variance-reduced (SPIDER) gradient estimates used in Algorithm 3.
Lemma 7. If we set the batch sizes defined in Eq. (7), then for all and d > O.
12BD vlog d. and Pr l1gr -FF(F))
12BD
E gr - VF(ww)) 2 1
log 56. (8)
1
Proof. The proof relies on standard properties of sub- sub-Gaussian random variables, all of which can be found in, e.g., [27]. Let Z,, (gr F)w,)) be the j'th coordinate of the error at step r. Note that Zr,j is zero-mean. We will show that Zr,; is also sub-Gaussian with parameter maximum of 2d zero-mean sub-Gaussians
6BD /t.
The claim will then follow since llg, VF((;; with parameter o,, which implies Eq. (8).
First, consider of the form = Tk and any coordinate [d]. The claim follows in this from variance reduction by mini-batching: condition on randomness before step 1; since all gradients bounded in L.o norm by G, have by Hoeffding's Lemma that (V (w,, FF(w.)) independent zero-mean G-sub-Gaussians RVs (for 1...., b,). thus their mean Z,,j = (g: (F(w;)); is zero-nn mean sub- sub-Gaussian with parameter = G/vb, = BD/r.
Next, consider any other round such that Tą Tk+1 and any coordinate j [d]. In this case, the claim will follow from accumulation of variance starting from the reset step Tę. Note that due to smoothness,
< 110/ -WA-FF(()---Ww---)))) FF(w:-))) < [V) (ttp::/))--/////....aaa1111111// -VF(w,-
< 26I[w, - -w--lli
s 26Dm
Thus, as before, the random variable - = (g. VF(w,)), (g--1 VF(W,-1)) is zero-mean uubGaaussian with parameter 28Dr,, conditioned on randomness before step By the martingale- summmttio property of uub-Gaussian RVs, we then obtain that Zr,j is zero-mean
18

---

sub-Gausse Gaussian with parameter o,, where
G
4B 12-2
o7
Σ
b
by
x=Tx+1
B D2
+42 D2
5(5 1)2
x=rp+1
B²D
1
188 D2
+
(s-1)²
5²
SmTA+l
B²D
8B2
kk
36B² D² f2
where the final inequality uses тą 1/2. Therefore, deduce that o, s 6BD/t.
We are now ready to prove Theorem 3.
Proof of Theorem 3. The theorem follows directly from Lemmas 6 and 7 and plugging in the spec- ified parameters. The number of steps for convergence to within a given e > O is therefore r = (() (d))). which is also the number of LOO calls. For the total sample com- plexity, observe that the contribution of rounds & (Te is bounded by N ( while the contribution of rounds E J22 is at most ((
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract contains claims that accurately describe the paper's setting and main contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the scope of the main results and compares them to related works.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
20

---

Answer: [Yes]
Justification: The paper contains a complete formal description of the problem setting and proofs for all the theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
21

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This is theoretical paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nipp cc/
cublic/guides//odeSttmmi sosoooooo for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: wwtpcc/pppppgppuiiieeeea
Codeeubm ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This is a theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
22

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard emror of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //nerr/////....// cc cc/public//eiieccccc httpa//ccccchhccccceeeeeeeee
Answer: [Yes]
Justification:
The research conducted in the paper wholly conform with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is purely theoretical paper and is not related to any societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
23

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi tecochhodee com/ dataasts has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
This is theoretical paper.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This is a theoretical paper.
Guidelines:
The answer NA means that the paper does involve crowdsoureing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "spWXQ5CJAQ", "reviewer": "Reviewer_TyCi", "summary": "This paper considers the problem of bandit multi class classification, where the learner only receives the true label if their prediction was correct. That is at time $t$ the learner receives a training sample $x_t$ with unknown label $y_t$. They then predict one of $K$ labels and are told if their prediction is correct. This problem is well studied in the case of regret minimisation. The authors consider a fixed confidence setting where the learner must be PAC$(\\epsilon,\\delta)$ in terms of classification error when compared to the best classifier of some hypothesis class. In addition to receiving samples the learner has access to a ERM oracle on the hypothesis class. \n\nFor the case of a finite hypothesis class the authors provide an algorithm with upper bound of the order $(K^9 + \\epsilon)\\log(\\frac{N}{\\delta})$ where $N$ is the size of the hypothesis class. For hypothesis class of potentially infinite size, but finite Natarajan dimension $d_N$, the authors provide an algorithm with upper bound $(K^9 + \\epsilon)d_N\\log(\\frac{N}{\\delta})$.", "questions": "Do the authors think there is a relation to contextual bandits in the PAC setting e.g. \"Instance-optimal PAC Algorithms for Contextual Bandits\" Li et al. ?\n\nHave the authors considered instance dependent bounds, specifically for a finite hypothesis class?", "limitations": "No concern.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Bandit multi class classification has been studied, mainly in the case of regret minimisation. I think its interesting to consider the problem in such a PAC setting. The question of whether one should pay $K/\\epsilon^2$ under bandit feedback, where one can achieve a rate of $1/\\epsilon^2$ in the full information case, appears to have been a question of interest for some time.", "weaknesses": "As mentioned by the authors, in practical settings the number of labels may be large and the $K^9$ term is significant. While one should keep in mind, that this work appears to be the first to get rates not dependent on $K$ as $\\epsilon \\rightarrow 0$, it would be nice for the authors to discuss how future works could reduce the degree of the poly dependence upon $K$. \n\nIt would also be nice to have more discussion when comparing to contextual bandits. The authors direct the reader to [13] for a more detailed comparison, however from what I can tell they consider solely regret minimisation therein and not a PAC setting.\n\nI believe the paper would benefit from a conclusion and perspectives on future work in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. Please see our comment below to the specified weaknesses and questions.\n\n* “...it would be nice for the authors to discuss how future works could reduce the degree of the poly dependence upon $K$.”\n\nWe believe that the polynomial dependence on $K$ could be reduced, but we are currently not sure how this can be done with our current techniques. One possibility is to employ an adaptive approach which combines estimated reward maximization together with lowering the variance of the sampling distribution over time. We will incorporate a short discussion in the revision, thanks for this suggestion.\n\n* “It would also be nice to have more discussion when comparing to contextual bandits…”\n\nThe vast majority of previous works on contextual bandits study the online objective of regret minimization. Our setting of bandit PAC multiclass classification most closely resembles a contextual bandit setup with a different objective of finding a nearly optimal policy with as few samples as possible. \n\n* “I believe the paper would benefit from a conclusion and perspectives on future work in the main text.”\n\nAgreed - we will add a conclusion section in the revision, incorporating a discussion of the two points you suggested earlier.\n\n* “Do the authors think there is a relation to contextual bandits in the PAC setting e.g. \"Instance-optimal PAC Algorithms for Contextual Bandits\" Li et al. ?”\n\nThank you for bringing this paper into our attention; we will make sure to cite and discuss it in subsequent versions of our paper. The work of Li et al. considers the PAC variant of contextual bandits, where no structural assumptions are made apriori on the reward functions. In this setting, they prove instance dependent sample complexity bounds, from which worst-case bounds of the form $ \\approx K / \\epsilon^2$ can be inferred. To our understanding, there is no direct relation between instance dependent bounds and the single-label classification setting which we consider, as even for the simple case of multi-armed bandits, the standard sample complexity bound of the form $\\sum_i (1 / \\Delta_i)$ does not suffice to obtain an improved result for sparse rewards. To obtain adaptivity to sparsity, the bounds must actually be variance-dependent (rather than gap-dependent), which to our understanding is not addressed in the work of Li et al.\n\n* “Have the authors considered instance dependent bounds, specifically for a finite hypothesis class?”\n\nWe have not previously considered instance-dependent (that is, gap-dependent) sample complexity bounds, as obtaining improved instance-independent bounds, regardless of sparsity, is in itself a highly nontrivial problem. Obtaining such bounds in the multiclass setting is a fantastic question for future research.", "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": "", "extra_scores": {}}, {"review_id": "zinjHgCLXY", "reviewer": "Reviewer_xcWH", "summary": "This paper studies the problem of multiclass classification with bandit feedback, where one only receives information on whether the prediction is correct or incorrect without revealing the actual label. This can be viewed as a very specific case of the well-known contextual multi-armed bandits, where the cost vector contains a single value of $0$ and one's elsewhere. The paper shows that unlike the full-power contextual multi-armed bandits, where the sample complexity scales as $\\Omega(K/\\epsilon^2)$, this restricted version has a sample complexity that scales as $O(K^9+ 1/\\epsilon^2)$. Moreover, their algorithm is computationally efficient given an ERM oracle.", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper addresses a natural and fundamental problem that has attracted much attention in the literature. It introduces several original techniques, such as finding exploration distributions via a log-barrier potential as in (2). I also find the implementation of the Stochastic Frank-Wolfe algorithm using an ERM oracle to be quite interesting. The paper is quite clean and easy to read. I believe it is worth being published in NeurIPS and would have impact within the learning theory community.", "weaknesses": "I do not see any significant weaknesses in the paper. This is a neat, pure theory paper that addresses an interesting problem, at least within the community.\n\nI have a few minor remarks as follows:\n\n1. It appears to me that the $K^9$ dependency mainly arises from the Stochastic Frank-Wolfe algorithm. Can this be improved? Perhaps with a computationally inefficient algorithm?\n\n2. The paper claims to resolve an open problem from Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011). This sounds a bit overselling, in my opinion. After browsing the cited paper, I did not find any statement of this problem, particularly regarding the dependency on $1/\\epsilon$.\n\n3. Can the techniques developed in this paper be used in more general bandit settings to yield improved bounds?\n\n4. The $J_{x,y}(h)$ after Eq (3) must be $r_{x,y}(h)$.\n\n5. It appears to me that your technical approach is quite similar to that of [12]. Can the authors comment on the similarities and differences with that work?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. Please see our comment below to the specified weaknesses and questions.\n\n* “...Can this be improved? Perhaps with a computationally inefficient algorithm?”\n\nWe believe that the sample complexity (specifically, the polynomial dependence on $K$) could be reduced even with a computationally efficient algorithm, but we are not sure how to do that with our current approach.\n\n* “The paper claims to resolve an open problem from Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011)...”\n\nSpecifically, we refer to the paragraph titled “The price of bandit information in the batch model” in section 4 of Daniely et al. (2011), where the authors note that “...it would be interesting to find a more tight characterization of the sample complexity in the bandit setting” while observing that the known multiplicative gap was linear (up to log factors) with the size of the label space. Since our results establish a sample complexity bound that matches (up to log factors) the full information bound for small values of $\\epsilon$, we view our results as a resolution of this question.\n\n* “Can the techniques developed in this paper be used in more general bandit settings to yield improved bounds?”\n\nIn the more general contextual bandit setup where there is no presumed structure on the reward functions, the best sample complexity achievable is of the form $K / \\epsilon^2$ which can be obtained by the trivial algorithm which pulls actions uniformly at random and returns the policy with the best empirical reward. For the online objective of regret minimization, we believe that variants of our approach can be used to obtain the optimal $\\sqrt{KT}$ regret in contextual bandits with a computationally efficient algorithm which is perhaps simpler than the previous approaches of Dudik et al. (2011) and Agrawal et al. (2014), but we did not attempt to work this out in full detail.\n\n* “The $J_{x,y}(h)$ after Eq (3) must be $r_{x,y}(h)$.”\n\nYou are correct, this is a typo that will be fixed in the final version.  Thanks for catching!\n\n* “It appears to me that your technical approach is quite similar to that of [12]. Can the authors comment on the similarities and differences with that work?”\n\nThe work of [12] considers the more general contextual bandit setting with the online objective of regret minimization. Their approach essentially amounts to adaptively computing low-variance sampling distributions which also induce high estimated reward in order to minimize regret over time. Our approach is similar in the sense that we also aim to compute a low-variance sampling distribution with which to estimate rewards of hypotheses, but in the setting we consider there is a special structure on the rewards (namely, a “sparse” one-hot structure) which allows us to compute such a low-variance distribution in time complexity that is polynomial in $K$, and then use it to estimate the rewards of all hypotheses uniformly with only $K / \\epsilon + 1 / \\epsilon^2$ samples. This approach would not work for regret minimization, since the initial phase alone would incur linear regret. We also add that our algorithm makes use of a stochastic Frank-Wolfe procedure in order to efficiently compute the low-variance sampling distribution, an approach which highly differs from the optimization scheme employed in each round in [12].", "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": "", "extra_scores": {}}, {"review_id": "Q210oi9uQs", "reviewer": "Reviewer_m8fV", "summary": "This paper studies bandit multiclass classification in the agnostic PAC setting. For both finite and infinite hypothesis classes, they provide efficient learning algorithms (assuming access to a weighted ERM oracle) whose sample complexity significantly improves upon the previous best known rate of $\\frac{K}{\\epsilon^2}$. As a corollary, they show that unlike the realizable PAC setting, there is no price of bandit feedback in the agnostic PAC setting. The main algorithmic ideas involve  a stochastic optimization technique for efficiently recovering a low-variance exploration distribution over the hypothesis class.", "questions": "- What are the known lower bounds (if any) in the bandit agnostic PAC setting? Is a poly factor of $K$ unavoidable? \n- When $K$ is finite, bandit PAC learnability is equivalent to PAC learnability. Presumably, this is not the case when $K$ is allowed to be infinite. Do you have any insight on what the right characterization of bandit PAC learnability might be in this case?", "limitations": "No limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper is very well written and easy to follow\n- The technical contributions are solid, results are interesting and surprising, and proof techniques are non-trivial. In particular, the fact that there is no price of bandit feedback in the agnostic PAC setting is interesting and not obvious apriori \n- This paper resolves an open question posed by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011)\n- Overall, I feel that this paper is a nice contribution to learning theory that furthers our understanding of bandit multiclass learnability", "weaknesses": "There are no major weakness. That said, I think it would be nice to have:\n\n- a more detailed discussion of the realizable bandit PAC setting in the main text summarizing the known rates and algorithmic techniques\n- some concrete practical scenarios where the bandit agnostic PAC setting is realistic\n- discussion of the assumption of finite label spaces and some thoughts on the right characterization of bandit PAC learnability and sample complexity when $K$ goes to infinity\n- some intuition (beyond the fact that the proof works) about why a separation occurs between the realizable and agnostic settings with regards to the price of bandit feedback", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. Please see our comment below to the specified questions.\n\n* “What are the known lower bounds (if any) in the bandit agnostic PAC setting? Is a poly factor of 𝐾 unavoidable?”\n\nWe can prove a simple lower bound of $K / \\epsilon + 1 / \\epsilon^2$ for bandit multiclass classification as follows: The $1 / \\epsilon^2$ term arises from a standard argument for two labels with probabilities $1/2 + \\epsilon$ and $1/2 - \\epsilon$ (this is the full information lower bound). The $K / \\epsilon$ lower bound holds for an instance with two examples $x_1$ and $x_2$ and $K$ labels, where the probability of sampling $x_1$ is $2 \\epsilon$ and $x_2$ has probability $1-2 \\epsilon$ (each example has a unique unknown correct label). A PAC learner for this instance must correctly predict the label of $x_1$, and to do that it needs at least $\\Omega(K)$ samples of $x_1$, which takes a total of $\\Omega(K / \\epsilon)$ samples. We believe that the polynomial dependence on $K$ in our upper bound can be further improved to decrease the gap from the lower bound described above, but we are unsure how this can be done with our current techniques. \n\n* “...Do you have any insight on what the right characterization of bandit PAC learnability might be in this case?”\n\nGood question. Yes, there is a relatively simple characterization: a class H is learnable if and only if the following holds: (i) it has finite Natarajan dimension, (ii) there is a finite bound $K$ such that for every point $x$, the set {$h(x) : h \\in H$} has at most $K$ distinct labels. Item (i) is clearly necessary, and it is relatively simple to prove that Item (ii) is necessary (it is necessary already for learnability in the realizable-case). For sufficiency, note that if Item (ii) holds then the class $H$ is effectively equivalent to a class over $K$ labels in total and therefore can be learned when its Natarajan dimension is finite, as follows from Theorem 2 in our work. We will add this to the final version of our paper, thanks for pointing this out!", "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": "", "extra_scores": {}}, {"review_id": "tD6uuSEey2", "reviewer": "Reviewer_Wz7L", "summary": "The authors present a novel algorithm to solve the epislon-delta PAC bandit multi-class classification problem. \n\nFor a finite hypothesis class, they give an algorithm with sample complexity O(poly(K) + 1/epsilon^2) that improves on the O(K/epsilon^2). They also similarly show that for a possibly infinite class they can also improve the state-of-the-art.", "questions": "What would be a scenario where this bound performs better than the previous work, although theoretically this is better?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper solves an existing know issue without introduction too many new assumptions. They show the bounds match the optimal rate in the full-information regime. Their use of the Frank-Wolfe algorithm is also interesting.", "weaknesses": "The improvement is shown by moving from O(K/epsilon^2) to O(poly(K) + 1/epsilon^2). The constants here are on the order of K^8 and the time horizon is on the order of K^4. This means that if K is relative large, you mind end up doing worse than the previous bounds which limits the scope of impact of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. Please see our comment below to the specified weaknesses and questions.\n\n* “...This means that if K is relative large, you mind end up doing worse than the previous bounds which limits the scope of impact of this work.”\n\nYou are correct in that our current bounds improve upon previous results in regimes where $K$ is not too large relative to $1 / \\epsilon$. However, we believe that removing polynomial dependencies in $K$ from the main $1/\\epsilon^2$ term is a crucial and significant step towards a comprehensive understanding of the bandit multiclass problem.\n\n* “What would be a scenario where this bound performs better than the previous work, although theoretically this is better?”\n\nSince this is a purely theoretical study, we do not focus on empirical scenarios in which our algorithm may outperform existing ones. Our results formally show that if we aim to find an $\\epsilon$-optimal policy where $\\epsilon \\ll 1 / K^4$, then our suggested algorithm uses considerably less samples than known algorithms which require $K / \\epsilon^2$ samples.", "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": "", "extra_scores": {}}, {"review_id": "aqZbY8n8Hk", "reviewer": "Reviewer_Lcb5", "summary": "This manuscript deals with Multiclass (K labels) PAC Classification a partial monitoring scheme, as introduced by Daniely et al. ('11). The complexity for $(\\epsilon,\\delta)$-PAC of a naive uniform sampling algorithm would be $K/\\epsilon^2 \\log (|\\mathcal{H}| / \\delta) \\big)$ where $\\mathcal{H}$ is a finite family of classifiers. This manuscript introduces a two-step procedure that achieves the nearly optimal bound $(poly(K) + 1/\\epsilon^2)\\log(1/\\delta)$. This bounds is optimal even in the simpler setting with complete feedback. Then, the authors extend the procedure to the infinite class with finite Natarajan dimension.", "questions": "Line 177: What is J_{x,y}?\n\nCould the procedure allows for a better dependency with respect to $K$?", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) The manuscript solves an open question in multi-class learning literature under partial monitoring. Although I am not an expert in the field, I feel that the idea a weighed ERM in the second step of the algorithm and to connect that to the guarantee of the SPIDER gradient estimates for Franck-Wolf algorithm.\n\n2) The manuscript is very well written and the authors manage to convey well the main ideas behind their procedures. The proofs are clear.", "weaknesses": "None.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. Please see our comment below to the specified questions.\n\n* “Line 177: What is J_{x,y}?”\n\nThis is a typo and should be replaced by $r_{x,y}$, this will be fixed in the final version.  Thanks for catching!\n\n* “Could the procedure allows for a better dependency with respect to $K$?”\n\nWe believe that the polynomial dependence on $K$ in the regret bound could be reduced, but we are currently unsure how exactly this can be done and what is the correct optimal dependence.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper gives a new rate of PAC bandit multiclass classification by improving the known O(K/epsilon^2) sample complexity to O( poly(K) + 1/epsilon^2 ). As a consequence, the price of bandit feedback in agnostic PAC multiclass classification (when epsilon is small) is settled, resolving an open problem in (Daniely et al, 2011), which is a constant, in contrast with the realizable setting. The reviewers find the result and algorithmic approach interesting and think this paper should be accepted. 

In the final version, we encourage the authors to incorporate discussions in e.g. lower bounds, and implications to infinite label spaces.
Decision: Accept (poster)