Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang
Published 2018-07-03Version 1
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in the special case of soft-margin support vector machines. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradient descent.
On the Computational Power of Transformers and Its Implications in Sequence Modeling
Fast Rates for Online Gradient Descent Without Strong Convexity via Hoffman's Bound
The Computational Power of Optimization in Online Learning
![QR code for arXiv:1807.01280 [cs.LG]](http://oss.arxitics.com/images/favicon.svg)