Research map / Multi-agent systems and games / Games and equilibria
PAC Learning with Improvements
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.
Introduces PAC learning with improvements, where agents can move within an improvement set to be classified positive, showing zero-error learnability in several settings and separations from standard and strategic PAC models, plus experiments on tabular data.
Problem
Standard PAC learning requires at least 1/epsilon samples and cannot reach zero error, and strategic classification focuses on gaming or incentives. The paper asks how agents' ability to genuinely improve by a limited amount changes learnability, sample complexity, and algorithm design for accurate
Approach
Model agents who respond to the published classifier by genuinely moving within an improvement set to a positively classified point, with loss counting errors after reaction. Under this model, risk-averse (conservative) learners such as the closure algorithm, the rightmost threshold, and dominating-set based classifiers can achieve zero error, which is impossible in the standard PAC model.
Key results
- Thresholds under uniform distribution: the rightmost consistent threshold achieves population error at most (epsilon - r)+ with O(1/epsilon log 1/delta) samples, reaching zero error when epsilon is at most r.
- Graph model: zero-error learning on a uniform distribution over nodes needs about n(log n + log 1/delta)/(d_min+ + 1) samples, with a matching lower bound of order n/(d_min+ + 1) log(n/(d_min+ + 1)).
- Experiments: risk-averse wBCE-trained models reduce test error as the improvement budget grows, with error sometimes reaching zero, and outperform BCE-trained models in overall error reduction as r increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow agents to improve by distance r and use the rightmost threshold consistent with the positive examples | Threshold learning · Uniform distribution on [0,1] | loss: \epsilon to (\epsilon -r)_+ | Helped |
| Use a positive-agreement classifier with angular improvement budget r | Homogeneous halfspaces · Uniform distribution on the unit sphere | loss: zero | Helped |
| Train with weighted BCE using a greater false-positive penalty than false-negative penalty | Two-layer neural network · Adult, OULAD, Law school, and synthetic tabular datasets | overall error | Helped |
| Use weighted-BCE loss-based risk aversion instead of a 0.9 decision threshold | Risk-averse classifiers · Tabular dataset experiments | error | Helped |
Surprising findings
- Learning with improvements can be easier than standard PAC learning (e.g., finite VC dimension is not necessary), and zero error is achievable for non-trivial classes where standard PAC cannot reach it.
- Finite strategic VC dimension does not imply PAC learnability with improvements, so the improvement setting is not simply easier than strategic classification.
Limitations
- Theoretical guarantees hold in the realizable setting, and the proper learning characterization is only partial (intersection-closed property is sufficient and essentially necessary under additional conditions).
- Empirical evaluation is limited to three tabular datasets and one synthetic dataset, with improvement assumed within an l_infinity ball and a decision-maker trained on labels from a zero-error decision tree.
- The graph sample complexity depends on the unknown minimum degree of the positive subgraph, which the learner does not know in advance.
Experimental setup
Datasets: Adult UCI OULAD Law school synthetic make_classification dataset
Benchmarks: Adult UCI OULAD Law school synthetic 8-dimensional dataset
Metrics: test error after agent improvement false positive rate false negative rate
Baselines: standard BCE-trained classifier threshold-based risk-averse classifier
Builds on: PAC learning strategic classification (Hardt et al.) strategic VC dimension (Sundaram et al.) closure algorithm
Closest papers by meaning
- Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.82)
- Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.80)
- On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.80)
- Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound (NeurIPS 2024 · similarity 0.80)
- Learning from positive and unlabeled examples -Finite size sample bounds (NeurIPS 2025 · similarity 0.79)
- Strategic PAC Learnability via Geometric Definability (NeurIPS 2026 · similarity 0.78)
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.