Research map / Learning theory and algorithms / Sample complexity
Multicalibration Yields Better Matchings
Riccardo Colini Baldeschi, Simone Di Gregorio, Simone Fioravanti, Federico Fusco, Ido Guy, Daniel Haimovich, Stefano Leonardi, Fridolin Linder, Lorenzo Perini, Matteo Russo, Cem Sirin, Niek Tax
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| multicalibrate the base predictor with the boosting procedure | linear predictor on quadratic synthetic data · Best Action and Max Matching synthetic | Utility Gap | Improved |
| use moderately high epsilon in multicalibration (ablation) | weighted multicalibration · Best Action and Max Matching synthetic | convergence speed | Improved |
| use very low epsilon with a small CHECK sample (ablation) | weighted multicalibration · Best Action and Max Matching synthetic | convergence | Hurt |
| use fewer arms in Best Action (ablation) | weighted multicalibration · Best Action, m in {4,16,64,256} | convergence | Improved |
| compare empirical samples against worst-case theory, Max Matching epsilon = 1/4 | weighted multicalibration · Max Matching, m = 45 | samples to positive utility gap: 28 * 1024 samples vs theoretical at least 105 * 28 * log(1024) | Improved |
Closest papers by meaning
- Improved Bounds for Swap Multicalibration and Swap Omniprediction (NeurIPS 2025 · similarity 0.84)
- Instance-Adaptive Online Multicalibration (NeurIPS 2026 · similarity 0.84)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.83)
- Proportionally Fair Matching via Randomized Rounding (AAAI 2025 · similarity 0.83)
- Discretization-free Multicalibration through Loss Minimization over Tree Ensembles (NeurIPS 2025 · similarity 0.83)
- Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.83)
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.
