Fast Rates for Bandit PAC Multiclass Classification

Authors: liad  erez
alon  cohen
tomer  koren
yishay  mansour
shay  moran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 14:50:23

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}$.

Main paper: 
 introduction: 
 Multiclass classification is a fundamental learning problem in which a learner is tasked with classifying 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 or not the prediction was correct. As a concrete example, consider a the task of classifying images, say, from the ImageNet dataset, with the number of labels 𝐾 being several thousands. After the learner predicts a label for a particular image, both the image and the prediction are shown to a human rater who is asked if the prediction is correct or 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 in this context, and on char-acterizing the achievable regret rates in terms of 𝐾, |H | and the number of prediction rounds 𝑇. For instance, Auer et al. [4] show that for any finite H one can obtain a regret bound of 𝑂 ( √︁ 𝐾𝑇 log |H |), by casting the classification problem as a (contextual) 𝐾-armed bandit problem. Daniely and Helbertal [9] demonstrate that the dependence on log |H | can be replaced by the Littlestone dimension of H , 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 { √︁ 𝐾𝑇 log |H |}, |H | + √ 𝑇), 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 a training set of i.i.d. examples along with their true labels, where the number of samples required to learn an 𝜀-optimal hypothesis was shown to be 𝑂 ((1/𝜀 2 ) log(|H |/𝛿)) for finite classes [22, 5, 10, 6] . In 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 or 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 approach 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 𝑂 ((𝐾/𝜀 2 ) log |H |) sample complexity which appears to be optimal due to the bandit feedback. Furthermore, the simple underlying algorithm 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 a generic 𝐾-armed (contextual) bandit problem and neglects a 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. 1The following questions thus remain:(1) What is the optimal sample complexity of the bandit multiclass setting? In particular, can one improve upon the prototypical 𝐾/𝜀 2 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?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 𝑂 ((poly(𝐾)+ 1/𝜀 2 ) log(|𝐻|/𝛿)) for producing an 𝜀-optimal classifier with probability at least 1 -𝛿; see Theorem 1 in Section 3. Further, our algorithm is a proper learner and can be implemented efficiently provided a (weighted) ERM oracle for the class H . In terms of the leading dependence on 𝜀, this bound significantly improves over the previously mentioned 𝑂 (𝐾/𝜀 2 ) 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 𝑑, we establish a generalized sample complexity bound of 𝑂 ((poly(𝐾) + 1/𝜀 2 )𝑑 log(1/𝛿)); see Theorem 2 in Section 4. This improves over the previous 𝑂 (𝐾 𝑑/𝜀 2 ) 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 𝜀.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 𝜀 → 0;namely, that the ratio between the optimal sample complexity rates in the bandit and the fullinformation settings is Θ(1), and not Θ(𝐾) as one might expect. Indeed, the latter is often the multiplicative price of bandit information in a 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 a 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-batch conversions of regret bounds very often give sharp sample complexity rates in the i.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 hypothesis classes an online-to-batch conversion of the optimal regret rate results with sample complexity Θ(𝐾/𝜀2 ) [13] , whereas the rate we establish here is 𝑂 (1/𝜀 2 + poly(𝐾)). 2 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 𝑂 (𝐾) obtained by simple uniform exploration of labels. We show that through minimization of a stochastic objective akin to 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.Bandit multiclass classification. In agnostic online multiclass classification with bandit feedback, regret bounds of the form 𝑂 ( √︁ 𝐾𝑇 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Θ(min { √︁ 𝐾𝑇 log |H |, |H | + √ 𝑇 })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 𝐾 can be replaced with a refined quantity which encapsulates the effective number of labels. Additional refinements in the realizable setting include the Bandit Littlestone dimension which provides a characterization of the optimal mistake bound for deterministic learning algorithms [10] .Contextual bandits. The PAC objective of the bandit multiclass classification problem can be seen as a 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 Ω(𝐾/𝜀 2 ) are known [4] , with regret upper bounds of the form 𝑂 ( √ 𝐾𝑇) 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 a bit more detail, in the works of [12, 1] , one of the main technical ideas is to compute a distribution over policies which induces a reward estimator whose variance is bounded, uniformly over the policies, by 𝑂 (𝐾) (it is actually nontrivial to show that such a distribution even exists). Our approach involves similar ideas in 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 𝑂 (1) rather than 𝑂 (𝐾). Li et al. [20] also consider the PAC objective for contextual bandits and establish a gap dependent sample complexity bound which never exceeds 𝐾/𝜀 2 , but to our understanding does not imply an improved bound for sparse rewards (or single-label classification), as even for the multiarmed 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.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 in 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 as motivation as long as it is clear that these goals are not attained by the paper. 
problem setup: 
 Bandit multiclass classification. We consider a learning setting in which a learner is tasked with classifying objects from a set of examples X with a single label from a set of 𝐾 possible labels Y = {1, . . . , 𝐾 }. A stochastic multiclass classification instance is specified by a hypothesis class H ⊆ {X → Y} and a joint distribution D over example-label pairs over X × Y. We focus on finite hypothesis classes and denote 𝑁 ≜ |H |. In the bandit setup, the learner interacts with the environment in an iterative manner according to the following protocol, over 𝑖 = 1, 2, . . .:(i) The environment generates a pair (𝑥 𝑖 , 𝑦 𝑖 ) ∼ D and the example 𝑥 𝑖 is revealed to the learner; (ii) The learner predicts a label 𝑦 𝑖 ∈ Y; (iii) The learner observes whether or not the classification of 𝑥 𝑖 is correct, namely 𝟙{ 𝑦 𝑖 = 𝑦 𝑖 }. 3Agnostic PAC model. In the PAC version of the problem, given parameters 𝜀, 𝛿 > 0 the goal of the learner is to produce a hypothesis ĥ : X → Y, 4 such that with probability at least 1 -𝛿 (over the randomness of the environment as well as any internal randomization of the algorithm):𝐿 D ( ĥ) -𝐿 D (ℎ ★ ) ≤ 𝜀,where here 𝐿 D (ℎ) ≜ Pr[ℎ(𝑥) ≠ 𝑦] is the expected zero-one loss of ℎ with respect to (𝑥, 𝑦) ∼ D, and ℎ ★ ≜ argmin ℎ∈ H 𝐿 D (ℎ) is the best hypothesis in H . That is, the learner needs to identify a hypothesis which is 𝜀-optimal in H with respect to the expected zero-one loss, with probability at least 1 -𝛿. In this model, the learner's performance is measured in terms of sample complexity, which is the number of interaction rounds with the environment as a function of 𝜀, 𝛿 required for satisfying the guarantee stated above.Weighted ERM oracle. For our computational results, we will assume a weighted empirical risk minimization (ERM) oracle access to the hypothesis class H . In more detail, we assume access to an oracle, denoted O H , defined as follows: given a sequence of examples, labels and weights (𝑥 1 , 𝑦 1 , 𝛼 1 ), . . . , (𝑥 𝑡 , 𝑦 𝑡 , 𝛼 𝑡 ) ∈ X × Y × ℝ as input, the oracle O H returnsEQUATIONWe remark that this is a 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 O H takes 𝑂 (1) time.Additional notation. We denote by Δ 𝑁 ≜ 𝑃 ∈ ℝ 𝑁 + | 𝑁 𝑖=1 𝑃 𝑖 = 1 the 𝑁-dimensional simplex which corresponds to the set of all probability distributions over H . Given 𝑃 ∈ Δ 𝑁 and ℎ ∈ H we use the notation 𝑃(ℎ) to denote the probability assigned to ℎ by the probability vector 𝑃. Given an example-label pair (𝑥, 𝑦) ∈ X × Y we define the binary vector 𝑟 𝑥,𝑦 ∈ {0, 1} 𝑁 by𝑟 𝑥,𝑦 (ℎ) ≜ 𝟙{ℎ(𝑥) = 𝑦} ∀ℎ ∈ H , that is, 𝑟 𝑥,𝑦 (ℎ)is the zero-one reward of the hypothesis ℎ on the pair (𝑥, 𝑦). Given 𝑃 ∈ Δ 𝑁 and (𝑥, 𝑦) ∈ X × Y we denote the probability of choosing the label 𝑦 when sampling a hypothesis from 𝑃 on 𝑥 by𝑊 𝑥,𝑦 (𝑃) ≜ ∑︁ ℎ=H 𝑃(ℎ)𝟙{ℎ(𝑥) = 𝑦} = 𝑃 • 𝑟 𝑥,𝑦 ,and for 𝛾 ∈ (0, 1) we let 𝑊 𝛾 𝑥,𝑦 (𝑃) ≜ (1 -𝛾)𝑊 𝑥,𝑦 (𝑃) + 𝛾/𝐾, which corresponds to mixing the distribution 𝑊 𝑥,𝑦 (𝑃) with a uniform distribution over labels with weight factor 𝛾. To analyze Algorithm 3, we first record a generic convergence guarantee for stochastic FW template with gradient estimates. The template operates as follows; starting from an arbitrary initialization 𝑤 1 ∈ 𝑊, for 𝑡 = 1, ..., 𝑇:(i) get gradient estimator 𝑔 𝑡 at 𝑤 𝑡 ;(ii) use LOO to compute 𝑣 𝑡 = argmin 𝑤 ∈𝑊 𝑔 𝑡 • 𝑤;(iii) update 𝑤 𝑡+1 = (1 -𝜂 𝑡 )𝑤 𝑡 + 𝜂 𝑡 𝑣 𝑡 . Lemma 6. Set 𝜂 𝑡 = 1/𝑡 for all 𝑡 and suppose that the gradient estimates satisfy, for some 𝑐 > 0, 5∀ 𝑡 ≥ 1 :𝔼∥𝑔 𝑡 -∇𝐹 (𝑤 𝑡 ) ∥ ∞ ≤ 𝑐𝜂 𝑡 .Then the FW iterations guarantees for all 𝑡 ≥ 2 and 𝑤 * ∈ 𝑊 that:𝔼[𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * )] ≤ 𝛽𝐷 2 + 2𝑐𝐷 𝑡 .Similarly, if the estimates satisfy∀ 𝑡 ≥ 1 : Pr(∥𝑔 𝑡 -∇𝐹 (𝑤 𝑡 ) ∥ ∞ > 𝑐 𝛿 𝜂 𝑡 ) ≤ 𝛿.for some 𝛿 ∈ (0, 1) and 𝑐 𝛿 > 0, then for any 𝑡 ≥ 2 and 𝑤 * ∈ 𝑊, with probability at least 1 -𝑡𝛿,𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * ) ≤ 𝛽𝐷 2 + 2𝑐 𝛿 𝐷 𝑡 .Proof. First, using 𝛽-smoothness (with respect to ∥•∥ 1 ) we have that𝐹 (𝑤 𝑡+1 ) ≤ 𝐹 (𝑤 𝑡 ) + ∇𝐹 (𝑤 𝑡 ) • (𝑤 𝑡+1 -𝑤 𝑡 ) + 1 2 𝛽∥𝑤 𝑡+1 -𝑤 𝑡 ∥ 2 1 ≤ 𝐹 (𝑤 𝑡 ) + 𝜂 𝑡 ∇𝐹 (𝑤 𝑡 ) • (𝑣 𝑡 -𝑤 𝑡 ) + 1 2 𝜂 2 𝑡 𝛽𝐷 2 .Next, due to the minimality of 𝑣 𝑡 , notice that for any 𝑤 * ∈ 𝑊,∇𝐹 (𝑤 𝑡 ) • (𝑣 𝑡 -𝑤 𝑡 ) = 𝑔 𝑡 • (𝑣 𝑡 -𝑤 𝑡 ) + (∇𝐹 (𝑤 𝑡 ) -𝑔 𝑡 ) • (𝑣 𝑡 -𝑤 𝑡 ) ≤ 𝑔 𝑡 • (𝑤 * -𝑤 𝑡 ) + (∇𝐹 (𝑤 𝑡 ) -𝑔 𝑡 ) • (𝑣 𝑡 -𝑤 𝑡 ) = ∇𝐹 (𝑤 𝑡 ) • (𝑤 * -𝑤 𝑡 ) + (∇𝐹 (𝑤 𝑡 ) -𝑔 𝑡 ) • (𝑣 𝑡 -𝑤 * ) ≤ 𝐹 (𝑤 * ) -𝐹 (𝑤 𝑡 ) + 𝐷 ∥∇𝐹 (𝑤 𝑡 ) -𝑔 𝑡 ∥ ∞ ,where the final inequality follows from convexity and the diameter bound. Plugging into the inequality and rearranging, we obtain𝐹 (𝑤 𝑡+1 ) -𝐹 (𝑤 * ) ≤ (1 -𝜂 𝑡 ) (𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * )) + 𝜂 𝑡 𝐷 ∥∇𝐹 (𝑤 𝑡 ) -𝑔 𝑡 ∥ ∞ + 1 2 𝜂 2 𝑡 𝛽𝐷 2 .Taking the expectation of both sides and using our assumption on the gradient estimates, we obtain the following progress inequality, that holds for all 𝑡 ≥ 1:𝔼[𝐹 (𝑤 𝑡+1 ) -𝐹 (𝑤 * )] ≤ (1 -𝜂 𝑡 )𝔼[𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * )] + 1 2 𝜂 2 𝑡 (𝛽𝐷 2 + 2𝑐𝐷).We are now ready to prove the main claim by induction on 𝑡 ≥ 2. First, plugging 𝑡 = 1 and 𝜂 1 = 1 into the progress inequality we have that 𝔼[𝐹 (𝑤 2 ) -𝐹 (𝑤 * )] ≤ 1 2 (𝛽𝐷 2 + 2𝑐𝐷), that is, the claim holds for 𝑡 = 2. For the induction step, let us assume that 𝔼[𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * )] ≤ (𝛽𝐷 2 + 2𝑐𝐷)/𝑡 for some 𝑡 ≥ 2. Then by the progress inequality:𝔼[𝐹 (𝑤 𝑡+1 ) -𝐹 * )] ≤ (1 -𝜂 𝑡 )𝔼[𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * )] + 1 2 𝜂 2 𝑡 (𝛽𝐷 2 + 2𝑐𝐷) = 1 - 1 𝑡 𝛽𝐷 2 + 2𝑐𝐷 𝑡 + 𝛽𝐷 2 + 2𝑐𝐷 2𝑡 2 ≤ 𝛽𝐷 2 + 2𝑐𝐷 𝑡 .This concludes the proof in expectation. The second claim regarding convergence with high probability follows from the same arguments together with a union bound. □The next lemma analyzes the variance-reduced (SPIDER) gradient estimates used in Algorithm 3.Lemma 7. If we set the batch sizes as defined in Eq. (7) , then for all 𝑡 and 𝛿 > 0: Proof. The proof relies on standard properties of sub-Gaussian random variables, all of which can be found in, e.g., [27] . Let 𝑍 𝑡 , 𝑗 = (𝑔 𝑡 -∇𝐹 (𝑤 𝑡 )) 𝑗 be the 𝑗'th coordinate of the error at step 𝑡. Note that 𝑍 𝑡 , 𝑗 is zero-mean. We will show that 𝑍 𝑡 , 𝑗 is also sub-Gaussian with parameter 𝜎 𝑡 = 6𝛽𝐷/𝑡. The claim will then follow since ∥𝑔 𝑡 -∇𝐹 (𝑤 𝑡 ) ∥ ∞ is a maximum of 2𝑑 zero-mean sub-Gaussians with parameter 𝜎 𝑡 , which implies Eq. ( 8).First ) -∇𝐹 (𝑤 𝑡 )) 𝑗 -(∇ 𝑓 (𝑤 𝑡 -1 , 𝑧 𝑖 ) -∇𝐹 (𝑤 𝑡 -1 )) 𝑗 | ≤ |(∇ 𝑓 (𝑤 𝑡 , 𝑧 𝑖 ) -∇ 𝑓 (𝑤 𝑡 -1 , 𝑧 𝑖 )) 𝑗 | + |(∇𝐹 (𝑤 𝑡 ) -∇𝐹 (𝑤 𝑡 -1 )) 𝑗 | ≤ ∥∇ 𝑓 (𝑤 𝑡 , 𝑧 𝑖 ) -∇ 𝑓 (𝑤 𝑡 -1 , 𝑧 𝑖 ) ∥ ∞ + ∥∇𝐹 (𝑤 𝑡 ) -∇𝐹 (𝑤 𝑡 -1 ) ∥ ∞ ≤ 2𝛽∥𝑤 𝑡 -𝑤 𝑡 -1 ∥ 1 ≤ 2𝛽𝐷𝜂 𝑡 -1 .Thus, as before, the random variable 𝑍 𝑡 , 𝑗 -𝑍 𝑡 -1, 𝑗 = (𝑔 𝑡 -∇𝐹 (𝑤 𝑡 )) 𝑗 -(𝑔 𝑡 -1 -∇𝐹 (𝑤 𝑡 -1 )) 𝑗 is a zero-mean sub-Gaussian with parameter 2𝛽𝐷𝜂 𝑡 -1 / √ 𝑏 𝑡 , conditioned on randomness before step 𝑡. By the martingale-summation property of sub-Gaussian RVs, we then obtain that 𝑍 𝑡 , 𝑗 is zero-mean sub-Gaussian with parameter 𝜎 𝑡 , where𝜎 2 𝑡 = 𝐺 2 𝑏 𝜏 𝑘 + 𝑡 ∑︁ 𝑠=𝜏 𝑘 +1 4𝛽 2 𝐷 2 𝜂 2 𝑠-1 𝑏 𝑠 = 𝛽 2 𝐷 2 𝜏 2 𝑘 + 4𝛽 2 𝐷 2 𝑡 ∑︁ 𝑠=𝜏 𝑘 +1 1 𝑠(𝑠 -1) 2 ≤ 𝛽 2 𝐷 2 𝜏 2 𝑘 + 8𝛽 2 𝐷 2 𝑡 ∑︁ 𝑠=𝜏 𝑘 +1 1 (𝑠 -1) 2 - 1 𝑠 2 ≤ 𝛽 2 𝐷 2 𝜏 2 𝑘 + 8𝛽 2 𝐷 2 𝜏 2 𝑘 ≤ 36𝛽 2 𝐷 2𝑡 2 where the final inequality uses 𝜏 𝑘 ≥ 𝑡/2. Therefore, we deduce that 𝜎 𝑡 ≤ 6𝛽𝐷/𝑡. □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 specified parameters. The number of steps for convergence to within a given 𝜖 > 0 is therefore 𝑡 = 𝑂 ((𝛽𝐷 2 /𝜖) √︁ log(𝑑/𝛿)), which is also the number of LOO calls. For the total sample complexity, observe that the contribution of rounds 𝑡 ∉ {𝜏 𝑘 } 𝑘 ≥1 is bounded by 𝑡 𝑠=1 𝑠 = 𝑂 (𝑡 2 ), while the contribution of rounds 𝑡 ∈ {𝜏 𝑘 } 𝑘 ≥1 is at most 𝑂 ((𝐺/𝛽𝐷) 2 𝑡 2 ). □NeurIPS Paper ChecklistQuestion: 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 no 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 a 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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 approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithm and analysis: 
 In this section we present and analyze our main contribution: an efficient bandit multiclass classification algorithm, detailed in Algorithm 1, which will be shown to satisfy the following agnostic PAC guarantee. √︁ log(𝑁/𝛿)) rounds with step sizes 𝜂 𝑡 = 1/𝑡 and batch sizes 𝑏 𝑡 = (𝛾/2𝐾) 2 𝑡 2 for 𝑡 ∈ {2 𝑘 -1} 𝑘 ≥1 and 𝑏 𝑡 = 𝑡 otherwise; then with probability at least 1-𝛿 Algorithm 1 outputs ĥ ∈ H with 𝐿 D ( ĥ) -𝐿 D (ℎ ★ ) ≤ 𝜀, using a total sample complexity of𝑂 𝐾 9 + 1 𝜀 2 log 𝑁 𝛿 .Furthermore, Algorithm 1 makes a total number of 𝑂 𝐾 4 √︁ log(𝑁/𝛿) calls to the weighted ERM oracle O H , and runs in total time polynomial in 𝐾, 1/𝜀 and log(𝑁/𝛿).Algorithm 1 operates in two phases. In the first phase, we construct a dataset 𝑆 of 𝑀 1 = poly(𝐾) log(𝑁/𝛿) 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 a stochastic optimization scheme which finds an approximate solution to the following stochastic optimization problem:EQUATIONs.t. 𝑃 ∈ Δ 𝑁 .The approximate solution, P ∈ Δ 𝑁 will be shown to satisfy certain low-variance properties, which will allow us to repeatedly sample from P for 𝑀 2 = 𝑂 𝐾/𝜀 + 1/𝜀 2 log(𝑁/𝛿) and estimate the loss of hypotheses in H rounds such that we are guaranteed to find an approximately optimal policy with high probability. We again emphasize that our algorithm is a proper learner in the sense that the returned hypothesis ĥ is a member of the underlying class H .We next outline the details and intuition behind the implementation of Algorithm 1.Low-variance exploration distribution. The main goal of the first phase of Algorithm 1 is to compute an exploration distribution P ∈ Δ 𝑁 with the property that with probability at least 1 -𝛿/2, the following holds:EQUATIONwhere 𝛾 is some predefined parameter and 𝐶 is an absolute constant, which crucially does not depend on 𝐾. 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𝑟 𝑥,𝑦 (ℎ)𝟙{𝑦 = ŷ} 𝑊 𝛾 𝑥,𝑦 ( P), which is an unbiased estimator of the expected reward of the hypothesis ℎ, that is, of 𝟙{ℎ(𝑥) = 𝑦} if the label ŷ is chosen according to an hypothesis drawn from P and (𝑥, 𝑦) 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 to make use of variance-sensitive concentration bounds, namely Bernstein'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 computing such a low-variance exploration distribution P is via approximately solving the stochastic convex optimization problem defined in Eq. ( 2). The reason for the choice of Φ as a convex potential to be minimized is the fact that its gradient is, up to a constant factor, given by ∀ℎ ∈ H :EQUATIONso that finding a low-variance exploration distribution amounts to computing P ∈ Δ 𝑁 for which ∇Φ( P) is bounded in 𝐿 ∞ norm. Indeed, we show that the optimal solution to the optimization problem given in Eq. ( 2) satisfies such a property. This, together with the properties of Φ as a selfconcordant function allows finding such P by approximately minimizing Φ over the simplex: the self-concordance of Φ acts as a "restricted strong convexity" property, which roughly implies that approximate minimizers of Φ must also have small (low norm) gradients.Efficient optimization via Stochastic Frank-Wolfe. In order to compute an approximate minimizer of the convex potential Φ defined in Eq. ( 2), we employ a stochastic optimization procedure, formally described in Algorithm 2, which is based on a stochastic version of the Frank-Wolfe (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 𝑁-dimensional space, with runtime essentially independent of 𝑁, by exploiting the weighted ERM oracle at our disposal. Furthermore, the FW algorithm, when performed over the simplex, generates iterates 𝑃 1 , 𝑃 2 , . . . such that 𝑃 𝑡 is supported on at most 𝑡 coordinates (provided that 𝑃 1 is initialized at an arbitrary vertex of the simplex), allowing us to maintain a succinct representation of the FW iterates-again, essentially independently of the ambient dimension 𝑁. 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 𝐿 2 -norm, our objective of interest, namely Φ, is not smooth in this classical sense, however it is smooth with respect to the 𝐿 1 norm. Therefore, we crucially rely on a different analysis of the FW algorithm with SPIDER gradient estimates, presented in Appendix C, which accommodates smoothness with respect to the 𝐿 1 norm.Final exploration phase. The second phase of Algorithm 1 is more straightforward, where we repeatedly predict labels using i.i.d. samples from a 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 𝑀 2 = 𝑂 𝐾/𝜀 + 1/𝜀 2 log(𝑁/𝛿) samples suffice in order to ultimately output an hypothesis ĥ ∈ H being 𝜀-optimal with probability at least 1 -𝛿/2. With this in hand, the desired PAC guarantee follows by a union bound over the failure probabilities of the two phases of the algorithm.Next, we present the stochastic FW procedure used in our algorithm as subprocedure; see Algorithm 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 a linear optimization oracle over the simplex denoted by LOO, that given an input 𝑔 ∈ ℝ 𝑁 computes LOO(𝑔) = argmin 𝑄∈Δ 𝑁 𝑄 • 𝑔. As we will show later, each of the calls Algorithm 2 makes to LOO can be implemented by a 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 𝐿 2 smoothness of the objective [29] , and here we provide an analysis with respect to 𝐿 1 smoothness being crucial in our case. We defer further details about SPIDER FW and its analysis to Appendix C. We now turn to formally prove Theorem 1. For clarity of notation, we henceforth use 𝔼[•] instead of 𝔼 ( 𝑥,𝑦)∼D [•] to denote an expectation of a random variable with respect to D. We begin this section by analyzing the first phase of Algorithm 1. 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 a constant in 𝐿 ∞ norm. Lemma 1. Suppose 𝛾 ≤ 1 2 and let 𝑃 ★ ∈ argmin 𝑃∈Δ 𝑁 Φ(𝑃), where Φ : Δ 𝑁 → ℝ + was defined in Eq. (2). Then for any 𝑃 ∈ Δ 𝑁 we haveEQUATIONIn particular, letting 𝑃 be the delta distribution on some ℎ ∈ H :𝔼 𝑟 𝑥,𝑦 (ℎ) 𝑊 𝛾 𝑥,𝑦 (𝑃 ★ ) ≤ 2.The next key lemma, whose proof is also in Appendix A ensures that a sufficiently approximate minimizer of Φ is also a point in which the gradient Φ is bounded in 𝐿 ∞ -norm, establishing the property given in Eq. (3).Lemma 2. Suppose 𝛾 ≤ 1 2 and assume that for all 𝑃 ★ ∈ Δ 𝑁 the following holds for P which was computed in phase 1 of Algorithm 1:Φ( P) -Φ(𝑃 ★ ) ≤ 𝜇.Then,∥∇Φ( P) ∥ ∞ ≤ 2 + √︄ 2𝜇𝐾 2 𝛾 2 .In particular, setting 𝜇 = 𝛾 2 /2𝐾 2 gives ∥∇Φ( P) ∥ ∞ ≤ 3.The fact that the property given in Eq. ( 3) can be guaranteed with high probability using as few as 𝑀 1 = Θ(poly(𝐾) log(𝑁/𝛿)) 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).Lemma 3. Suppose 𝛾 ≤ 1 2 . If 𝑀 1 = 58000 𝐾 8 /𝛾 8 log(16𝑁/𝛿) and 𝑇 = 240 𝐾 4 /𝛾 4 √︁ log(16𝑁/𝛿), then with probability at least 1 -𝛿/2, for all 𝑃 ★ ∈ Δ 𝑁 it holds thatΦ( P) -Φ(𝑃 ★ ) ≤ 𝛾 2 2𝐾 2 .We are now in position to prove Theorem 1 by analyzing the second phase of Algorithm 1. 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 in order to compute an 𝜀-optimal hypothesis in high probability using only ≈ 𝐾/𝜀 + 1/𝜀 2 samples.Proof of Theorem 1. We first show that we can in fact use Algorithm 2 as specified in the theorem's statement. That is, we prove that the calls to the linear optimization oracle, denoted by LOO in Algorithm 2 can be implemented using the weighted ERM oracle O H . Indeed, we first note that for any 𝑔 ∈ ℝ 𝑁 it holds that LOO(𝑔) = argmin 𝑃∈Δ 𝑁 {𝑃 • 𝑔} = argmin ℎ∈ H {𝑔 ℎ },≤ 3. Fix some ℎ ∈ H . For 𝑖 ∈ {1, . . . , 𝑀 2 } define 𝑋 𝑖 (ℎ) = 𝑟 𝑥 𝑖 ,𝑦 𝑖 (ℎ)𝟙{ 𝑦 𝑖 = ŷ𝑖 } 𝑊 𝛾 𝑥 𝑖 ,𝑦 𝑖 ( P) . Note that 𝔼[𝑋 𝑖 (ℎ)] =Pr[ℎ(𝑥) = 𝑦] and that 𝑋 1 (ℎ), . . . , 𝑋 𝑀 2 (ℎ) are i.i.d. Additionally, by the guarantee of phase 1:Var[𝑋 𝑖 (ℎ)] ≤ 𝔼[𝑋 𝑖 (ℎ) 2 ] = 𝔼 𝑟 𝑥 𝑖 ,𝑦 𝑖 (ℎ)𝟙{𝑦 𝑖 = ŷ𝑖 } (𝑊 𝛾 𝑥 𝑖 ,𝑦 𝑖 ( P)) 2 = 𝔼 𝑟 𝑥,𝑦 (ℎ) 𝑊 𝛾 𝑥,𝑦 ( P) ≤ 3. Define X (ℎ) = 1 𝑀 2 𝑀 2𝑖=1 𝑋 𝑖 (ℎ), and note that by the form of the weighted ERM oracle, ĥ = argmax ℎ∈ H X (ℎ). Therefore, by an application of Bernstein's inequality (see e.g. [19] , page 86) and a union bound, we have with probability at least 1 -𝛿/2 for all ℎ ∈ H :| X (ℎ) -Pr[ℎ(𝑥) = 𝑦] | ≤ √︄ 6 log(2𝑁/𝛿) 𝑀 2 + 2𝐾 log(2𝑁/𝛿) 𝛾𝑀 2 .Hence for ĥ, with probability at least 1 -𝛿/2 we have𝐿 D ( ĥ) -𝐿 D (ℎ ★ ) = Pr[ ĥ(𝑥) ≠ 𝑦] -Pr[ℎ ★ (𝑥) ≠ 𝑦] = Pr[ℎ ★ (𝑥) = 𝑦] -Pr[ ĥ(𝑥) = 𝑦] ≤ Pr[ℎ ★ (𝑥) = 𝑦] -X (ℎ ★ ) + X ( ĥ) -Pr[ ĥ(𝑥) = 𝑦] ≤ √︄ 36 log(2𝑁/𝛿) 𝑀 2 + 4𝐾 log(2𝑁/𝛿) 𝛾𝑀 2 .Choosing 𝑀 2 ≥ max{144 log(2𝑁/𝛿)/𝜀 2 , 8𝐾 log(2𝑁/𝛿)/(𝛾𝜀)} gives 𝐿 D ( ĥ) -𝐿 D (ℎ ★ ) ≤ 𝜀. Thus, using Lemma 2 and Lemma 3, we are only left with proving that with high probability, collecting 𝑀 1 samples for 𝑆 takes at most 𝑂 (𝐾 9 log(𝑁/𝛿)) 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 𝑋 ∼ Bin(4𝐾 𝑀 1 , 1/𝐾) then with probability at least 1 -𝛿 it holds that 𝑋 ≥ 2𝑀 1log(1/𝛿) ≥ 𝑀 1 , which means that 4𝐾 𝑀 1 trials suffice to guarantee that with probability at least 1 -𝛿, the dataset 𝑆 will contain at least 𝑀 1 samples. Thus, the proof of Theorem 1 is complete once we make the observation that 2𝐾/𝜀 ≤ 𝐾 2 + 1/𝜀 2 (using the AM-GM inequality) so that the 𝐾/𝜀 term is of lower order and can be dropped from the final bound. □Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Justification: This is a theoretical paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 as well as 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 make it into the paper). 
