PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning, Compression, and Meta-Complexity

Halley Goldberg, Mikito Nanashima, Igor C. Oliveira

arXiv:2610.16535v1cs.CCcs.LG

TL;DR

The survey asks how far the prediction–compression connection extends under computational efficiency, including whether it can inform concrete language models. It examines learning and compression through classical generalization and time-bounded complexity, and reports conditional links from efficient learning to cryptographic nonexistence results. Existing correspondences remain idealized and do not yet guarantee outcomes for concrete large language models.

  • Problem

    How far prediction–compression correspondences extend under computational efficiency, and whether they can yield guarantees for concrete language models, remain open questions.

    Source: §6.2.4 · p. 73

  • Method

    The survey examines classical compression-based generalization and idealized prediction–compression correspondences using time-bounded complexity measures.

    Source: §1.2 · p. 7, §3.1 · p. 23, §6.2.4 · p. 73

  • Results

    Efficient PAC learning would imply that AIPRFs do not exist, while efficient heuristic learning would imply that ioPRFs, one-way functions, and pseudorandom generators do not exist.

    Source: §4.4 · p. 33

  • Takeaways & Limitations

    In supervised learning, short hypotheses fitting observations and compressed samples can control generalization.

    Source: §1.2 · p. 7, §3.1 · p. 23

    The surveyed time-bounded correspondences do not yet yield guarantees for concrete large language models.

    Source: §6.2.4 · p. 73

Abstract

from arXiv · show

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.

1 Introduction

The survey formalizes connections among learning, compression, and meta-complexity, asking when these connections support efficient learning and what learning can reveal about computational hardness. It develops the theme through classical generalization, learning-model hierarchies, time-bounded complexity, information theory, and converse hardness results.

1.1 Overview

  • The survey formulates reductions showing when a learner can be transformed into a compressor and when compression can construct a learner.Both directions are studied under computational efficiency constraints.Source: §1.1 · p. 5
  • The survey distinguishes Shannon information, which assigns information through a source distribution, from Kolmogorov complexity, which measures the shortest program for an individual string.Time-bounded descriptions matter for efficient learning because classical Kolmogorov complexity is uncomputable to estimate and key properties may fail under time bounds.Source: §1.1 · p. 5
  • Meta-complexity studies the difficulty of recognizing or finding short, time-bounded descriptions, connecting compression problems to average-case complexity and cryptographic hardness.A decision procedure for separating structured objects from random ones can suffice to construct a learner, despite learning itself being a search task.Source: §1.1 · pp. 5–6

1.2 Organisation

  • Classical connections show how short fitting hypotheses and compressed samples can control generalization in supervised learning.The survey also compares learning tasks from universal sequence extrapolation and distribution learning to heuristic PAC learning, relating them to average-case complexity, meta-complexity, cryptography, and white-box access.Source: §1.2 · p. 7
  • The survey explains how low-complexity distinguishers support supervised reconstruction and time-bounded Solomonoff-style unsupervised learning, and discusses equivalences and learning speedups.It also develops Shannon-theoretic connections among coding and distribution learning, including next-bit prediction and autoregressive language modelling.Source: §1.2 · pp. 7–8
  • The survey's converse direction uses deterministic, randomized, and quantum learning to derive circuit-size and meta-complexity lower bounds.Its scope does not comprehensively cover statistical, information-theoretic, or empirical perspectives on learning and compression.Source: §1.1 · p. 6, §1.2 · p. 8

2.1 Basic Notation

This section establishes notation for strings, coordinate restrictions, and probabilistic polynomial-time algorithms.

2.1 Basic Notation

  • For m ≥ 1, [m] denotes {1, . . . , m}, and ϵ denotes the empty string.The length of string x is |x|, and concatenating strings x and y is written xy.Source: §2.1 · p. 9
  • For a string z and coordinate set S, z|S denotes the string restricted to coordinates in S.The resulting string has length |S|.Source: §2.1 · p. 9
  • PPT denotes probabilistic polynomial time.Source: §2.1 · p. 9

2.2 Probability Theory and Information Theory

This section introduces notation and definitions for probability distributions, divergence, and entropy used in the survey.

2.2 Probability Theory and Information Theory

  • The section defines distribution-sampling notation, uniform distributions, and total variation distance, and notes the relation between KL-divergence and statistical distance.For x sampled from D, x ∼ D; Uℓ is uniform over {0,1}^ℓ.Source: §2.2 · p. 9
  • The Kullback–Leibler divergence is defined for distributions on the same finite set.Source: §2.2 · p. 9
  • The section states a chain rule for KL-divergence of random vectors and defines entropy for a finite-set distribution.It also introduces conditional KL-divergence for random pairs.Source: §2.2 · p. 9

