Concentration Of Importance-Weighted Risks

Why Importance-Weighted Risk Can Be Noisy

Under covariate shift, observations come from a source distribution, but performance is assessed under a target distribution. Importance weighting expresses the target risk as an expectation under the source distribution. This identity makes a source sample useful for estimating target performance, but it does not guarantee that the estimate is precise: a few observations can receive very large weights and dominate the average.

This tutorial quantifies that variability. We first bound deviations when both the loss and the weights are bounded, then give a finite-sample bound under a finite moment condition that permits unbounded weights. In both cases, the key quantities are the variability and tail behavior of the weighted loss, not just the sample size.

Setup and definition: Let $Z=(X,Y)$ have source distribution $P$, and let the target distribution $Q$ differ only in the marginal distribution of $X$. Assume $Q_X$ is absolutely continuous with respect to $P_X$, and write $w(x)=dQ_X/dP_X(x)$. Thus $E_P[w(X)]=1$. For a fixed prediction rule with loss $0\leq \ell(Z)\leq B$, its target risk is $R_Q=E_Q[\ell(Z)]=E_P[w(X)\ell(Z)]$. For independent source observations $Z_1,\ldots,Z_n$, the importance-weighted empirical risk is $\widehat R_w=n^{-1}\sum_{i=1}^n w(X_i)\ell(Z_i)$.

The equality defining $R_Q$ uses the covariate-shift condition: the conditional distribution of $Y$ given $X$ is the same under source and target. The density ratio changes the distribution of $X$, while the loss remains evaluated on each observed pair. Since the observations are independent and the weighted loss has expectation $R_Q$, $\widehat R_w$ is unbiased. Concentration asks how far this random average can be from that expectation.

Bounded Weights: A Bernstein Bound

Suppose $w(X)\leq W$ with probability one. Then the summands $U_i=w(X_i)\ell(Z_i)$ lie in $[0,BW]$. Let $v=\operatorname{Var}_P(w(X)\ell(Z))$. Bernstein's inequality gives a deviation bound in terms of both this variance and the maximum possible summand.

Theorem (bounded-weight concentration): Suppose $Z_1,\ldots,Z_n$ are independent and identically distributed under $P$, $0\leq\ell(Z)\leq B$, $0\leq w(X)\leq W$ almost surely, and $v=\operatorname{Var}_P(w(X)\ell(Z))<\infty$. For any $0<\delta<1$, with probability at least $1-\delta$, $$ \left|\widehat R_w-R_Q\right| \leq \sqrt{\frac{2v\log(2/\delta)}{n}} +\frac{2BW\log(2/\delta)}{3n}. $$ In particular, since $v\leq E_P[(w\ell)^2]\leq B^2E_P[w^2]$, the variance term can be bounded using the second moment of the weights.

Here is a derivation from the exponential-moment argument for Bernstein's inequality. If $V$ is centered, $|V|\leq M$, and $E[V^2]=v$, then, for $0<\lambda<3/M$, expansion of the exponential and the bounds $E|V|^k\leq M^{k-2}v$ and $k!\geq2\cdot3^{k-2}$, for $k\geq2$, give

E[e^{\lambda V}] \leq 1+\frac{\lambda^2v}{2(1-\lambda M/3)} \leq \exp\left(\frac{\lambda^2v}{2(1-\lambda M/3)}\right).

For independent centered summands with this bound, multiply their moment-generating-function bounds and apply Markov's inequality to their sum. Choosing $\lambda=t/(nv+Mt/3)$ yields

P\left(\left|\sum_{i=1}^n V_i\right|\geq t\right) \leq 2\exp\left(-\frac{t^2}{2(nv+Mt/3)}\right).

Apply this inequality to $V_i=U_i-E[U_i]$. Since $U_i\in[0,BW]$, we have $|V_i|\leq BW$. Setting the right-hand side to $\delta$ and solving the resulting quadratic inequality gives $t=\sqrt{2nv\log(2/\delta)}+(2/3)BW\log(2/\delta)$ as a valid threshold. Dividing by $n$ proves the stated bound. Finally, $v\leq E[U_i^2]\leq B^2E[w^2]$, as claimed. $\square$

Worked Example: A Bounded-Weight Risk Bound

