Outcome Assumptions and Duality Theory for Balancing Weights

David Bruns-Smith Avi Feller

UC Berkeley UC Berkeley

###### Abstract

We study balancing weight estimators, which reweight outcomes from a source
population to estimate missing outcomes in a target population. These
estimators minimize the worst-case error by making an assumption about the
outcome model. In this paper, we show that this outcome assumption has two
immediate implications. First, we can replace the minimax optimization problem
for balancing weights with a simple convex loss over the assumed outcome
function class. Second, we can replace the commonly-made overlap assumption
with a more appropriate quantitative measure, the minimum worst-case bias.
Finally, we show conditions under which the weights remain robust when our
assumptions on the outcomes are wrong.

##  1 Introduction

Using covariates to transfer outcome information from one setting to another
is a central task in domain adaptation, observational causal inference, and
missing data imputation. These tasks share a common structure: we observe
covariates and outcomes for a source data set and want to predict outcomes
given covariates in a target data set, which might have a different covariate
distribution than the source. One standard approach is to reweight the source
distribution to have a similar covariate distribution to the target. When the
source and target distributions have common support, using the density ratio
for weights leads to unbiased estimation, known as _importance weighting_ for
domain adaptation under covariate shift (Sugiyama et al., 2007a) and _inverse
propensity score weighting_ (IPW) for observational causal inference
(Rosenbaum and Rubin, 1983).

Importance weighting has several drawbacks. First, using the density ratio for
weights can lead to extremely large variance and unstable estimation (Kang et
al., 2007; Cortes et al., 2010). Second, the density ratio is notoriously
difficult to estimate, and simple plug-in estimates do not guarantee covariate
balance between the reweighted source distribution and target distributions
(see Ben-Michael et al., 2021).

Due to these drawbacks, in practice we would like to use weights with smaller
variance than the density ratio that directly target a specified level of
covariate balance (e.g., Gretton et al., 2009; Imai and Ratkovic, 2014). In
general, such a bias-variance trade-off only exists if we assume restrictions
on the outcome model; without restrictions, only the density ratio can
guarantee finite bias. This motivates the so-called _minimax balancing
weights_ estimators, which we study in this paper. These estimators find the
minimum dispersion weights that constrain the worst-case bias between groups
over an outcome function class (see Zubizarreta, 2015; Hirshberg et al., 2019;
Zhao, 2019; Kallus, 2020b).

###  1.1 Summary of the Paper

We begin by reviewing existing balancing weights estimators, which achieve a
smaller mean squared error than importance weighting by introducing an
assumption on the outcome model. We argue that the outcome assumption implies
two new results.

First, we use convex duality to show that the minimax optimization problem for
balancing weights can be replaced with a simple convex loss over the outcome
function class. Our dual formulation in Section 4 shows that the minimax
weights are always a (rescaled and recentered) function from that class. For
example, if the outcomes are bounded, the corresponding weights will be
bounded. If the outcome function belongs to an RKHS with some kernel, the
corresponding weights will belong to an RKHS with the same kernel. The outcome
assumption pins down the shape of the balancing weights.

Second, we show that after making an outcome assumption, we do not need the
density ratio to exist, i.e., we do not need to make the additional “overlap”
assumption that is common in causal inference. Instead, there is an explicit
quantity, the minimum achievable bias, which depends on the outcome function
class, and which acts as a quantitative measure of the degree of overlap
violations. We show that this measure can be more appropriate than an overlap
assumption in finite samples for quantifying the underlying difficulty of the
reweighting problem.

Finally, given the central role of restrictions on the outcome model in both
of the previous results, we briefly consider the setting in which this
assumption is incorrect. In particular, we provide simple moment conditions
under which we can retain a finite bound on the error when the true outcome
model is not in the assumed class.

###  1.2 Related work

Estimators that target balance. Many reweighting estimators in causal
inference explicitly target the discrepancy between source and target
distribution, also known as _balance_ (Hainmueller, 2012; Zubizarreta, 2015;
Athey et al., 2018; Hirshberg et al., 2019; Zhao, 2019; Tan, 2020; Hazlett,
2020; Arbour et al., 2021). See Ben-Michael et al. (2021) for a summary. The
literature on domain adaptation also uses worst-case discrepancy between
distributions (Mansour et al., 2009; Gretton et al., 2009; Yu and Szepesvári,
2012; Courty et al., 2014). Some approaches learn representations that
minimize these discrepancies (Ganin et al., 2016; Shen et al., 2018; Assaad et
al., 2021). Closely related are estimators that target the density ratio
between two groups through a surrogate loss (Sugiyama et al., 2007b; Nguyen et
al., 2010; Sugiyama et al., 2012).

Overlap in causal inference and adversarial training. Many existing
theoretical treatments of balancing weights require the density ratio to exist
(called _overlap_ in causal inference), which is typically used for proving
asymptotic consistency (see Hirshberg et al., 2019; Kallus, 2020b). This
assumption, however, can be highly restrictive especially in high-dimensions,
as illustrated by D’Amour et al. (2021). See also Khan and Tamer (2010) for a
discussion of the implications of overlap violations for causal inference. The
same topic arises in adversarial training. See, for example, Dupuis and Mao
(2019); Birrell et al. (2020a), who generalize $\phi$-divergences to
distributions that do not have common support. This idea is applied to GANs in
Song and Ermon (2020); Glaser et al. (2021).

Domain adaptation and causal inference. We emphasize that domain adaptation
and causal inference are both special cases of the same problem setup. Related
work combines ideas from these two literatures. For example, Shalit et al.
(2017); Johansson et al. (2020) use integral probability metrics to estimate
causal effects without the need for an overlap assumption. The same idea is
used in Kallus (2020b) for matching estimators in causal inference. Other work
has made the connection between causal inference and adversarial training
(Yoon et al., 2018; Ozery-Flato et al., 2018).

##  2 Problem Setup

Let $X\in\mathcal{X}$ denote covariates, and $Y\in\mathbb{R}$ denote outcomes.
We study the general class of problems with source and target populations, $P$
and $Q$, with different joint distributions over $X$ and $Y$. We observe $X$
in both populations, but only observe the outcomes, $Y$, for the source
population, $P$. The goal is to estimate the missing mean in the target
population, $\mathbb{E}_{Q}[Y]$. Many important problems share this structure,
including causal inference and domain adaptation.

######  Problem Setting 1 (Causal Inference).

Consider the causal inference setting with a binary treatment status variable,
$T$, and potential outcomes $Y(0)$ and $Y(1)$. For the control group, we
observe covariates $X$ and the potential outcome $Y(0)$. In the treated group,
we still observe $X$ but do not observe $Y(0)$. Therefore, finding the average
treatment effect on the treated is equivalent to solving the problem setup
described above, where $P$ corresponds to the $T=0$ population, $Q$
corresponds to the $T=1$ population, and $Y$ corresponds to $Y(0)$.

######  Problem Setting 2 (Domain Adaptation).

Consider a classification task with features $X$, labels $Z$, and loss
function $\ell$. In a source environment where we observe both $X$ and $Z$, we
train a model $h$ for predicting $Z$ given $X$. We would like to estimate the
average risk of our classifier in a new environment where we observe $X$ but
not $Z$. This problem is equivalent to the setup above, where $P$ corresponds
to the source environment, $Q$ corresponds to the target environment, and $Y$
corresponds to the loss, $\ell(h(X),Z)$.

###  2.1 Ignorability and Overlap

To estimate the mean of $Y$ in $Q$ using the outcomes from $P$, we require
some kind of regularity between the source and target populations. A common
assumption is the _ignorability_ assumption (also called the _covariate shift_
assumption, or _selection on observables_), which requires the relationship
between covariates and outcomes to be the same across the two groups:

######  Assumption 1 (Ignorability).

For all $x\in\mathcal{X}$,

$\displaystyle P(Y|X=x)=Q(Y|X=x).$

Notice that in the causal inference setting described above, Assumption 1 is
equivalent to the standard conditional independence assumption,
$Y(0){\perp\\!\\!\\!\perp}T|X$.

Typically, Assumption 1 is paired with a requirement that the density ratio
$dQ/dP$ exists, also known as _overlap_ or _continuity_ in different
literatures:

######  Definition (Overlap).

We say that _overlap_ holds if $Q$ is absolutely continuous with respect to
$P$.

###  2.2 Importance Weighting

In the special case where Assumption 1 and overlap hold, we can estimate the
mean of the missing outcomes by reweighting the observed outcomes with the
density ratio. This estimator is called _importance weighting_ or _inverse
probability weighting_ (IPW) and is unbiased:

$\displaystyle\mathbb{E}_{P}\left[\frac{dQ}{dP}(X)\hskip 2.84544ptY\right]$
$\displaystyle=\mathbb{E}_{P}\left[\frac{dQ}{dP}(X)\hskip
2.84544pt\mathbb{E}_{P}[Y|X]\right]$
$\displaystyle=\mathbb{E}_{Q}[\mathbb{E}_{P}[Y|X]]=\mathbb{E}_{Q}[Y],$

where we use ignorability for the last equality.

Importance weighting has two main drawbacks. First, the overlap assumption is
very strong, especially in high dimensions (D’Amour et al., 2021). But even if
overlap holds in the super-population, in finite samples there are usually so-
called practical overlap violations: regions of the covariate space that are
well-represented in the target population, but very rare in the source
population, leading to large importance weights.

###  2.3 Mean Squared Error

