Research map / Bandits and online learning / Online convex optimization and games
Fast Rates for Bandit PAC Multiclass Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a proper, computationally efficient bandit PAC multiclass learner whose sample complexity is O((poly(K)+1/eps^2) log(|H|/delta)), removing the K/eps^2 leading term, and extends it to Natarajan-dimension classes.
Problem
Sample complexity of agnostic (eps,delta)-PAC multiclass classification when the learner only receives bandit feedback (whether the predicted label is correct), which prior work bounded by O(K/eps^2).
Approach
Compute a low-variance exploration distribution over hypotheses by minimizing a log-barrier potential over induced label probabilities with stochastic Frank-Wolfe (SPIDER) using an L1-smoothness analysis; the resulting uniform variance bound O(1) (rather than O(K)) enables Bernstein-based importance-weighted ERM with sample complexity leading term 1/eps^2.
Key results
- Algorithm achieves sample complexity O((K^9 + 1/eps^2) log(N/delta)) for finite classes of size N, improving the leading eps-dependence from K/eps^2 to 1/eps^2.
- Extension to Natarajan-dimension classes gives O~((K^9 + 1/eps^2) d_N log(1/delta)), matching full-information rate up to logs for small eps.
- The algorithm is proper and makes O(K^4 sqrt(log(N/delta))) weighted ERM oracle calls, running in time polynomial in K, 1/eps, log(N/delta).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use low-variance exploration from log-barrier stochastic optimization instead of uniform random label exploration | Agnostic bandit PAC multiclass classification · Finite hypothesis classes | sample complexity: O((K/\eps^2)\log{|\mathcal{H}|}) -> O((K^9 + 1/\eps^2)\log (N/\delta)) | Helped |
| Use the proposed finite-class algorithm with a finite discretization of the Natarajan class | Agnostic bandit PAC multiclass classification · Classes with finite Natarajan dimension d_N | sample complexity: \smash{\widetilde{O}}(\ifrac{K d_N}{\eps^2}) -> \smash{\widetilde{O}} \brk{\brk{K^9 + \ifrac{1}{\eps^2}}d_N \log(\ifrac{ | Helped |
Surprising findings
- The price of bandit feedback in agnostic multiclass PAC learning is O(1) as eps goes to 0, not Theta(K) as in the realizable case.
- Online-to-batch conversion of optimal bandit multiclass regret rates yields K/eps^2 sample complexity, a separation from the PAC rate achieved here.
Limitations
- Polynomial dependence on K is large (poly(K) = K^9 in the leading additive term), not optimized.
- Efficiency relies on a weighted ERM oracle over the hypothesis class being available at O(1) cost.
Experimental setup
Metrics: sample complexity excess zero-one loss
Baselines: uniform label exploration with importance sampling (O(K/eps^2)) online-to-batch conversion of bandit multiclass regret bounds
Builds on: SPIDER Frank-Wolfe contextual bandit policy optimization with low-variance exploration distribution Natarajan dimension Sauer-Shelah lemma
Closest papers by meaning
- Instance-optimal PAC Algorithms for Contextual Bandits (NeurIPS 2022 · similarity 0.88)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.88)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.87)
- Collaborative Learning with Different Labeling Functions (ICML 2024 · similarity 0.87)
- Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs (NeurIPS 2024 · similarity 0.85)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.