Research map / Learning theory and algorithms / Prediction and decision losses
Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning
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.
Characterizes learnability with improvements (strategic agents who genuinely improve) across proper/improper realizable PAC, bounded label noise, and online graph settings, using conservative classifiers.
Problem
Understanding which concept classes are learnable when classified agents genuinely improve (rather than merely manipulate) their features, across proper and improper PAC learning, label noise, and online learning.
Approach
Introduces "nearly minimally consistent" concept classes (minimal consistency required only on samples containing a negative example) that exactly characterize proper PAC-learnability with improvements; shows memorization is near-optimal for improper learning under coverability; gives Bayes-optimal noisy-label learners for linear separators and risk-averse (weighted) majority vote mistake bounds o
Key results
- Exact characterization: a concept class is properly PAC-learnable with improvements for all improvement functions and distributions iff it has finite VC-dimension and is nearly minimally consistent.
- Memorization rule improperly learns any class under coverability with sample complexity O((1/beta) log(N/gamma)), matched by an Omega((1/beta) log(1/beta)) lower bound up to logs.
- Risk-averse majority vote makes at most (Delta_G+1) log|H| mistakes in the realizable online graph setting; risk-averse weighted majority makes O(Delta_G (OPT + log|H|)) mistakes in the agnostic setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the nearly minimally consistent condition to characterize proper learnability | Proper PAC learning with improvements for all improvement functions and data distributions · Realizable setting | learnability characterization | Helped |
| Assume coverability of the positive-instance distribution and use memorization | Improper PAC learning with Euclidean-ball improvements · Coverable positive-instance distributions | improvement loss: improvement loss ≤ ε | Helped |
| Use Euclidean-ball improvement sets and the coverability assumption rather than arbitrary improvement functions | Improper learning of any concept class · Coverable distributions | learnability | Helped |
| Use a conservative classifier built from a standard noisy-label separator learner | Linear separators under bounded noise and isotropic log-concave distributions · Bounded label noise | expected error: OPT + ε -> exactly OPT | Helped |
| Use the risk-averse majority-vote threshold and neighbor-aware hypothesis elimination | Online learning with improvements · Realizable graph setting | mistakes: (Δ_G+1) log |H| | Helped |
| Use the risk-averse weighted-majority threshold and neighbor-aware weight updates | Online learning with improvements · Agnostic graph setting | mistakes: O(Δ_G · (OPT + log|H|)) | Helped |
| Use standard majority vote instead of the risk-averse majority-vote modification | Online learning with improvements · Realizable star-graph example | mistakes: unbounded | Hurt |
| Increase the improvement region for the memorization predictor | Improper learning with improvements · Any setting where the memorization rule applies | improvement loss | Helped |
| Use the memorization rule under coverability instead of a general learner without that assumption | Improper learning with Euclidean-ball improvements · Coverable distributions | sample complexity: O(1/β log N/γ); lower bound Ω(1/β log 1/β) | Mixed |
Surprising findings
- Learning with improvements can be easier than standard PAC learning: the memorization rule can achieve zero error w.h.p. when X has finite diameter, and improper learning works even for infinite VC-dimension classes under coverability.
- Majority vote can make an unbounded number of mistakes in the online improvement setting (star graph example), unlike standard online learning.
Limitations
- Improper results for Euclidean balls require a coverability assumption on the data distribution.
- Online mistake bound for the realizable/agnostic case depends on maximum degree Delta_G, and the lower bound is for deterministic learners only.
- Proper-learning characterization is for the realizable setting only.
Experimental setup
Metrics: improvement loss sample complexity mistake bound
Baselines: standard PAC learning majority vote online learner intersection-closed proper learner
Builds on: minimally consistent learning with one-sided error PAC learning with improvements (Attias et al.) coverability (Gourdeau et al.) weighted majority vote
Closest papers by meaning
- Bayesian Strategic Classification (NeurIPS 2024 · similarity 0.88)
- Strategic Classification With Externalities (ICLR 2025 · similarity 0.87)
- One-Shot Strategic Classification Under Unknown Costs (ICML 2024 · similarity 0.86)
- Should Decision-Makers Reveal Classifiers in Online Strategic Classification? (ICML 2025 · similarity 0.86)
- Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification (NeurIPS 2024 · similarity 0.86)
- Strategic PAC Learnability via Geometric Definability (NeurIPS 2026 · similarity 0.86)
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.