2.3 Learning Frameworks

The section distinguishes supervised learning from unsupervised learning and introduces five frameworks for prediction or modeling. These range from predicting sequence continuations and learning distributions to PAC, agnostic, and heuristic learning.

2.3 Learning Frameworks

  • The section classifies sequence extrapolation and distribution learning as unsupervised, while PAC and heuristic learning use labeled examples and are supervised.Source: §2.3 · p. 10

2.3.1 Sequence Extrapolation

  • Sequence extrapolation predicts a sequence's next block from its prefix when the source is generated by a short randomized program.The goal is to approximate the source's conditional distribution rather than guess the next block exactly.Source: §2.3.1 · p. 10

2.3.2 Learning Distributions

  • Distribution learning uses independent samples to produce a circuit whose sampled distribution is close to the unknown source.The framework measures both running time and sample complexity.Source: §2.3.2 · p. 11

2.3.3 PAC Learning

  • PAC learning seeks a hypothesis with low error on fresh examples drawn from the target distribution, with high probability.The learner receives independently sampled labeled examples; weak learning requires only inverse-polynomial advantage over random guessing.Source: §2.3.3 · pp. 11–12

2.3.4 Agnostic Learning

  • Agnostic learning allows arbitrary input-label distributions and measures performance against the best concept in the chosen class.The setting does not assume labels arise from a fixed target function in that class.Source: §2.3.4 · p. 12

2.3.5 Heuristic Learnability

  • Heuristic learnability measures prediction on average over both a sampled target function and sampled examples, allowing rare failures.Weak and strong average predictability distinguish inverse-polynomial advantage from advantage bounded away from random guessing by an inverse polynomial.Source: §2.3.5 · p. 13

2.4 Theoretical Computer Science

This section introduces cryptographic variants and defines compression, circuit, and meta-complexity notions for studying computational difficulty, including Kolmogorov complexity as effective compression and circuits as succinct representations of Boolean functions. It surveys meta-complexity problems, natural properties linking circuit lower bounds to efficient tests, and pseudorandomness notions used in cryptography and learning.

2.4.1 Cryptography

  • Hardness-to-cryptography connections motivate considering infinitely-often security and auxiliary-input primitives, the latter a weaker assumption than standard cryptography.Infinitely-often security allows failure at finitely many input lengths; learning hardness at a fixed length may yield cryptographic security only at infinitely many lengths.Source: §2.4.1 · p. 14

2.4.2 Kolmogorov Complexity

  • Kolmogorov complexity captures best effective compression up to an additive constant, while time-bounded versions constrain decompression and Levin’s Kt jointly accounts for description length and runtime.Randomized variants are relevant to randomized computation; rKt randomizes execution, whereas pKt allows descriptions to depend on shared randomness, and derandomization assumptions relate Kpoly(t) and rKpoly(t) up to an additive logarithmic term.Source: §2.4.2 · pp. 16–17

2.4.3 Circuit Complexity

  • A small circuit is a local-decoding compression of a Boolean truth table, and TC0 threshold circuits model neural networks while super-polynomial lower bounds for depth-2 circuits remain a frontier.TC0 uses threshold gates; the cited passage identifies proving super-polynomial circuit-size lower bounds for an explicit function as a current frontier.Source: §2.4.3 · pp. 18–19

2.4.4 Meta-Complexity

  • Meta-complexity asks about the complexity of objects under measures such as circuit or Kolmogorov complexity; MCSP tests whether a truth table has a circuit within a size threshold.Partial-MCSP instead asks whether a circuit within a size threshold fits a collection of input/output pairs.Source: §2.4.4 · p. 20
  • MINKT asks whether Kt(x) ≤ s; it is in NP, is not in P assuming cryptographically secure one-way functions, and is not known to be NP-complete.Source: §2.4.4 · p. 20
  • MKtP is in EXP, while proving MKtP ∉ P remains open; such a lower bound would imply only EXP ⊈ P, already known from the time hierarchy theorem.Source: §2.4.4 · pp. 20–21