Large weights lead to large mean squared error. Consider arbitrary weights
$w(X)$. We will expand the mean squared error (MSE) of $\mathbb{E}_{P}[w(X)Y]$
for estimating $\mathbb{E}_{Q}[Y]$ using the standard bias-variance
decomposition. Define the _outcome function_ ,
$f_{0}(x)\coloneqq\mathbb{E}_{P}[Y|X=x]=\mathbb{E}_{Q}[Y|X=x]$ and likewise,
let $\sigma^{2}_{0}(x)$ be the conditional variance of $Y$. Then,

$\displaystyle\text{MSE}(w)$
$\displaystyle=\mathbb{E}_{P}[(w(X)Y-\mathbb{E}_{Q}[Y])^{2}]$
$\displaystyle=(\mathbb{E}_{P}[w(X)Y]-\mathbb{E}_{Q}[Y])^{2}+\text{Var}_{P}[w(X)Y]$
$\displaystyle=(\mathbb{E}_{P}[w(X)f_{0}(X)]-\mathbb{E}_{Q}[f_{0}(X)])^{2}$
(1) $\displaystyle\;\;\;+\mathbb{E}_{P}[w(X)^{2}\sigma^{2}_{0}(X)].$ (2)

The MSE depends on two quantities: (1) the imbalance of the mean of the
outcome function $f_{0}$ between the re-weighted source distribution and the
target distribution; and (2) the variability of the weights under the source
distribution, which amplifies the noise in the outcomes. With practical
overlap violations in high dimensional problems, $w=dQ/dP$ can be enormous,
and (2) will result in a large MSE (see, for example, Kang et al., 2007).
Balancing weights, introduced in Section 3, explicitly target the trade-off
between bias and variance, as discussed extensively in Kallus (2020b).

###  2.4 Notation

We now introduce formal notation used for the remainder of the paper. Let
$(\mathcal{X},\mathcal{S})$ be a measurable space.111To side-step topological
issues, we assume that $\mathcal{X}$ is a separable Banach space. Let $P$ and
$Q$ be given probability measures on $(\mathcal{X},\mathcal{S})$. Let $f_{0}$
be a real-valued measurable function on $\mathcal{X}$. Denote
$\mathcal{M}(\mathcal{X})$ the space of signed finite measures on
$(\mathcal{X},\mathcal{S})$ and $\mathcal{M}(P)$ those absolutely continuous
with respect to $P$. Denote $\mathcal{P}(\mathcal{X})$ the space of
probability measures on $(\mathcal{X},\mathcal{S})$ and $\mathcal{P}(P)$ those
absolutely continuous with respect to $P$.

With a slight abuse of notation, for measurable
$f:\mathcal{X}\rightarrow\mathbb{R}$ and _both_ $M\in\mathcal{M}(\mathcal{X})$
and $M\in\mathcal{P}(\mathcal{X})$, we will write
$\mathbb{E}_{M}[f]\coloneqq\int_{\mathcal{X}}f(x)dM(x)$. We assume
$\mathbb{E}_{P}[|f_{0}|]<\infty$ and $\mathbb{E}_{Q}[|f_{0}|]<\infty$.

While our setting is quite general, it may be helpful for the reader to keep
in mind the case where $\mathcal{X}$ is finite and discrete with cardinality
$n$. In this case, $P$ and $Q$ are probability vectors of length $n$ and
measurable functions are simply vectors in $\mathbb{R}^{n}$. Likewise,
$\mathcal{M}(\mathcal{X})$ is just $\mathbb{R}^{n}$.

##  3 Balancing Weights

In this section, we briefly review the existing work on balancing weights
estimators and then introduce our main contributions. Balancing weights
estimators find weights $w(X)$ with minimum dispersion, subject to a balance
constraint between the target covariate distribution and the reweighted source
distribution. In general, we will consider weights such that
$\mathbb{E}_{P}[w(X)]=1$, i.e., we always end up with the same “size”
population that we started with. The problem of choosing weights can be
reformulated as finding a measure $R\in\mathcal{M}(P)$ such that
$\int_{\mathcal{X}}dR(x)=1$, with $w\coloneqq dR/dP$. This corresponds to the
intuition behind reweighting as creating a “pseudo-population” based on $P$
intended to match $Q$. We will therefore often use $w$ and $R$ interchangably.

A simple balancing weights estimator might constrain the mean of the
covariates to match within tolerance $\delta$, similarly to Zubizarreta
(2015). For example, let $\mathcal{X}=\mathbb{R}^{d}$. We could find the
minimum variance $w$ such that

$\displaystyle\|\mathbb{E}_{R}[X]-\mathbb{E}_{Q}[X]\|_{2}\leq\delta,$ (3)

where, as a reminder, $w=dR/dP$. If the outcome function $f_{0}(X)$ is linear
with bounded coefficients, then this constraint will bound the bias term (2)
and the tuning parameter $\delta$ lets us trade-off bias and variance to
achieve a smaller MSE than the importance weights.

###  3.1 Assumptions on the Outcome Function

More generally, we may not want to assume that $f_{0}$ is linear. But this
presents a difficulty: without any further restrictions, for any $w\neq
dQ/dP$, there always exists an adversarial $f_{0}$ that can make the bias term
(1) arbitrarily large. Only the density ratio guarantees bounded bias for
_any_ $f_{0}$, but often at the cost of high variance.

Therefore, in practical settings, we instead restrict the outcome function in
order to control the error. To make progress, we assume that $f_{0}$ belongs
to some function class $\mathcal{F}$:

######  Assumption 2.

The outcome function $f_{0}$ belongs to $\mathcal{F}$ where $\mathcal{F}$ is a
closed and convex set of measurable real-valued functions such that for all
$f\in\mathcal{F}$, $\mathbb{E}_{P}[|f|]<\infty,\mathbb{E}_{Q}[|f|]<\infty$,
and $-f\in\mathcal{F}$.

For the causal inference problem setting, Assumption 2 requires making an
assumption about the relation of the potential outcome $Y(0)$ to the
covariates. For the domain adaptation problem setting, the assumption is about
the relationship between the accuracy of a predictor, $\ell(h(X),Z)$, to its
input features, $X$.

Many choices of $\mathcal{F}$ in Assumption 2 are quite general and
justifiable with domain knowledge. Some examples for $0<B<\infty$ are:

Bounded functions:
$\displaystyle\mathcal{F}_{\infty}\coloneqq\\{f:\|f\|_{\infty}\leq B\\}$
Lipschitz functions:
$\displaystyle\mathcal{F}_{\text{Lip(c)}}\coloneqq\\{f:\|f\|_{\text{Lip(c)}}\leq
B\\}$ RKHS functions:
$\displaystyle\mathcal{F}_{\mathcal{H}}\coloneqq\\{f:\|f\|_{\mathcal{H}}\leq
B\\},$

where $\|\cdot\|_{\text{Lip(c)}}$ denotes the Lipschitz constant with respect
to a metric $c$ and $\|\cdot\|_{\mathcal{H}}$ denotes the norm in some
Reproducing Kernel Hilbert Space (RKHS), $\mathcal{H}$.

Under Assumption 2, the bias is bounded by the worst-case discrepancy in means
over $\mathcal{F}$. This quantity is called an _integral probability metric_
(IPM), defined for any set of functions, $\mathcal{G}$, and any
$M,N\in\mathcal{M}(\mathcal{X})$ as:222If
$g\in\mathcal{G}\implies-g\in\mathcal{G}$ then the absolute value can be
omitted.

$\displaystyle\text{IPM}_{\mathcal{G}}(M,N)\coloneqq\sup_{g\in\mathcal{G}}\big{\\{}|\mathbb{E}_{M}[g]-\mathbb{E}_{N}[g]|\big{\\}}.$

The bias term (1) for a re-weighted population $R$ under Assumption 2 is
upper-bounded by:

$\displaystyle\left|\mathbb{E}_{Q}[f_{0}]-\mathbb{E}_{R}[f_{0}]\right|\leq\text{IPM}_{\mathcal{F}}(Q,R).$
(4)

This value is always finite by our assumptions on $\mathcal{F}$ and we can
trade it off against the variance of the weights.

Before introducing the general form of balancing weights in Section 3.2, we
define two quantities that will be useful in our discussion below, the maximum
and minimum bias.

######  Definition (Maximum and minimum bias).

The maximum bias, $\delta_{\max}$, is the bias under uniform weights (when
$R=P$). The minimum bias, $\delta_{\min}$, is the smallest bias achieveable by
reweighting $P$.

$\displaystyle\delta_{\max}$
$\displaystyle\coloneqq\text{IPM}_{\mathcal{F}}(Q,P)$ (5)
$\displaystyle\delta_{\min}$
$\displaystyle\coloneqq\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}\text{IPM}_{\mathcal{F}}(Q,R)\big{\\}}.$
(6)

Since $R=P$ is feasible for (6), $\delta_{\min}\leq\delta_{\max}$. In the
special case where overlap holds, $R=Q$ is also feasible, which implies
$\delta_{\min}=0$.

###  3.2 Minimax Balancing Weights

Assumption 2 and the resulting IPM bound on the bias (4) lead to a generalized
balancing weights estimator as discussed in Kallus (2020b) and Ben-Michael et
al. (2021). Define
$\sigma^{2}\coloneqq\sup_{x\in\mathcal{X}}\sigma^{2}_{0}(x)$, where we assume
$0<\sigma^{2}<\infty$. We can plug these bounds into the MSE to arrive at the
following optimization problem:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\Bigg{\\{}\text{IPM}_{\mathcal{F}}$
$\displaystyle(Q,R)^{2}+\sigma^{2}\mathbb{E}_{P}\left[\left(\frac{dR}{dP}\right)^{2}\right]\Bigg{\\}}$
(7)

