PaperlayerView exact revision on arXiv

Source-linked AI summary

From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence

Marc Finzi, Shikai Qiu, Yiding Jiang, Pavel Izmailov, J. Zico Kolter, Andrew Gordon Wilson

arXiv:2601.03220v2cs.LGstat.ML

TL;DR

Classical information measures do not capture useful structure available to computationally bounded learners, motivating a task-independent account of learnable information. The paper introduces epiplexity to measure structural information extracted from data, separating it from time-bounded entropy, and evaluates practical estimators. The reported results show that epiplexity distinguishes data sources and interventions, tracks downstream performance, and correlates with out-of-distribution generalization.

  • Problem

    Shannon information and Kolmogorov complexity assume effectively unlimited observers and do not directly quantify useful structural information that bounded learners can extract from data.

  • Method

    The paper defines epiplexity as structural information extracted by a computationally bounded observer, separates it from time-bounded entropy, and estimates it using neural-network loss curves.

  • Results

    Epiplexity captures differences across data sources, tracks downstream performance, and correlates with out-of-distribution generalization across dataset interventions.

  • Takeaways & Limitations

    Epiplexity provides a task-independent foundation for selecting, generating, or transforming data according to the reusable structural information it induces in learning systems.

  • Takeaways & Limitations

    Classical sophistication has few concrete high-sophistication examples, and its optimal programs may require computation beyond practical bounds.

Abstract

from arXiv · show

Can we learn more from data than existed in the generating process itself? Can new and useful information be constructed from merely applying deterministic transformations to existing data? Can the learnable content in data be evaluated without considering a downstream task? On these questions, Shannon information and Kolmogorov complexity come up nearly empty-handed, in part because they assume observers with unlimited computational capacity and do not target the useful information content. In this work, we identify and exemplify three seeming paradoxes in information theory: (1) information cannot be increased by deterministic transformations; (2) information is independent of the order of data; (3) likelihood modeling is merely distribution matching. To shed light on the tension between these results and modern practice, and to quantify the value of data, we introduce epiplexity, a formalization of information capturing what computationally bounded observers can learn from data. Epiplexity captures the structural content in data while excluding time-bounded entropy, the random unpredictable content exemplified by pseudorandom number generators and chaotic dynamical systems. With these concepts, we demonstrate how information can be created with computation, how it depends on the ordering of the data, and how likelihood modeling can produce more complex programs than present in the data generating process itself. We also present practical procedures to estimate epiplexity which we show capture differences across data sources, track with downstream performance, and highlight dataset interventions that improve out-of-distribution generalization. In contrast to principles of model selection, epiplexity provides a theoretical foundation for data selection, guiding how to select, generate, or transform data for learning systems.

1 Introduction

The paper argues that classical information measures miss how computationally bounded observers extract useful structure from data. It introduces epiplexity to separate learnable structural information from unpredictable content and uses it to reinterpret computation, ordering, likelihood modeling, and data selection.

  • Motivation: Modern transfer across tasks and domains often depends more on the data models encounter than on architectural choices.This motivates evaluating data for broad out-of-distribution generalization rather than treating the training distribution as fixed.
  • Empirical phenomena: Computation and data transformations can increase measurable information by producing emergent, learnable structures, including gliders and invariant measures.The paper also studies how data ordering changes structural information and downstream out-of-distribution performance.
  • Measurement and data selection: Epiplexity can be estimated from neural-network loss curves and correlates with out-of-distribution generalization across data sources and interventions.The paper presents it as a task-independent basis for comparing, selecting, generating, and transforming data.
  • Three paradoxes: Three apparent paradoxes expose tensions between classical information theory and machine-learning practice: deterministic processes cannot increase information, order should not matter, and likelihood modeling is distribution matching.The paper uses these tensions to motivate computationally bounded information measures.
  • Likelihood modeling: Likelihood modeling can let bounded observers learn emergent structures that exceed the structure explicit in the data-generating process.Conway’s game of life illustrates how simple rules generate predictable object species and behaviors useful to bounded observers.
  • Epiplexity: Epiplexity measures structural information that a computationally bounded observer can extract from data, while time-bounded entropy captures random and unpredictable content.The framework makes information observer dependent and distinguishes useful structure from apparent randomness.

2 Background

