Correcting Covariate Shift with the Frank-Wolfe Algorithm

Junfeng Wen, Russell Greiner, Dale SchuurmansIJCAI 2015 · OpenReview

Abstract

Covariate shift is a fundamental problem for learning in non-stationary environments where the conditional distribution $p(y|x)$ is the same between training and test data while their marginal distributions $p_{tr}(x)$ and $p_{te}(x)$ are different. Although many covariate shift correction techniques remain effective for real world problems, most do not scale well in practice. In this paper, using inspiration from recent optimization techniques, we apply the Frank-Wolfe algorithm to two well-known covariate shift correction techniques, Kernel Mean Matching (KMM) and Kullback-Leibler Importance Estimation Procedure (KLIEP), and identify an important connection between kernel herding and KMM. Our complexity analysis shows the benefits of the Frank-Wolfe approach over projected gradient methods in solving KMM and KLIEP. An empirical study then demonstrates the effectiveness and efficiency of the Frank-Wolfe algorithm for correcting covariate shift in practice.

Introduction

In many machine learning applications, the distribution of training data differs from that of the test data, a phenomenon known as covariate shift. While the relationship between inputs and outputs ($p(y|x)$) remains constant, the marginal distribution of inputs ($p(x)$) changes. To mitigate this, importance reweighting is employed to adjust training point weights so the training distribution aligns with the test distribution.

Standard methods like Kernel Mean Matching (KMM) and the Kullback-Leibler Importance Estimation Procedure (KLIEP) often rely on projected gradient descent. However, the projection step is computationally prohibitive for large datasets, scaling poorly as $O(n^2)$ or worse. This paper demonstrates that the Frank-Wolfe algorithm—a "projection-free" optimization technique—is a highly efficient way to correct for covariate shift.

The Frank-Wolfe Approach

The authors propose using the Frank-Wolfe (FW) algorithm (also known as conditional gradient descent) to solve the optimization problems in KMM and KLIEP.

Key Technical Contributions

  • The Herding Connection: The authors prove that "kernel herding"—a greedy sampling technique—is actually a specific instance of the Frank-Wolfe algorithm applied to the KMM objective.
  • Projection-Free Efficiency: Unlike standard gradient descent, Frank-Wolfe doesn't require projecting back onto a constraint set. For KMM, this reduces the per-iteration complexity from $O(n^2)$ to $O(n)$ by maintaining inner products recursively.
  • Sparse KLIEP: FW naturally produces sparse solutions. In KLIEP, this allows the use of all test points as potential Gaussian centers, as the algorithm automatically selects only the most relevant ones, outperforming the common "100-center" heuristic.

Experimental Evaluation

The approach was evaluated on synthetic 1D regression tasks and various benchmark datasets (e.g., kin-8fm, cpusmall).

Computational Efficiency

As shown below, the Frank-Wolfe variants of KMM and KLIEP consistently outperform standard projected gradient methods in terms of computation time as sample sizes increase.

Log-scale computation time vs. sample size for KMM (left) and KLIEP (right) variants.

Sparsity and Model Fit

A critical advantage of FW is its ability to find sparse weight distributions. In the following comparison, we observe the weight distributions (pink vertical lines) and resulting model fits. The FW methods, particularly with line search, achieve a better fit to the "True model" (black curve) using significantly fewer non-zero weights than the projected gradient method.

Comparison of weight sparsity and model fit for (a) Projected gradient, (b) Frank-Wolfe with 1/(t+1) step size, and (c) Frank-Wolfe with line search.

On the kin-8fm dataset, KLIEP(FW) reduced normalized loss to 0.738, a dramatic improvement over the 5.329 loss seen with the traditional 100-center KLIEP approach.

Conclusion

The Frank-Wolfe algorithm provides a robust and efficient framework for covariate shift correction. By leveraging its projection-free nature and inherent sparsity, researchers can scale KMM and KLIEP to much larger datasets while achieving superior task performance. Future work includes investigating FW for other shift correction objectives like RuLSIF or integrated end-to-end learning objectives.

Summary updated

Abstract

Covariate shift is a fundamental problem for learning in non-stationary environments where the conditional distribution p(y|x) is the same between training and test data while their marginal distributions ptrpxq and ptr(x) are different. Although many covariate shift correction techniques remain effective for real world problems, most do not scale well in practice. In this paper, using inspiration from recent optimization techniques, we apply the Frank-Wolfe algorithm to two well-known covariate shift correction techniques, Kernel Mean Matching (KMM) and Kullback-Leibler Importance Estimation Procedure (KLIEP), and identify an important connection between kernel herding and KMM. Our complexity analysis shows the benefits of the Frank-Wolfe approach over projected gradient methods in solving KMM and KLIEP. An empirical study then demonstrates the effectiveness and efficiency of the Frank-Wolfe algorithm for correcting covariate shift in practice.
BibTeX
@inproceedings{wen2015correcting,
  author = {Junfeng Wen and Russell Greiner and Dale Schuurmans},
  title = {{Correcting Covariate Shift with the Frank-Wolfe Algorithm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=HyEBtrf_WH},
}
Figure