A solution always exists because the objective is finite for $R=P$, which is
feasible. For $\sigma^{2}>0$, the problem is strongly convex in $R$ and has a
unique solution. Since the IPM term is itself a supremum, this estimator is
sometimes referred to as minimax balancing weights.

Furthermore, $\exists\delta>0$ such that (7) has the same minimizer as:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}$
$\displaystyle\mathbb{E}_{P}\left[\left(\frac{dR}{dP}\right)^{2}\right]$ (8)
such that $\displaystyle\text{IPM}_{\mathcal{F}}(Q,R)\leq\delta.$

We view $\sigma^{2}$ and $\delta$ as exchangeable tuning parameters:
$\sigma^{2}$ represents the importance of reducing the variance of the
weights; $\delta$ represents the level of acceptable bias. For
$\sigma^{2}\in(0,\infty)$, the corresponding $\delta$ lies in
$(\delta_{\min},\delta_{\max})$.

###  3.3 Our Contributions

In this paper, we start from the premise that Assumption 2 is necessary to
achieve a reasonable MSE in high dimensions leading to estimators (7) and (8).
Our main argument is that Assumption 2 immediately implies two additional
results.

First, we derive a general duality result that lets us rewrite problems (7)
and (8) as a single convex optimization problem over $\mathcal{F}$. Therefore,
we can solve the minimax balancing weights problem by optimizing a simple
convex loss over a function class. Furthermore, this reformulation shows that
the optimal weights are always a rescaled and recentered member of
$\mathcal{F}$.

Second, we no longer need an overlap assumption. Before restricting $f_{0}$,
we saw that only $w=dQ/dP$ could guarantee finite bias. Therefore, to bound
the MSE we needed the density ratio to exist. But once we assume that
$f_{0}\in\mathcal{F}$, we no longer need the density ratio to exist, and we
can simply minimize our bound on the MSE directly. Moreover, we argue that
Assumption 2 provides us with a more appropriate _quantitative_ measure of
overlap — the minimum bias, $\delta_{\text{min}}$ — that precisely
characterizes the difficulty of translating results from one distribution to
another.

##  4 Duality Theory for Balancing Weights

In this section, we derive a dual characterization of the solution, $R^{*}$,
to problems (7) and (8) and the corresponding minimax weights
$w^{*}=dR^{*}/dP$.

###  4.1 The Variance of the Weights

Our dual derivation uses the fact that the variance term can be written as a
special case of a class of information-theoretic divergences called
$\phi$-divergences (Sriperumbudur et al., 2009). These have a variational
representation that will allow us to simplify the minimax problems (7) and (8)
into a single convex loss.

######  Definition ($\phi$-Divergence).

For any convex function $\phi$ with $\phi(1)=0$, the $\phi$-_divergence_
between $M\in\mathcal{M}(\mathcal{X})$ and $N\in\mathcal{P}(\mathcal{X})$ is:

$\displaystyle
D_{\phi}(M||N)\coloneqq\mathbb{E}_{N}\left[\phi\left(dM/dN\right)\right],$

where $D_{\phi}(M||N)=\infty$ if $M$ is not absolutely continuous with respect
to $N$.

Notice that we can subtract off a constant to re-center our variance term in
(8) without affecting the minimizer over $R$. We can then rewrite the
objective as the divergence between $R$ and $P$ with $\phi(x)=x^{2}-1$. This
is known as the $\chi^{2}$ divergence, and we denote it $D_{2}(R||P)$:

$\displaystyle\mathbb{E}_{P}\left[\left(\frac{dR}{dP}\right)^{2}-1\right]=D_{2}(R||P).$

#### Variational representations.

It is possible to express $\phi$-divergences in a dual form, called a
_variational representation_ , as a supremum over measurable functions. Let
$M\in\mathcal{M}(\mathcal{X})$ and let $N\in\mathcal{P}(\mathcal{X})$. Let
$\phi^{*}$ denote the convex conjugate of $\phi$. Then Keziou (2003) and
Nguyen et al. (2005) show that:

$\displaystyle
D_{\phi}(M||N)=\sup_{f}\big{\\{}\mathbb{E}_{M}[f]-\mathbb{E}_{N}[\phi^{*}(f)]\big{\\}},$
(9)

where the supremum is over all real-valued measurable functions on
$\mathcal{X}$. If we additionally assume, as we do for $R$, that
$\mathbb{E}_{M}[1]=1$, then we have the tighter representation,

$\displaystyle
D_{\phi}(M||N)=\sup_{f}\big{\\{}\mathbb{E}_{M}[f]-\Lambda_{N}^{\phi}[f]\big{\\}}$
(10) $\displaystyle\text{ where
}\Lambda_{N}^{\phi}[f]\coloneqq\inf_{\lambda\in\mathbb{R}}\\{\lambda+\mathbb{E}_{N}[\phi^{*}(f-\lambda)]\\}.$

This result, using the infimum over $\lambda$ in the spirit of Ruderman et al.
(2012), appears to have been independently proposed by Agrawal and Horel
(2020) and Birrell et al. (2020b). Under minimal conditions on $\phi$, the
suprema in (9) and (10) are achieved by $\phi^{\prime}(dM/dN)$.

###  4.2 Dual Formulation

We now present our main duality result under Assumption 2 where
$f_{0}\in\mathcal{F}$.

######  Theorem 4.1.

Under Assumptions 1 and 2, for $\delta>\delta_{\min}$, the optimization
problem (8) has a unique solution,

$\displaystyle\frac{dR^{*}}{dP}=1+\left(\frac{\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\delta}{\text{Var}_{P}[f^{*}]}\right)\left(f^{*}-\mathbb{E}_{P}[f^{*}]\right),$

where, for a unique $\mu\geq 0$ corresponding to $\delta$, $f^{*}$ achieves
the following supremum:

$\displaystyle\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f]\Big{\\}}.$
(11)

The resulting MSE is:

MSE
$\displaystyle(R^{*})\leq\delta^{2}+\sigma^{2}\frac{(\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\delta)^{2}}{\text{Var}_{p}[f^{*}]}.$
(12)

Proof Sketch. The full proof is available in the Appendix. Here we provide a
brief outline. In the first step, we show that problem (8) is equivalent to:

$\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]+\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{(1/\mu)D_{2}(R||P)-\mathbb{E}_{R}[f]\\}\Big{\\}}$

for some $\mu>0$ corresponding to $\delta$. In the second step, we apply (10)
for the $\chi^{2}$ divergence to show that the inner subproblem has an
explicit solution:

$\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{(1/\mu)D_{2}(R||P)-\mathbb{E}_{R}[f]\\}=-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f].$

The theorem then follows from standard convex duality results.

######  Remark 4.1 (The Shape of the Weights).

The weights $dR^{*}/dP$ are equal to $f^{*}$ multiplied by some scalar $s_{1}$
and then shifted by some scalar $s_{2}$:

$\displaystyle\frac{dR^{*}}{dP}=s_{1}+s_{2}f^{*},$

where $s_{1}$ and $s_{2}$ depend on both $\delta$ and $f^{*}$. Therefore, if
we assume $\mathcal{F}$ is the set of quadratic functions, then the balancing
weights will also be quadratic, and if we assume $\mathcal{F}$ is an RKHS with
a certain kernel, then the balancing weights will belong to an RKHS with that
same kernel.

######  Remark 4.2 (Other $\phi$-Divergences).

We can replace the $\chi^{2}$ divergence in the balancing weight problems (7)
and (8) with other $\phi$-divergences. A duality result corresponding to
Theorem 4.1 will hold for any convex function $\phi$ such that $\phi(1)=0$
with convex conjugate $\phi^{*}$ such that $\\{\phi^{*}<\infty\\}=\mathbb{R}$.
See the Appendix for details. We can use this general formulation to derive
corresponding duality results for entropy balancing (Hainmueller, 2012) or
other measures of dispersion (see Ben-Michael et al., 2021).

######  Remark 4.3 (Tuning Parameters).

For every $\delta$ there is a unique corresponding $\mu$. Therefore, we can
treat $\mu$ as a tuning parameter instead of $\delta$ and solve (11) directly.
In terms of $\mu$, the solution to (8) is:

$\displaystyle\frac{dR^{*}}{dP}=1+\frac{\mu}{2}\left(f^{*}-\mathbb{E}_{P}[f^{*}]\right)$
(13)

and there is a closed form relationship between $\mu$ and $\delta$ given by:

$\delta=\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\frac{\mu}{2}\text{Var}_{P}[f^{*}].$

Going forward, we will often use $\delta$ and $\mu$ interchangeably.

###  4.3 The Full Information Case

To help illustrate Theorem 4.1, consider the simplified setting where we know
$f_{0}$ exactly. This corresponds to a special case of Assumption 2 where
$\mathcal{F}$ is the convex hull of $\\{f_{0},-f_{0}\\}$. Assume without loss
of generality that $\mathbb{E}_{Q}[f_{0}]\geq\mathbb{E}_{P}[f_{0}]$. Then,
applying Theorem 4.1, we get $f^{*}=f_{0}$, and

$\displaystyle\frac{dR^{*}}{dP}=1+\left(\frac{\mathbb{E}_{Q}[f_{0}]-\mathbb{E}_{P}[f_{0}]-\delta}{\text{Var}_{P}[f_{0}]}\right)\left(f_{0}-\mathbb{E}_{P}[f_{0}]\right).$

The optimal weights are always a rescaled and recentered version of $f_{0}$.
In this special case, the dual optimal $f^{*}$ does not depend on $\delta$;
only the scaling factor does. Therefore, the MSE bound (12) becomes a
quadratic in $\delta$ and we can solve for the optimal bias:

