How Does Machine Learning Manage Complexity?

• URL: http://arxiv.org/abs/2604.07233v1
• Date: Wed, 08 Apr 2026 15:57:24 GMT
• Title: How Does Machine Learning Manage Complexity?
• Abstract summary: We provide a computational complexity lens to understand the power of machine learning models.<n>We show that if a machine learning model produces a distribution $$ that minimizes error against the distribution generated by a cryptographic pseudorandom generator, then $$ must be close to uniform.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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 $μ$ that minimizes error against the distribution generated by a cryptographic pseudorandom generator, then $μ$ must be close to uniform.

Related papers

• Multi-Objective Learning for Diffusion Models: A Statistical Theory under Semi-Supervised Learning [83.65494573724904]
  We develop a principled MOL framework for diffusion models with limited data.<n>We propose a two-stage training procedure that first fits lightweight specialist models from limited paired data.<n>We establish bounds generalization showing that the required number of paired samples only depends on the complexity of the specialist model classes.
  arXiv  Detail & Related papers  (2026-05-24T18:19:40Z)
• A theory of learning data statistics in diffusion models, from easy to hard [11.841482748098327]
  We show that diffusion models trained on natural images exhibit a distributional simplicity bias, learning simple, pair-wise input statistics before specializing to higher-order correlations.<n>We reproduce this behaviour in simple denoisers trained on a minimal data model, the mixed cumulant model.<n>Our work describes a key mechanism for how diffusion models can learn distributions of increasing complexity.
  arXiv  Detail & Related papers  (2026-03-13T11:07:01Z)
• On Stronger Computational Separations Between Multimodal and Unimodal Machine Learning [0.0]
  Lu (NeurIPS '23, ALT '24) introduces a theory of multimodal learning. In particular, Lu (ALT '24) shows a computational separation, which is relevant to textitworst-case instances of the learning task. We prove that under basic conditions, any given computational separation between average-case unimodal and multimodal learning tasks implies a corresponding cryptographic key agreement protocol.
  arXiv  Detail & Related papers  (2024-04-02T19:21:28Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  We argue that neural network models share this same preference, formalized using Kolmogorov complexity. Our experiments show that pre-trained and even randomly language models prefer to generate low-complexity sequences. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.
  arXiv  Detail & Related papers  (2023-04-11T17:22:22Z)
• An Entropy-Based Model for Hierarchical Learning [3.1473798197405944]
  A common feature among real-world datasets is that data domains are multiscale. We propose a learning model that exploits this multiscale data structure. The hierarchical learning model is inspired by the logical and progressive easy-to-hard learning mechanism of human beings.
  arXiv  Detail & Related papers  (2022-12-30T13:14:46Z)
• How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions [5.553167334488855]
  We show that even though Empirical Risk Minimization (ERM) needs an exponential number of samples to learn on product distributions, an algorithm designed specifically for product distributions is needed. This leads to the conclusion that a product distribution by itself does not make a learning problem easier -- an algorithm designed specifically for product distributions is needed.
  arXiv  Detail & Related papers  (2022-12-13T08:14:32Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Unsupervised multi-modal Styled Content Generation [61.040392094140245]
  UMMGAN is a novel architecture designed to better model multi-modal distributions in an unsupervised fashion. We show that UMMGAN effectively disentangles between modes and style, thereby providing an independent degree of control over the generated content.
  arXiv  Detail & Related papers  (2020-01-10T19:36:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.