The background contrasts unbounded notions of randomness and complexity with computationally constrained views. It motivates epiplexity as a data-selection criterion dual to MDL’s model-selection role.

  • Computational perspective: Classical information theory and Kolmogorov complexity treat information and randomness without making the observer’s computational resources central.The paper argues that learnability depends on available computational resources.
  • Shannon information: Shannon information assigns surprisal log 1/P(x) to outcomes and entropy as its expectation over a random variable.In the machine-learning setting, the random variable can represent an entire dataset rather than a single sample.
  • Algorithmic randomness: Martin–Löf randomness characterizes sequences that pass all computable randomness tests, equivalently requiring nearly incompressible prefixes.Finite-sequence randomness can be expressed through randomness discrepancy δ(x) = n − K(x).
  • Algorithmic complexity: Kolmogorov complexity K(x) is the length of the shortest self-delimiting program that outputs and halts on x.Conditional complexity additionally measures the shortest program producing x when given y.
  • Computational randomness: Cryptographic pseudorandomness limits the observer to polynomial-time tests, making generated sequences computationally indistinguishable from random ones.This observer-relative notion supports the paper’s emphasis on computational bounds.
  • Random versus structural information: Sophistication aims to isolate an object’s structural component but offers few concrete high-sophistication examples and can require uncomputably large computation.Complex systems may therefore lose apparent complexity under unbounded descriptions, while bounded observers can regard encrypted or pseudorandom outputs as random.
  • MDL and epiplexity: Epiplexity is presented as MDL’s dual: a criterion for data selection under a fixed computation budget rather than model selection for a fixed dataset.This reframes the object of optimization from explanations of data to data that induces extractable structure.

3 Epiplexity: Structural Information Extractable by a Computationally Bounded Observer

Epiplexity measures the structural information that computationally bounded observers can extract, separating it from time-bounded entropy, the random and unpredictable content remaining under a compute limit.

  • Definition and motivation: Epiplexity captures structural information visible to a computationally bounded observer, while the division between structure and randomness changes with computational constraints.The framework is introduced to address empirical phenomena that classical information measures do not adequately quantify.
  • Computational model: The framework restricts probability models to efficiently implemented programs running on a prefix-free universal Turing machine within a fixed runtime.The model class can be adapted to other constraints, including memory, function classes, or models reachable by a specified optimization procedure.
  • Formal quantities: Epiplexity is the optimal program length, while time-bounded entropy is the expected negative log probability under that program.These quantities arise from minimizing a two-part time-bounded MDL code consisting of model bits and data-given-model bits.
  • Definition and motivation: Time-bounded entropy measures random, unpredictable information, whereas epiplexity measures structure and regularity captured by the best time-bounded model.A uniform random variable has trivial epiplexity but large time-bounded entropy.
  • Examples and consequences: For pseudorandom generators, polynomial-time observers see nearly maximal time-bounded entropy but only negligibly more than constant epiplexity.This distinguishes high random content from the absence of efficiently extractable structure.
  • Conditional information: Conditional epiplexity and entropy extend the framework to settings such as predicting labels from images while conditioning on an input variable.The conditional model receives the conditioning variable as input and measures structure or randomness in the target conditional distribution.
  • Datasets and scaling: For machine-learning datasets, epiplexity typically grows with dataset size because larger datasets allow models to identify and extract more intricate structure and patterns.The dataset is treated as a collection of many samples, so expected entropy scales with dataset size as well.

4 Measuring Epiplexity and Time-Bounded Entropy

The paper estimates epiplexity through neural-network coding procedures that decompose a compute-bounded two-part code into model description length and residual data entropy. Prequential coding is convenient but heuristic, whereas requential coding is more rigorous and typically slower; both often produce comparable dataset rankings.

  • Estimation framework: Epiplexity estimation decomposes a two-part code into program length for structure and expected entropy-coding length for the data realization.Because direct program search is intractable, the practical procedure restricts models to neural networks and encodes the training process rather than merely storing weights.
  • Prequential coding: Prequential coding estimates model information from the area under the loss curve above final loss while training on data matching the test distribution.A sustained loss reduction indicates that training has absorbed information from the data; random data do not produce a decreasing coding loss.
  • Prequential coding: Prequential coding optimizes model size, training data, and other hyperparameters under a compute budget to minimize the two-part code and estimate both quantities.The expected held-out coding loss is approximated empirically using validation loss scaled by test-set size.
  • Prequential coding: Prequential coding is not rigorous because its complexity difference need not upper-bound model complexity, and its explicit code may not satisfy the required runtime bound.It remains useful for crude estimation, especially when a loss curve from an expensive training run is already available.
  • Requential coding: Requential coding constructs an explicit runtime-bounded model code by training students on synthetic data sampled from teacher checkpoints rather than coding a particular training dataset.Its expected code length is related to the cumulative KL divergence between student and teacher distributions.
  • Scaling with compute and data: Under natural scaling assumptions, epiplexity typically increases with compute while time-bounded entropy decreases, and infinite-compute epiplexity typically increases with test-set size.These are typical trends rather than universal laws; the paper notes a counterexample associated with emergence.

