# Provable Regret Bounds for Deep Online Learning and Control

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 54 references that are in the map.
- First posted on arXiv 15 Oct 2021.

## Builds on (most cited first, 30 of 32)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [Towards Generalization and Simplicity in Continuous Control](https://mlsanity.com/paper/1703.02660/) (2017)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems](https://mlsanity.com/paper/1905.11675/) (2019)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality](https://mlsanity.com/paper/2002.06668/) (2020)
- [Exponentiated Gradient Meets Gradient Descent](https://mlsanity.com/paper/1902.01903/) (2019)
- [Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network](https://mlsanity.com/paper/1902.07111/) (2019)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)

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

- [A Review of Machine Learning Methods Applied to Structural Dynamics and Vibroacoustic](https://mlsanity.com/paper/2204.06362/) (2022)
- [Neural Exploitation and Exploration of Contextual Bandits](https://mlsanity.com/paper/2305.03784/) (2023)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [A Regret Minimization Approach to Multi-Agent Control](https://mlsanity.com/paper/2201.13288/) (2022)
- [Online Nonstochastic Model-Free Reinforcement Learning](https://mlsanity.com/paper/2305.17552/) (2023)
- [Incremental Online Learning of Randomized Neural Network with Forward Regularization](https://mlsanity.com/paper/2412.13096/) (2024)

## Abstract (arXiv)

The theory of deep learning focuses almost exclusively on supervised learning, non-convex optimization using stochastic gradient descent, and overparametrized neural networks. It is common belief that the optimizer dynamics, network architecture, initialization procedure, and other factors tie together and are all components of its success. This presents theoretical challenges for analyzing state-based and/or online deep learning. Motivated by applications in control, we give a general black-box reduction from deep learning to online convex optimization. This allows us to decouple optimization, regret, expressiveness, and derive agnostic online learning guarantees for fully-connected deep neural networks with ReLU activations. We quantify convergence and regret guarantees for any range of parameters and allow any optimization procedure, such as adaptive gradient methods and second order methods. As an application, we derive provable algorithms for deep control in the online episodic setting.