On the Computational Power of Online Gradient Descent
classification
💻 cs.LG
stat.ML
keywords
descentgradientonlinearbitraryassumptionsbehaviorcomplexity-theoreticcomputational
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.