Provable Regret Bounds for Deep Online Learning and Control
This work addresses the problem of providing theoretical guarantees for deep online learning and control, which is incremental as it extends existing optimization theory to deep networks in online settings.
The paper tackles the theoretical challenge of analyzing deep learning in online and state-based settings by providing a black-box reduction from deep learning to online convex optimization, enabling provable regret bounds for deep neural networks with ReLU activations and applying this to derive algorithms for deep control.
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.