# On the Convergence of Multicalibration Gradient Boosting

arXiv: https://arxiv.org/abs/2602.06773 · HTML: https://mlsanity.com/paper/2602.06773/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 29 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 18 of 18)

- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [Bridging Multicalibration and Out-of-distribution Generalization Beyond Covariate Shift](https://mlsanity.com/paper/2406.00661/) (2024)
- [Randomized Gradient Boosting Machine](https://mlsanity.com/paper/1810.10158/) (2018)
- [Discretization-free Multicalibration through Loss Minimization over Tree Ensembles](https://mlsanity.com/paper/2505.17435/) (2025)
- [MCGrad: Multicalibration at Web Scale](https://mlsanity.com/paper/2509.19884/) (2025)
- [Shrinkage degree in L2-re-scale boosting for regression](https://mlsanity.com/paper/1505.04369/) (2015)

## Built on by (most cited first, 1 of 1)

- [Augmented Feature Boosting for Multicalibration](https://mlsanity.com/paper/2609.33891/) (2026)

## Abstract (arXiv)

Multicalibration gradient boosting has recently emerged as a scalable method that empirically produces approximately multicalibrated predictors and has been deployed at web scale. Despite this empirical success, its convergence properties are not well understood. In this paper, we provide computational guarantees for multicalibration gradient boosting algorithms. We show that the magnitude of successive prediction updates decays at O(1/√T), which implies the same convergence rate bound for the empirical multicalibration error over rounds. Under additional smoothness assumptions on the weak learners, this rate improves to linear convergence. We further establish convergence for adaptive variants. Experiments on real-world datasets support our theory and clarify the regimes in which the method achieves fast convergence.