# The Information Complexity of Learning Tasks, their Structure and their Distance

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2019.

## Built on by (most cited first, 30 of 36)

- [Efficiently Identifying Task Groupings for Multi-Task Learning](https://mlsanity.com/paper/2109.04617/) (2021)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Less Data, More Knowledge: Building Next Generation Semantic Communication Networks](https://mlsanity.com/paper/2211.14343/) (2022)
- [What Has a Foundation Model Found? Using Inductive Bias to Probe for World Models](https://mlsanity.com/paper/2507.06952/) (2025)
- [A linearized framework and a new benchmark for model selection for fine-tuning](https://mlsanity.com/paper/2102.00084/) (2021)
- [Probing transfer learning with a model of synthetic correlated datasets](https://mlsanity.com/paper/2106.05418/) (2021)
- [Concept-skill Transferability-based Data Selection for Large Vision-Language Models](https://mlsanity.com/paper/2406.10995/) (2024)
- [Beyond Scale: The Diversity Coefficient as a Data Quality Metric for Variability in Natural Language Data](https://mlsanity.com/paper/2306.13840/) (2023)
- [Selective Task Group Updates for Multi-Task Optimization](https://mlsanity.com/paper/2502.11986/) (2025)
- [What Are We Measuring When We Evaluate Large Vision-Language Models? An Analysis of Latent Factors and Biases](https://mlsanity.com/paper/2404.02415/) (2024)
- [The Curse of Low Task Diversity: On the Failure of Transfer Learning to Outperform MAML and Their Empirical Equivalence](https://mlsanity.com/paper/2208.01545/) (2022)
- [Limits of Model Selection under Transfer Learning](https://mlsanity.com/paper/2305.00152/) (2023)
- [Model-agnostic Measure of Generalization Difficulty](https://mlsanity.com/paper/2305.01034/) (2023)
- [Task Fingerprinting for Meta Learning in Biomedical Image Analysis](https://mlsanity.com/paper/2107.03949/) (2021)
- [X-Learner: Learning Cross Sources and Tasks for Universal Visual Representation](https://mlsanity.com/paper/2203.08764/) (2022)
- [Hierarchical Optimal Transport for Comparing Histopathology Datasets](https://mlsanity.com/paper/2204.08324/) (2022)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [On the Learnability of Physical Concepts: Can a Neural Network Understand What's Real?](https://mlsanity.com/paper/2207.12186/) (2022)
- [Meta-Learning for Unsupervised Outlier Detection with Optimal Transport](https://mlsanity.com/paper/2211.00372/) (2022)
- [Task Grouping for Automated Multi-Task Machine Learning via Task Affinity Prediction](https://mlsanity.com/paper/2310.16241/) (2023)
- [Disentangling Learnable and Memorizable Data via Contrastive Learning for Semantic Communications](https://mlsanity.com/paper/2212.09071/) (2022)
- [Provable Pathways: Learning Multiple Tasks over Multiple Paths](https://mlsanity.com/paper/2303.04338/) (2023)
- [Neuroplasticity in Artificial Intelligence -- An Overview and Inspirations on Drop In & Out Learning](https://mlsanity.com/paper/2503.21419/) (2025)
- [Semantic Communication of Learnable Concepts](https://mlsanity.com/paper/2305.08126/) (2023)
- [Beyond Knowledge Silos: Task Fingerprinting for Democratization of Medical Imaging AI](https://mlsanity.com/paper/2412.08763/) (2024)
- [Measuring Fine-Grained Relatedness in Multitask Learning via Data Attribution](https://mlsanity.com/paper/2505.21438/) (2025)
- [The Advantage of Fine-Grained Training](https://mlsanity.com/paper/2509.05130/) (2025)
- [Task Specific Sharpness Aware O-RAN Resource Management using Multi Agent Reinforcement Learning](https://mlsanity.com/paper/2511.15002/) (2025)
- [Efficiently Estimating Data Efficiency for Language Model Fine-tuning](https://mlsanity.com/paper/2512.24991/) (2025)
- [The Curse of Zero Task Diversity: On the Failure of Transfer Learning to Outperform MAML and their Empirical Equivalence](https://mlsanity.com/paper/2112.13121/) (2021)

## Abstract (arXiv)

We introduce an asymmetric distance in the space of learning tasks, and a framework to compute their complexity. These concepts are foundational for the practice of transfer learning, whereby a parametric model is pre-trained for a task, and then fine-tuned for another. The framework we develop is non-asymptotic, captures the finite nature of the training dataset, and allows distinguishing learning from memorization. It encompasses, as special cases, classical notions from Kolmogorov complexity, Shannon, and Fisher Information. However, unlike some of those frameworks, it can be applied to large-scale models and real-world datasets. Our framework is the first to measure complexity in a way that accounts for the effect of the optimization scheme, which is critical in Deep Learning.