- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the optimal expected number of mistakes in realizable multiclass classification with bandit feedback, comparing adaptive adversaries that preserve feedback consistency with oblivious adversaries that commit to a realizable sequence. It constructs a four-function class with adaptive value and oblivious value , and proves that fewer functions cannot separate the two models. For the -point binary cube augmented with distinct constant-label shields, denoted , it derives an exact adaptive-state recursion and proves and , giving a limiting ratio of . Further results bound amplification through specified forms of class union and give necessary conditions for a linear-in- separation. The evidence consists of proofs and finite exact or interval certificates. The worst-case adaptivity ratio as a function of the number of labels remains open.
Critical strengths
S1. A precise answer to the existence question. The four-function witness establishes that adaptivity can increase the optimal mistake bound for genuine concept classes, while the cardinality argument proves that the witness is minimal. Matching learner and adversary arguments make the separation convincing; in particular, the oblivious upper bound covers every fixed target and instance sequence. This answers the existence aspect of the question raised by Filmus et al. (2024).
S2. A substantive analysis beyond the finite witness. Diagnostic invariance reduces the tower games to a two-parameter recursion, and separate adaptive and oblivious analyses establish the exact limiting ratio . The all-negative-path lower bound and threshold learner also identify the logarithmic correction on the oblivious side. These results explain the behavior of an explicit growing family rather than relying only on small numerical examples.
Critical weaknesses
No critical weakness. The following concerns are minor.
W1. Some quantitative bounds remain loose. The composition framework has limited quantitative precision. Remark 5.6 (p. 8) explains that its multiplicative caps for nontrivial atoms do not rule out ratios between and . Remark E.1 (pp. 20–21) gives a concrete example where the localization-rank bound charges an additional , while the actual additional cost is only . These acknowledged limitations restrict how precisely the framework characterizes composition costs. Separately, Section 4.2 (p. 6) leaves the tightness of the adaptive remainder unresolved. This limits the precision beyond the leading term without weakening the exact limiting ratio .
W2. A notation change interrupts the central example. Section 3 (p. 4) names the hypotheses , then uses and in its explanation and table. The renaming and subroutines are explained in Appendix B.1 (p. 13), but consulting the appendix is necessary to follow this part of the main-text example.
Questions for authors
-
Composition bounds (W1): What is the main source of slack in the localization-rank bound for the Hamming-cover example of Remark E.1?
-
Future-direction interpretation (W1): How do you interpret the finite-range excess doubling ratios reported in Section 4.2? Although they do not establish an asymptotic order, do they motivate a conjecture about the growth of ?
4 comments
Response (2/3): how the open problem is solved
Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.
How the upper and lower bounds are obtained. In a concept class, every function is fixed in advance on the whole domain. An adaptive adversary may still decide, as the game unfolds, which function it is following, but every label it declares correct must be supported by some function consistent with all feedback so far. Both bounds rest on the same harmonic-sum mechanism, used once by the learner and once by the adversary; this is why the answer is logarithmic.
Upper bound: adaptivity costs at most a factor of about .
- Measuring what remains to be learned. An oblivious adversary can force two kinds of cost: searching for the correct label among the feasible ones, and resolving binary splits of the class (does the target take label at instance ?). We combine both into one potential, which never exceeds .
- Paying for each mistake. In every round, the learner chooses its prediction distribution so that, whichever feasible label the adversary then declares correct, the expected mistake is at most times the expected drop of the potential (inequality (9)). Summing over the rounds, the total expected number of mistakes is at most times the initial potential, which gives .
- Where comes from. A label whose correct guess lowers the potential a lot needs only a small probability, roughly inversely proportional to that drop. The search cost keeps too many labels from having small drops. Leaving out the smallest drop, the smallest of the others add up to at least about , much as an oblivious search reaches the th label only after about mistakes. A label that makes little progress when guessed correctly makes substantial progress when guessed wrongly, and the proof uses this as well. Comparing the drops with the sequence then gives the factor in the cost.
Lower bound: a factor of order cannot be avoided.
- The construction. We build one finite class from blocks of functions, called worlds. All worlds share a set of top instances, where a correct prediction identifies the world, and each world then continues on its own tail class. On the top instances, heavy worlds take all binary patterns of two private labels, and light worlds take one constant label.
- Keeping every fixed target cheap. Against a fixed target, a learner first searches for the target's world, trying heavy labels for a bounded number of rounds and then the light worlds in a fixed order, and then learns its tail. Light worlds that come later in this order receive tails that are cheaper by exactly the extra search cost, and a heavy target is found before the light scan except with small probability. So every fixed target costs at most the same budget, which bounds .
- Keeping many targets alive. An adaptive adversary need not commit to a target. While it forces mistakes among the heavy worlds, it keeps many light worlds feasible.
- Why the learner cannot protect all of them. During the search on the top instances, suppose that every feasible label led to an adaptive cost below the bound the construction maintains at that stage. Then each light label would claim a share of the learner's probability, set by weighing the mistake on a miss against the cheaper tail after a hit; this share is roughly of order , where is the target ratio and is the number of mistakes an oblivious search makes before reaching that label. With enough light labels these shares add up to more than one, so they cannot all be met: some feasible label still forces the bound, and the adversary declares it. Once the adversary's surplus is used up, a surviving heavy world's tail carries the bound.
- From the mechanism to the constant . Summing over the light labels gives about , so keeping enough light worlds multiplies the number of labels by about . In our parameter choice, the heavy part contributes a further factor of about , since it uses about that many worlds to supply the adaptive gain. Hence about labels suffice, up to factors polynomial in (Theorem 5.1), and nesting the construction on the same labels attains ratio ; inverting gives .
Response (3/3): W1, W2, Q1 and Q2
We are grateful for the positive assessment of the paper, and we thank the reviewer for the thoughtful comments on the quantitative bounds and the central example, as well as for the two careful questions.
Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.
W1 (loose quantitative bounds). We agree with these observations: the composition bounds leave room for sharper constants, and the tower remainder is not yet determined. These bounds are not needed for the proof of Theorem 2.1 (Appendix A), and the growth question they bear on is now settled by Theorem 2.1. In detail:
- The multiplicative composition bounds discussed in Remark J.6 (Remark 5.6 of the submitted version) are unchanged: when some layer is nontrivial, each of them is at least , so they limit growth but do not determine the constants of small separations.
- For the localization-rank bound (Remark E.1, now Remark J.8), the revised remark identifies two sources of slack; see Q1.
- The order of the remainder for the towers is still open. It concerns the tower family only and is recorded as a direction for future work at the end of Appendix I.3 and in Section 7.
W2 (notation change in the central example). Thank you for this helpful observation. The main text now presents the four-function class only by its value pairs (Section 6), so no renaming occurs there. In Appendix H.1 (p. 51), the paragraph that contains the table opens with the renaming and its correspondence to the original names: and if the first point played is , and and if it is . The subroutines Pair and Follow are defined in the same paragraph.
Q1 (source of slack in the localization-rank bound). Two effects add up, and the first one accounts for the factor . Theorem J.5 charges for localizing and then adds the full value of a layer, but in the two-layer Hamming cover these costs overlap: the coordinates fixed while localizing also count toward that layer's cost. Fair labels on fresh coordinates keep the version space in neither layer for rounds, so every learner makes at least expected mistakes before localizing, already a factor of order above the true surcharge , where (Theorem J.7). Second, the rank itself is large: a valid rank must decrease after every correct prediction at an informative point while it is positive, although such feedback costs nothing, and a history that confirms predictions of each label on fresh coordinates leaves the version space in neither layer, so every valid rank is at least . This costs a further constant factor. Remark J.8 now states both effects, and we thank the reviewer for prompting this clarification.
Q2 (the finite-range doubling ratios). This is an interesting question. In our view, the ratios do not yet support a conjecture. For the excess satisfies (base-2 logarithms of these ratios: about 0.36, 0.35 and 0.34). An excess would make the ratios approach ; the observed values are smaller and still decreasing, so they do not determine the order of . Since the trend has not stabilized, we do not state a conjecture; the revised version records the comparison with at the end of Appendix I.3 (p. 56). We agree that the growth of is a natural question; as noted under W1, it concerns the tower family only, and we see it as a direction for future work.
Correspondence with the submitted version. To make it easy to compare the two versions, the items discussed in this review appear in the revised version as follows; the general comment contains a reading guide and the full table.
| Submitted version | Revised version |
|---|---|
| Section 3 and Appendix B.1 (four-function example) | Section 6 and Appendix H.1 |
| Theorems 4.1–4.4 (tower family) | Theorems I.1, I.4, I.5, I.6 |
| Section 4.2 (asymptotics, doubling ratios) | Appendices I.3–I.5 (ratios at the end of I.3.2) |
| Remark 5.6 | Remark J.6 |
| Remark E.1 | Remark J.8 |
Thank you again for the kind words about the witness and the tower analysis, and for the careful questions; we enjoyed thinking about them. We hope Theorem 2.1 answers the open question noted in the review, and we would be glad to clarify anything further.
Thank you for the response and revised manuscript. I keep my positive rating: 4.
To the AC: Given how substantially the paper has changed from the original submission (26 to 68 pages), I don't have enough time to carefully check the added content.
Response (1/3): the open problem is closed
Thank you very much for the careful and review, and in particular for the close reading of the four-function witness and the tower analysis. As the summary of the review notes, the worst-case adaptivity ratio as a function of the number of labels was left open; we have now resolved this question.
Below, "the submitted version" means the paper as submitted at the deadline and "the revised version" the PDF we uploaded for the discussion; numbers refer to the revised version unless stated otherwise.
The revised version completely resolves the open problem of Filmus et al. (NeurIPS 2024): in its default weakly realizable model, the worst-case price of adaptivity for concept classes is Θ(logk), where k is the number of labels.
The open problem reads in full (Filmus et al., Section 4.1): "The price of adaptivity for concept classes. Our proof of Theorem E.1 uses pattern classes. Can we prove it using only concept classes, similarly to Theorem F.1? If not, what is the price of adaptivity when learning concept classes?" The revised version answers both questions with two new results. Section 3 shows that for every concept class, finite or infinite, the optimal adaptive mistake bound A(H) is at most (1+o(1))lnk times the optimal oblivious bound B(H), so the Ω(k) separation of their Theorem E.1 cannot be achieved with concept classes. Sections 4 and 5 construct explicit finite concept classes with ratio (2/3−o(1))lnk; for instance, ratios at least 2, 3 and 4 are reached with 6364, 71922 and 628217 labels (p. 9 and Appendix E.6). Hence the price for concept classes is Θ(logk) (Theorem 2.1). As with the linear price for pattern classes, the price is thus determined up to constant factors. The exact constant in front of lnk, between 2/3 and 1, remains open and is a natural direction for future work.
The table below sums up, for the three questions behind this open problem, where the submitted version stood and what the revised version proves.
The revised version keeps all theorems, propositions and examples of the submitted version, together with their proofs, techniques and certificates; in particular, the four-function witness and the tower analysis are kept in full (Section 6 and Appendices H–I). In addition, the two new results resolve the question the submitted version left open (its Open Problem 6.1): how the price grows with k. Together with what the submitted version established, that concept classes can separate at all, with exact minimal examples, they completely resolve the open problem of Filmus et al.
The localization results of the submitted version, which the review discusses under W1, fit this picture: nesting classes on disjoint label blocks keeps the ratio at most C0+2 at every finite depth when the innermost classes have ratio at most C0 (Theorem J.2; Theorem 5.2 of the submitted version), and the construction of Sections 4–5 is not subject to this bound, since its tails reuse one label alphabet.