Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation

Anastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim, Gregory Cousins, Haitz Sáez de Ocáriz Borde

arXivarxiv/2606.26705Jun 25, 2026cs.LGscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.26705
curl -X POST /api/v1/records/arxiv/2606.26705/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.26705/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'