PaperlayerView exact revision on arXiv

Source-linked AI summary

Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

Guangjian Zhang

arXiv:2609.29694v1cs.LG

TL;DR

Prior work left open whether every finite-BDS class admits a uniform sample bound of the proposed form, and its published lower-bound theorem is challenged. This paper develops revised proof tools and an anchored-dimension upper-bound approach. It refutes the lower bound and shows that dimension profiles alone do not fully characterize fine-grained complexity.

  • Problem

    HMMS left open whether every class with finite BDS admits a uniform O((BDS + log(1/δ))/ε) sample bound, and the published lower-bound theorem is challenged.

    Source: §1 · p. 2, §1.1 · p. 2

  • Method

    The paper uses a conditional-fiber equality-query lemma and fiberization, including a positive-feedback step that bounds the surviving class's BDS by aBDS.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Results

    Explicit examples with BDS = K −1 contradict Ω(BDS /ε), and the cited theorem's proof has two independent gaps.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The triples (aBDS, BDS, R) are not complete statistics for fine-grained bandit complexity; a confidence direct-sum profile is missing.

    Source: §8 · p. 21

    A general theory of the δ →1 boundary, agnostic bandit feedback, and sharper per-class constants remain open.

    Source: §8 · p. 22

Abstract

from arXiv · show

We study realizable multiclass PAC learning with bandit feedback: the learner observes an i.i.d. instance, predicts one of $K$ labels, and learns only whether the prediction was correct. Hanneke, Meng, Moran, and Shaeiri (arXiv:2605.25678) characterized the optimal sample complexity via the bandit DS dimension $\mathrm{BDS}$ up to logarithmic factors, and asked whether every class admits sample complexity $O((\mathrm{BDS}+\log(1/\delta))/\epsilon)$. First, we show that the published lower bound $\Omega((\mathrm{BDS}+\log(1/\delta))/\epsilon)$ is incorrect as stated: we exhibit explicit classes with $\mathrm{BDS}=K-1$ whose sample complexity is exponentially smaller, and locate two independent gaps in its proof. We repair the lower-bound theory around a new anchored dimension $\mathrm{aBDS}\le\mathrm{BDS}$, proving a constant-free three-part lower bound. On the upper-bound side we remove the ambient label count $K$ entirely, proving $O((B\log^3 B+B\log(1/\delta))/\epsilon)$ for $B=\mathrm{BDS}$, plus a constant-confidence bound via a new fiberization lemma; for two natural families we determine the sample complexity up to constant factors. Finally, we answer the open question in the negative under its uniform-constant reading, and show the failure is intrinsic: for an explicit affine multiplexer class we establish the full confidence profile $\Theta((n\min{n,\log(1/\delta)}+\log(1/\delta))/\epsilon)$, a confidence direct-sum regime where a multiplicative $\log(1/\delta)$ cost is information-theoretically necessary, followed by a rank-saturation phase transition. Two classes with identical dimension profiles can have polynomially different sample complexities, so no characterization by these dimensions alone is accurate to polylogarithmic factors. We also show these results are consistent with additive-confidence list-PAC guarantees via the ListCascade bridge.

1 Introduction

This paper revisits bandit multiclass PAC sample complexity, correcting a published lower bound and refining the dimension-based picture. It gives K-free upper bounds, exact rates for two families, and a confidence direct-sum result for affine multiplexers.

1.1 Main results

  • The published lower bound fails: explicit classes with BDS = K −1 contradict Ω(BDS /ε), and its proof has two independent gaps.The gaps are discarding a witness coordinate and assuming arbitrary learners predict uniformly among neighboring labels.Source: §1.1 · p. 2
  • The anchored dimension aBDS refines BDS for lower bounds, and the paper gives a corrected, fully quantified lower bound.aBDS is defined through pseudo-box witnesses with a zero-multiplicity anchor.Source: §1.1 · p. 2
  • A positive feedback lets fiberization bound the surviving class's BDS by the original class's aBDS, yielding an anchored-dimension upper bound at constant confidence.The paper also sharpens the cascade to remove dependence on the ambient label count K.Source: §1.1 · p. 3
  • For classes with aBDS = 0, the sample complexity is exact at every (ε, δ); private-shell anchored-block classes have a log-free rate.The constant-class and anchored-class examples appear among the benchmark families; the stated PAB rate applies for 0 < ε ≤ 1/16 and 0 < δ ≤ 1/4.Source: §1.1 · pp. 2–3
  • For affine multiplexers, confidence cost is multiplicative when ln(1/δ) ≲ n, then the profile transitions to Θ((n² + L)/ε) near ln(1/δ) ≈ n.The multiplicative regime is necessary because evidence against distinct macro-groups cannot be shared.Source: §1.1 · pp. 3–4