5 Three Apparent Paradoxes of Information

The paper reframes three information-theoretic paradoxes by introducing computational bounds and epiplexity, showing that deterministic computation, ordering, and likelihood modeling can yield more learnable structure than classical accounts predict.

  • Three apparent paradoxes concern deterministic transformations, factorization order, and the claim that likelihood modeling only matches the data-generating process.The paper argues that time bounding and epiplexity help resolve tensions between these principles and empirical observations.
  • Paradox 1: Information Cannot be Created by Deterministic Transformations: A deterministic transformation can increase time-bounded information when its inverse lacks a short, efficiently executable program.The paper contrasts this computational asymmetry with unlimited-computation invariance and advises avoiding synthetic-data transformations with simple efficient inverses.
  • Paradox 1: Information Cannot be Created by Deterministic Transformations: Cellular automata illustrate distinct outcomes: rule 15 yields little information, rule 30 mostly unpredictable information, and rule 54 both random and structural information.These outcomes correspond to rapid loss saturation, no progress, and continued progress with compute, respectively.
  • Paradox 2: Information Content is Independent of Factorization: For one-way functions, reversing the factorization creates a time-bounded entropy gap, and reverse-ordered chess data acquires more structural information despite greater prediction difficulty.The chess comparison uses move-sequence–then-board versus board–then-moves orderings.
  • Paradox 3: Likelihood Modeling is Merely Distribution Matching: Likelihood models can require predictive circuits and programs more complex than the data-generating process, especially when computation limits make inversion difficult.This pattern appears in induction settings and in emergence, where models trade increased program length for reduced computation.
  • Emergent Phenomena: Epiplexity-emergent systems have equivalent one-step structural complexity but asymptotically greater multistep structural complexity for observers with fewer computational resources.In ECA rule 54, compute-limited models learn emergent patterns instead of directly simulating every intermediate state.

6 Epiplexity, Pre-Training, and OOD Generalization

Epiplexity is proposed as a measure of reusable structural information in pre-training data, distinguishing it from time-bounded entropy and relating it to OOD transfer. The paper applies it to data ordering, modalities, scaling laws, and selection strategies.

  • Epiplexity and OOD Generalization: Epiplexity measures reusable structure acquired by a model, whereas training loss primarily reflects residual unpredictability or time-bounded entropy.Two corpora can yield similar in-distribution loss yet differ in OOD transfer because their learned structures differ.
  • Epiplexity and OOD Generalization: Reverse board-then-moves ordering produces higher epiplexity and better chess downstream performance, especially on the more shifted centipawn task.The authors attribute this to richer board-state representations that transfer beyond next-move prediction.
  • Natural Data: Language, image, and video data exhibit different estimated structural information, while video has less time-bounded entropy and epiplexity than same-resolution images.The paper attributes the video difference likely to redundancy across the temporal dimension.
  • Scaling Laws: For a fixed dataset, optimal training and inference compute splits approach predictable limits as compute increases, with asymptotic training tokens approaching dataset size D.Asymptotic epiplexity is capped by D when compute is not the bottleneck and can grow with dataset size.
  • Data Selection: ADO selects data with higher measured epiplexity than standard sampling, alongside improved downstream performance and OOD perplexity.The evaluation uses 1.3B-parameter decoder-only transformers trained on 125B Pile tokens and tested on seven zero-shot tasks plus two OOD datasets.
  • Data Selection: Higher-loss data subsets can contain more learnable information, so selecting faster-decreasing-loss subsets may increase epiplexity while increasing the area under the training-loss curve.Thus, lower observed training loss is not equivalent to selecting data with more structural information.

7 Additional Related Work

The paper situates epiplexity among complexity and observer-dependent information measures, emphasizing that computational limits alter what counts as simple, random, or learnable. It distinguishes epiplexity from related measures by explicitly accounting for the cost of extracting structure.

  • Complexity Measures: Sophistication, effective complexity, and logical depth separate or characterize meaningful structure, but existing notions do not explicitly account for an observer’s limited computation.The paper argues that this omission prevents them from characterizing encrypted objects and CSPRNG outputs as random in the relevant sense.
  • Complexity Measures: Replacing Kolmogorov complexity with time-bounded Kolmogorov complexity does not solve the problem because CSPRNG outputs have short, efficiently runnable generating programs and sophistication becomes trivial for all strings.The latter issue is discussed in more detail in Appendix A.6.
  • Observer-Dependent Information: Pseudoentropy and V-entropy capture the random component of information, whereas epiplexity targets the non-random component useful for understanding what models learn.The distinction is between unpredictability under a feasible model and structural information extracted by the learner.
  • Related Data Measures: Excess entropy resembles the area-under-the-curve construction used for prequential epiplexity but assumes stationary processes and computationally unbounded observers.SDL and information transfer instead emphasize downstream learning efficiency or learned information in more specific settings.
  • Data Complexity: PAC-Bayes data complexity concerns the existence of a small near-optimal in-distribution reference model, while epiplexity includes the cost of obtaining a model under bounded computation.The paper’s primary scope extends beyond supervised in-distribution generalization to intrinsic data value.
  • Resource Constraints: Resource constraints can fundamentally change simplicity and learnability, a theme shared with speed priors and computationally constrained learning theory.The paper places epiplexity within this broader effort to incorporate computation into information and complexity.

8 Discussion

The discussion reframes information around computationally bounded observers, distinguishing structural information from time-bounded entropy. It connects epiplexity to data evaluation, representation learning, and future theory while identifying unresolved scope and research directions.

  • Learning depends on available computational resources as well as statistical feasibility, motivating theories that treat computation and information as fundamental resources.
  • Epiplexity decomposes information into time-bounded entropy and structural information, helping explain why computation can change perceived information.
  • Epiplexity can compare data sources, formatting, and transformations that produce more transferable models even without improving training loss.
  • Representation learning can be viewed as accumulating increasingly rich internal programs that approximate a data distribution within a fixed time budget.
  • The framework is not a complete theory of generalization or learning, and future work must study dependence on computational budget, model class, and data transformations.
  • Appendices provide proofs, estimation methodology, experimental specifications, transformer constructions, background examples, and discussions of MDL, resources, and licensing.

Appendix A. Proofs

The appendix establishes theoretical properties of time-bounded entropy and epiplexity, including near-maximal entropy and low epiplexity for pseudorandom-generator outputs. These results formalize how computational limitations separate unpredictable content from structural content.

  • The appendix begins by proving basic lemmas about epiplexity and time-bounded entropy.
  • For sufficiently large linear time bounds, the uniform distribution on {0, 1}^n has a bounded-description model and characterized time-bounded entropy.
  • For a non-uniform pseudorandom generator G mapping k bits to n bits, polynomial-time entropy remains close to n up to the generator’s distinguishing advantage.
  • The resulting generator output has epiplexity bounded by a constant plus nε(k), despite its expanded output length.
  • The proofs derive these bounds by combining entropy lower bounds for generator outputs with general upper bounds on total description length.

A.4 Existence of High Epiplexity random variables

This section proves the existence of distributions with high epiplexity using pseudorandom-function constructions. The argument shows that short models cannot describe at least one distribution as efficiently as a keyed model can.

  • The construction relies on standard cryptographic assumptions connecting one-way functions to secure pseudorandom functions.
  • The heavy-set argument identifies outputs receiving unusually high probability under a candidate model and bounds their mass under the uniform distribution.
  • A keyed pseudorandom-function construction supplies distributions whose generating process is deterministic while remaining difficult for polynomial-time models to describe.
  • A candidate model can be converted into a single-query distinguisher, linking efficient description to the ability to distinguish a pseudorandom function from a random function.
  • A union bound over short programs yields a key for which every sufficiently short model has description length at least m+t.
  • The keyed model remains short, so the MDL minimizer must use a program longer than the chosen threshold s.

A.5 Information Content is not Independent of Factorization

The section proves that information content can depend on how data are factorized when models are computationally bounded. One-way permutations create an asymmetry between easy forward prediction and difficult inversion.

  • For a one-way permutation applied to a uniform input, polynomial-time conditional entropy of the input given the output grows at least logarithmically with n.
  • Consequently, the factorization Hpoly(X | Y) + Hpoly(Y) exceeds Hpoly(Y | X) + Hpoly(X) by c log n.
  • The output is easy to generate from the input, giving Hpoly(Y | X) = O(1), while the unconditional complexities of X and Y differ by only O(1).
  • The proof obtains the reverse-direction lower bound by treating conditional sampling as a polynomial-time inverter and invoking one-wayness.
  • A model family supporting both factorizations must therefore violate Bayes consistency by a margin that grows with n.

A.6 Problems with time-bounded sophistication

A naive time-bounded version of sophistication collapses because a constant-size timeout-equipped interpreter can serve as the model for every string. Consequently, it cannot distinguish structured strings from random-looking ones.

  • The model program must be total, meaning it halts on every auxiliary input.Totality prevents an unbounded universal interpreter from serving as the model while shifting all information into the data part.
  • Naive time-bounded sophistication replaces K(x) with Kt(x) in the two-part description criterion.
  • Time bounds allow a constant-size clocked interpreter to totalize a universal interpreter by enforcing a timeout.It outputs the simulated result if computation halts within the budget and otherwise returns a fixed default string.
  • Naive time-bounded sophistication is O(1) for every string, so it does not meaningfully distinguish structured from random-looking strings.The interpreter paired with a shortest time-bounded program witnessing Kt(x) pushes essentially all description length into the data part.

B.1 Further details on estimating epiplexity

The paper estimates epiplexity with two-part codes built from neural training trajectories and test-set entropy coding. Practical corrections smooth finite-sweep artifacts, while prequential coding is related to requential coding with a static teacher.

  • Epiplexity estimation encodes a model description together with the test data under the trained model.The model code is estimated through training losses or teacher-student KL, while the test data are entropy encoded.
  • Estimating the Pareto Frontier: A lower convex hull smooths noisy Pareto frontiers, and retaining the median checkpoint per fixed-model-size training run removes spurious multiple-frontier points.Finite hyperparameter sweeps otherwise produce jagged frontiers and oscillatory epiplexity estimates.
  • Sources of errors: The estimate can have systematic errors from frontier corrections, fixed architectures and algorithms, and suboptimal hyperparameters.The authors expect these sources to contribute mainly sub-leading corrections in many cases.
  • Prequential and requential coding: Prequential coding is an approximation to requential coding with a static teacher, and its estimate is expected to overestimate requential code length.Time-varying teachers can remain close to the student while guiding it toward the target distribution.

B.3 A Solvable Model Using Scaling Laws

A solvable scaling-law model analyzes how compute allocation affects epiplexity and time-bounded entropy. Epiplexity grows with compute, eventually saturating at large compute, while entropy approaches its irreducible level.

  • The model combines neural scaling laws with prequential coding to analyze compute-optimal model and dataset sizes.It uses normalized model size, training data, test-set size, and compute under a simplified compute constraint.
  • Large-compute regime: At large compute, the optimal training set size approaches the test set size, model size grows linearly with compute, and epiplexity saturates.The limiting epiplexity is S∞(X) = β/(1−β) D0^β D^(1−β).
  • Large-compute regime: Entropy approaches irreducible entropy DE plus a finite-data residual whose per-token contribution scales as O(D^−β).
  • Small-compute regime: At small compute, the optimal training set size grows sublinearly as d⋆∝t^α/(β+1), and epiplexity also grows sublinearly with compute.
  • Small-compute regime: For typical exponents α ≈0.34 and β ≈0.28, epiplexity scales as ST ∝T^0.19 while entropy above irreducibility scales as HT−DE ∝T^−0.07.

B.4 How Epiplexity and Time-Bounded Entropy Scale with Compute and Dataset Size

Under natural assumptions, compute-optimal model and training-data sizes increase with compute, while epiplexity typically increases and time-bounded entropy decreases. Dataset size also raises limiting epiplexity and lowers limiting per-token entropy.

  • Increasing compute raises the compute-optimal model size N⋆(T) and training-data size D⋆(T), while epiplexity typically grows and time-bounded entropy decreases.
  • At infinite compute, S∞(X) is nondecreasing in dataset size D, while limiting per-token time-bounded entropy is nonincreasing in D.
  • For prequential coding, the compute-optimal training size approaches the test-set size from below as compute tends to infinity.

B.4.1 Monotonicity of N ∗(T), D∗(T), ST (X), and HT (X)

Under stated complementarity and diminishing-returns assumptions, compute-optimal model size and effective data increase with compute. The infinite-compute structural and entropy terms are monotonic in test-set size, while training-set size approaches a finite limit and model size grows linearly at large compute.

  • Compute-optimal allocation: The result relies on complementarity plus diminishing returns in model size and effective data.These are expressed through the stated derivative conditions at the optimum.
  • Compute-optimal allocation: Both compute-optimal choices increase strictly with compute T.The theorem assumes a unique interior optimizer, positive effective-data slack, and T = N eD.
  • Large-compute behavior: The time-bounded entropy H_T(X) is nonincreasing in T and approaches any finite large-compute limit from above.This requires only that loss is nonincreasing in model size and data size.
  • Infinite-compute limits: At infinite compute, structural information S∞(X_D) is nondecreasing and achieved loss h∞(X_D) is nonincreasing in test-set size D.The monotonicity holds regardless of the coding scheme, assuming the unconstrained optimum exists.
  • Large-compute behavior: The compute-optimal training-set size approaches a finite limit from below as T increases.This follows from strict increase together with convergence under the large-model-size assumptions.
  • Large-compute behavior: The compute-optimal model size grows linearly with T in the large-compute regime.The conclusion follows after the training-set size converges and the compute frontier determines N⋆(T).

Appendix C. Experiment Details

The experiments use GPT-2-style transformers and vary architectures, data formats, tasks, and coding procedures across cellular automata, induction, natural data, chess, and image-like sequences. Epiplexity and entropy are estimated using the paper’s derived expressions, with targeted interventions such as looped prediction and alternative data orderings.

  • General setup: The default experiments use GPT-2 transformers trained with Adam, with µP and CompleteP for model-size comparisons.Teacher and student models share key hyperparameters in prequential-coding experiments.
  • Natural-data evaluation: Natural-data experiments use character-level OpenWebText and Lichess chess data, including both board-before-moves and moves-before-board formats.The chess representation combines algebraic move sequences with final-board FEN notation.
  • Natural-data evaluation: The chess evaluation fine-tunes a 10M-parameter, depth-24 model on 50k examples and reports greedy-decoding accuracy.Downstream datasets include difficult Lichess puzzles and nine Stockfish-based position-evaluation buckets.
  • Cellular automata: The ECA experiments cover ten rules across all four rule classes, with widths 16–128, depths 1–3, and up to 10000 steps.The reported maximum epiplexity is taken over the resulting compute range.
  • ECA emergence: For looped ECA prediction, only ℓ = 16 improves the two-part code; ℓ ∈ {2, 4, 8} provides no advantage over ℓ = 1.The experiment uses t = 64 and evaluates models across widths, depths, and loop counts.
  • Estimation: Estimated epiplexity and time-bounded entropy are computed with the expressions derived in Section B.3.For induction tasks, the quantities stabilize as compute and test-set size increase.

Appendix F. Emergence

The emergence examples show how computational constraints turn simple or deterministic generators into sources of substantial learnable structure. Chaotic dynamics produce unpredictable trajectories but retain learnable invariant structure, while likelihood modeling can require sophisticated algorithms beyond direct distribution matching.

  • Chaotic dynamics: Chaotic Lorenz trajectories become unpredictable under limited precision, yet their invariant SRB measure remains structured.The system’s largest Lyapunov exponent is approximately 0.9, and entropy is produced despite deterministic dynamics.
  • Chaotic dynamics: An LLM trained 30 Lyapunov times into the future learned the Lorenz invariant measure despite being unable to distinguish initial conditions.The two prediction setups had nearly identical loss and estimated epiplexity.
  • Emergence: Simple generating processes can yield large structural information for computationally constrained observers through emergent phenomena.The paper frames this as a general consequence illustrated by its emergence examples.
  • Likelihood modeling: Likelihood computation can be harder than sampling, forcing bounded models to learn cheaper but more sophisticated algorithms for evaluating P_X(x).The paper identifies explicit or implicit approximation of the inverse latent posterior P_Z|X as one such strategy.
  • Coding methods: Prequential coding provides a tractable sequential alternative because normalized maximum likelihood is generally intractable for deep neural networks.The prequential update can use sequential learning procedures such as stochastic gradient descent.
Loading 2601.03220v2…