BRIDGING ALGORITHMIC INFORMATION THEORY AND MACHINE LEARNING - A NEW APPROACH TO KERNEL LEARNING

Aug 3, 2026

Upload by Noah

Machine Learning and Algorithmic Information Theory offer complementary ways to measure complexity. By adopting an AIT perspective on learning kernels from data within kernel ridge regression, this work studies Sparse Kernel Flows and connects them to Minimal Description Length and machine-learning regularization. The analysis proves Sparse Kernel Flows as a natural choice, providing a theoretical foundation that avoids cross-validation arguments. The derivation relies directly on code-lengths and complexities central to AIT, enabling kernel-learning algorithms to be reformulated with more solid theory.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages14

Reading Time35 min

AccessFree to download

Introduction

Kernel Flows and Gaussian Processes

arXiv :2311 . 12624v3 [ cs .LG] 10 Apr 2024 BRIDGING ALGORITHMIC INFORMATION THEORY AND MACHINE LEARNING: A NEW APPROACH TO KERNEL LEARNING BOUMEDIENE HAMZI 1 ,2 , MARCUS HUTTER4 ,5 , AND HOUMAN OWHADI1 Abstract. Machine Learning (ML) and Algorithmic Information Theory (AIT) look at Complexity from di􀀛erent points of view. We explore the interface between AIT and Kernel Methods (that are prevalent in ML) by adopting an AIT perspective on the problem of learning kernels from data, in kernel ridge regression, through the method of Sparse Kernel Flows. In particular, by looking at the di􀀛erences and commonalities between Minimal Description Length (MDL) and Regularization in Machine Learning (RML), we prove that the method of Sparse Kernel Flows is the natural approach to adopt to learn kernels from data. This approach aligns naturally with the MDL principle, o􀀛ering a more robust theoretical basis than the existing reliance on cross-validation. The study reveals that deriving Sparse Kernel Flows does not require a statistical approach; instead, one can directly engage with code-lengths and complexities, concepts central to AIT. Thereby, this approach opens the door to reformulating algorithms in machine learning using tools from AIT, with the aim of providing them amore solid theoretical foundation. 1. Introduction Algorithmic Information Theory (AIT) and Machine Learning are key approaches for analyzing complex systems. AIT aims to formalize simplicity and complexity using measures like Kolmogorov Complexity and Algorithmic Solomono􀀛 Probability [RH11, Hut07a, GV08] . Conversely, Machine Learning (ML) focuses on algorithms designed to improve performance with more data, enabling the analysis of high-dimensional complex systems, even when the model is unknown. Reproducing Kernels, are often used as measures of similarity in ML, and Kernel-based methods hold potential for considerable advantages in terms of theoretical analysis, numerical implementation, regularization, guaranteed convergence, automatization, and interpretability. Indeed, reproducing kernel Hilbert spaces (RKHS) [CS02] have provided strong mathematical foundations for analyzing dynamical systems [BH10, HKA+ 90, HHSW18, D.W21, GHRW19, BKH+ 21, HC19, KNH20, Key words and phrases. Machine Learning, Algorithmic Information Theory, Regression, Sparse Kernel Flows, Minimum Description Length Principle, Compression, Similarity. 2 BOUMEDIENE HAMZI 1 ,2 , MARCUS HUTTER4 ,5 , AND HOUMAN OWHADI 1 KNP+ 20, AG20, KS19, BH12, BH17a, BH17b, HKM19, ABOS22, HOP23] and surrogate modeling (cf. [SH19] for a survey) . Recently, experiments by Hamzi and Owhadi and collaborators [HO21, Owh21, Tur21, LDHO23, DTL+ 21, DHS+ 21, HOK22, YSH+ 24, YHK+ 23] have shown that Kernel Flows (KFs)[OY19] (an RKHS technique) can successfully reconstruct the dynamics of prototypical chaotic dynamical systems under both regular and irregular sampling in time and that it can be successful in predicting complex, large-scale systems, including climate data. In this paper, we look at the problem of learning kernels from data from an AIT point of view and show that the problem of learning kernels from data can be viewed as a problem of compression of data. In particular, using the Minimal Description Length (MDL) principle, we show that Sparse Kernel Flows [YSH+ 24] is a natural approach for learning kernels from data from an AIT point of view and that it is not necessary to use a cross-validation argument to justify its e􀀞ciency, thus giving it a more solid theoretical foundation. Our work can also be viewed as a step to bridge the gap between AIT and Kernel Methods; and is to be contrasted vis-à-vis [Bac22], where the author considered (Classical) Information with Kernel Methods, and our work could also be viewed as a perspective on Kernel Methods from an AIT point of view instead of the classical Information Theory point of view adopted in [Bac22], cf. [GV08] for common points an

FAQs

How does the paper connect Algorithmic Information Theory with kernel learning?

It treats learning kernels as a compression problem from an AIT viewpoint and uses code-length and complexity concepts to justify the approach.

What role does Minimal Description Length (MDL) play in Kernel Learning here?

MDL is used to link Sparse Kernel Flows with machine-learning regularization, yielding a more robust theoretical basis than reliance on cross-validation.

Why are Sparse Kernel Flows presented as a natural approach for learning kernels from data?

The paper proves that, under the AIT/MDL perspective, Sparse Kernel Flows align naturally with the principles governing compression and complexity, making cross-validation unnecessary for justification.

Aug 3, 2026

Upload by Noah