Links between learning algorithms compression and computational complexity
Learning, Compression, and Meta-Complexity
Computational ComplexityMachine Learning
Summary
The paper looks at how learning from data is deeply connected to compressing information efficiently. It explains how methods from computer science complexity theory help design better learning tools with proofs that they work. Also, it shows how studying learning algorithms sheds light on tough problems about how hard it is to compress data. A key part is meta-complexity, which studies how difficult it is to solve compression problems under time limits.
What this means in practice
- •For machine learning engineers: Design learning algorithms with formal guarantees inspired by complexity theory techniques.
- •For data compression developers: Gain insights on computational difficulty of compression tasks guided by meta-complexity theory.
A survey. It maps existing work.
Authors
Halley Goldberg, Mikito Nanashima, Igor C. Oliveira
Abstract
The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory. Here we focus on settings in which that intuition can be made mathematically precise, surveying formal connections among learning algorithms, data compression, and computational complexity theory, with an emphasis on recent progress and current frontiers. We describe how techniques from complexity theory can guide the design of both supervised and unsupervised learning algorithms with provable guarantees, and conversely, how learning algorithms can yield new insights and results in complexity theory. A central theme is the role of data compression as a bridge between learning and complexity, especially through an area called meta-complexity, which studies the computational difficulty of compression problems and time-bounded variants of Kolmogorov complexity.