Suppose $P(w=0.5)=P(w=1.5)=0.5$, and the loss is $0.2$ when $w=0.5$ and $0.8$ when $w=1.5$. The weights have mean $0.5(0.5)+0.5(1.5)=1$, as a density ratio must. The weighted losses are $0.1$ and $1.2$, so

R_Q=E_P[w\ell]=0.5(0.1)+0.5(1.2)=0.65.

Their variance is

$$ v=0.5(0.1-0.65)^2+0.5(1.2-0.65)^2=0.3025. $$

Take $n=100$, $\delta=0.05$, $B=1$, and $W=1.5$. Since $\log(2/\delta)=\log(40)\approx3.689$, the square-root term is $\sqrt{2(0.3025)(3.689)/100}\approx0.149$, and the linear term is $2(1.5)(3.689)/(3(100))\approx0.037$. Thus the theorem guarantees $|\widehat R_w-0.65|\leq0.186$ with probability at least $0.95$. This is a finite-sample guarantee, not a prediction that the error will equal the bound.

Finite Moments: A Bound Without Bounded Weights

A uniform upper bound on $w$ may be unrealistic. A weaker condition still gives a finite-sample guarantee: assume $E_P[w^q]<\infty$ for some $q$ with $1<q\leq2$. This permits weights with heavy tails, although the resulting probability bound generally decays more slowly than a Bernstein bound.

Theorem (finite-moment concentration): Let $Z_1,\ldots,Z_n$ be independent and identically distributed, let $0\leq\ell(Z)\leq B$, and suppose $E_P[w^q]<\infty$ for some $1<q\leq2$. For every $\varepsilon>0$, $$ P\left(\left|\widehat R_w-R_Q\right|\geq\varepsilon\right) \leq \frac{2^{2q}B^q E_P[w^q]}{n^{q-1}\varepsilon^q}. $$ Consequently, with probability at least $1-\delta$, $$ \left|\widehat R_w-R_Q\right| \leq 2^2 B\left(\frac{E_P[w^q]}{n^{q-1}\delta}\right)^{1/q}. $$

To justify the bound, put $U_i=w(X_i)\ell(Z_i)$ and $V_i=U_i-E[U_i]$. For $1<q\leq2$, independent centered variables satisfy

E\left|\sum_{i=1}^n V_i\right|^q \leq 2^q\sum_{i=1}^n E|V_i|^q.

One way to obtain this inequality is to introduce independent copies $V_i'$. Conditional Jensen's inequality bounds the left side by $E|\sum_i(V_i-V_i')|^q$. The differences are independent and symmetric. Conditional on their magnitudes, randomizing their signs and applying Jensen's inequality gives $E_\epsilon|\sum_i\epsilon_i a_i|^q\leq(\sum_i a_i^2)^{q/2}\leq\sum_i|a_i|^q$, where the last inequality uses $q/2\leq1$. Finally, $E|V_i-V_i'|^q\leq2^{q-1}(E|V_i|^q+E|V_i'|^q)=2^qE|V_i|^q$, proving the displayed inequality.

A second application of $|a-b|^q\leq2^{q-1}(|a|^q+|b|^q)$, together with Jensen's inequality, gives $E|V_i|^q\leq2^qE|U_i|^q$. Because $0\leq\ell\leq B$, $E|U_i|^q\leq B^qE[w^q]$. Therefore

E\left|\widehat R_w-R_Q\right|^q \leq \frac{2^{2q}B^qE[w^q]}{n^{q-1}}.

Markov's inequality applied to $|\widehat R_w-R_Q|^q$ proves the probability bound. Solving that bound for $\varepsilon$ proves the confidence statement. $\square$

Worked Example: Pareto Weights With a Finite Moment

Let $T$ have a Pareto distribution with $P(T>t)=t^{-3/2}$ for $t\geq1$, and set $w=T/3$. The Pareto mean is $E[T]=(3/2)/(3/2-1)=3$, so $E[w]=1$. For $1<q<3/2$, integration of the Pareto density gives

E[w^q]=\frac{1}{3^q}\frac{3/2}{3/2-q}.

Take $q=5/4$. Then $E[w^{5/4}]=6/3^{5/4}$, which is finite, even though the weight distribution has a heavy tail. For a loss bounded by $B=1$, the theorem gives