2.4.5 Natural Properties

  • [RR97] showed that many circuit-size lower-bound arguments implicitly yield efficient tests separating low-complexity functions from a large set of random functions.A natural property is constructive, accepts a set containing at least half of all N-bit strings with probability at least 2/3, and accepts each function in C[s] with probability at most 1/3.Source: §2.4.5 · p. 21
  • Natural properties use prBPP because the randomized procedure may accept some strings with probability near 1/2, yielding a promise problem rather than a language.Source: §2.4.5 · p. 21

2.4.6 Pseudorandomness

  • A generator fools a distinguisher class when every member's advantage is at most ε; cryptographic generators fool potentially slower tests, while complexity-theoretic generators can support reconstruction for learning.Source: §2.4.6 · p. 22

3 Classical Connections Between Learning and Compression

Model compression connects short descriptions to generalization, while sample compression connects retaining a few examples to PAC learnability. Together, these connections relate the information retained from data to learning guarantees.

3.1 Model Compression

  • A consistent hypothesis finder over a finite hypothesis class generalizes from sufficiently many examples: with probability at least 1 −δ, its output has error at most ε.The Occam argument bounds the chance that any substantially incorrect candidate agrees with the sample.Source: §3.1 · p. 23
  • If the finder runs in polynomial time, outputs polynomial-length models, and those models are efficiently evaluatable, this construction gives an efficient PAC learner.The training sample uses m(n + 1) bits, while the extracted explanation uses ℓ(n) bits.Source: §3.1 · p. 24
  • For linear threshold functions, linear programming finds polynomial-description-length consistent rational weights, yielding a distribution-independent PAC learner.There are 2^O(n^2) distinct linear threshold functions on {0, 1}^n.Source: §3.1 · p. 24
  • Feature expansion turns degree-d polynomial threshold functions into linear threshold functions, so a polynomial threshold degree bound yields a PAC learner without knowing the target representation.The passage also names decision trees, DNF formulas, and bounded-depth Boolean formulas among classes reached by this approach.Source: §3.1 · pp. 24–25

3.2 Sample Compression

  • Sample compression retains at most k observed examples plus ℓ bits of side information, from which reconstruction produces a hypothesis consistent with the original sample.The reconstructed hypothesis need not have a short standalone description.Source: §3.2 · p. 25
  • For axis-aligned rectangles, retaining the four extreme positive examples reconstructs a consistent rectangle, giving a scheme with k = 4 and ℓ = 0.Those extreme points determine the reconstructed rectangle and suffice to recover every sample label.Source: §3.2 · pp. 25–26, Figure 4 · p. 26
  • A bounded sample compression scheme yields a PAC learner; it is efficient when compression, reconstruction, and evaluation are efficient, and otherwise gives an information-theoretic sample-complexity bound.The theorem guarantees error at most ε with probability at least 1 −δ.Source: §3.2 · pp. 26–27
  • For binary concept classes, bounded sample compression characterizes PAC learnability, but the known 2^O(d) size bound exceeds the conjectured O(d) bound for VC dimension d.Closing the gap would match retained information to the parameter governing PAC sample complexity up to constant factors.Source: §3.2 · p. 27

4 Complexity-Theoretic Foundations of Learning and Compression

This section examines complexity-theoretic foundations of learning and compression by relating learning paradigms and white-box learning to cryptography and time-bounded Kolmogorov complexity. It also describes how these connections characterize learnability and link efficient distribution learning to efficient agnostic learning.

4.1 Learning Paradises

  • The five paradises assume learning over unrestricted Boolean circuits, while feasible-distribution PAC learning is adopted as a representative supervised setting.In PAC learning, examples come from a feasible distribution but the target may be arbitrary; heuristic learning additionally assumes a feasible distribution over concepts, as in key-generation and encryption experiments.Source: §4.1 · p. 28

4.2 Basic Relations

  • P.I implies P.II, P.II implies P.III, P.III implies P.IV, and P.IV implies P.V.These scenarios range from efficient extrapolation and distribution learning to weak heuristic learning.Source: §4.2 · p. 28

4.3 Impagliazzo’s Worlds and Meta-Complexity

  • The feasibility of P.I–P.V is tied to estimating time-bounded Kolmogorov complexity, with learning paradises positioned between Heuristica and Pessiland.The section connects average-case easiness of NP through Gap-MINKT ∈ P to extrapolation and weaker learning scenarios, and links P.V to one-way functions and average-case complexity estimation.Source: §4.3 · p. 31, Figure 5 · p. 32
  • It remains open whether efficient estimation of time-bounded Kolmogorov complexity makes NP easy on average or in the worst case.The stated questions are whether Gap-MINKT ∈ P implies DistNP ⊆ AvgP and whether MINKT ∈ P implies NP ⊆ P.Source: §4.3 · pp. 31–32

