On the Computational Power of Online Gradient Descent

  • 2018-07-03 16:56:14
  • Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang
  • 22


We prove that the evolution of weight vectors in online gradient descent canencode arbitrary polynomial-space computations, even in the special case ofsoft-margin support vector machines. Our results imply that, under weakcomplexity-theoretic assumptions, it is impossible to reason efficiently aboutthe fine-grained behavior of online gradient descent.


Introduction (beta)



Conclusion (beta)