mlsanityData to 7 Oct 2026

Provable Regret Bounds for Deep Online Learning and Control

arXiv 2110.07807 ↗First posted 15 Oct 2021cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

32 of 54 references.

References · 32

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  9. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  10. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  11. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  12. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
20 more
  1. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  2. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  3. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  4. 2020Naive Exploration is Optimal for Online LQRcited by 111
  5. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  6. 2019Online Control with Adversarial Disturbancescited by 92
  7. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  8. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  9. 2020Improper Learning for Non-Stochastic Controlcited by 83
  10. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  11. 2017Towards Generalization and Simplicity in Continuous Controlcited by 65
  12. 2019Convergence of Adversarial Training in Overparametrized Neural Networkscited by 58
  13. 2019Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problemscited by 40
  14. 2020Adaptive Regret for Control of Time-Varying Dynamicscited by 38
  15. 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
  16. 2019Exponentiated Gradient Meets Gradient Descentcited by 32
  17. 2019Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Networkcited by 27
  18. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  19. 2021On the Stability of Nonlinear Receding Horizon Control: A Geometric Perspectivecited by 4
  20. 2021AdaLoss: A computationally-efficient and provably convergent adaptive gradient methodcited by 3

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 3; 2024: 1.

6 papers.

  1. 2022A Review of Machine Learning Methods Applied to Structural Dynamics and Vibroacousticcited by 7
  2. 2023Neural Exploitation and Exploration of Contextual Banditscited by 7
  3. 2023Online Nonstochastic Control with Adversarial and Static Constraintscited by 5
  4. 2022A Regret Minimization Approach to Multi-Agent Controlcited by 4
  5. 2023Online Nonstochastic Model-Free Reinforcement Learningcited by 2
  6. 2024Incremental Online Learning of Randomized Neural Network with Forward Regularizationcited by 2