4.4 Auxiliary Results

  • If efficient heuristic learning is possible, infinitely-often pseudorandom functions, one-way functions, and pseudorandom generators do not exist.The proof distinguishes an oracle implementing the pseudorandom function from a random function by testing a learner’s prediction on a fresh input; the reductions to one-way functions and generators are standard.Source: §4.4 · p. 33
  • Efficient PAC learning rules out auxiliary-input pseudorandom functions, including when membership queries are allowed.The learner’s membership queries can be simulated through the oracle being tested.Source: §4.4 · p. 33
  • Efficient distribution learning also rules out auxiliary-input pseudorandom functions.The proof learns a sampler for the graph distribution of the candidate function and validates it on a fresh input.Source: §4.4 · p. 34

4.5 White-Box Learning and One-Way Functions

  • This connection supports the implication from efficient distribution learning (P.II) to efficient agnostic learning (P.III).The section notes that the result yields white-box learning for SIZE[s] for any s, which may be used in a proof of that implication.Source: §4.5 · p. 34, §4.5.2 · p. 35

4.5.1 White-Box Learning Frameworks

  • White-box learning gives the learner an explicit circuit sampling the labelled-example distribution, but computing labels on a desired input may remain hard.The learner can generate its own labelled examples by running the sampler, so it needs no example oracle.Source: §4.5 · p. 34, §4.5.1 · pp. 34–35

4.5.2 White-Box Learning and Breaking Auxiliary-Input One-Way Functions

  • Over PSAMP/poly, white-box learning of all Boolean functions is easy if and only if auxiliary-input one-way functions do not exist.For the converse, a white-box learner can be used to distinguish pseudorandom generator outputs from random strings, breaking the assumed construction.Source: §4.5.2 · pp. 35–38
  • Whether white-box learning SIZE[s] for a fixed polynomial s implies the nonexistence of auxiliary-input one-way functions remains open.A positive answer would make white-box learnability of SIZE[s] and all Boolean functions equivalent over distributions samplable in PSAMP/poly.Source: §4.5.2 · p. 35

5.1 Detecting Structure: Supervised Learning via Distinguishers

This section examines how distinguishers connect meta-complexity algorithms and natural properties to supervised learning, including through breaking pseudorandom generators and distinguishing their outputs from random strings. It covers learners using random examples or membership queries and extensions to agnostic and efficiently samplable-distribution settings under stated conditions.

5.1 Detecting Structure: Supervised Learning via Distinguishers

  • Meta-complexity algorithms that distinguish high- from low-complexity objects can break pseudorandom generators, whose reconstruction properties then yield learners.The section considers Direct Product and Nisan-Wigderson generators; the resulting learners can use random examples or require membership queries, respectively, and can be unconditional when the corresponding assumption is known to hold.Source: §5.1 · p. 39

5.1.1 From Distinguishers to Predictors

  • Yao’s hybrid argument converts a distinguisher with advantage ε into a next-bit predictor with expected advantage at least ε/ℓ at some bit.The argument compares hybrids that replace the output bits one at a time, locating a bit where the distinguisher’s probability changes by at least ε/ℓ in expectation.Source: §5.1.1 · pp. 39–40

5.1.2 Direct Product and Random Examples

  • A successful distinguisher against a candidate PRG construction yields a learner succeeding with high probability over randomly sampled target functions; RRHS refutation yields a weak PAC learner.This learner can be boosted to a strong PAC learner.Source: §5.1.2 · pp. 40, 42
  • Efficient agnostic learning of P/poly over PSAMP/poly distributions follows from DistNP ⊆ AvgP, and the same conclusion follows from the weaker assumption DistNP ⊆ AvgBPP.[HN21] reduces correlative RRHS refutation to Gap-MINKT; instead establishes worst-case easiness for probabilistic time-bounded Kolmogorov complexity pKt.Source: §5.1.2 · pp. 43–44
  • Average-case easiness of Kt or KT for randomized algorithms over the uniform distribution yields agnostic learners, but removing a distribution-knowledge caveat for nonuniform targets requires worst-case KT easiness.KT is polynomially related to Boolean circuit size; for Kt, the argument handles the lack of a coding theorem by incorporating additional randomness, while worst-case KT easiness uses amortization for concatenated samples.Source: §5.1.2 · pp. 44–45

