Chapter 4

Phi-Regret and Multicalibration

The black-box reduction from \(\Phi\)-regret to online learning due to Gordon, Greenwald and Marks [GGM08[GGM08] G. J. Gordon, A. Greenwald and C. Marks. (2008). No-regret learning in convex games. International Conference on Machine Learning.] centers around the algorithmic primitive of fixed points. This chapter introduces a different route to the same destination that passes through forecasting [FP26[FP26] G. Farina and J. C. Perdomo. (2026). An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to \(\Phi\)-Regret Minimization. arXiv preprint arXiv:2604.19592.].

At a high level, the moral of this section is the following, also depicted in Figure 1.

As we will show towards the end of the chapter, this forecasting-based reduction comes with algorithmic benefits that forego the need for complicated semiseparation (cf. Chapter 3, Section 3.2). We note however that it is not known whether a forecasting-based approach can yield fast offline algorithms for \(\Phi\)-equilibrium computation (cf. Chapter 2, Section 2.3).

4.1 A Gordon-Greenwald-Marks result for multicalibration

We start with online multicalibration. In every round \(t\), Nature reveals a context \(\boldsymbol{c}^{(t)} \in \mathcal{C}\). The learner outputs a distribution \(D^{(t)}\) over forecasts \(\boldsymbol{p}^{(t)} \in \mathcal{U} \subseteq \mathbb{R}^{d}\), and Nature then reveals the true utility vector \(\boldsymbol{u}^{(t)} \in \mathcal{U}\). Given test \(h : \mathcal{C} \times \mathcal{U} \to \mathbb{R}^{d}\), the calibration error against \(h\) is

The forecasts are \(\mathcal{H}\)-multicalibrated if \(\text{MC-Err}^{(T)} (h) = o(T)\) for every \(h \in \mathcal{H}\).

As we show in Theorem 4.2, multicalibration admits a black-box reduction to online learning in the style of Gordon, Greenwald and Marks [GGM08]. However, in the case of multicalibration the nonlinear primitive is not fixed points, but rather expected variational inequalities, as defined next.¹1Expected variational inequalities have appeared in the literature under different names, including “outgoing minimax problems” [FH21[FH21] D. P. Foster and S. Hart. (2021). Forecast Hedging and Calibration. Journal of Political Economy.], “accuracy certificates” [NOR10[NOR10] A. Nemirovski, S. Onn and U. G. Rothblum. (2010). Accuracy Certificates for Computational Problems with Convex Structure. Mathematics of Operations Research.], or “negative correlation search” [PR25[PR25] J. C. Perdomo and B. Recht. (2025). In Defense of Defensive Forecasting. arXiv preprint arXiv:2506.11848.].

Efficient algorithms for EVIs are known for general compact convex sets under mild oracle access assumptions [ZAT+25[ZAT+25] B. H. Zhang, I. Anagnostides, E. Tewolde, R. E. Berker, G. Farina, V. Conitzer and T. Sandholm. (2025). Expected Variational Inequalities. International Conference on Machine Learning, 74422–74446.].

Armed with the EVI primitive, we can reduct multicalibration to an external-regret minimizer \(R_{\mathcal{H}}\) whose decision set is the class of tests \(\mathcal{H}\) as follows.

Necessity of EVIs. In a precise sense, EVIs are also necessary. Suppose we already had an efficient \(\mathcal{H}\)-multicalibrated forecaster. Fix a context \(\boldsymbol{c} \in \mathcal{C}\) and a test \(h \in \mathcal{H}\), and consider the EVI operator \(S(\boldsymbol{p}) = h(\boldsymbol{c}, \boldsymbol{p})\). To solve this EVI, run the forecaster for \(T\) rounds with the same context \(\boldsymbol{c}^{(t)} = \boldsymbol{c}\). After it outputs \(D^{(t)}\), choose Nature’s response as

For any fixed \(\boldsymbol{u}^{⋆} \in \mathcal{U}\), the choice in (3) gives

Averaging the distributions \(D^{(1)}, \dots , D^{(T)}\) uniformly therefore produces a distribution \(D\) with

As \(T\) grows, the multicalibration condition drives the right-hand side to \(0\). So an online multicalibrated forecaster gives a black-box EVI solver.

4.2 From Multicalibration to Phi-regret minimization

We now use forecasting to construct a \(\Phi\)-regret minimizer. Let \(\mathcal{X} \subseteq \mathbb{R}^{d}\) be a compact convex action set, \(\mathcal{U} \subseteq \mathbb{R}^{d}\) be a compact convex set of possible utility vectors, and \(\Phi \subseteq \{\phi : \mathcal{X} \to \mathcal{X}\}\) be a family of deviations. Recall that if the learner outputs distributions \(\mu^{(t)}\) over \(\mathcal{X}\), its \(\Phi\)-regret against a deviation \(\phi \in \Phi\) is