$\displaystyle\delta^{*}=\left(\frac{\sigma^{2}}{\text{Var}_{P}[f_{0}]+\sigma^{2}}\right)|\mathbb{E}_{Q}[f_{0}]-\mathbb{E}_{P}[f_{0}]|,$

which gives

MSE
$\displaystyle(w^{*})\leq\left(\frac{\sigma^{2}}{\text{Var}_{P}[f_{0}]+\sigma^{2}}\right)(\mathbb{E}_{Q}[f_{0}]-\mathbb{E}_{P}[f_{0}])^{2}.$

This is an independently interesting result. With complete information, we can
analytically find the optimal bias-variance trade-off. Under homoskedasticity,
these weights have the smallest possible MSE over all $w$ such that
$\mathbb{E}_{P}[w]=1$.

###  4.4 The Linear Case

For a second simple example, we return to the linear problem in (3). In this
case, duality shows that balancing weights are equivalent to fitting a linear
model. In fact, for a certain choice of linear $\mathcal{F}$, problem (11) is
identical to linear regression.

Let $g:\mathcal{X}\rightarrow\mathbb{R}^{d}$ be some feature map. Assume that
our balance constraint is:

$\|\mathbb{E}_{R}[g(X)]-\mathbb{E}_{Q}[g(X)]\|_{2}\leq\delta.$

This is equivalent to problem (8) using the following linear function class:

$f_{0}\in\mathcal{F}_{\text{lin}}=\left\\{\beta^{T}g(X):\|\beta\|_{2}\leq
1\right\\}.$

Applying Theorem 4.1, we know
$f^{*}=(\beta^{*})^{T}g(X)\in\mathcal{F}_{\text{lin}}$ and therefore the
optimal weights will be linear. Solving (11) via calculus, we get:

$\beta^{*}=c_{1}(\text{Cov}_{P}[g(X)]+c_{2}I)^{-1}(\mathbb{E}_{Q}[g(X)]-\mathbb{E}_{P}[g(X)])$

for some scalars $c_{1}$ and $c_{1}$ that depend on $\mu$. Notice the
dependence on the inverse of the covariance of the features plus a
regularization term. This is another way of deriving a well-known result: for
$\mathcal{F}_{\text{lin}}$, problem (8) is identical to estimating
$\mathbb{E}_{Q}[Y]$ by fitting a ridge regression in the $P$ population and
then applying it to the $Q$ population. See Kallus (2020b) for a direct proof.
If we replace the $\ell_{2}$-norm with the $\ell_{1}$-norm, we obtain a
similar equivalence for Lasso. When the regularization term is $0$, we obtain
linear regression as a special case.

Several other papers have recognized the duality between linear regression and
balancing weights estimators for a linear function class; see Zhao and
Percival (2017); Zhao (2019); Wang and Zubizarreta (2020); Tan (2020); Ben-
Michael et al. (2021). Theorem 4.1 generalizes these existing duality results
for linear function classes to general function classes $\mathcal{F}$.

##  5 Outcome Assumptions and Overlap

In this section, we discuss the implications of the outcome assumption for
overlap. First, we show that if overlap holds, then under conditions on
$\mathcal{F}$, as $\delta\rightarrow 0$, the balancing weights converge to the
importance weights $dQ/dP$.

However, when overlap is violated, the only impact on the balancing weights
estimator is that the minimum bias (which depends on our function class
$\mathcal{F}$) is greater than zero. Due to Assumption 2, for any
$\delta>\delta_{\min}$ there still exists a solution to (8) that bounds the
MSE. If the variance of the outcomes is large, then we naturally want to
choose $\delta$ larger than $\delta_{\min}$ and the failure of overlap has no
impact on our estimator.

Instead, we argue that we should use the minimum bias, $\delta_{\min}$,
directly as a measure of practical overlap violations. We illustrate that in
finite samples, $\delta_{\min}$ can be large even when overlap holds in the
super population, and likewise that $\delta_{\min}$ can be small even when
overlap is violated in the super population. Therefore, under Assumption 2,
$\delta_{\min}$ is a more precise summary of the underlying difficulty of the
reweighting problem.

###  5.1 Convergence to Importance Weights

We begin with an example. Let $\mathcal{X}=\mathbb{R}$. Let $P$ be Gaussian
with mean $1$ and variance $1$, let $Q$ be Gaussian with mean $2$ and variance
$1$, and let $p$ and $q$ denote their densities. Let
$\mathcal{F}=\\{f:\|f\|_{\infty}\leq 1\\}$ so that the outcome function is
bounded between $-1$ and $1$. The solution to the dual problem, $f^{*}$, and
the corresponding optimal weights are illustrated in Figure 1.

Figure 1: The optimal weights and corresponding dual optimal function for the
Gaussian example, with $\delta$ starting at $\delta_{\max}$ and shrinking
towards zero.

The weights have a distinctive form. When $\delta=\delta_{max}$, the optimal
weights are uniform. As the allowed bias $\delta$ decreases, the optimal
weights trace out the density ratio $dQ/dP$ but truncated above and below.
This is the form of a well-known estimator in the causal inference literature,
IPW with a trimmed propensity score (Yang and Ding, 2018): under Assumption 2
with bounded functions, the balancing weights formulation provides formal
justification for using the truncated density ratio for weights. As
$\delta\rightarrow 0$, the optimal weights converge to $dQ/dP$.

In general, convergence to the importance weights will _always_ occur as
$\delta\rightarrow 0$ under certain conditions on $\mathcal{F}$.

######  Definition (Distribution-defining).

$\mathcal{F}$ is _distribution-defining_ if $\forall
M,N\in\mathcal{P}(\mathcal{X})$, $\text{IPM}_{\mathcal{F}}(M,N)=0$ if and only
if $M=N$.

For example, $\mathcal{F}_{\infty}$ and $\mathcal{F}_{\text{Lip(c)}}$ are
distribution-defining, as is $\mathcal{F}_{\mathcal{H}}$ for a universal
kernel. When $\mathcal{F}$ is distribution-defining then only $dQ/dP$ can
achieve worst-case bias zero. Therefore, when overlap holds and $\mathcal{F}$
is distribution-defining, the optimal weights, $w^{*}\rightarrow dQ/dP$ as
$\delta\rightarrow 0$.

This connection between balancing weights and the density ratio is not new:
among others, Zhao (2019) makes a similar point. We discuss the connections to
our duality result in the Appendix.

###  5.2 Balancing Weights Without Overlap

What if overlap does not hold? Then if $\mathcal{F}$ is distribution-defining,
by definition, $\delta_{\min}>0$. In this case, problem (8) still has a
solution that bounds the MSE for any $\delta\geq\delta_{\min}$, but the
failure of overlap precludes us from using $\delta=0$. However, the motivation
behind balancing weights is to avoid using an unbiased estimator: if the
variance of the outcomes is sufficiently high, we might still prefer to use
$\delta>\delta_{\min}$.

Consider a simple example in which we reweight $P=\text{Uniform}(1,2)$ to
target $Q=\text{Uniform}(1.01,2.01)$. While $Q$ is not absolutely continuous
with respect to $P$, intuitively, we should be able to find $w$ that achieves
small error because the distributions are close to each other. The function
class $\mathcal{F}$ provides a formal definition of “close to each other” for
the purposes of reweighting.

For these uniform $P$ and $Q$, there is an irreducible bias, $\delta_{\min}$,
for any possible weights:

$\delta_{\min}=\sup_{f\in\mathcal{F}}\int_{1}^{1.01}f(x)dx+\sup_{f\in\mathcal{F}}\int_{2}^{2.01}f(x)dx$

If $\mathcal{F}$ is unrestricted, then $f$ could take on arbitrarily large
values on the intervals $[1,1.01]$ and $[2,2.01]$. Therefore, the bias is
unbounded without Assumption 2, which typically justifies imposing an overlap
assumption. However, if we assume $\mathcal{F}\in\\{f:\|f\|_{\infty}\leq
B\\}$, for example, then we have $\delta_{\min}=0.02B$ which may be quite
small.

The parameter $\delta>\delta_{\min}$ in problem (8) is a tuning parameter that
trades off bias and variance. If the variance of the outcomes is very large,
then we may prefer to use a value of $\delta$ larger than $\delta_{\min}$. In
this case, the overlap violation would not have any impact on our estimator at
all. On the other hand, if the variance of the outcomes is small relative to
$\delta_{\min}$, we may prefer to use a value of $\delta$ close to $0$. The
best we could do would be to set $\delta=\delta_{\min}$; without overlap, the
best achievable lower bound for the MSE is $\delta_{\min}^{2}$.

###  5.3 Quantitative Overlap

In finite samples, we argue that $\delta_{\min}$ will often be a more useful
measure of overlap than the existence of the density ratio in a super-
population. For example, let $P_{\text{super}}=\mathcal{N}(100,1)$ and
$Q_{\text{super}}=\mathcal{N}(-100,1)$. Technically, overlap holds and the
density ratio exists over all of $\mathbb{R}$. For concreteness, let
$\mathcal{F}=\mathcal{F}_{\mathcal{H}}$ be an RKHS with a Gaussian kernel.
Then for $P_{\text{super}}$ and $Q_{\text{super}}$, $\delta_{\min}=0$, because
$w=dQ/dP$ will perfectly balance the RKHS. However, any finite dataset will
have severe practical overlap violations. Let $P$ be a sample of $n$ data
points from $P_{\text{super}}$ and likewise for $Q$. With high probability,
the points in $P$ and the points in $Q$ will be far apart, and as a result,
$\delta_{\min}$ over the RKHS will be large.

