Multicalibration Yields Better Matchings

AI summary

Overview

Research area: Machine learning theory at the intersection of algorithmic fairness (multicalibration), algorithms with predictions, and combinatorial optimization (maximum-weight matching).

Technical level: Advanced. The paper is a theory contribution built on formal definitions, proof-based guarantees, and sample complexity bounds, complemented by synthetic numerical experiments.

Scope in one sentence: The paper shows that post-processing a black-box edge-weight predictor into a multicalibrated predictor lets a single standard maximum-weight matching routine match the performance of the best algorithm in a given family of matching algorithms applied to the original predictor.

What This Paper Is About

In many deployed systems, a machine learning model predicts the weights of a graph (for example the value of matching one node to another), and an optimization routine then computes the best matching from those predicted weights. When the predictor is not perfect, blindly trusting its outputs can be worse than a simple heuristic. The paper asks how to modify, or "multicalibrate", the predictor after the fact so that simply running the standard optimal matching algorithm on the adjusted predictions is competitive with the best decision rule from a given class of matching algorithms run on the original predictions. The authors prove this is possible up to an additive precision, give sample complexity bounds for learning such a predictor, and run synthetic experiments.

Key Contributions

1. A conceptual link between multicalibration and matching. The paper argues that the right property for a predictor in a predict-then-optimize pipeline is a version of multicalibration, instantiated by defining a weight class whose protected events are of the form "a given edge is chosen by a certain decision rule c in the class C".

2. An optimization guarantee (Theorem 3.1). If γ̂ is (W, α)-multicalibrated with respect to a weight class W = W₁ ∪ {w*}, then the maximum-weight matching computed on γ̂ is within additive ε of the best decision rule in C applied to the original predictor γ, where α = ε/(2√m).

3. A practical boosting algorithm with sample complexity bounds (Algorithm 1 and Theorem 3.3). The iterative boosting procedure (adapted from Gopalan et al., 2022b) initializes γ̂ as γ and alternates between a CHECK routine that finds violations and a projected gradient descent step with step size η = α/2 clipping to [0,1]^m. The paper proves convergence in O(r/(nα²)) iterations and O(rn³ log(nr|C|/(εδ)) / ε⁴) i.i.d. samples, where r upper-bounds the mean square error of the initial predictor.

4. Generalizations to other linear optimization problems. The framework extends to choosing the best action (reduced to a max-weight matching on a star graph of m+1 nodes), learning with rejection (three actions), and max-weight independent set under matroid constraints.

Main Findings

• Multicalibration makes argmax matching competitive. Theorem 3.1 states that max over c in C of E[Σ_{e in M_c(γ(x))} y_e] ≤ ε + E[Σ_{e in M_{c*}(γ̂(x))} y_e], where c* is the optimal matching algorithm. The construction of W has two parts: W₁ (built from the indicators of edges chosen by each c in C on γ(x)) ensures γ̂ faithfully captures the value of the algorithms in C, and w* (the indicators of edges chosen by c* on γ̂ itself) enforces self-consistency.

• Best-case sample complexity. Using adaptive data analysis techniques the predictor can be constructed with Õ(n^3.5/ε^3 · log|C|) samples, or with Õ(n^5/ε^4 · log|C|) samples when implementing boosting by iterating over disjoint parts of the dataset. The notation Õ hides terms polylogarithmic in n and 1/ε.

• Comparison to a simpler alternative. Estimating the expected performance of each algorithm by sampling from D and committing to the best one would require fewer samples, Õ(n²/ε² log|C|), but the multicalibration approach instead improves on the original black-box predictor both for the task at hand and in mean square error sense, and allows the developer to decide ex-ante what the best algorithm will look like as long as it is optimal with perfect information.

• Worst-case versus realistic sample complexity. Theorem 3.3's worst-case bound (with r in O(n²)) is Õ(n^5/ε^4). If the initial predictor has per-edge mean-squared error O(ε²), a realistic expectation for industry predictors, the sample complexity reduces to Õ(n^5/ε²). The 1/ε worst-case dependency can be improved to 1/ε³ using adaptive data analysis, giving O(n^2.5 √r log(n|C|/ε) log^{3/2}(n/(εδ)) / ε³).

• Runtime of the adaptive implementation. The adaptive version, which relies on the exponential mechanism over W, keeps the O(N|W|) iteration running time comparable to Algorithm 1 with a simpler CHECK implementation, which requires O(N′|W|) time per iteration.

• Other models have better bounds. For finding the best action the sample complexity is Õ(√m/ε³ log|C|), since only one edge is active per decision and the multicalibration error α does not need to be scaled down as for matching. Learning with rejection needs Õ(1/ε³ log|C|) samples because there are only a constant number of actions. For max-weight independent set under a matroid of rank r, setting α = ε/r gives Õ(√n · r^2.5/ε³ log|C|).

• A motivating failure example. With two deterministic arms of value 1 and 1/ε, and a context X uniform on [0,1], an unbiased estimator that is correct on the first arm but outputs 1/ε² for the second arm when X ∈ [0, ε] and 0 otherwise causes the naive argmax rule to pick the suboptimal first arm with probability 1 − ε, even though "always choose the second action" strictly dominates it.

• Empirical evaluation is truncated in the available content. The paper reports numerical experiments in two synthetic settings characterised by model misspecification, named Best Action and Max Matching, motivated by the fact that standard loss minimization may fail to capture the local signals required for downstream optimization tasks. The specific results, metrics and figures from those experiments are not reported in the content available here.