extension to natarajan classes: 
 In this section we extend our result for finite classes given in Theorem 1 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 as follows: Definition 1 (Natarajan dimension [22] ). The Natarajan dimension of a hypothesis class H ⊆ X → Y is the largest integer 𝑑 for which there exist 𝑑 points 𝑥 1 , . . . , 𝑥 𝑑 ∈ X and 𝑑 pairs of distinct labels{𝑦 1,1 , 𝑦 1,2 }, . . . , {𝑦 𝑑,1 , 𝑦 𝑑,2 } ∈ | Y | 2such that all 2 𝑑 sequences of the form (𝑥 1 , 𝑦 1 ), . . . , (𝑥 𝑑 , 𝑦 𝑑 ), with 𝑦 𝑖 ∈ {𝑦 𝑖1 , 𝑦 𝑖2 }, are realizable by H .Note that in the binary case, when Y = {0, 1}, the Natarajan dimension reduces to the VC dimension. Our main result in this case effectively replaces the log|H | term, relevant when H is finite, with the Natarajan dimension 𝑑 𝑁 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 𝐾 ∈ ℕ such that |{ℎ(𝑥) : ℎ ∈ H }| ≤ 𝐾 for every 𝑥 ∈ X.Furthermore, let H : X → Y be a hypothesis class of finite Natarajan dimension 𝑑 𝑁 . Then there exists a bandit multiclass classification algorithm which outputs a hypothesis ĥ with 𝐿 D ( ĥ)inf ℎ∈ H 𝐿 D (ℎ) ≤ 𝜀 with a sample complexity of 𝑂 ((𝐾 9 + 1/𝜀 2 )𝑑 𝑁 log(1/𝛿)).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 𝑂 (𝐾 𝑑 𝑁 /𝜀 2 ), and left obtaining tighter bounds as an open question. In particular, for small target excess loss (𝜀 → 0), our bound eliminates the linear dependence on the number of labels 𝐾, thereby matching the Θ(𝑑 𝑁 /𝜀 2 ) 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 𝑁 over a label-space of size 𝐾 is at most 𝑚(𝑁, 𝐾, 𝜀, 𝛿), where 𝜖, 𝛿 are the error and confidence parameters. Then, the sample complexity of learning an infinite class H is at most 𝑠 + 𝑚(𝑆, 𝐾, 𝜖/2, 𝛿/2), where𝑠 := 𝑂 𝑑 𝑁 ln(𝐾) ln(1/𝜖) + ln(1/𝛿) 𝜖 , 𝑆 := 𝑑 𝑁 ∑︁ 𝑖=0 𝑠 𝑖 𝐾 2 𝑖 ≤ 𝑒 𝑠 𝑑 𝑁 𝑑 𝑁 𝐾 2𝑑 𝑁 ,and 𝑑 𝑁 is the Natarajan dimension of H .The proposition is proven by using the first 𝑠 examples to construct a finite discretization of size 𝑆 of the class H , which is (𝜖/2)-dense in H in the sense that every ℎ ∈ H is (𝜖/2)-close to some ℎ ′ 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. A 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 symmetric differences of hypotheses from H and analyzing the VC dimension of that class using standard techniques. In our proof, we follow a 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. ), leading to a lower bound of 1/2 • 1/2 = 1/4 on the population error. For sufficiency, note that if Item (ii) holds, the class H effectively reduces to a class over 𝐾 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 𝑁 of 𝑚(𝑁, 𝐾, 𝜀, 𝛿) = 𝑂 (𝐾 9 + 1/𝜀 2 ) log(𝑁/𝛿) .Thus, the proof follows immediately from Proposition 1 together with the fact that:log 𝑆 𝛿 ≤ 𝑑 𝑁 log 𝑒𝑠 𝑑 𝑁 + 2𝑑 𝑁 log 𝐾 + log 1 𝛿 ,where 𝑠 and 𝑆 are defined in the statement of Proposition 1 (note that log(𝑠) only contributes logarithmic terms to the overall bound).In this work, we establish a nearly-optimal sample complexity of 𝑂 ((poly(𝐾)+1/𝜀 2 ) log(|𝐻|/𝛿)) 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 on 𝜀) is optimal, our bound exhibits a 𝐾 9 additive dependence on the size of the label space. We conjecture that the optimal bound is of the form 𝑂 𝐾/𝜀 + 1/𝜀 2 , for which a matching lower bound can be shown in a straightforward manner. One possible approach to improve the dependence on 𝐾 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 a very interesting question for future research. ≤ 0, which rearranges to the first inequality to be proven. Letting 𝑃 be the delta distribution on some ℎ ∈ H , we have proven that ≤ 𝐾 2 𝛾 2 ∥𝑃 -𝑄∥ 1 ,where in the last step we used Hölder's inequality. Now, using Theorem 3, our choice of 𝑇 and 𝑀 1 for which the batch sizes 𝑏 𝑡 defined in Theorem 3 satisfy 𝑇 𝑡=1 𝑏 𝑡 ≤ 𝑀 1 , the proof is complete. □ Lemma 4. Let 𝜔(𝑧) =log 𝑧 + 𝑧 -1. It holds that:𝜔(𝑧) ≥ min 1 2 (1 -𝑧) 2 , 𝑧 2 1 -1 𝑧 2 .The first lower bound is relevant for 𝑧 ≤ 1 and the second for 𝑧 ≥ 1.Proof. Note that 𝜔 ′ (𝑧) = 1 -1/𝑧 and 𝜔(1) = 0, hence 𝜔(𝑧) = ∫ 𝑧 1 (1 -1/𝑥)𝑑𝑥. When 0 < 𝑧 ≤ 1 we can bound 1 -1/𝑥 ≤ 1 -𝑥 for any 𝑧 ≤ 𝑥 ≤ 1. Therefore, 𝜔(𝑧) = ∫ 𝑧 1 (1/𝑥 -1)𝑑𝑥 ≥ ∫ 𝑧 1 (𝑥 -1)𝑑𝑥 = 1 2 (1 -𝑧) 2 .When 𝑧 ≥ 1, we can use the elementary inequality, for any 𝑧 ≥ 𝑥 ≥ 1:1 - 1 𝑥 ≥ 1 2 1 - 1 𝑥 2 = 𝑑 𝑑𝑥 𝑥 2 1 - 1 𝑥 2 to bound 𝜔(𝑧) = ∫ 𝑧 1 (1 -1/𝑥)𝑑𝑥 ≥ ∫ 𝑧 1 1 2 (1 -1/𝑥 2 ) 𝑑𝑥 = 𝑧 2 (1 -1/𝑧) 2 .Proof of Proposition 1. Consider the following learning rule: first sample 𝑠 examples 𝑥 1 , . . . , 𝑥 𝑠 from the population (guess their label arbitrarily). Now for each pattern {(𝑥 𝑖 , 𝑦 𝑖 )} 𝑠 𝑖=1 which is realizable by some function ℎ ∈ H , pick a representative ℎ ∈ H such that ℎ(𝑥 𝑖 ) = 𝑦 𝑖 for all 𝑖 ≤ 𝑠. Define H fin to be the set of all such representatives. The Sauer-Shelah-Perles Lemma for the Natarajan dimension [16] implies that |H fin | ≤ 𝑆.Now, apply the assumed algorithm on the finite class H fin with error and confidence parameters 𝜀/2, 𝛿/2. Let ĥ denote the hypothesis outputted by the algorithm. Thus, with probability at least 𝛿/2 the excess loss (or regret) of ĥ with respect to H fin is at most 𝜀/2. A union bound combined with the following lemma imply that with probability at least 𝛿, the excess loss of ĥ with respect to H is at most 𝜀.Lemma 5. With probability at least 1 -𝛿/2 over the sampling of 𝑥 1 , . . . 𝑥 𝑠 , the finite class H fin is an (𝜀/2)-cover for H . That is, for every ℎ ∈ H there exists ℎ ′ ∈ H fin such that the probability that ℎ ′ (𝑥) ≠ ℎ(𝑥) for a random point 𝑥 drawn from the population is at most 𝜀/2.Indeed, by a union bound, with probability at least 1 -𝛿, both (i) the excess loss of ĥ is at most 𝜖/2, and (ii) H fin is an (𝜀/2)-cover for H . Hence, the excess loss of ĥ with respect to the best hypothesis in H is at most 𝜀/2 + 𝜀/2 = 𝜀, as required. □ Lemma 5 follows from a standard uniform convergence argument. In the case of binary labels 𝐾 = 2, this lemma is 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 to show that with probability at least 1 -𝛿/2 over (𝑥 1 , 𝑦 1 ), . . . , (𝑥 𝑠 , 𝑦 𝑠 ) ∼ D, for every ℎ ∈ H , there exists ℎ ′ ∈ H fin such that Pr ( 𝑥,𝑦)∼D [ℎ(𝑥) ≠ ℎ ′ (𝑥)] ≤ 𝜀/2. For convenience, we use the notation 𝑑 (ℎ, ℎ ′ ) := Pr ( 𝑥,𝑦)∼D [ℎ(𝑥) ≠ ℎ ′ (𝑥)].Let 𝑇 = (𝑥 1 , . . . , 𝑥 𝑠 ) be the sequence of points in the random sample, and for a hypothesis ℎ let ℎ(𝑇) = (ℎ(𝑥 1 ), . . . , ℎ(𝑥 𝑠 )). By construction, for every ℎ ∈ H , there exists ℎ ′ ∈ H fin such that ℎ ′ (𝑇) = ℎ(𝑇). We will show that 𝑑 (ℎ, ℎ ′ ) ≤ 𝜀/2. Define the eventEQUATION)Before we do so, we first show that this suffices to prove the lemma: indeed, if 𝑑 (ℎ, ℎ ′ ) > 𝜖/2 for some ℎ ∈ H and ℎ ′ ∈ H fin such that ℎ ′ (𝑇) = ℎ(𝑇), then the event 𝐸 occurs because H fin ⊆ H . Now, via standard manipulation, this bound is at most 𝛿/2 for some𝑠 = 𝑂 𝑑 𝑁 ln(𝐾) ln(1/𝜖) + ln(1/𝛿) 𝜖 ,which yields the desired bound and completes the proof.It remains to prove (6) . To do so, we use a standard VC-based uniform convergence bound on the classH Δ = {Δ ℎ 1 ,ℎ 2 : ℎ 1 , ℎ 2 ∈ H }, where Δ ℎ 1 ,ℎ 2 (𝑥) = 1 ℎ 1 (𝑥) ≠ ℎ 2 (𝑥), 0 ℎ 1 (𝑥) = ℎ 2 (𝑥).Let G Δ denote the growth function of H Δ ; that is, for any number 𝑚,G Δ (𝑚) = max {𝑉:|𝑉 |=𝑚} H Δ | 𝑉 ,where H Δ | 𝑉 is the set of all restrictions (or projections) on 𝑉 of functions from H Δ . Note thatG Δ (𝑚) ≤ 2𝑒 𝑠 𝑑 𝑁 2𝑑 𝑁 𝐾 4𝑑 𝑁 .This follows from the fact that for any set 𝑉 of size 𝑚, we have|H Δ | 𝑉 | ≤ |H | 𝑉 | 2 , since every binary vector in H Δ | 𝑉 is determined by a pair of functions in H | 𝑉 . Hence, G Δ (𝑚) ≤ max |𝑉 |=𝑚 H | 𝑉 2 ≤ 2𝑒 𝑠 𝑑 𝑁 2𝑑 𝑁 𝐾 4𝑑 𝑁 ,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 havePr[𝐸] = Pr[∃ℎ 1 , ℎ 2 ∈ H : 𝑑 (ℎ 1 , ℎ 2 ) > 𝜀/2 and ℎ 1 (𝑇) = ℎ 2 (𝑇)] = Pr[∃𝑏 ∈ H Δ : 𝑑 (𝑏, 𝑏 0 ) ≥ 𝜀/2 and 𝑏(𝑇) = 𝑏 0 (𝑇)](Here 𝑏 0 is the all-zero vector)≤ 2G Δ (2 𝑠) 𝑒 -𝜀,𝑠/4 (double-sample symmetrization argument) ≤ 2 2𝑒 𝑠 𝑑 𝑁 2𝑑 𝑁 𝐾 4𝑑 𝑁 𝑒 -𝜖 𝑠/4 .The bound in the third line is non-trivial; it is known as the double-sample argument which was used by Vapnik and Chervonenkis in their seminal paper [26] . The same argument is used in virtually all VC-based uniform convergence bounds. This proves inequality (6) and completes the proof of the lemma. □In this section we present and analyze the stochastic Frank-Wolfe (FW) method used as a subprocedure in our main algorithm. Crucially, we require a 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 to obtain the optimal 1/𝜀 2 rate of convergence in a general stochastic setting that involves a convex and smooth objective [28] . However, the existing analysis pertain to the Euclidean case, whereas we crucially require an 𝐿 1 -𝐿 ∞ analysis. We provide such analysis here with a specialized argument for variance-reduction with respect to the 𝐿 1 norm. (We note that similar arguments have appeared in [3] in the context of differentially-private optimization.)Setup. The setup for this section is the following. We consider a stochastic optimization problem of the form minimize𝐹 (𝑤) = 𝔼[ 𝑓 (𝑤, 𝑧)] s.t.𝑤 ∈ 𝑊, where 𝑊 is a convex domain in ℝ 𝑑 and the expectation is over 𝑧 drawn from an underlying distribution D. In the context of this section, we think of D as being unknown but assume that i.i.d. samples 𝑧 1 , 𝑧 2 , . . . ∼ D are readily available. We further make the following assumptions:• We assume that 𝑓 convex, 𝛽-smooth and 𝐺-Lipschitz (in its first argument) with respect to the 𝐿 1 norm over 𝑊, that is,𝑓 (𝑢, 𝑧) ≤ 𝑓 (𝑣, 𝑧) + ∇ 𝑓 (𝑣, 𝑧) • (𝑢 -𝑣) + 𝛽 2 ∥𝑢 -𝑣∥ 21 ∀𝑧 ∈ Z, ∀𝑢, 𝑣 ∈ 𝑊, and further, that ∥∇ 𝑓 (𝑣, 𝑧)∥ ∞ ≤ 𝐺 for all 𝑧 ∈ 𝑍 and 𝑣 ∈ W; • We assume that the feasible domain 𝑊 has 𝐿 1 diameter ≤ 𝐷, that is, ∥𝑢 -𝑣∥ 1 ≤ 𝐷 for all 𝑢, 𝑣 ∈ 𝑊. the algorithmic access to the set 𝑊 is through a linear optimization oracle (LOO), that given any vector 𝑔 ∈ ℝ 𝑑 computes LOO(𝑔) = argmin 𝑤 ∈𝑊 𝑔 • 𝑤.The SPIDER FW algorithm is presented in Algorithm 3. The algorithm makes Frank-Wolfe type updates using "SPIDER" gradient estimates 𝑔 𝑡 , that are computed from the raw stochastic gradients.The SPIDER estimates work in mini-batches, but employ low-variance bias correction in order to update the estimates without resetting them entirely from round to round, thus saving in the minibatch sizes.The main result of this section is given in the following theorem. Theorem 3. Algorithm 3 with step sizes 𝜂 𝑡 = 1/𝑡 and batch sizes 𝑏 𝑡 defined asEQUATIONguarantees that, for all 𝑡 ≥ 2 and any 𝛿 > 0:𝔼[𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * )] ≤ 25𝛽𝐷 2 𝑡 √︁ log 𝑑 , and Pr 𝐹 (𝑤 𝑡 ) -𝐹 (𝑤 * ) ≤ 25𝛽𝐷 2 𝑡 √︂ log 𝑑𝑡 𝛿 ≥ 1 -𝛿 .Consequently, for convergence to within 𝜖 > 0 with probability at least 1 -𝛿, the algorithm requires 𝑂 ((𝛽𝐷𝑔 𝑡 = 𝑔 𝑡 -1 + 1 𝑏 𝑡 𝑏 𝑡 ∑︁ 𝑖=1 (∇ 𝑓 (𝑤 𝑡 , 𝑧 𝑖 ) -∇ 𝑓 (𝑤 𝑡 -1 , 𝑧 𝑖 )); end if Compute 𝑣 𝑡 = LOO(𝑔 𝑡 ); Update 𝑤 𝑡+1 = (1 -𝜂 𝑡 )𝑤 𝑡 + 𝜂 𝑡 𝑣 𝑡 ; end for C. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a purely theoretical paper and is not related to any societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This is a theoretical paper.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: This is a theoretical paper.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).We note that Daniely and Helbertal[9] do provide a stochastic lower bound construction, but it pertains to multi-label multiclass rather to the standard single-label setting we consider here.A similar separation has been observed before, e.g., in the context of general online/stochastic convex optimization[24].Note that in the bandit setting, the learner does not observe the true label 𝑦 𝑖 directly.In this model we allow for improper learners, that is, the output hypothesis may not be a member of H ; we emphasize, however, that our main algorithm below is a proper learner, namely it returns a hypothesis ĥ ∈ H .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 𝐿 1 -𝐿 ∞ case. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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. 

