Model Ensembling for Constrained Optimization

We study a setting in which a decision maker solves a $d$-dimensional optimization problem with an objective that is a linear function of the $d$ label variables, denoted $y$. The decision maker does not know the objective, but instead has estimates of the $d$ label variables from a collection of $k$ predictive models. The central question is: what action should the decision maker take, given (differing) predictions and recommended actions from the collection of models? The optimization problem can be defined by a set of specified (and not necessarily convex) constraints.

Our white box ensembling method follows a simple, intuitive idea. Given a context vector $x$, each of the $k$ constituent models, denoted $h_i$ for $i\in [k]$, produces a predicted label vector $h_i(x)$, which, after solving the corresponding optimization problem produces the action ${\pi }_i(x)$. If model $i$’s predictions were correct, then the corresponding payoff of the model’s action would be ${\pi }_i(x)\cdot h_i(x)$. We call this model $i$’s self-assessed payoff. The idea is to “transparently ensemble” the models by always taking the action of the model with the largest self-assessment: $\arg {\max }_i{\pi }_i(x)\cdot h_i(x)$. But this idea runs into several obstacles. First, the self-assessed expected payoff of a model $𝔼[{\pi }_i(x)\cdot h_i(x)]$ need not have any clean relationship with its actual expected payoff $𝔼[{\pi }_i(x)\cdot y]$. Second, even if each model is “self-consistent” in the sense that $𝔼[{\pi }_i(x)\cdot y]=𝔼[{\pi }_i(x)\cdot h_i(x)]$, we would expect to lose self-consistency after selecting the model with the highest self-assessment, because we would be conditioning on a model having an unusually high self-assessed payoff: this would result in upward bias for the selected model conditional on the selection event even if the models produced independent, unbiased forecasts of the outcome variables. We solve these problems by showing how to efficiently post-process the constituent models so that they have consistent self-assessments even conditional on their selection – using techniques from the multicalibration literature [14]. For each model $i$ in the set that we are ensembling, our conditions guarantee:

We show that the ensembled policy ${\pi }^{\ast }$ that results from selecting the action ${\pi }^{\ast }(x)={\pi }_{i^{\ast }(x)}(x)$ (where $i^{\ast }(x)=\arg {\max }_i[{\pi }_i(x)\cdot h_i(x)]$ is the index of the model with the highest self-assessment) is self-consistent and is guaranteed to obtain expected payoff that is at least (up to error terms):

Note that the maximum is inside the expectation, and so this is the point-wise maximum self-assessed payoff. This can be substantially higher than the expected payoff of the best constituent model, which is (because of the self-consistency condition) ${\max }_i𝔼[{\pi }_i(x)\cdot y]={\max }_i𝔼[{\pi }_i(x)\cdot h_i(x)]$.

Our white box ensembling method offers a strong guarantee, but has three limitations. First, it requires access to the predictive model $h_i(x)$ that underlies the policy ${\pi }_i(x)$ This might not always be available – for example, if the decision maker receives action suggestions from a “prediction as a service” provider or a recommendation system, which may not be based on underlying predictions of the objective coefficients, or even if so, may not be made visible to the decision maker. Second, it requires updating and maintaining all of the constituent models to be ensembled, which might be prohibitive if the number of models is large.

Towards addressing these limitations, we introduce an alternative “black box” ensembling method. This method maintains only a single predictive model, and only requires access to the collection of $k$ policies ${\pi }_i(x)$ to be ensembled, not any details of their implementation (i.e. the constituent models or their point predictions). In broad strokes, it works by maintaining a single predictive model $h^{\ast }(x)$ for the labels that is unbiased both conditional on each coordinate of its own induced action ${\pi }^{\ast }(x)$ and conditional on each coordinate of the actions ${\pi }_i(x)$ chosen by each model to be ensembled. We prove a swap regret-like guarantee for this ensemble: not only is it self-consistent, but it obtains higher payoff than any of the constituent models even conditional on any coordinate of its induced action. Because this technique only requires maintaining a single predictive model and requires fewer evaluations of the downstream optimization problem, it can be trained substantially faster than our white box ensembling method. However, as a consequence of the limitations of its black box access to the constituent policies, it does not give the same form of strong point-wise guarantee that the white box approach does.

The problem of finding policies that solve optimization problems in the face of unknown label vectors is often solved by first predicting the label vectors and then optimizing for the predicted label. The “Smart Predict then Optimize” framework of [5] focuses on the design of surrogate loss functions to minimize in the prediction training phase that are best suited for the particular downstream optimization task. Our work differs from this in that we do not train a single model using a surrogate loss function that incorporates the downstream optimization, but instead leverage techniques from the multicalibration literature [14] to ensemble a collection of models to provide transparent and utility-preserving guarantees on the downstream task.

A line of work on omniprediction in both the unconstrained and constrained settings [12, 8, 15, 10, 13] gives theorems that informally state that if a 1-dimensional predictor $f$ (usually for a binary outcome) is multicalibrated with respect to a set of models, then for some family of loss functions, $f$ has loss at most the loss of the best model in the class. Here the focus is generally on the ability of the model $f$ to perform well over multiple loss functions, and the promise is only that $f$ performs as well as the best model in the class, rather than strictly better than it. One notable exception is [11] which analyzes multicalibration as a boosting algorithm for regression functions, and proves that if $f$ is multicalibrated with respect to a class of models $\mathscr{H}$, then it in fact performs as well as the best model in a strictly more expressive class (that $\mathscr{H}$ serves as weak learners for). Similarly, [9] and [18] consider the problem of reconciling two 1-dimensional regression functions that have similar error, but make different predictions. They show how to combine two such models into a single, more accurate model. A primary point of departure for us is that we consider ensembling models for high dimensional optimization problems, rather than 1-dimensional classification and regression problems.

