Learning Bounds for Importance Weighting

Corinna Cortes, Yishay Mansour, Mehryar MohriNeurIPS 2010 · OpenReview

Overview

Importance weighting is a go-to technique for fixing distribution mismatch between training and test data, but it is notoriously unstable in practice. This paper provides the first rigorous generalization bounds for the common case where weights are unbounded, linking learning stability to the Rényi divergence between distributions. The authors also introduce a principled reweighting algorithm that balances bias and variance, outperforming standard importance weighting in challenging scenarios.

The Problem: Distribution Mismatch

Most machine learning algorithms assume that training data and test data come from the exact same probability distribution. In the real world, this is rarely true. Whether dealing with "sample bias" (e.g., only seeing data for customers who were actually granted credit) or "domain adaptation" (e.g., training on synthetic images but testing on real ones), practitioners frequently face distribution mismatch.

The standard fix is Importance Weighting (IW). If our training distribution is $Q$ and our target is $P$, we weight each training instance by $w(x) = P(x)/Q(x)$. While this makes the training loss an "unbiased" estimate of the test loss, it often fails spectacularly in practice. Small samples can lead to massive weights that dominate the learning process, causing high variance and poor generalization. This paper seeks to understand why and when IW works by providing formal mathematical guarantees.

Theoretical Contributions

The authors approach the problem through the lens of information theory and statistical learning theory, making a significant breakthrough regarding unbounded weights.

Traditionally, researchers assumed weights must be capped (bounded) to prove anything about generalization. This paper shows that as long as the second moment of the weights is finite, you can still guarantee that the model will learn, albeit at a slightly slower rate ($O(m^{-3/8})$ instead of the standard $O(m^{-1/2})$).

They identify the second-order Rényi divergence ($d_2(P||Q)$) as the critical metric. This measures how much the target distribution $P$ "stretches" beyond the source $Q$. For bounded weights, they use Bernstein’s inequality to show that error scales directly with this divergence. For the more realistic unbounded case, they derive novel bounds for unbounded loss functions—a significant theoretical contribution on its own.

Datasets & The Failure of Standard IW

To validate their theory, the authors use 2D Gaussian distributions to simulate distribution shift. By varying the means and standard deviations of the source ($Q$) and target ($P$), they create scenarios where importance weights are either well-behaved or extremely "spiky" (unbounded).

Synthetic Gaussian mixture setup and the failure of standard importance weighting when the source distribution is too narrow (Ratio = 0.3).

As demonstrated in the experiments, standard IW is highly vulnerable to narrow source distributions. When the source distribution was much "narrower" than the target (e.g., $\sigma_Q/\sigma_P = 0.3$), standard IW failed to converge even with 5,000 samples, hovering at a 50% error rate with massive variance.

A Better Approach: Bias-Variance Tradeoff

Standard IW is unbiased but has high variance. Conversely, "unweighted" learning is biased but has low variance. The authors show that the optimal approach lies somewhere in between.

Based on their bounds, they propose an optimization problem that doesn't just use the "true" weights $w$. Instead, it looks for a weight function $u$ that minimizes a combination of bias (how much $u$ deviates from $w$) and variance (the second moment of $u$).

Many practitioners simply "cap" or "truncate" large weights at an arbitrary threshold to control variance. The authors show that this blunt instrument can actually hurt performance if those large weights are necessary to represent rare but important parts of the target distribution. Instead, they implement a Quantile Parameterization, grouping weights into quantiles and averaging them to smooth out extreme values in a principled way.

Performance of the proposed Quantile reweighting algorithm, showing stable and fast convergence.

Their proposed "Quantile" reweighting algorithm converged significantly faster and more reliably than standard IW, unweighted learning, or simple weight capping.

Limitations and Future Work

While the theoretical bounds and the new algorithm are strong steps forward, the paper notes a few limitations:

  • Known Weights: The theory assumes we actually know the true distributions $P$ and $Q$ to calculate $w(x) = P(x)/Q(x)$. In many real-world cases, we have to estimate these weights from data, introducing a new source of error.
  • Estimation of Divergence: Accurately estimating the Rényi divergence from finite samples is a difficult problem in itself and warrants further study to make these bounds fully computable in practice.

Summary updated

Abstract

This paper presents an analysis of importance weighting for learning from finite samples and gives a series of theoretical and algorithmic results. We point out simple cases where importance weighting can fail, which suggests the need for an analysis of the properties of this technique. We then give both upper and lower bounds for generalization with bounded importance weights and, more significantly, give learning guarantees for the more common case of unbounded importance weights under the weak assumption that the second moment is bounded, a condition related to the Renyi divergence of the training and test distributions. These results are based on a series of novel and general bounds we derive for unbounded loss functions, which are of independent interest. We use these bounds to guide the definition of an alternative reweighting algorithm and report the results of experiments demonstrating its benefits. Finally, we analyze the properties of normalized importance weights which are also commonly used.
BibTeX
@inproceedings{cortes2010learning,
  author = {Corinna Cortes and Yishay Mansour and Mehryar Mohri},
  title = {{Learning Bounds for Importance Weighting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=ry-MGY-dZB},
}
Figure