1.2 Techniques

  • Three tools support the results: conditional-fiber equality queries, a conservative online-to-PAC conversion, and fiberization.The equality-query reduction handles arbitrary adaptive randomized learners without relying on witness symmetry; the conversion requires monotone pointwise mistake sets and a bounded negative-feedback count.Source: §1.2 · p. 4

1.3 Related work and positioning

  • The contribution sharpens prior ListCascade upper bounds and replaces the cited lower-bound theorem; the counterexample mechanism itself has precedents.The exact δ-dependent constant and anchored counterexample are identified as new contributions relative to.Source: §1.3 · p. 5

2 Preliminaries

The preliminaries define bandit PAC learning and the BDS and anchored BDS witness dimensions. The dimension chain relates them to pointwise width and identifies examples attaining its extremes.

2 Preliminaries

  • BDS uses witnesses whose restriction vectors have coordinatewise neighbors, while aBDS requires a zero-multiplicity anchor; the paper defines realizable bandit PAC sample complexity using error ε and failure probability δ.BDS is the supremum of total witness multiplicity; aBDS is defined using anchored witnesses.Source: §2 · pp. 5–6

2.1 The dimension chain

  • aBDS equals the zero-allowed witness quantity T0, while the all-positive quantity T+ is at most aBDS and can be smaller by an unbounded gap.The rare-label class has aBDS = K−1 but T+ = 0.Source: §2.1 · pp. 6–7
  • The full box [q]^d has BDS = d(q−1), aBDS = (d−1)(q−1), and R = q; the constant class has BDS = R−1 and aBDS = 0.These examples attain both extremes of the dimension chain.Source: §2.1 · pp. 6–7
  • Positive-multiplicity witness coordinates must be distinct instances and cannot coincide with an anchor.If two coordinates use the same instance, a neighbor changing one while preserving the other cannot exist.Source: §2.1 · p. 6
  • The dimensions satisfy aBDS ≤ BDS, R−1 ≤ BDS, and BDS ≤ aBDS + R−1.Here R is the supremum number of labels realized at one instance.Source: §2.1 · pp. 6–7

3 The lower-bound side, corrected

The section refutes the published BDS lower bound as stated and develops corrected lower bounds using anchored witnesses, width, and confidence. It also gives an exact rate for classes with aBDS zero.

3.1 Refutation of the published lower bound

  • Classes with BDS = K−1 contradict the published unconditional Ω(BDS/ε) lower bound, and its proof has independent gaps for single-coordinate witnesses and arbitrary learners.The examples include an anchored class satisfying the common-anchor condition implicitly used in the published proof.Source: §3.1 · pp. 7–8

3.2 The conditional-fiber equality-query lemma

  • The conditional-fiber lemma bounds any adaptive guesser’s success by (n+1)/|Qi(u)| after n equality queries on a fiber of size at least Ni+1.It applies without label-swap symmetry; the example witness lacks the relevant label-swap automorphism.Source: §3.2 · pp. 8–9

3.3 The Ω(A/ε) bound

  • Every finite anchored witness of value M forces more than M/(32ε) samples, yielding the Ω(aBDS/ε) lower bound against randomized improper learners.The proof takes the supremum over finite witnesses.Source: §3.3 · p. 9

3.4 Width, and the exact complexity of aBDS = 0 classes

  • When aBDS = 0 and R is finite, distinct hypotheses disagree everywhere and the exact sample complexity is max{0, ⌈(1−δ)R⌉−1}.If R is infinite in the infinite-alphabet extension, no finite sample size suffices.Source: §3.4 · p. 10

3.5 Confidence bound and the combined theorem

  • For 0 < δ ≤ 1/4, the confidence lower bound is ln(1/δ)/(8ε); the combined theorem joins anchored-dimension, confidence, and width lower bounds.When R ≥ 2, the width contribution can use R/2.Source: §3.3 · p. 9, §3.5 · p. 10, §3.4 · p. 10

