Provable Regret Bounds for Deep Online Learning and Control
- URL: http://arxiv.org/abs/2110.07807v1
- Date: Fri, 15 Oct 2021 02:13:48 GMT
- Title: Provable Regret Bounds for Deep Online Learning and Control
- Authors: Xinyi Chen, Edgar Minasyan, Jason D. Lee, Elad Hazan
- Abstract summary: We show that any loss functions can be adapted to optimize the parameters of a neural network such that it competes with the best net in hindsight.
As an application of these results in the online setting, we obtain provable bounds for online control controllers.
- Score: 77.77295247296041
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The use of deep neural networks has been highly successful in reinforcement
learning and control, although few theoretical guarantees for deep learning
exist for these problems. There are two main challenges for deriving
performance guarantees: a) control has state information and thus is inherently
online and b) deep networks are non-convex predictors for which online learning
cannot provide provable guarantees in general.
Building on the linearization technique for overparameterized neural
networks, we derive provable regret bounds for efficient online learning with
deep neural networks. Specifically, we show that over any sequence of convex
loss functions, any low-regret algorithm can be adapted to optimize the
parameters of a neural network such that it competes with the best net in
hindsight. As an application of these results in the online setting, we obtain
provable bounds for online episodic control with deep neural network
controllers.
Related papers
- Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization [53.15874572081944]
We study computability in the deep learning framework from two perspectives.
We show algorithmic limitations in training deep neural networks even in cases where the underlying problem is well-behaved.
Finally, we show that in quantized versions of classification and deep network training, computability restrictions do not arise or can be overcome to a certain degree.
arXiv Detail & Related papers (2024-08-12T15:02:26Z) - Neural Network Pruning as Spectrum Preserving Process [7.386663473785839]
We identify the close connection between matrix spectrum learning and neural network training for dense and convolutional layers.
We propose a matrix sparsification algorithm tailored for neural network pruning that yields better pruning result.
arXiv Detail & Related papers (2023-07-18T05:39:32Z) - Rational Neural Network Controllers [0.0]
Recent work has demonstrated the effectiveness of neural networks in control systems (known as neural feedback loops)
One of the big challenges of this approach is that neural networks have been shown to be sensitive to adversarial attacks.
This paper considers rational neural networks and presents novel rational activation functions, which can be used effectively in robustness problems for neural feedback loops.
arXiv Detail & Related papers (2023-07-12T16:35:41Z) - Benign Overfitting for Two-layer ReLU Convolutional Neural Networks [60.19739010031304]
We establish algorithm-dependent risk bounds for learning two-layer ReLU convolutional neural networks with label-flipping noise.
We show that, under mild conditions, the neural network trained by gradient descent can achieve near-zero training loss and Bayes optimal test risk.
arXiv Detail & Related papers (2023-03-07T18:59:38Z) - Globally Optimal Training of Neural Networks with Threshold Activation
Functions [63.03759813952481]
We study weight decay regularized training problems of deep neural networks with threshold activations.
We derive a simplified convex optimization formulation when the dataset can be shattered at a certain layer of the network.
arXiv Detail & Related papers (2023-03-06T18:59:13Z) - Imbedding Deep Neural Networks [0.0]
Continuous depth neural networks, such as Neural ODEs, have refashioned the understanding of residual neural networks in terms of non-linear vector-valued optimal control problems.
We propose a new approach which explicates the network's depth' as a fundamental variable, thus reducing the problem to a system of forward-facing initial value problems.
arXiv Detail & Related papers (2022-01-31T22:00:41Z) - Building Compact and Robust Deep Neural Networks with Toeplitz Matrices [93.05076144491146]
This thesis focuses on the problem of training neural networks which are compact, easy to train, reliable and robust to adversarial examples.
We leverage the properties of structured matrices from the Toeplitz family to build compact and secure neural networks.
arXiv Detail & Related papers (2021-09-02T13:58:12Z) - Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
We study neural-linear bandits for solving problems where both exploration and representation learning play an important role.
We propose a likelihood matching algorithm that is resilient to catastrophic forgetting and is completely online.
arXiv Detail & Related papers (2021-02-07T14:19:07Z) - Theoretical Analysis of the Advantage of Deepening Neural Networks [0.0]
It is important to know the expressivity of functions computable by deep neural networks.
By the two criteria, we show that to increase layers is more effective than to increase units at each layer on improving the expressivity of deep neural networks.
arXiv Detail & Related papers (2020-09-24T04:10:50Z) - A Deep Conditioning Treatment of Neural Networks [37.192369308257504]
We show that depth improves trainability of neural networks by improving the conditioning of certain kernel matrices of the input data.
We provide versions of the result that hold for training just the top layer of the neural network, as well as for training all layers via the neural tangent kernel.
arXiv Detail & Related papers (2020-02-04T20:21:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.