On the other hand, if we let $P_{\text{super}}=\text{Uniform}(1,2)$ and
$Q_{\text{super}}=\text{Uniform}(1.01,2.01)$, overlap does not hold and
$\delta_{\min}$ will be non-zero for the super-population. But, for
corresponding finite samples $P$ and $Q$, $\delta_{\min}$ is still likely to
be very small. In these examples, super-population overlap is misleading,
whereas $\delta_{\min}$ is a precise quantitative summary of the difficulty of
the reweighting problem for function class $\mathcal{F}$.

##  6 IHDP Example

In this section, we walk through an example on a real dataset to make the
previous two sections more concrete. We apply balancing weights to the Infant
Health and Development Program (IHDP) using an RKHS function class.

###  6.1 The IHDP Dataset and Setup

The Infant Health and Development Program (IHDP) data set is a standard
observational causal inference benchmark from Hill (2011), based on data from
a randomized control trial of an intensive home visiting and childcare
intervention for low birth weight infants born in 1985. We consider a non-
experimental subset of the original data with $n_{0}=608$ children assigned to
control, $n_{1}=139$ children assigned to treatment, and $n=747$ total
children. For all children, we have a range of baseline covariates, including
both categorical covariates, like the mother’s educational attainment, and
continuous covariates, like the child’s birth weight. Our goal is to estimate
the average outcome (a standardized test score) in the absence of the
intensive intervention. We observe this outcome for the 608 control children,
and want to re-weight these observations to estimate the missing mean for the
139 treated children.

To do so, we use an RKHS as a flexible but tractable functional form for
$f_{0}$. In particular, we assume that
$\mathcal{F}=\mathcal{F}^{B}_{\mathcal{H}}\coloneqq\\{f:\|f\|_{\mathcal{H}}\leq
B\\}$ for $B<\infty$, where $\mathcal{H}$ is the RKHS induced by the Gaussian
kernel,

$\mathcal{K}(x_{1},x_{2})=\exp\left(-\frac{1}{2}\|x_{1}-x_{2}\|_{2}^{2}\right).$

Define $K\in\mathbb{R}^{n\times n}$ with $K_{ij}=\mathcal{K}(X_{i},X_{j})$.
Then for any $f\in\mathcal{F}$, there exists an $\alpha\in\mathbb{R}^{n}$ such
that $\alpha^{T}K\alpha\leq B$ and
$f(X_{j})=\sum_{i=1}^{n}\alpha_{i}K_{ij},\forall j.$

###  6.2 Solving the Dual Problem

We compute the minimax balancing weights by solving the dual problem (11)
directly for many values of the tuning parameter $\mu>0$. The dual problem can
be written as a quadratic optimization problem over the vectors $\alpha$ that
characterize the $f\in\mathcal{F}$. See the Appendix for details. We obtain
the corresponding optimal weights by plugging the resulting $f^{*}$ into (13).

The balancing weights interpolate between two extremes. See Figure 2 for an
illustration. At one extreme are the weights with maximum bias and minimum
variance. This is achieved at $\mu=0$, which results in uniform weights and
corresponding bias $\delta=\delta_{\max}$.

At the other extreme are the weights with maximum variance and minimum bias.
Since some of the covariates are continuous, the data points for the control
and treated groups have disjoint support. Therefore, there are no weights that
achieve zero bias. Instead, we find weights that achieve the smallest possible
bias over $\mathcal{F}^{B}_{\mathcal{H}}$, $\delta_{\min}$, which will
correspond to some $\mu=\mu_{\max}<\infty$. We find $\mu_{\max}$ by increasing
$\mu$ until the bias stops decreasing. The corresponding weights are shown in
black in Figure 2.

The function class $\mathcal{F}^{B}_{\mathcal{H}}$ has the nice property that
the worst-case bias scales with the norm bound $B$,
$\text{IPM}_{\mathcal{F}^{B}_{\mathcal{H}}}(R,Q)=B\cdot\text{IPM}_{\mathcal{F}^{1}_{\mathcal{H}}}(R,Q)$.
Furthermore, regardless of $B$, the optimal weights remain identical.
Therefore, we can report the bias as a fraction of the size of functions in
$\mathcal{F}$. For the IHDP data, $\delta_{\max}=0.102B$ and
$\delta_{\min}=0.089B$ with corresponding variances $\sigma^{2}$ (with uniform
weights) and $1.7\sigma^{2}$. For this particular problem, we achieve most of
the bias reduction with smaller weights: the intermediate weights in Figure 2
have $\delta=0.090B$ with variance $1.35\sigma^{2}$, highlighting the
relevance of the bias-variance trade-off.

In any real data set with continuous covariates, two finite samples will
typically have disjoint support like we have here. The standard approach in
causal inference is to assume that overlap holds in the super-populations from
which the samples were drawn. In this case, we could approximate the density
ratio asymptotically. However, as we emphasized in Section 5.3, the
implications of overlap for balancing weights are entirely summarized by
$\delta_{\min}$ so we do not need to make such an assumption.

Figure 2: The optimal weights and corresponding dual optimal function for the
IHDP example for the extreme values of $\mu$ and one intermediate value.

######  Remark 6.1 (Computational Advantages of the Dual).

For an RKHS, there is a closed form of the IPM, which makes the primal and
dual problems equally easy to solve. But in some situations, it is
computationally easier to solve the dual problem (11) directly instead of the
primal problem (8). Consider a class of neural networks parameterized by
bounded network weights $\theta$. Then handling the IPM constraint in the
primal problem requires adversarial training, as in Kallus (2020a), which can
be quite computationally challenging. On the other hand, (11) requires
training a neural network once with a convex loss function which can be
accomplished with off-the-shelf SGD.

##  7 Robustness

Balancing weights rely heavily on the function class in Assumption 2. In this
section, we show that with minimal moment conditions we can still retain a
bound on the bias even if we have misspecified the function class
$\mathcal{F}$. We consider two functions classes. First, a _misspecified_
$\mathcal{F}$ for which we solve (8) to find $R^{*}$ such that
$\text{IPM}_{\mathcal{F}}(Q,R^{*})\leq\delta$. Second, the _true_ function
class, $\mathcal{G}$ such that $f_{0}\in\mathcal{G}$ and
$f_{0}\notin\mathcal{F}$. To bound the bias, we need to show that

$\displaystyle\text{IPM}_{\mathcal{F}}(Q,R^{*})\leq\delta\implies\text{IPM}_{\mathcal{G}}(Q,R^{*})\leq\rho(\delta)$
(14)

for some $\rho<\infty$ which has good scaling with $\delta$. Without further
assumptions, (14) will _not_ hold for any $\mathcal{G}$.

IPMs correspond to common perturbations in the robust statistics literature.
For example, $\text{IPM}_{\mathcal{F}_{\infty}}$ and
$\text{IPM}_{\mathcal{F}_{\text{Lip(c)}}}$ are equivalent to the total
variation (TV) distance and Wasserstein distance respectively. For
$\mathcal{F}=\mathcal{F}_{\infty}$, we can apply Lemma E.2 from Zhu et al.
(2019) to achieve (14) for any $\mathcal{G}$. We require an Orlicz norm bound
under $Q$ and $R^{*}$ on $g(X)$ for all $g\in\mathcal{G}$. For a simple
example, let $\mathcal{G}$ be linear. Then we get the following result:

######  Proposition 7.1.

Let $TV(Q,R^{*})\leq\delta$ and let $f_{0}\in\\{\beta^{T}x:\|\beta\|\leq
1\\}.$ If $R^{*}$ and $Q$ have bounded covariance, then we have the following
upper bound on the bias:

$|\mathbb{E}_{Q}[f_{0}]-\mathbb{E}_{R^{*}}[f_{0}]|\leq\rho_{1}(\delta),$

where $\rho_{1}(\delta)=O(\sqrt{\delta})$.

If instead $R^{*}$ and $Q$ are sub-Gaussian, then we have the following upper
bound on the bias:

$|\mathbb{E}_{Q}[f_{0}]-\mathbb{E}_{R^{*}}[f_{0}]|\leq\rho_{2}(\delta),$

where $\rho_{2}(\delta)=O(\delta\sqrt{\log(1/\delta)})$.

For general $\mathcal{G}$, the rate of $\rho$ in terms of $\delta$ is similar,
but the moment conditions on $X$ become stronger. In practice, these robust
statistics results mean that we can make a best guess about $\mathcal{F}$ and
as long as $Q$ is sufficiently “nice”, the true bias will not be much larger
than $\delta$.

