# Classification Tree Pruning Under Covariate Shift

arXiv: https://arxiv.org/abs/2305.04335 · HTML: https://mlsanity.com/paper/2305.04335/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 53 references that are in the map.
- First posted on arXiv 7 May 2023.

## Builds on (most cited first, 7 of 7)

- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier](https://mlsanity.com/paper/1906.02903/) (2019)
- [On the Value of Target Data in Transfer Learning](https://mlsanity.com/paper/2002.04747/) (2020)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [A new similarity measure for covariate shift with applications to nonparametric regression](https://mlsanity.com/paper/2202.02837/) (2022)
- [A Generalized Neyman-Pearson Criterion for Optimal Domain Adaptation](https://mlsanity.com/paper/1810.01545/) (2018)

## Built on by (most cited first, 3 of 3)

- [Help Me Help You: The Aggregate Value of Source and Target Data in Transfer Learning](https://mlsanity.com/paper/2408.16189/) (2024)
- [Harnessing the Power of Vicinity-Informed Analysis for Classification under Covariate Shift](https://mlsanity.com/paper/2405.16906/) (2024)
- [Provable Target Sample Complexity Improvements as Pre-Trained Models Scale](https://mlsanity.com/paper/2602.04233/) (2026)

## Abstract (arXiv)

We consider the problem of pruning a classification tree, that is, selecting a suitable subtree that balances bias and variance, in common situations with inhomogeneous training data. Namely, assuming access to mostly data from a distribution PX, Y, but little data from a desired distribution QX, Y with different X-marginals, we present the first efficient procedure for optimal pruning in such situations, when cross-validation and other penalized variants are grossly inadequate. Optimality is derived with respect to a notion of average discrepancy PX → QX (averaged over X space) which significantly relaxes a recent notion -- termed transfer-exponent -- shown to tightly capture the limits of classification under such a distribution shift. Our relaxed notion can be viewed as a measure of relative dimension between distributions, as it relates to existing notions of information such as the Minkowski and Renyi dimensions.