{"id":"arxiv/2606.26705","url":"https://arxiv.org/abs/2606.26705","tags":["cs.LG","cs.AI","cs.LO","math.NA"],"score":0,"title":"Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation","domain":"cs.LG","source":"arxiv","authors":["Anastasis Kratsios","Simone Brugiapaglia","Bum Jun Kim","Gregory Cousins","Haitz Sáez de Ocáriz Borde"],"reviews":0,"subject":"cs.LG","summary":"Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comparable regularity, such as the square-root function and a typical Brownian path. The guiding message is that neural networks should be viewed not only as flexible basis functions, but also as models of computation. If a function is computable by a real-valued circuit over a prescribed elementary…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-25","reactions":{}}