# Positive Distribution Shift as a Framework for Understanding Tractable Learning

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

## Key facts

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

## Builds on (most cited first, 30 of 53)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Learning Compositional Functions with Transformers from Easy-to-Hard Data](https://mlsanity.com/paper/2505.23683/) (2025)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [An Analytical Theory of Curriculum Learning in Teacher-Student Networks](https://mlsanity.com/paper/2106.08068/) (2021)
- [Deep Learning and Hierarchal Generative Models](https://mlsanity.com/paper/1612.09057/) (2016)
- [Probing transfer learning with a model of synthetic correlated datasets](https://mlsanity.com/paper/2106.05418/) (2021)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Poly-time universality and limitations of deep learning](https://mlsanity.com/paper/2001.02992/) (2020)

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

- [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026)
- [Learning through Internalization](https://mlsanity.com/paper/2606.20937/) (2026)
- [The Power of Power Law: Asymmetry Enables Compositional Reasoning](https://mlsanity.com/paper/2604.22951/) (2026)

## Abstract (arXiv)

We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training distribution D'(x), labeled by the true target f(x). Such a distribution shift (here in the form of covariate shift) is usually viewed negatively, as hurting or making learning harder, and the traditional distribution shift literature is mostly concerned with limiting or avoiding this negative effect. In contrast, we argue that with a well-chosen D'(x), the shift can be positive and make learning easier -- a perspective called Positive Distribution Shift (PDS). Such a perspective is central to contemporary machine learning, where much of the innovation is in finding good training distributions D'(x), rather than changing the training algorithm. We further argue that the benefit is often computational rather than statistical, and that PDS allows computationally hard problems to become tractable even using standard gradient-based training. We formalize different variants of PDS, show how certain hard classes are easily learnable under PDS, and make connections with membership query learning.