5.1.3 Nisan-Wigderson and Membership Queries

  • NW reconstruction turns a distinguisher for the Nisan-Wigderson generator into a circuit approximating its underlying function; natural properties use this approach to obtain PAC learning with membership queries.The NW designs have bounded pairwise intersections, and reconstruction produces a polynomial-size circuit with inverse-polynomial approximation advantage.Source: §5.1.3 · p. 45
  • Carmosino et al. obtain an unconditional quasi-polynomial-time learning algorithm for AC0[p] using its known natural property [CIKK16].This complexity-theoretic approach remains the only known learning technique for AC0[p].Source: §5.1.3 · p. 46
  • The AC0[p] natural property distinguishes Nisan-Wigderson generator outputs from random truth tables, and reconstruction converts the distinguisher into a hypothesis using membership queries [CIKK16].The reconstruction procedure requires oracle access to the target function.Source: §5.1.3 · p. 46, Figure 6 · p. 46
  • Tolerant natural properties yield agnostic learners, and the framework extends AC0[p] learning to targets at distance 1/poly(n) from AC0[p].Tolerant natural properties are essentially equivalent to easiness of the Minimum Approximate Circuit Size Problem (MACSP).Source: §5.1.3 · pp. 46–47
  • Whether AC0[p] can be learned in subexponential time under the uniform distribution using random examples instead of membership queries remains open.Recent related work is cited as [GJK+24].Source: §5.1.3 · p. 47
  • The result extends to efficiently samplable distributions when the sampler code is known and the target composed with the sampler belongs to the learner’s concept class [BCK+22].This extension uses distributional inversion; natural properties imply efficient distributional inverters for every polynomial-time function.Source: §5.1.3 · p. 47

5.2 Solomonoff Induction: Unsupervised Learning via Kolmogorov Complexity

The section connects Solomonoff induction to sequence extrapolation, then shows how time-bounded Kolmogorov complexity can support efficient prediction under a meta-complexity assumption.

5.2 Solomonoff Induction: Unsupervised Learning via Kolmogorov Complexity

  • Under GapKt-vs-K ∈pr-BPP, extrapolation runs in randomized polynomial time when m ≥ eO(n^2 · s · ε^-6 · δ^-5).This is Theorem 5.2’s guarantee for the stated parameters.Source: §5.2 · p. 48

5.2.1 The Classical Theory

  • Solomonoff induction weights continuations with low Kolmogorov complexity, and its universal measure dominates the source distribution up to a factor 2^-O(s).The resulting global log-loss bound decomposes into one-step prediction errors; Pinsker’s inequality gives ε-close predictions on all but a δ-fraction of positions for sufficiently large m = O(s · ε^-2 · δ^-1).Source: §5.2.1 · pp. 48–49
  • For sequences generated by an s-bit randomized program, Solomonoff induction predicts accurately on most positions once m ≫ s/ε^2.In the time-unbounded setting, it solves extrapolation when the sequence is sufficiently longer than the generator program’s description.Source: §5.2.1 · pp. 48–49

5.2.2 The Time-Bounded Setting

  • For efficiency, the time-bounded predictor moves long-range history into advice and keeps only a short local prefix as context.The time-bounded method separates the roles of advice and observed context while maintaining correct extrapolation.Source: §5.2.2 · p. 50
  • With b = Ω(s/log t) blocks, amortized KL-divergence is O(log t), and choosing w = Ω(ε^-2 · δ^-1 · log t) yields m = Ω(s · ε^-2 · δ^-1).For most positions and inputs, the time-bounded universal sampler runs in poly(t) time.Source: §5.2.2 · pp. 51–52
  • For δ = o(1), the known sample lower bound as a function of ε and δ is suboptimal, and obtaining efficient prediction requires a more involved argument.The survey states as an open problem whether the sample bound can be reduced to eO(s · ε^-2 · δ^-1) under the same assumption.Source: §5.2.2 · p. 52

5.3 Equivalences Between Learning and Meta-Complexity

This section relates efficient learning to the ease of suitable meta-computational problems. It develops equivalences for random-example learning and membership-query learning, showing how hardness and structure detection connect to learner construction.

Equivalences Between Learning and Meta-Complexity

  • A suitable meta-computational problem associated with a learning model and concept class is easy exactly when that class is efficiently learnable in the model.This equivalence reframes learning as detecting structure in data, although typical meta-complexity problems inspect the full input while learning accesses only a small portion.Source: §5.3 · p. 52

