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

By Alessandro Achille, Giovanni Paolini, Glen Bigan Mbeng, Stefano Soatto. 2019

61 citations recorded by the source corpus.

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 and 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Where is the Information in a Deep Neural Network? (2019, background): “This section is inspired by [1], who derive these relations in the even more general setting of Kolmogorov Complexity.”
Multi-task Learning (2020, background): “…transfer learning focused on understanding task relationships (Zamir et al., 2018; Achille et al., 2019b; Dwivedi & Roig, 2019; Zhuang et al., 2020; Achille et al., 2019a); however, Standley et al. (2019) show transfer learning algorithms which determine task similarity do not carry over to the…”
Revisiting Meta-Learning as Supervised Learning (2020, methodology): “We expect that applying a more sophisticated and application-dependent metric (e.g., using higher-order statistics (Achille et al., 2019b) or Task2Vec (Achille et al., 2019a)) to characterize task similarity would further improve the performance.”
Efficiently Identifying Task Groupings for Multi-Task Learning (2021, background): “different approach may leverage recent advances in transfer learning focused on understanding task relationships [54, 3, 15, 58, 2]; however, [46] show transfer learning algorithms which determine task similarity do not carry over to the multi-task learning domain and instead propose a multi-task sp”