On the Computational Power of Online Gradient Descent
Not on the map. Why?
Abstract (arXiv)
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradient descent.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 3 Jul 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1.
1 paper.