Learning from Membership Queries

  • Efficient learning with membership queries is equivalent to the existence of a promise-BPP natural property against the circuit class.Such a property accepts a dense set of truth tables while rejecting every truth table computed by a low-complexity circuit.Source: §5.3 · pp. 52, 54

Learning from Random Examples

  • Efficient PAC learning of general Boolean circuits from uniform random examples is equivalent to average-case easiness of Partial-MCSP.The reverse direction uses a learner’s prediction on a held-out example to distinguish labels consistent with a circuit from random labels.Source: §5.3 · p. 53

5.4 Learning Speedups: Reducing the Running Time via Meta-Complexity

Complexity-theoretic techniques yield generic learning speedups by using a learner on harder concepts over fewer input bits. The result is subexponential-time learning under uniform-distribution and membership-query assumptions.

Learning Speedups: Reducing the Running Time via Meta-Complexity

  • The speedup reduces learning f on n bits to learning a more complex function on m ≪ n bits, using the original learner on the smaller instance.A good hypothesis for the auxiliary function can be transformed into a good hypothesis for f.Source: §5.4 · pp. 55–56
  • A nontrivial uniform-distribution learner for C-circuits of size n^k yields a learner for the same size class running in O(2^nε) time, for every k and ε > 0.The theorem assumes C is at least as powerful as bounded-depth circuits with parity gates, and that the initial learner works for every constant circuit-size exponent.Source: §5.4 · p. 55
  • A nontrivial learner yields a promise-BPP natural property, which the Nisan–Wigderson reconstruction converts into a PAC learner using membership queries.The natural-property and reconstruction stages run in time polynomial in 2^m; choosing m = n^γ gives the stated subexponential bound after amplification.Source: §5.4 · pp. 55–56
  • The speedup phenomenon is currently restricted to uniform-distribution PAC learning with membership queries and reasonably expressive classes.The class expressivity supports implementation of the techniques from.Source: §5.4 · p. 56

6 Learning vs Compression via Shannon’s Information Theory

This section uses Shannon’s information theory and source coding to frame connections between learning and compression, including their relationship to meta-complexity and language modeling.

6 Learning vs Compression via Shannon’s Information Theory

  • The survey reviews source-coding tools for connecting learning with compression and explains how meta-complexity fits this information-theoretic framework.It also briefly relates this perspective to language modeling.Source: §6 · p. 57

6.1 Starting from Shannon’s Information Theory

Shannon’s theory characterizes compression when the source distribution is known, while universal coding addresses unknown sources and Kolmogorov complexity captures ideal individual-string description length. The section derives information-theoretic transformations between distribution learning and coding, then identifies computational obstacles to efficient versions.

6.1 Starting from Shannon’s Information Theory

  • For a known source D, Shannon coding achieves expected code length at most H(D) + 1, and entropy lower-bounds the expected length of uniquely decodable codes.The source distribution is assumed known to both encoder and decoder.Source: §6.1 · p. 57

6.1.1 Universal Coding and Kolmogorov Complexity as Its Ultimate Goal

  • Universal coding avoids an explicit source description, but Lempel–Ziv’s source-universal guarantee does not compress every simple individual sequence, such as concatenated binary representations of the integers.Kolmogorov complexity is the ideal distribution-free description length; its time-bounded variant also constrains decoding time.Source: §6.1.1 · p. 58

6.1.2 Universal Coding and Learning

  • A distribution learner yields a code with expected length close to the source entropy, while a code approximating Kolmogorov complexity can yield a learner for distributions with short sampler descriptions.For the latter transformation, the sampler-description length contributes an additive term; amortizing it over a batch can make the resulting total-variation approximation small.Source: §6.1.2 · pp. 59, 62, 63
  • If the learned distribution E is close to D in total variation, its ideal code length is rarely much larger than D’s, supporting expected-code-length and Kolmogorov-complexity comparisons.The bound holds with high probability over x drawn from D.Source: §6.1.2 · pp. 59–60
  • These information-theoretic transformations do not establish computational efficiency: Kolmogorov complexity is uncomputable, and evaluating or sampling the conditional distribution may be inefficient.The resulting question concerns efficient learning versus efficient compression near time-bounded Kolmogorov complexity for efficiently samplable distributions.Source: §6.1.2 · p. 63

6.2 Computational Learning and Meta-Complexity

This section examines connections between learning and time-bounded compression, including efficient transformations in both directions and the computational constraints they depend on. It also surveys how average-case prequential compression relates to sequential generation and next-bit prediction, and how language models connect prediction with compression without current time-bounded guarantees for concrete large language models.