The idea of the reduction asks the forecaster to predict the next utility vector. Given a forecast \(\boldsymbol{p} \in \mathcal{U}\), define the deterministic best response

with ties broken by a fixed rule. If the forecaster outputs a distribution \(D^{(t)}\) over forecasts \(\boldsymbol{p}^{(t)}\), the decision maker plays the pushforward distribution \(\mu^{(t)}\) induced by \(\boldsymbol{x}^{(t)} = \sigma (\boldsymbol{p}^{(t)})\).

What tests should the forecaster be calibrated against? For each deviation \(\phi \in \Phi\), define

As it turns out, multicalibration with respect to the test class \(\mathcal{H}_{\Phi}\) suffices to control \(\Phi\)-regret.

Quite intuitively, the complexity of the required calibration class scales with the complexity of the deviation class. We can think of Theorem 4.3 as a generalization of the classical connection between \(ℓ_{1}\)-calibration and swap regret [FV97[FV97] D. P. Foster and R. V. Vohra. (1997). Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21, 40–55.].

4.2.1 Putting the two reductions together

Combining Theorem 4.2 and Theorem 4.3 gives the promised route from external regret to \(\Phi\)-regret. Set \(\mathcal{H} = \mathcal{H}_{\Phi}\). Run the multicalibration algorithm as the forecaster inside the best-response algorithm. Then, for every \(\phi \in \Phi\),

Thus, the burden of \(\Phi\)-regret minimization shifts to two primitives:

1. no-regret learning over the induced test class \(\mathcal{H}_{\Phi}\); and
2. solving EVIs over the forecast domain \(\mathcal{U}\).

The key distinction from the Gordon-Greenwald-Marks path is that we do not need to optimize over valid deviations directly. We only need a regret minimizer over tests that contain the maps \(h_{\phi}\). This extra flexibility is useful when characterizing the deviation class would otherwise require complex machinery, such the semiseparation construction of Daskalakis, Farina, Fishelson, Pipis and Schneider [DFF+25[DFF+25] C. Daskalakis, G. Farina, M. Fishelson, C. Pipis and J. Schneider. (2025). Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games. Symposium on Theory of Computing (STOC).] mentioned in Chapter 2, Section 2.2.

4.2.2 Linear deviations

As an illustration, consider linear deviations \(\phi (\boldsymbol{x}) = \mathbf{M} \boldsymbol{x}\) over a convex compact set \(\mathcal{X} \subseteq \mathbb{R}^{d}\). The classical GGM approach asks us to understand the geometry of all matrices \(\mathbf{M}\) satisfying \(\mathbf{M} \mathcal{X} \subseteq \mathcal{X}\), and then compute fixed points of the matrices selected by the regret minimizer. That geometry of the endomorphisms can be difficult [DFF+25].

The multicalibration route permits a relaxation. From (6),

If every valid linear endomorphism has spectral norm at most \(S\), then each test above lies in a Frobenius ball of radius on the order of \(\sqrt{d}(S + 1)\). Hence, instead of learning over valid endomorphisms, we can learn over the larger class

where \(ρ\) is chosen large enough to contain all tests \(h_{\phi}\). This larger class is easy: external regret over a Euclidean ball can be easily handled by projected online gradient descent. Indeed, recall that the utility sent to the matrix learner at time \(t\) is linear:

Consequently, if \(\Vert \boldsymbol{x}\Vert_{2} \le B\) for \(\boldsymbol{x} \in \mathcal{X}\) and \(\Vert \boldsymbol{u}\Vert_{2} \le L\) for \(\boldsymbol{u} \in \mathcal{U}\), the standard projected-gradient bound gives \(O(B L S \sqrt{d T})\) linear-swap regret, up to constants. This improves the dimension dependence of the recent semi-separation-based route of Daskalakis, Farina, Fishelson, Pipis and Schneider [DFF+25], while avoiding semi-separation altogether.

4.2.3 RKHS deviations

The same idea extends beyond finite-dimensional linear classes. Suppose that the deviation functions \(\phi : \mathcal{C} \times \mathcal{X} \to \mathcal{X}\) lie in a vector-valued reproducing kernel Hilbert space with matrix-valued kernel

For the contextual reduction, the relevant tests are

These tests also lie in an RKHS. Indeed, the first term is represented by composing the deviation kernel with the best-response map, while the second term is represented by the linear kernel on \(\sigma (\boldsymbol{p})\). The resulting kernel is

So, if we have an online learner over the RKHS ball associated with \(\Gamma'\), Theorem 4.2 supplies a multicalibrated forecaster, and Theorem 4.3 turns it into a no-\(\Phi\)-regret algorithm. This recovers low-degree polynomial deviations as a special case and also covers infinite-dimensional kernels, such as Gaussian kernels, where the fixed-point route does not have an obvious finite-dimensional endomorphism geometry to exploit.