Optimal Online Learning using Potential Functions
We study a family of potential functions for online learning. We show that if the potential function has strictly positive derivatives of order 1-4 then the min-max optimal strategy for the adversary is Brownian motion. Using that fact we analyze different potential functions and show that the Normal-Hedge potential provides the tightest upper bounds on the cumulative regret of the top {\epsilon}-percentile.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
PDE-Based Optimal Strategy for Unconstrained Online Learning
Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of…
Learning Neural Controllers with Optimality and Stability Guarantees Using Input-Output Dissipativity
Deep learning methods have demonstrated significant potential for addressing complex nonlinear control problems. For real-world safety-critical tasks, however, it is crucial to provide formal stability guarantees for the…
Learning optimal nonlinearities for iterative thresholding algorithms
Iterative shrinkage/thresholding algorithm (ISTA) is a well-studied method for finding sparse solutions to ill-posed inverse problems. In this letter, we present a data-driven scheme for learning optimal thresholding fun…
Koopman System Approximation Based Optimal Control of Multiple Robots -- Part I: Concepts and Formulations
This paper presents a study of the Koopman operator theory and its application to optimal control of a multi-robot system. The Koopman operator, while operating on a set of observation functions of the state vector of a …
Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization
In this paper, we study adaptive online convex optimization, and aim to design a universal algorithm that achieves optimal regret bounds for multiple common types of loss functions. Existing universal methods are limited…