How Does Machine Learning Manage Complexity?
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908947852558336 |
|---|---|
| author | Fortnow, Lance |
| author_facet | Fortnow, Lance |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07233 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How Does Machine Learning Manage Complexity? Fortnow, Lance Machine Learning Computational Complexity 68Q15, 68T05 (Primary) 94A17, 94A60, 68Q30 (Secondary) F.1.1; I.2.6 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. |
| title | How Does Machine Learning Manage Complexity? |
| topic | Machine Learning Computational Complexity 68Q15, 68T05 (Primary) 94A17, 94A60, 68Q30 (Secondary) F.1.1; I.2.6 |
| url | https://arxiv.org/abs/2604.07233 |