Fast Rates for Bandit PAC Multiclass Classification

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.

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

Questions

Line 177: What is J_{x,y}? Could the procedure allows for a better dependency with respect to $K$?

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

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.

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.

Questions

What would be a scenario where this bound performs better than the previous work, although theoretically this is better?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes

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.

Strengths

- This paper is very well written and easy to follow - 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 - This paper resolves an open question posed by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011) - 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: - 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

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

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

No limitations.

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.

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

See above.

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A

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

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

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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No concern.