Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes machine learning through the lens of computational complexity, specifically focusing on how ML models manage complexity when trained on data from various distributions. It models machine learning as producing P/poly-computable distributions with polynomially-bounded max-entropy, abstracting away from specific learning mechanisms. The key result demonstrates that if a machine learning model accurately approximates a distribution generated by a cryptographic pseudorandom generator, its output distribution must be close to uniform, indicating a limitation in capturing the underlying complexity.
ML models that accurately mimic cryptographically secure pseudorandom generators are doomed to output near-uniform distributions, revealing a fundamental limit in their ability to capture certain types of complexity.
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.