P\left(|\widehat R_w-R_Q|\geq\varepsilon\right) \leq \frac{2^{5/2}(6/3^{5/4})}{n^{1/4}\varepsilon^{5/4}}.

The rate in the denominator is $n^{1/4}$, rather than the $n^{1/2}$ scale associated with a finite-variance deviation bound. This illustrates the cost of having only a $5/4$-moment available. The inequality can be numerically loose, especially for small $\varepsilon$; its role is to give a valid guarantee under the stated moment assumption, not to promise a sharp numerical approximation.

Weight Variability and Effective Sample Size

Since $E[w]=1$, the second moment $E[w^2]$ measures variability around the average weight. By $E[w^2]=1+\operatorname{Var}(w)$, it is at least one, with equality only when $w=1$ almost surely. The variance part of the bounded-weight result is at most $B^2E[w^2]/n$. Thus, all else equal, greater weight variability can increase the scale of the estimation error.

Effective sample size: When $E[w]=1$, the population effective sample size associated with the weights is $n_{\mathrm{eff}}=n/E[w^2]$. For observed nonnegative weights $w_1,\ldots,w_n$, the commonly used empirical version is $$ \widehat n_{\mathrm{eff}}=\frac{(\sum_{i=1}^n w_i)^2}{\sum_{i=1}^n w_i^2}, $$ provided the denominator is positive. This summarizes weight concentration; it is not, by itself, a confidence bound for a particular risk estimate.

Worked Example: Weight Variability and Effective Sample Size

Suppose weights equal $0.2$ or $1.8$, each with source probability $1/2$. Their mean is $0.5(0.2)+0.5(1.8)=1$, and

$$ E[w^2]=0.5(0.2^2)+0.5(1.8^2)=0.5(0.04)+0.5(3.24)=1.64. $$

For $n=100$, the population effective sample size is $100/1.64\approx61$. By comparison, constant weights $w=1$ give $E[w^2]=1$ and effective sample size $100$. The weighted sample still contains 100 observations, but unequal weights make its average behave, in this particular weight-variability summary, more like an average based on fewer equally weighted observations. Actual risk precision also depends on how the losses vary and relate to the weights.

Interpretation and a Common Pitfall

The bounds explain why unbiasedness alone is not enough. A weighted average can target the correct risk in expectation and still vary substantially across source samples. A bounded-weight Bernstein bound gives both a variance-sensitive term and a finite-sample range term; a finite-moment bound remains available when weights are unbounded, but its guarantee weakens as the available moment order decreases.

Pitfall: treating $n_{\mathrm{eff}}$ as an exact sample size. It is tempting to replace $n$ by $\widehat n_{\mathrm{eff}}$ in an ordinary unweighted confidence interval and assume that the result is guaranteed. That conclusion does not follow from the definition. The effective sample size summarizes weight concentration; a valid risk bound also needs assumptions about the loss, weights, dependence, and tail behavior, as well as a concentration argument.
Pitfall: assuming a finite mean guarantees concentration. $E[w]=1$ ensures the importance weights are normalized, but it does not ensure a finite variance or a strong deviation bound. The finite-moment result requires $E[w^q]<\infty$ for some $q>1$; without such additional control, the stated rate does not apply.
Pitfall: applying these results to a normalized ratio without checking. The estimator here is the unnormalized average $n^{-1}\sum_iw_i\ell_i$, whose expectation is the target risk. Dividing by the observed sum of weights produces a different, random-denominator estimator; the bounds above do not automatically apply to it.

Key takeaway: Importance-weighted risk concentrates according to the distribution of the weighted loss. Bounded weights yield a Bernstein bound; finite moments yield a weaker but still explicit deviation guarantee. Large weight variability lowers effective sample size and can make target-risk estimates unstable.

Check Your Understanding

Use the definitions and bounds above to answer the following.

Why is the unnormalized importance-weighted empirical risk unbiased for the target risk under the stated covariate-shift conditions?
In the bounded-weight theorem, what roles do the variance term and the maximum-weight term play?
For weights with mean one, show that $E[w^2]=1+\operatorname{Var}(w)$, and explain what this implies for population effective sample size.
Why does the finite-moment bound require $q>1$, and what happens to its dependence on $n$ as $q$ approaches one?
Why does an empirical effective sample size alone not certify a confidence interval for weighted risk?