4 Upper bounds without the ambient label count

The upper-bound analysis removes dependence on the ambient label count and uses fiberization to obtain a structural bound led by the anchored dimension. It also specifies when an online-to-PAC conversion applies.

4.1 A conservative online-to-PAC conversion

  • A pointwise-monotone bandit algorithm with at most M negative feedbacks on every realizable sequence converts to PAC learning when mε ≥ max{2M, 8 ln(1/δ)}.Both monotonicity and the adversarial negative-feedback bound are indispensable, and finite BDS alone does not guarantee the latter.Source: §4.1 · p. 11

4.2 The K-free cascade bound

  • The K-free cascade bound depends on BDS and R rather than the ambient label count K, using alphabet reduction, per-epoch confidence budgets, and non-uniform error allocation.The analysis repairs two steps in the published cascade proof.Source: §4.2 · pp. 11–13

4.3 Fiberization: from B to A after one positive

  • After one positive feedback at (x,y), the surviving fiber Hx=y has BDS at most aBDS(H).The structural upper bound consequently has an additive width term and an anchored-dimension 1/ε coefficient.Source: §4.3 · p. 13
  • The structural algorithm first predicts uniformly among labels realized at each instance until a positive occurs, then learns within the resulting fiber using fresh i.i.d. rounds.The first phase costs R ln(2/δ) rounds, a cost noted as optimal in the affine multiplexer direct-sum regime.Source: §4.3 · p. 13

5 Exact rates for private-shell anchored-block classes

Private-shell anchored-block classes admit explicit dimension formulas and a log-free rate, established by a two-phase learner and matching lower bounds. Multi-scale unions show a limitation of stagewise cascades.

5 Exact rates for private-shell anchored-block classes

  • For PAB classes, aBDS = M, BDS = max{M, R−1}, R = q+1+wmax, and nontriviality is equivalent to M > 0.The class consists of disjoint fully-product blocks with external anchors and pointwise-private hypotheses.Source: §5 · p. 14
  • The PAB learner tests private hypotheses first, then identifies the active block on its first negative feedback and changes a point’s prediction only after a negative at that point.This keeps the pointwise error set nonincreasing and bounds negative feedbacks in the active block by M.Source: §5 · pp. 14–15

5 Exact Rates for private-shell anchored-block classes

  • For M > 0, the PAB upper bound and the three-part lower bound match up to universal constants on the stated parameter ranges.For M = 0, the core is a singleton and the sample bound is R−1.Source: §5 · pp. 14–15
  • Multi-scale unions can saturate every cascade stage, producing a Θ(B log K/ε) stagewise cost while the PAB algorithm localizes the active scale after a first negative.The cascade barrier concerns that architecture, not other algorithms.Source: §5 · p. 15

6 The confidence direct-sum phenomenon

The affine multiplexer places n linear-algebraic groups behind a shared anchor, creating a confidence direct-sum regime and a rank-saturation transition. Its confidence profile refutes a universal additive-confidence bound, while matching upper and lower bounds identify the costs in each regime.

6 The confidence direct-sum phenomenon

  • The construction uses n macro-groups of affine binary labelings behind a common anchor, with BDS = aBDS = 2n − 1.The class uses K = 2n + 1 labels; each nonzero instance realizes 2n labels, while the common anchor realizes only ⊥.Source: §6 · pp. 15–16

6.1 The direct-sum lower bound, uniformly over an interval of confidences

  • Theorem 6.4 proves a lower bound of order n·min{n, log(1/δ)}/ε over an interval of confidence levels, by retaining many consistent low-rank groups.On its good event, at least 3n/4 groups remain consistent with rank below ℓ, and a surviving group other than the output's selected group retains misclassified targets.Source: §6.1 · pp. 16–17

6.2 Matching upper bounds and the full confidence profile

  • The rank-saturation algorithm tests groups sequentially and has at most n^2 + n − 1 negative feedbacks on every realizable sequence.Its mistakes are pointwise-monotone, enabling the online-to-PAC conversion; the theorem also gives an upper bound of 10nL/ε.Source: §6.2 · pp. 17–18
  • For the affine multiplexer, mB = Θ(R·ln(1/δ)/ε) when ln(1/δ) ≲ n, then mB = Θ((n^2 + ln(1/δ))/ε) in the rank-saturated regime.Theorem 6.7 gives the full profile for 0 < δ ≤ 1/4.Source: §6.2 · p. 18

