Provable Regret Bounds for Deep Online Learning and Control
arXiv:2110.07807
Abstract
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.
References in corpus (17)
- Continuous control with deep reinforcement learning
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
- Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
- Improper Learning for Non-Stochastic Control
- Convergence of Adversarial Training in Overparametrized Neural Networks
- Online Control with Adversarial Disturbances
- Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
- Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
- Towards Generalization and Simplicity in Continuous Control
- Information Theoretic Regret Bounds for Online Nonlinear Control
- Adaptive Regret for Control of Time-Varying Dynamics
- Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks