A Tutorial on Algorithmic Information Theory in Modern ML

Add to your list(s) Download to your calendar using vCal

• Szilvia Ujvary, Arik Reuter, Xianda Sun (University of Cambridge)
• Wednesday 05 November 2025, 11:00-12:30
• Cambridge University Engineering Department, CBL Seminar room BE4-38..

If you have a question about this talk, please contact Xianda Sun.

This tutorial explores how ideas from algorithmic information theory connect to modern machine learning through three recent papers. We begin with Solomonoff induction—the theoretically optimal but uncomputable predictor—and show how neural networks can approximate it by training on Universal Turing Machine data (Grau-Moya et al., 2024). We then establish the formal foundations by examining Kolmogorov complexity and its connections to compression and randomness in images, exploring how the Solomonoff prior helps us understand what makes images “realistic” and guides the design of better generative models and anomaly detectors (Theis, 2024). Finally, we demonstrate these principles at scale, deriving non-vacuous generalization bounds for large language models with billions of parameters through compression-based analysis using the SubLoRA technique (Lotfi et al., 2024). No prior background in algorithmic information theory required—we’ll build intuition from first principles while connecting to familiar ML concepts throughout.

Papers:

1. Learning Universal Predictors (Grau-Moya et al., 2024) – https://arxiv.org/abs/2401.14953
2. What Makes an Image Realistic? (Theis, 2024) – https://arxiv.org/abs/2403.04493
3. Non-Vacuous Generalization Bounds for Large Language Models (Lotfi et al., 2024) – https://arxiv.org/abs/2312.17173

This talk is part of the Machine Learning Reading Group @ CUED series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge University Engineering Department Talks
• Cambridge University Engineering Department, CBL Seminar room BE4-38.
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• ML
• Machine Learning Reading Group
• Machine Learning Reading Group @ CUED
• Machine Learning Summary
• Quantum Matter Journal Club
• Required lists for MLG
• School of Technology
• Simon Baker's List
• TQS Journal Clubs
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list
• yk449

Note that ex-directory lists are not shown.