How Does Machine Learning Manage Complexity?

arXiv:2604.07233v1 Announce Type: new Abstract: We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems. Machine learning models are often trained on data drawn from sampleable or more complex distributions, a far wider range of distributions than just computable ones. By focusing on computable distributions, machine learning models can better manage complexity via probability. We abstract away from specific learning mechanisms, modeling machine learning as producing P/poly-computable distributions with polynomially-bounded max-entropy. We illustrate how learning computable distributions models complexity by showing that if a machine learning model produces a distribution mu that minimizes error against the distribution generated by a cryptographic pseudorandom generator, then mu must be close to uniform.

Weaves, Wires, and Morphisms: Formalizing and Implementing the Algebra of Deep Learning
Non-identifiability of Explanations from Model Behavior in Deep Networks of Image Authenticity Judgments
Stochastic Gradient Descent in the Saddle-to-Saddle Regime of Deep Linear Networks
The Illusion of Superposition? A Principled Analysis of Latent Thinking in Language Models
Theory and interpretability of Quantum Extreme Learning Machines: a Pauli-transfer matrix approach

Source: arXiv cs.LG | 2026-04-10

Related