## References

  * Agrawal and Horel (2020) R. Agrawal and T. Horel.  Optimal bounds between f-divergences and integral probability metrics.  In _International Conference on Machine Learning_ , pages 115–124. PMLR, 2020.
  * Arbour et al. (2021) D. Arbour, D. Dimmery, and A. Sondhi.  Permutation weighting.  In _International Conference on Machine Learning_ , pages 331–341. PMLR, 2021.
  * Assaad et al. (2021) S. Assaad, S. Zeng, C. Tao, S. Datta, N. Mehta, R. Henao, F. Li, and L. Carin Duke.  Counterfactual representation learning with balancing weights.  In A. Banerjee and K. Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 1972–1980. PMLR, 13–15 Apr 2021.  URL https://proceedings.mlr.press/v130/assaad21a.html.
  * Athey et al. (2018) S. Athey, G. W. Imbens, and S. Wager.  Approximate residual balancing: debiased inference of average treatment effects in high dimensions.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(4):597–623, 2018.
  * Ben-Michael et al. (2021) E. Ben-Michael, D. Hirshberg, A. Feller, and J. Zubizarreta.  The balancing act in causal inference.  2021\.
  * Birrell et al. (2020a) J. Birrell, P. Dupuis, M. A. Katsoulakis, Y. Pantazis, and L. Rey-Bellet.  $(f,\gamma)$-divergences: Interpolating between $f$-divergences and integral probability metrics.  _arXiv preprint arXiv:2011.05953_ , 2020a.
  * Birrell et al. (2020b) J. Birrell, M. A. Katsoulakis, and Y. Pantazis.  Optimizing variational representations of divergences and accelerating their statistical estimation.  _arXiv preprint arXiv:2006.08781_ , 2020b.
  * Broniatowski and Keziou (2006) M. Broniatowski and A. Keziou.  Minimization of $\varphi$-divergences on sets of signed measures.  _Studia Scientiarum Mathematicarum Hungarica_ , 43(4):403–442, 2006.
  * Cortes et al. (2010) C. Cortes, Y. Mansour, and M. Mohri.  Learning bounds for importance weighting.  In _Nips_ , volume 10, pages 442–450. Citeseer, 2010.
  * Courty et al. (2014) N. Courty, R. Flamary, and D. Tuia.  Domain adaptation with regularized optimal transport.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 274–289. Springer, 2014.
  * Dupuis and Mao (2019) P. Dupuis and Y. Mao.  Formulation and properties of a divergence used to compare probability measures without absolute continuity.  _arXiv preprint arXiv:1911.07422_ , 2019.
  * D’Amour et al. (2021) A. D’Amour, P. Ding, A. Feller, L. Lei, and J. Sekhon.  Overlap in observational studies with high-dimensional covariates.  _Journal of Econometrics_ , 221(2):644–654, 2021\.
  * Ganin et al. (2016) Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky.  Domain-adversarial training of neural networks.  _The journal of machine learning research_ , 17(1):2096–2030, 2016.
  * Glaser et al. (2021) P. Glaser, M. Arbel, and A. Gretton.  Kale flow: A relaxed kl gradient flow for probabilities with disjoint support.  _arXiv preprint arXiv:2106.08929_ , 2021.
  * Gretton et al. (2009) A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf.  Covariate shift by kernel mean matching.  _Dataset shift in machine learning_ , 3(4):5, 2009\.
  * Ha (1981) C. Ha.  A noncompact minimax theorem.  _Pacific Journal of Mathematics_ , 97(1):115–117, 1981.
  * Hainmueller (2012) J. Hainmueller.  Entropy balancing for causal effects: A multivariate reweighting method to produce balanced samples in observational studies.  _Political analysis_ , pages 25–46, 2012.
  * Hazlett (2020) C. Hazlett.  Kernel balancing.  _Statistica Sinica_ , 30(3):1155–1189, 2020.
  * Hill (2011) J. L. Hill.  Bayesian nonparametric modeling for causal inference.  _Journal of Computational and Graphical Statistics_ , 20(1):217–240, 2011.
  * Hirshberg et al. (2019) D. A. Hirshberg, A. Maleki, and J. R. Zubizarreta.  Minimax linear estimation of the retargeted mean.  _arXiv preprint arXiv:1901.10296_ , 2019.
  * Imai and Ratkovic (2014) K. Imai and M. Ratkovic.  Covariate balancing propensity score.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 76(1):243–263, 2014.
  * Johansson et al. (2020) F. D. Johansson, U. Shalit, N. Kallus, and D. Sontag.  Generalization bounds and representation learning for estimation of potential outcomes and causal effects.  _arXiv preprint arXiv:2001.07426_ , 2020.
  * Kallus (2020a) N. Kallus.  Deepmatch: Balancing deep covariate representations for causal inference using adversarial training.  In _International Conference on Machine Learning_ , pages 5067–5077. PMLR, 2020a.
  * Kallus (2020b) N. Kallus.  Generalized optimal matching methods for causal inference.  _Journal of Machine Learning Research_ , 21(62):1–54, 2020b.
  * Kang et al. (2007) J. D. Kang, J. L. Schafer, et al.  Demystifying double robustness: A comparison of alternative strategies for estimating a population mean from incomplete data.  _Statistical science_ , 22(4):523–539, 2007.
  * Keziou (2003) A. Keziou.  Dual representation of $\varphi$-divergences and applications.  _Comptes rendus mathématique_ , 336(10):857–862, 2003.
  * Khan and Tamer (2010) S. Khan and E. Tamer.  Irregular identification, support conditions, and inverse weight estimation.  _Econometrica_ , 78(6):2021–2042, 2010.
  * Mansour et al. (2009) Y. Mansour, M. Mohri, and A. Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  _arXiv preprint arXiv:0902.3430_ , 2009.
  * Nguyen et al. (2005) X. Nguyen, M. J. Wainwright, and M. I. Jordan.  On divergences, surrogate loss functions, and decentralized detection.  _arXiv preprint math.ST/0510521_ , 2005.
  * Nguyen et al. (2010) X. Nguyen, M. J. Wainwright, and M. I. Jordan.  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  _IEEE Transactions on Information Theory_ , 56(11):5847–5861, 2010.
  * Ozery-Flato et al. (2018) M. Ozery-Flato, P. Thodoroff, M. Ninio, M. Rosen-Zvi, and T. El-Hay.  Adversarial balancing for causal inference.  _arXiv preprint arXiv:1810.07406_ , 2018.
  * Rosenbaum and Rubin (1983) P. R. Rosenbaum and D. B. Rubin.  The central role of the propensity score in observational studies for causal effects.  _Biometrika_ , 70(1):41–55, 1983.
  * Ruderman et al. (2012) A. Ruderman, M. Reid, D. García-García, and J. Petterson.  Tighter variational representations of f-divergences via restriction to probability measures.  _arXiv preprint arXiv:1206.4664_ , 2012.
  * Shalit et al. (2017) U. Shalit, F. D. Johansson, and D. Sontag.  Estimating individual treatment effect: generalization bounds and algorithms.  In _International Conference on Machine Learning_ , pages 3076–3085. PMLR, 2017.
  * Shen et al. (2018) J. Shen, Y. Qu, W. Zhang, and Y. Yu.  Wasserstein distance guided representation learning for domain adaptation.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Sion (1958) M. Sion.  On general minimax theorems.  _Pacific Journal of mathematics_ , 8(1):171–176, 1958.
  * Song and Ermon (2020) J. Song and S. Ermon.  Bridging the gap between f-gans and wasserstein gans.  In _International Conference on Machine Learning_ , pages 9078–9087. PMLR, 2020.
  * Sriperumbudur et al. (2009) B. K. Sriperumbudur, K. Fukumizu, A. Gretton, B. Schölkopf, and G. R. Lanckriet.  On integral probability metrics,$\backslash$phi-divergences and binary classification.  _arXiv preprint arXiv:0901.2698_ , 2009.
  * Sugiyama et al. (2007a) M. Sugiyama, M. Krauledat, and K.-R. Müller.  Covariate shift adaptation by importance weighted cross validation.  _Journal of Machine Learning Research_ , 8(5), 2007a.
  * Sugiyama et al. (2007b) M. Sugiyama, S. Nakajima, H. Kashima, P. Von Buenau, and M. Kawanabe.  Direct importance estimation with model selection and its application to covariate shift adaptation.  In _NIPS_ , volume 7, pages 1433–1440. Citeseer, 2007b.
  * Sugiyama et al. (2012) M. Sugiyama, T. Suzuki, and T. Kanamori.  Density-ratio matching under the bregman divergence: a unified framework of density-ratio estimation.  _Annals of the Institute of Statistical Mathematics_ , 64(5):1009–1044, 2012.
  * Tan (2020) Z. Tan.  Regularized calibrated estimation of propensity scores with model misspecification and high-dimensional data.  _Biometrika_ , 107(1):137–158, 2020.
  * Wang and Zubizarreta (2020) Y. Wang and J. R. Zubizarreta.  Minimal dispersion approximately balancing weights: asymptotic properties and practical considerations.  _Biometrika_ , 107(1):93–105, 2020.
  * Yang and Ding (2018) S. Yang and P. Ding.  Asymptotic inference of causal effects with observational studies trimmed by the estimated propensity scores.  _Biometrika_ , 105(2):487–493, 2018.
  * Yoon et al. (2018) J. Yoon, J. Jordon, and M. Van Der Schaar.  Ganite: Estimation of individualized treatment effects using generative adversarial nets.  In _International Conference on Learning Representations_ , 2018.
  * Yu and Szepesvári (2012) Y. Yu and C. Szepesvári.  Analysis of kernel mean matching under covariate shift.  _arXiv preprint arXiv:1206.4650_ , 2012.
  * Zhao (2019) Q. Zhao.  Covariate balancing propensity score by tailored loss functions.  _The Annals of Statistics_ , 47(2):965–993, 2019\.
  * Zhao and Percival (2017) Q. Zhao and D. Percival.  Entropy balancing is doubly robust.  _Journal of Causal Inference_ , 5(1), 2017.
  * Zhu et al. (2019) B. Zhu, J. Jiao, and J. Steinhardt.  Generalized resilience and robust statistics.  _arXiv preprint arXiv:1909.08755_ , 2019.
  * Zubizarreta (2015) J. R. Zubizarreta.  Stable weights that balance covariates for estimation with incomplete outcome data.  _Journal of the American Statistical Association_ , 110(511):910–922, 2015.

Supplementary Material:
Outcome Assumptions and Duality Theory for Balancing Weights

CONTENTS

  1. A

Proof of Theorem 4.1

  2. B

General statement and proof for $\phi$-divergences for Remark 4.2

  3. C