6.2.1 Learning to Compression via Arithmetic Coding

  • An efficient next-bit predictor with inverse-polynomial additive accuracy enables arithmetic coding without support enumeration; encoding and decoding need only n conditional-probability queries, and accuracy affects code length rather than correctness.For randomized predictors, the encoder and decoder must share fixed random coins to obtain identical answers.Source: §6.2.1 · pp. 64–65
  • A sampler alone does not generally yield an efficient next-bit predictor: such a gap exists if AIOWFs exist, while under their nonexistence distributional inversion can produce predictors from efficient samplers.For general efficiently samplable sources, polynomial-time compression close to entropy is impossible under the plausible assumption SZK ≠ BPP.Source: §6.2.1 · pp. 64–65
  • Next-bits-predictable distributions admit efficient rKpoly coding [HLN24], with expected encoding length at most H(Dn) + O(log n), and average-case coding extends to efficiently samplable distributions if one-way functions do not exist.The average-case bound absorbs rare low-probability next bits into additive overhead; the extension uses distributional inversion.Source: §6.2.1 · pp. 65–66

6.2.2 Compression to Learning over Polynomially Many Messages

  • Direct conditional learning from unconditional compression remains open: conditional compressors can be harder to obtain, and existing results do not generally turn unconditional compression into conditional KL guarantees without also compressing contexts well.Conditional coding and symmetry of information are natural tools, but their time-bounded versions are tied to complexity-theoretic and cryptographic assumptions.Source: §6.2.2 · pp. 67–69
  • For logarithmic-length outputs, an efficiently computable, polynomially bounded compressor yields enumerable incremental-description-length conditional hypotheses with average conditional KL closeness when the induced joint distribution is close to D.The polynomial-size output range lets the learner normalize and sample the weights by direct enumeration.Source: §6.2.2 · pp. 67–68

6.2.3 Compression to Learning over General Messages

  • Without infinitely-often one-way functions, every efficiently samplable distribution represented by a sampler of logarithmic computational depth is polynomial-time learnable in total variation distance.Universal extrapolation runs in polynomial time for such low-depth conditioning prefixes; more generally, its running time grows exponentially with their computational depth.Source: §6.2.3 · p. 70
  • Universal extrapolation requires ruling out one-way functions, a dependence that is unavoidable for general distribution classes because efficient universal extrapolation itself implies their nonexistence.It remains unclear whether this approach can give unconditional learning guarantees for restricted classes that exclude cryptographically hard sources.Source: §6.2.3 · p. 70
  • Universal extrapolation remains open in the worst case: distributional inversion takes exponential time in the conditioning prefix's computational depth.The section asks what weakest assumption enables efficient extrapolation for every prefix, and whether a meta-complexity assumption characterizes it.Source: §6.2.3 · p. 70
  • For constant accuracy and confidence, efficient sequential generation is equivalent to average-case prequential qpoly-compression and, equivalently, average-case prequential rKpoly-compression.The compression groups consecutive elementary symbols into O(log n)-symbol blocks, while the generator predicts one symbol at a time; Hirahara and Nanashima develop this characterization.Source: §6.2.3 · p. 71
  • Under the stated compression condition, a polynomial-time learner outputs a polynomial-time randomized next-bit predictor for any P/poly-samplable distribution.Theorem 6.8 assumes the condition for every batch size and uses blocks of length C log n; the guarantee is Yao-style and does not require a support-size restriction.Source: §6.2.3 · pp. 71–72
  • The transformation uses completed blocks as advice and rejection sampling within O(log n)-length blocks to amortize per-block KL loss, without assuming one-way-function hardness.The current construction's rejection-sampling time is n^O(1/ϵ), so it is polynomial for constant ϵ but not jointly polynomial in n and ϵ^-1; extending the equivalence to arbitrary parameters remains open.Source: §6.2.3 · p. 72

6.2.4 Language Modeling

  • Autoregressive language models use next-token conditional distributions, and arithmetic coding turns those probabilities into lossless codes, making log-loss minimization equivalent to minimizing encoding length.A compressor's incremental code lengths can also be normalized into next-token distributions, though good overall compression does not guarantee accurate conditionals.Source: §6.2.4 · p. 73
  • Time-bounded complexity measures provide idealized benchmarks for prediction and compression, but existing correspondences do not yet guarantee performance for concrete large language models.Transferring compression guarantees to efficient sequential-generation guarantees without quantitative loss is identified as a future research direction.Source: §6.2.4 · p. 73