6.3 Consequences

  • There is no universal constant C giving the proposed additive-confidence rate for every finite-BDS class; on the multiplexer, the gap is Θ(n^2/ε) versus Θ(n/ε) at the stated confidence point.This is the uniform-constant reading of the open problem; the per-class asymptotic reading is distinct.Source: §6.3 · p. 19
  • Classes G2n and the affine multiplexer share dimension profiles yet have complexities Θ(n/ε) and Θ(n^2/ε), respectively, so those dimensions do not characterize complexity within polylogarithmic factors.The comparison is made at a common parameter point.Source: §6.3 · p. 19
  • The direct-sum mechanism is per-cell confidence certification: ruling out a group at confidence 2^-ℓ needs ℓ independent equations that provide no evidence against other groups.The rare-label class has one block, whereas the multiplexer has n such groups.Source: §6.3 · p. 19

7 Compatibility with ListCascade and additive list-PAC bounds

The section audits whether additive-confidence list-PAC guarantees could pass through ListCascade and contradict the bandit lower bounds. It finds no contradiction: harvesting labeled examples multiplies confidence costs by the current list size, and the multiplexer lower bound shows this loss can be necessary.

7 Compatibility with ListCascade and additive list-PAC bounds

  • ListCascade harvests labeled examples only on correct bandit guesses, so obtaining them with high confidence costs raw rounds scaled by the current list size.A uniform guess from a list of size s succeeds with probability 1/s; the first list has size Θ(R).Source: §7 · pp. 20–21
  • An additive list-PAC bound could improve the list-learning step, but cannot remove the separate confidence cost of harvesting examples.The setting and learner quantifiers are compatible across the bridge, and ℓ·DSℓ(H) ≤ BDS(H).Source: §7 · p. 20
  • The cascade must succeed across Θ(log R) stages, requiring its failure budget to be split across stages.Even assuming an additive list-learning step, the raw stage cost retains the list-size multiplier.Source: §7 · pp. 20–21
  • The multiplexer lower bound shows the harvest-related multiplicative confidence cost is necessary for every learner when log(1/δ) ≲ n.Against a candidate macro-group, gaining confidence 2^-ℓ requires ℓ informative guesses addressed to that group, and evidence cannot be shared across Θ(R) groups.Source: §7 · p. 21
  • On PAB classes, harvesting can be localized because one negative feedback at a non-base point identifies the active block, so additivity survives.The paper treats the claimed additive list-PAC rate as a hypothesis; its results do not depend on that claim being true.Source: §7 · pp. 20–21

8 Discussion and open problems

The discussion identifies limits of dimension-based approaches and points to confidence direct-sum structure as a missing ingredient. It leaves broader confidence profiles, agnostic bandit learning, and sharper constants open.

8 Discussion and open problems

  • Finite BDS does not guarantee a finite adversarial mistake bound, so online-to-PAC conversion alone cannot yield general PAC upper bounds; the i.i.d. structure must be used.The threshold example has aBDS = BDS = 1 and R = 2 yet admits unbounded adversarial negative-feedback counts.Source: §8 · p. 21
  • The multiplexer nevertheless has a finite adversarial budget of n^2 + n − 1, which supports its additive rank-saturated regime.The discussion contrasts this with the general finite-BDS barrier.Source: §8 · p. 21
  • The dimension triple (aBDS, BDS, R) is incomplete for fine-grained complexity; the paper points to a confidence direct-sum profile as the missing ingredient.Affine multiplexer restrictions are offered as a way to locate such structure.Source: §8 · pp. 21–22
  • The proposed confidence direct-sum functional is a research template, not a formal conjecture, and defining it with matching bounds remains open.The suggested profile should vanish on PAB classes, equal Θ(n) on the multiplexer, and dominate certificates of affine multiplexer restrictions.Source: §8 · p. 22
  • Open problems include constant-confidence removal of all polylogarithmic factors, general full-δ behavior near the zero-sample boundary, agnostic bandit feedback, and sharper per-class constants.For the multiplexer, the λ^3 term is lower-order, leaving the constant-confidence question open on both sides.Source: §8 · p. 22
Loading 2609.29694v1…