For 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})$.
strength_weakness: strength_weakness: 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$. 

It 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.

I believe the paper would benefit from a conclusion and perspectives on future work in the main text.
questions: 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. ?

Have the authors considered instance dependent bounds, specifically for a finite hypothesis class?
limitations: limitations: No concern.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

I have a few minor remarks as follows:

1. 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?

2. 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$.

3. Can the techniques developed in this paper be used in more general bandit settings to yield improved bounds?

4. The $J_{x,y}(h)$ after Eq (3) must be $r_{x,y}(h)$.

5. 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?
questions: questions: See above.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: There are no major weakness. That said, I think it would be nice to have:

- a more detailed discussion of the realizable bandit PAC setting in the main text summarizing the known rates and algorithmic techniques
- some concrete practical scenarios where the bandit agnostic PAC setting is realistic
- 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
- 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
questions: questions: - What are the known lower bounds (if any) in the bandit agnostic PAC setting? Is a poly factor of $K$ unavoidable? 
- 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: limitations: No limitations.
paper_summary: paper_summary: The authors present a novel algorithm to solve the epislon-delta PAC bandit multi-class classification problem. 

For 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.
strength_weakness: strength_weakness: 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.
questions: questions: What would be a scenario where this bound performs better than the previous work, although theoretically this is better?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: None.
questions: questions: Line 177: What is J_{x,y}?

Could the procedure allows for a better dependency with respect to $K$?
limitations: limitations: Yes.

Comments: title: Response to rebuttal
comment: Thank you for your response. I maintain my rating of accept
Thank you for the response. I maintain my current rating, favoring the acceptance of the paper.
Thanks for the response.
Thank you for your response.