Extension with non-negative weights

  4. D

Connection to surrogate loss for density ratio estimation

  5. E

Details of RKHS optimization problem in Section 6

##  Appendix A Proof of Theorem 4.1

We derive a dual formulation of the optimization problem:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}$ $\displaystyle D_{2}(R||P)$ such that
$\displaystyle\text{IPM}_{\mathcal{F}}(Q,R)\leq\delta,$

where $\delta>\delta_{\min}$. As a reminder,
$D_{2}(R||P)\coloneqq\mathbb{E}_{P}[(dR/dP)^{2}-1]$ is the $\chi^{2}$
divergence and
$\text{IPM}_{\mathcal{F}}(Q,R)\coloneqq\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}$.
Note that this problem takes the form of a projection in $D_{2}$ of $P$ onto
an IPM ball around $Q$.

By the definition of $\delta_{\min}$, the constraint set is non-empty and
convex. $D_{2}$ is strictly convex in $R$ and $0\leq D_{2}(R||P)<\infty$ so
there is a unique solution.

When $P$ already satisfies the IPM constraint, then $R=P$ has objective $0$
and we’re done (i.e. we don’t need to do a projection, $P$ is already on or in
the ball). Otherwise, by standard use of the Lagrangian, we claim (details in
Section A.5 below) that for some $\mu>0$ corresponding to $\delta$, this
problem is equivalent to:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}(1/\mu)D_{2}(R||P)+\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}\big{\\}}.$

###  A.1 Exchanging hard subproblem for an easy subproblem

The inner supremum is hard to solve for arbitrary $\mathcal{F}$. However, we
can make a series of transformations to get an easier subproblem with a
closed-form solution:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}(1/\mu)D_{2}(R||P)+\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}\big{\\}}$
$\displaystyle=\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\sup_{f\in\mathcal{F}}\Big{\\{}(1/\mu)D_{2}(R||P)+\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\Big{\\}}$
$\displaystyle=\sup_{f\in\mathcal{F}}\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\Big{\\{}(1/\mu)D_{2}(R||P)+\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\Big{\\}}$
$\displaystyle=\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]+\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{(1/\mu)D_{2}(R||P)-\mathbb{E}_{R}[f]\\}\Big{\\}}$

The only non-trivial step is the interchange of the $\inf$ and the $\sup$.
This follows by Sion’s Minimax Theorem (Sion, 1958). We assumed that
$\mathcal{X}$ was a separable Banach space so we have the necessary
topological properties. The objective on the second line is continuous and
strictly convex in $R$ and is linear in $f$. The set $\mathcal{F}$ is convex
and closed and $R$ is in a linear subspace. Furthermore, we know there is a
unique solution $R^{*}$, and so we can always find the necessary compact
subset of the linear subspace for $R$ to apply the theorem (e.g. ala Ha,
1981).

###  A.2 Solving the easy subproblem with the variational representation

Next, we apply the variational representation of $\phi$-divergences to get a
dual formulation of the inner sub-problem over $R$. Define:
$\phi(x)=(1/\mu)(x^{2}-1)$ which has convex conjugate
$\phi^{*}(y)=(\mu/4)y^{2}+(1/\mu)$. The Lagrangian for the infimum for a fixed
$f$ is:

$\displaystyle\mathcal{L}_{f}(R,\lambda)=D_{\phi}(R||P)-\mathbb{E}_{R}[f-\lambda]-\lambda$

We get the first-order condition:

$\displaystyle\phi^{\prime}(dR^{*}/dP)=f-\lambda^{*}\implies\frac{dR^{*}}{dP}=\frac{\mu}{2}(f-\lambda^{*})$

where $\lambda^{*}$ solves the supremum $\sup_{\lambda\geq 0}g(\lambda)$ over
the dual function:

$\displaystyle g(\lambda)$
$\displaystyle\coloneqq-\lambda+\inf_{R\in\mathcal{M}(P)}\\{D_{\phi}(R||P)-\mathbb{E}_{R}[f-\lambda]\\}$
$\displaystyle=-\lambda-\sup_{R\in\mathcal{M}(P)}\\{\mathbb{E}_{R}[f-\lambda]-D_{\phi}(R||P)\\}$
$\displaystyle=-\lambda-D_{\phi}^{*}(f-\lambda),$

where $D^{*}_{\phi}$ is the convex conjugate of the $\phi$-divergence as a
function of $R$ for a fixed $P$. We can then use the standard result
(Proposition 4.2 Broniatowski and Keziou, 2006),
$D^{*}_{\phi}(f)=\mathbb{E}_{P}[\phi^{*}(f)]$.

Using this form of the dual function, we can write our subproblem over $R$ as:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{(1/\mu)D_{2}(R||P)-\mathbb{E}_{R}[f]\\}=\sup_{\lambda\geq
0}\\{-\lambda-\mathbb{E}_{P}[\phi^{*}(f-\lambda)]\\}$

Plugging in $\phi^{*}$, we can solve for $\lambda^{*}$ by straightforward
calculus:

$\displaystyle\lambda^{*}=\mathbb{E}_{P}[f]-\frac{2}{\mu}.$

Now using the first-order conditions, we can find the optimal $R^{*}$:

$\displaystyle\frac{dR^{*}}{dP}=\frac{\mu}{2}(f-\mathbb{E}_{P}[f])+1$

and after some algebra, a closed form of the subproblem:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{(1/\mu)D_{2}(R||P)-\mathbb{E}_{R}[f]\\}=-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f].$

###  A.3 Writing the original problem as a single optimization problem over
$\mathcal{F}$

Finally, we substitute this form of the sub-problem into our original
optimization problem:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}(1/\mu)D_{2}(R||P)+\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}\big{\\}}$
$\displaystyle=\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]+\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{(1/\mu)D_{2}(R||P)-\mathbb{E}_{R}[f]\\}\Big{\\}}$
$\displaystyle=\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f]\Big{\\}}$

and therefore by duality:

$\displaystyle\frac{dR^{*}}{dP}=\frac{\mu}{2}(f^{*}-\mathbb{E}_{P}[f^{*}])+1$

where $f^{*}$ achieves this supremum.

###  A.4 Recovering $\delta$ in terms of $\mu$

Most of the proof of the theorem is complete. We just need to rewrite $\mu$ in
terms of the original tuning parameter $\delta$. Remember from the projection
perspective, that $\mu>0$ corresponds to $P$ outside of the IPM ball. As a
result:

$\displaystyle\delta=\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R^{*}}[f]\\}$

We just proved that $R^{*}$ achieves the infimum of the objective which equals
the supremum of the dual:

$\displaystyle\text{IPM}_{\mathcal{F}}(Q,R^{*})+(1/\mu)D_{2}(R^{*}||P)$
$\displaystyle=\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\frac{\mu}{4}\text{Var}_{P}[f^{*}]$
$\displaystyle=\Big{(}\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{R^{*}}[f^{*}]\Big{)}+\Big{(}\mathbb{E}_{R^{*}}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\frac{\mu}{4}\text{Var}_{P}[f^{*}]\Big{)}$

But then, using the variational representation of the $\phi$-divergence and
the definition of the IPM we have:

$\displaystyle\text{IPM}_{\mathcal{F}}(Q,R^{*})+(1/\mu)D_{2}(R^{*}||P)$
$\displaystyle=\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]-\mathbb{E}_{R^{*}}[f]\Big{\\}}+\sup_{f}\Big{\\{}\mathbb{E}_{R^{*}}[f]-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f^{*}]\Big{\\}}$
$\displaystyle=\Big{(}\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{R^{*}}[f^{*}]\Big{)}+\Big{(}\mathbb{E}_{R^{*}}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\frac{\mu}{4}\text{Var}_{P}[f^{*}]\Big{)}$

which implies

$\delta=\sup_{f\in\mathcal{F}}\Big{\\{}\mathbb{E}_{Q}[f]-\mathbb{E}_{R^{*}}[f]\Big{\\}}=\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{R^{*}}[f^{*}]$

Finally, substituting the form of $R^{*}$ in terms of $f^{*}$ we get

$\displaystyle\delta$
$\displaystyle=\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\frac{\mu}{2}\text{Var}_{P}[f^{*}]$
$\displaystyle\implies\mu$
$\displaystyle=2\left(\frac{\mathbb{E}_{Q}[f^{*}]-\mathbb{E}_{P}[f^{*}]-\delta}{\text{Var}_{P}[f^{*}]}\right),$

which concludes the proof.

###  A.5 Transformation from $\delta$ to $\mu$ via Lagrangian

Here we provide the details for our earlier claim that we can rewrite the
problem over $\delta$ as a problem over $\mu$. The dual function corresponding
to the original $\delta$ problem is:

$\displaystyle g(\mu)$
$\displaystyle=\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\mathcal{L}(R,\mu)$
$\displaystyle=\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\\{D_{2}(R||P)+\mu(\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}-\delta)\\}$

where $\mathcal{L}$ is the Lagrangian. Notice that the original optimization
problem has a strictly convex objective. Furthermore, since the function class
$\mathcal{F}$ is convex and closed, $\delta>\delta_{\min}$, and the individual
constraints for $f\in\mathcal{F}$ are all linear, the feasible set is convex
with a non-empty interior. Then by standard convex duality there exists
$R^{*}$ and $\mu^{*}\geq 0$ such that $R^{*}$ solves the original optimization
problem, $\mu^{*}$ achieves $\sup_{\mu\geq 0}g(\mu)$, and $R^{*}$ achieves the
infimum inside $g(\mu^{*})$.

