# On the Computational Power of Online Gradient Descent

arXiv: https://arxiv.org/abs/1807.01280 · HTML: https://mlsanity.com/paper/1807.01280/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics](https://mlsanity.com/paper/2109.03974/) (2021)

## 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.