The debiasing steps that we use are closest in spirit to those used in “decision calibration” [21] or “prediction for action” [16], which aim to produce predictors that are unbiased conditional on the action taken by some downstream decision maker. Independently and concurrently of our work, [4] adapt the “reconciliation” procedure of [18] to the decision calibration setting, updating pairs of models that frequently induce different decisions in downstream decision makers on the regions on which they induce different downstream decisions. Their end result is two new and reconciled models which agree with one another and are unbiased conditional on the action induced – and their bounds inherit a polynomial dependence on $k$, the number of actions of the downstream decision maker. Because the optimization problems we consider have linear objectives, we only need that our predictions are unbiased subject to the coordinates of the actions that result from optimization – a fact that was also used by [16]. This is what lets us handle downstream optimization problems with very large action spaces. The focus of [21, 16] was on producing policies that offer a downstream decision maker various forms of low regret guarantees – in contrast, our interest is in ensembling multiple explicit policies. The focus of [4] is on reconciling model multiplicity, whereas our focus is on achieving superior performance for the task at hand than the base models, and not explicitly on resolving disagreements between them.

In order to relate a model’s self-assessed payoff to its actual payoff, we will leverage the ability to make conditionally “consistent” predictions – informally, predictions which are accurate on average, marginally, but also conditional on arbitrary sets of interest. The parameterization we choose is related to the multicalibration literature – see e.g. [17] for a discussion of this and alternative parameterizations.

One important class of sets we will be concerned with making consistent predictions on is the level sets of different policies we aim to ensemble.

For shorthand, if a model is consistent with respect to a collection of sets ${𝒞}_{\pi }^{𝒯}$ for some policy $\pi$, we say that it is consistent to that policy.

As we will see, we will be able to post-process a model $h$ to be consistent with collections of sets $𝒞$ that may be defined in terms of $h$ itself. In particular, it will be useful for us to ask that a model $h$’s predictions are consistent with respect to the policy ${\pi }_h$ that it itself induces. This will turn out to be the condition we need to make a model “self-consistent” – the transparency condition in the sense that its self-assessed payoff accords with its actual payoff. Thus when a model $h$ is consistent (in the sense of Definition 3) with ${\pi }_h$, we will say that $h$ is self-consistent.

In this section, we show that consistency with respect to carefully constructed sets of events allows us to evaluate the payoff of a policy induced by a model via its self-assessments, and lets us compare the policy induced by a model with other policies. These statements will be the basic building blocks of our ensembling methods.

First we show that if a model $h$ is consistent with respect to a policy $\pi$’s level sets (Definition 4), then the model $h$’s predicted label can be used in place of the true label $y$ to correctly estimate the payoff of $\pi$.

An especially useful special case of Lemma 9 is the case in which a model $h$ is consistent with the policy ${\pi }_h$ that it itself induces. In this case, the model can be used to correctly evaluate its own payoff (up to error terms), and corresponds to a natural and useful “transparency” condition similar in spirit to the transparency conditions of [21, 16].

In this method, we will require consistency of our predictions with respect to another special collection of conditioning events: the sets on which each constituent model is most “optimistic” – or has the highest self-assessed payoff.

The procedure for ensembling $k$ models involves modifying the constituent models so each is consistent with respect to the level sets of its own induced policy conditional on the identity of the model with the highest self-evaluated payoff. Informally, consistency on this set of events is useful because they are related to how the decision maker takes actions – the ensemble follows the action of policy $i$ exactly when it has the highest self-assessed payoff. If each constituent model’s predictions are self-consistent and consistent conditional on these sets characterizing when the decision maker is taking different actions, the resulting ensembling satisfies strong outcome guarantees.

Convergence of the white box ensembling method follows similarly to convergence of Algorithm 1. Algorithm 2 repeatedly calls Algorithm 1 as a subroutine on each of the $k$ constituent models, on an adaptively chosen sequence of conditioning events.

We now analyze our white box ensembling method. First, we prove that it is self-consistent – its self-assessed payoff is equal (up to error terms) to its realized payoff, in expectation.

We next prove two bounds on the performance of the method. The first states that – up to error terms – the payoff of the ensemble is equal to the expected maximum self assessed payoff of each of the constituent models. Notice that here we bound the performance of the ensemble by the expected max, which is larger than the max expectation, the latter of which corresponds to the best single constituent model.

The next performance bound is a “swap-regret” like guarantee. It states that on the subset of examples on which the model chooses to follow policy $i$, it could not have improved by instead following some other policy $j$ – simultaneously for all $i$ and $j$.

This method maintains a model that is unbiased with respect to the policy it itself induces, as well as each constituent policy to be ensembled.

We now state and prove our main utility statement for our black box ensembling method: A swap-regret style guarantee that establishes that the policy induced by the ensemble model performs better than any of its constituent policies, not just overall, but also conditional on level sets of any policy in its ensemble.

Our algorithms operate in the batch/distributional setting, and the guarantees we prove are limited to when the data at deployment time is distributed identically to the training data. An important open question is how to adapt similar practical techniques to give robust methods that allow for various kinds of distribution shift. Techniques of [16] could be adapted to give similar ensembling algorithms in the online adversarial setting when the prediction target can be observed shortly after prediction at test time; these algorithms are mainly of theoretical interest, and practical variants would need to be developed. Even in the batch setting, our white box ensembling method is computationally expensive, and more efficient algorithms would be important improvements.