7 Meta-Complexity and Computational Hardness from Learning

The section surveys how learning algorithms can yield complexity lower bounds, including unconditional hardness results for meta-computational problems. It also highlights open learning and lower-bound questions at the frontier, including for TC0.

7.1 Deterministic Learners

  • Deterministic uniform-PAC learners with error ε ≤0.499 yield MKtP ∉ C at time 2^(n/2)/n^ω(1), or MKtP ∉ P from size-n^k circuits learned in 2^n/n^ω(1).Both results use membership queries; the second applies for every k ≥1.Source: §7.1 · p. 75

7.2 Randomized and Quantum Learners

  • Randomized or quantum uniform-PAC learners for polynomial-size C-circuits in 2^n/n^ω(1) imply BPE ⊈ C(poly) or BQE ⊈ C(poly), respectively.Both theorems assume membership queries and error ε < 0.499.Source: §7.2 · p. 76

A typical circuit class C

  • For TC0, a nontrivial learner would imply an explicit-function circuit lower bound, but neither such a learner nor a superpolynomial lower bound is known.The section describes this as a recurring pattern: at frontier classes, the learner and lower-bound questions have the same status.Source: §7.2 · p. 76, A typical circuit class C · p. 77, Figure 7 · p. 77

7.3 Unconditional Meta-Complexity Lower Bounds via Learning

  • A nontrivial randomized or quantum learner for Boolean functions 1/n-approximable by poly(log n)-degree Torus polynomials would yield a new lower bound against ACC0.The implication uses that every ACC0 function admits such approximating polynomials.Source: §7.3 · p. 78
  • Nontrivial randomized or quantum learning of quasi-polynomial-size DOR-MAJ-AND circuits with polylogarithmic bottom fan-in would also imply lower bounds against ACC0.This follows by combining Theorem 7.3 with the stated ACC0 simulation.Source: §7.3 · p. 78
  • MrKtP ∉ BPP follows unconditionally by assuming MrKtP ∈ BPP, deriving randomized circuit learning and a BPE lower bound, then contradicting that assumption via reductions to MrKtP.MrKtP asks for an estimate of randomized time-bounded Kolmogorov complexity rKt; the analogous MKtP ∉ P problem remains open.Source: §7.3 · p. 79
  • The section derives lower bounds only from PAC learning; stronger consequences from more expressive learning tasks remain a direction for further research.The examples named are distribution learning and sequence extrapolation.Source: §7.3 · p. 79

8 Related Work

The related work connects the survey’s themes to neighboring research on learning, compression, prediction, and complexity. It distinguishes these formal connections from practical analogues and from other uses of compression.

Search vs Decision in Meta-Complexity

  • Meta-complexity’s search-versus-decision gap connects to reconstruction arguments in learning and to direct search-to-decision reductions for time-bounded Kolmogorov complexity [HLN24].The gap is between recognizing that a short description exists and producing one.Source: §8 · p. 80

Compression in Supervised Learning

  • Model compression reduces a trained model or its representation, while dataset distillation replaces training data with synthetic examples that recover comparable performance [HMD16].These are distinct from the survey’s sample-compression connection to generalization and the sample compression conjecture.Source: §8 · p. 80

Practical Analogues of the Learning Paradises

  • Practical learning systems provide analogues to the survey’s learning paradises, but their restricted-instance successes do not match the paradises’ uniform guarantees over broad families.The discussion gives examples involving sequence prediction, generative modeling, noisy labels, and real-world heuristics.Source: §8 · pp. 80–81

Cryptographic Hardness of Learning

  • Cryptographic research also studies hardness of learning from assumptions [PV88, KV94b, KS09, DLSS14], while related work links cryptographic primitives to white-box learning and meta-complexity.The survey notes both barriers based on worst-case assumptions [ABX08] and results deriving tradeoffs from NP hardness [BKST25].Source: §8 · pp. 81–82

Description Length in Statistical Inference and Prediction

  • Compression also supports statistical inference and sequential prediction: MDL and MML use description length for model selection, while predictive log-loss can define a code.These traditions generally emphasize statistical performance rather than the efficient computational transformations central to the survey.Source: §8 · p. 82

Other Uses of Compression

  • Other compression connections include algorithmic statistics’ separation of model from randomness and compressor-based similarity measures such as normalized compression distance.The latter uses compression directly for data analysis without learning an explicit model.Source: §8 · p. 82

Related papers

Loading 2610.16535v1…