By complementary slackness, $\mu^{*}=0$ only when the worst-bias constraint
doesn’t bind which only occurs when $R=P$ already satisfies the IPM
constraint. Then $R=P$ has minimum variance and we’re done. So we only need to
consider the case where $\mu^{*}>0$.

At $\mu=\mu^{*}$, the solution to:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}D_{2}(R||P)+\mu\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}\big{\\}}$

has the same solution as the original problem. Furthermore, since $\mu^{*}>0$,
we can apply one more transformation without affecting the infimum to get:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}(1/\mu)D_{2}(R||P)+\sup_{f\in\mathcal{F}}\\{\mathbb{E}_{Q}[f]-\mathbb{E}_{R}[f]\\}\big{\\}}$

##  Appendix B General Statement and Proof for Remark 3.1

######  Theorem (Birrell et al).

Let $\phi$ be a convex function such that $\phi(1)=0$ with convex conjugate
$\phi^{*}$ such that $\\{\phi^{*}<\infty\\}=\mathbb{R}$. Let $\phi_{\mu}$
denote the weighted function $\phi_{\mu}(x)=(1/\mu)\phi(x)$ and
$\phi_{\mu}^{*}$ its convex conjugate. Then under Assumption 2, for
$\delta>0$, $\exists\mu\geq 0$ such that the optimization problem,

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}$ $\displaystyle D_{\phi}(R||P)$ such that
$\displaystyle\text{IPM}_{\mathcal{F}}(Q,R)\leq\delta,$

has a solution,

$\displaystyle R^{*}=P\text{ when $\mu=0$, }$
$\displaystyle\frac{dR^{*}}{dP}=(\phi_{\mu}^{*})^{\prime}(f^{*}-\lambda^{*})\text{
otherwise,}$

where $f^{*}$ and $\lambda^{*}$ achieve the supremum,

$\displaystyle\sup_{f\in\mathcal{F}}\left\\{\mathbb{E}_{Q}[f]-\inf_{\lambda\in\mathbb{R}}\\{\lambda+\mathbb{E}_{P}[\phi_{\mu}^{*}(f-\lambda)]\\}\right\\}.$

The proof begins with an argument identical to 1.5 above which gives the
equivalent optimization problem:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}D_{\phi_{\mu}}(R||P)+\text{IPM}_{\mathcal{F}}(Q,R)\big{\\}}.$

From here, conceptually, the proof is similar to above, except we cannot apply
our proof directly because general $\phi$ loses some of the nice properties of
the quadratic. Instead, using the theory of infimal convolutions, Birrell et
al. (2020a) prove that for Polish $\mathcal{X}$ and any $\phi$-divergence such
that $\\{\phi^{*}<\infty\\}=\mathbb{R}$:

$\displaystyle\inf_{\begin{subarray}{c}R\in\mathcal{M}(P)\\\
\mathbb{E}_{R}[1]=1\end{subarray}}\big{\\{}D_{\phi}(R||P)+\text{IPM}_{\mathcal{F}}(Q,R)\big{\\}}$
$\displaystyle=\sup_{f\in\mathcal{F}}\left\\{\mathbb{E}_{Q}[f]-\inf_{\lambda\in\mathbb{R}}\\{\lambda+\mathbb{E}_{P}[\phi^{*}(f-\lambda)]\\}\right\\}$

and so in particular, it holds for $\phi_{\mu}$ above.

This result follows from Theorems 2.15 and 3.3 in Birrell et al. (2020a) with
one minor modification: we do not require that
$\lim_{y\rightarrow-\infty}\phi^{*}(y)<\infty$ which results in $R^{*}$ no
longer being a probability measure because we lose statement (174) in their
proof of Theorem C.6. This is in the spirit of the arguments in (Broniatowski
and Keziou, 2006). In fact, since the original problem is a projection of $P$
in $\phi$-divergence onto an IPM, we can interpret this as a version of
(Broniatowski and Keziou, 2006) Theorem 5.1 which applies for the case of
finitely-many linear inequality constraints, generalized to the case of a
linear inequality constraint for each $f$ in a convex and closed set
$\mathcal{F}$.

##  Appendix C Extension with non-negative weights

We can use the general Theorem to immediately get results for the case where
we require non-negative weights. This is identical to taking
$\phi(x)=x^{2}-1$, but restricting the domain to $[0,\infty)$. Then we have

$\phi^{*}_{\mu}(y)=\frac{\mu}{4}y^{2}\mathbf{1}(y\geq 0)+\frac{1}{\mu}$

and applying the theorem, we get the dual formulation:

$\displaystyle\frac{dR^{*}}{dP}=\frac{\mu}{2}(f^{*}-\lambda^{*})\mathbf{1}(f^{*}\geq\lambda^{*})$

such that:

$\displaystyle\mathbb{E}_{P}\left[\frac{\mu}{2}(f^{*}-\lambda^{*})\mathbf{1}(f^{*}\geq\lambda^{*})\right]=1$

and $f^{*}$ and $\lambda^{*}$ solve:

$\displaystyle\sup_{f\in\mathcal{F}}\left\\{\mathbb{E}_{Q}[f]-\inf_{\lambda\in\mathbb{R}}\left\\{\lambda+\frac{\mu}{4}\mathbb{E}_{P}\left[(f-\lambda)^{2}\mathbf{1}(f\geq\lambda)\right]\right\\}+\frac{1}{\mu}\right\\}.$

The minimax weights are extremely simliar to the minimax weights from Theorem
3.1. In Theorem 3.1 we found a function $f^{*}$, such that we de-meaned it,
rescaled it, and then shifted the result to get weights with expectation equal
to 1. In the case where the weights are non-negative, we can no longer just
de-mean and add 1. Instead, we have to optimize over all shifts $\lambda$
which give expectation 1 _after_ truncating at $0$.

##  Appendix D Connection to surrogate loss for density ratio estimation

A closely related literature implements regularized estimators of the density
ratio via a surrogate loss as first proposed in Nguyen et al. (2010). Similar
connections have been made for balancing weights; see the relation to
propensity score estimation in Zhao (2019); Ben-Michael et al. (2021). Here,
we compare our dual formulation based on variational representations to
density ratio estimation with a surrogate loss.

Consider the variational representation (10). Specializing to
$\phi(x)=\mu(x^{2}-1)$ for $\mu>0$, we can write the weighted $\chi^{2}$
divergence between $Q$ and $P$ as:

$\displaystyle\frac{1}{\mu}D_{2}(Q||P)=\sup_{f}\Big{\\{}\mathbb{E}_{Q}[f]-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f]\Big{\\}},$

where the supremum is over all real-valued measurable functions. If overlap
holds then the supremum is achieved by $2\mu(dQ/dP)$, otherwise
$D_{2}(Q||P)=\infty$. The variational representation is identical to (11),
except that the problem in (11) is restricted to functions in $\mathcal{F}$.
We immediately have the following corollary:

######  Corollary D.1.

Under the conditions in Theorem 4.1,

$\displaystyle\frac{2}{\mu}\frac{dQ}{dP}\in\mathcal{F}\implies
f^{*}=\frac{2}{\mu}\frac{dQ}{dP}\text{ and }\frac{dR^{*}}{dP}=\frac{dQ}{dP}.$

If the density ratio exists and a scaled version belongs to the outcome
function class, then it is minimax optimal to reweight so that there is zero
bias. If $\mathcal{F}$ is sufficiently flexible, then this will always hold as
$\mu\rightarrow\infty$, as in the example from Section 5.1.

There is a clear similarity to density ratio estimation using
$\phi$-divergences as in Nguyen et al. (2010). The form of their final
estimator looks the same as ours: maximizing a variational representation over
a function class. However, our motivations and assumptions are entirely
different. Nguyen et al. (2010) assumes that the density ratio exists and that
it belongs to $\mathcal{F}$. We do not make any assumption about the density
ratio. It could have some arbitrary functional form. We show that the shape of
the optimal weights is determined by the shape of $f_{0}$, _not_ by the shape
of $dQ/dP$.

If the density ratio exists, and our dual problem is solved over all
measurable functions, the only unique solution will be $dQ/dP$. In that sense,
once we restrict to optimization over $\mathcal{F}$, it might be helpful to
think of the balancing weights as a projection of the density ratio onto our
outcome function class. However, in general, we do not need a functional form
for the density ratio to specified. In fact, we do not need even require that
the density ratio exists.

##  Appendix E RKHS optimization problem

The optimization problem that implements our dual formulation using an RKHS
for the IHDP dataset is:

$\displaystyle\sup_{f\in\mathcal{F}_{\mathcal{H}}^{B}}\Big{\\{}\mathbb{E}_{Q}[f]-\mathbb{E}_{P}[f]-\frac{\mu}{4}\text{Var}_{P}[f]\Big{\\}}$
$\displaystyle=\sup_{\begin{subarray}{c}f=K\alpha\\\
\alpha\in\mathbb{R}^{n}:\alpha^{T}K\alpha\leq
B\end{subarray}}\Big{\\{}f^{T}e_{q}-f^{T}e_{p}-(f^{T}I_{p}f-(f^{T}e_{p})^{2})\Big{\\}}$

where:

  * •

$e_{p}\in\mathbb{R}^{n}$ is a vector equal to $1/n_{0}$ for those indices
corresponding to control group data points and $0$ otherwise

  * •

$e_{q}\in\mathbb{R}^{n}$ is a vector equal to $1/n_{0}$ for those indices
corresponding to treatment group data points and $0$ otherwise

  * •

$I_{p}\in\mathbb{R}^{n\times n}$ is the matrix with $e_{p}$ on the diagonal.

We solve this problem using the scipy Python package.