Methodology in Plain English

The researchers start from a standard "predict-then-optimize" pipeline: a black-box model predicts edge weights, and a matching algorithm turns those predictions into a matching. They want to avoid ad-hoc manual patches to that pipeline. Their idea is to modify the predictor itself before the optimizer sees it, so that the optimizer's usual argmax choice becomes good.

To do this, they define a set of "tests" (the weight class W) that the modified predictor must pass. One family of tests checks that the new predictor is unbiased on the edges that each candidate algorithm in C would select from the original predictor's outputs. Another test checks that the new predictor is unbiased on the edges that the optimal matching algorithm would select from the new predictor's own outputs. Passing both simultaneously is what lets them compare the best algorithm on the original predictor against the standard algorithm on the adjusted one.

To actually find such a predictor, they use a boosting loop over a dataset: check whether the current predictor violates any test, and if so, nudge the predictor in the direction that reduces the violation (a projected gradient step with clipping to the valid range). They prove that a potential function measuring the mean squared error to the Bayes-optimal predictor decreases by a fixed amount each round, which bounds the number of rounds, and then use concentration arguments to bound how much data each check needs. A refined analysis makes the bound depend on how good the original predictor already is, so a better starting model needs fewer samples.

Why This Matters

Impact on research. The paper connects multicalibration — a concept from the algorithmic fairness literature (Hébert-Johnson et al., 2018) and extended by weighted multicalibration (Gopalan et al., 2022b), omnipredictors (Gopalan et al., 2022a) and outcome indistinguishability (Dwork et al., 2021; Gopalan et al., 2023) — to combinatorial optimization, where it had not been applied in this form. It differs from Zhao et al. (2021) and the concurrent work of Kiyani et al. (2026) by defining protected groups based on the input predictor γ and by guaranteeing competitiveness with the best post-processing of γ within a class C, rather than only establishing that argmax is the rational choice on a calibrated predictor.

Real-world applications (as motivated in the paper):

• Large-scale matching systems operating on unknown inputs, where the standard design pattern is predict-then-optimize.
• Replacing ad-hoc "IF-THEN" overrides that developers add when the pipeline makes suboptimal decisions; a heuristic can instead be included as a test function and the system is guaranteed to remain competitive with it.
• Learning with rejection, where the learner can predict a label or abstain at a lower cost.
• Choosing the best of several actions guided by context, which includes standard classification tasks and max-weight independent set under matroid constraints.

Industry relevance. The paper is co-authored by researchers at Meta Central Applied Science alongside Sapienza University of Rome and EPFL, and it explicitly targets the lifecycle of deployed matching systems. It argues that multicalibration offers a rigorous alternative to the cycle of manual patching, preserving architectural simplicity downstream because only one algorithm (the max-weight matching solver) is needed at test time. The authors also note that the worst-case sample complexity is pessimistic relative to practice: because the analysis uses expected MSE as a potential, the closer the original predictor is to Bayes optimal, the fewer samples are needed, and they describe this as realistic for industry-quality predictors.

Future Directions

1. Extensions beyond matching with an exact solver. The authors state that with proper adjustments the analysis goes through even when the underlying problem cannot be solved optimally but an approximation routine is available.

2. Other linear maximization tasks with deterministic constraints. The paper notes that max-weight matching is a running example and the approach applies to any linear maximization task with deterministic constraints, citing max-weight independent set in a matroid and learning with rejection as examples that are only briefly developed here.

3. Closing the sample complexity gap. The authors contrast their multicalibration bound with the Õ(n²/ε² log|C|) needed by the simpler "estimate and commit" alternative, and improve the ε dependency from 1/ε⁴ to 1/ε³ using adaptive data analysis; whether further improvements are possible is left open.

4. Full empirical characterisation. The available content truncates the empirical section, leaving the detailed results of the synthetic Best Action and Max Matching experiments as something a reader would need the complete paper to assess.

Target Audience

This paper is aimed at researchers and practitioners working on algorithms with predictions, calibrated and multicalibrated learning, algorithmic fairness notions, and the theory of combinatorial optimization under uncertainty. It is also relevant to machine learning engineers and system designers who run predict-then-optimize matching pipelines in production and want a principled alternative to hand-coded overrides, and to theoretically inclined readers comfortable with sample complexity bounds and boosting arguments.

Authors’ abstract

Consider the problem of finding the best matching in a weighted graph where we only have access to predictions of the actual stochastic weights, based on an underlying context. If the predictor is the Bayes optimal one, then computing the best matching based on the predicted weights is optimal. However, in practice, this perfect information scenario is not realistic. Given an imperfect predictor, a suboptimal decision rule may compensate for the induced error and thus outperform the standard optimal rule. In this paper, we propose multicalibration as a way to address this problem. This fairness notion requires a predictor to be unbiased on each element of a family of protected sets of contexts. Given a class of matching algorithms $\mathcal C$ and any predictor $γ$ of the edge-weights, we show how to construct a specific multicalibrated predictor $\hat γ$, with the following property. Picking the best matching based on the output of $\hat γ$ is competitive with the best decision rule in $\mathcal C$ applied onto the original predictor $γ$. We complement this result by providing sample complexity bounds, and by performing numerical experiments.