Learning, Compression, and Meta-Complexity

Halley Goldberg; Mikito Nanashima; Igor C. Oliveira

cs.CCOct 12, 2026

Learning, Compression, and Meta-Complexity

Authors: Halley Goldberg, Mikito Nanashima, Igor C. Oliveira

Organizations: Department of Computer Science, University of Oxford · School of Computing, Institute of Science Tokyo · Department of Computer Science, University of Warwick

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.

Figures & tables

Panel of Figure 1 — Figure 1: Three perspectives on structure in data: learning, compression, and meta-complexity. We investigate correspondences among them through several lenses, including Shannon’s information theory, modern variants of (time-bounded) Kolmogorov complexity, and the theory of computational pseudorandomness. Interestingly, these connections can be used both to design new learning algorithms and to prove that certain compression problems admit no efficient algorithms.

Panel of Figure 2 — Figure 2: A depth- $2$ threshold circuit $C$ . The top threshold gate receives the outputs taking values in $\{0,1\}$ from the threshold gates in the bottom layer, each of which is connected to the input variables $x_{1},\ldots,x_{n}$ .

Panel of Figure 3 — Figure 3: A diagram representation of a natural property ( Definition 2.31 ). The outer rectangle is the ground set of all $N$ -bit strings. The small region represents the “structured” strings corresponding to functions in the low complexity class $\mathcal{C}_{n}[s(n)]$ . The large region represents the “random” strings in $\mathcal{F}_{n}\subseteq\{0,1\}^{N}$ . Its relative size illustrates the largeness condition, while $\mathcal{F}_{n}\cap\mathcal{C}_{n}[s(n)]=\varnothing$ illustrates usefulness against $\mathcal{C}_{n}[s(n)]$ . A natural property is constructive : it postulates the existence of an efficient algorithm that distinguishes these two sets, thereby separating the structured strings in $\mathcal{C}_{n}[s(n)]$ from the random strings in $\mathcal{F}_{n}$ .

Panel of Figure 4 — Figure 4: A sample compression scheme for axis-aligned rectangles in the plane. The four extreme positive examples determine the reconstructed rectangle $R_{S}$ . Since $R_{S}\subseteq R^{\star}$ , where $R^{\star}$ denotes the unknown target rectangle, $R_{S}$ contains every positive sample point and no negative sample point. All labels in the original sample can be reconstructed from the four extreme positive points.

Panel of Figure 5 — Figure 5: Learning paradises P.I – P.V ( Section 4.1 ) between Impagliazzo’s worlds [ 100 ] Heuristica and Pessiland, including their relationship to compression and meta-complexity via the computational task of estimating time-bounded Kolmogorov complexity.

Panel of Figure 6 — Figure 6: The diagram presents the key steps of the $\mathsf{AC}^{0}[p]$ learning algorithm of Carmosino, Impagliazzo, Kabanets, and Kolokolova [ 32 ] , a breakthrough result in computational learning theory. The Razborov and Smolensky circuit lower bounds [ 154 , 165 ] yield a natural property [ 153 ] against $\mathsf{AC}^{0}[p]$ . For an unknown target $f\in\mathsf{AC}^{0}[p]$ , this property distinguishes the output of the Nisan-Wigderson generator $G^{f}_{NW}$ [ 142 ] from a random truth table. The NW reconstruction procedure converts the distinguisher into a hypothesis using membership query access to $f$ . To date, this complexity-theoretic approach remains the only known learning technique for this circuit class.

Panel of Figure 7 — Figure 7: Two closely related questions about a typical circuit class $\mathcal{C}$ , illustrated by the class $\mathsf{TC}^{0}_{2}$ of depth- $2$ threshold circuits (see Section 2.4.3 ). By Theorem 7.2 and Theorem 7.3 , a nontrivial classical or quantum learner for $\mathcal{C}$ yields a new circuit size lower bound against $\mathcal{C}$ for an explicit function. Conversely, a combinatorial lower bound that naturalises yields a constructive property that can be converted into a learning algorithm for $\mathcal{C}$ , as discussed in Section 5.1 . A recurring pattern across circuit classes at the frontier is that the two questions have the same status: either learners and lower bounds are known, or both remain open. In particular, for $\mathsf{TC}^{0}_{2}$ , neither a nontrivial learner nor a superpolynomial circuit size lower bound for an explicit function is known.

Kolmogorov Complexity

See all 12 papers

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
Oct 9, 2026Simone Garatti, Marco C. CampiSample Compression Statistical Learning Theory
Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia. · Dipartimento di Ingegneria dell’Informazione - Universit`a di Brescia, via Branze 38, 25123 Brescia, Italia.
Does Compression Imply Generalization? A Minimum Description Length Perspective
Oct 15, 2026Lincen Yang, Jiayang Shi, Nan Pu +4Neural Network Generalization Generalization Bounds
Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands · Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands · Hefei University of Technology, Hefei, China +3
An Introduction to Compression-Based Machine Learning
Sep 18, 2026John Hurwitz, Edward Raff, Charles K. NicholasMinimum Description Length
University of Maryland, Baltimore County · CrowdStrike · Syracuse University

Oct 9, 2026J/K move · Enter open · S save

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Simone Garatti, Marco C. Campi

Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia. · Dipartimento di Ingegneria dell’Informazione - Universit`a di Brescia, via Branze 38, 25123 Brescia, Italia.

Sample Compression Statistical Learning Theory Information-Theoretic Generalization Bounds

Open paper AskPDF arXiv

Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity

\boldsymbol{k}

, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order

O(\sqrt{\ln N/N})

above

\boldsymbol{k}/N

. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level

1-δ

, the risk is bounded with probability at least

1-δ

\frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right),

uniformly over all possible values of

\boldsymbol{k}

. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term

\boldsymbol{k}/N

is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the

O(1/\sqrt{N})

convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the

O(1/\sqrt{N})

rate.

Abstract

Kolmogorov Complexity

Explore similar work

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Does Compression Imply Generalization? A Minimum Description Length Perspective

An Introduction to Compression-Based Machine Learning