A continuous-time approach to online optimization
We consider a family of learning strategies for online optimization problems that evolve in continuous time and we show that they lead to no regret. From a more traditional, discrete-time viewpoint, this continuous-time approach allows us to derive the no-regret properties of a large class of discrete-time algorithms including as special cases the exponential weight algorithm, online mirror descent, smooth fictitious play and vanishingly smooth fictitious play. In so doing, we obtain a unified view of many classical regret bounds, and we show that they can be decomposed into a term stemming from continuous-time considerations and a term which measures the disparity between discrete and continuous time. As a result, we obtain a general class of infinite horizon learning strategies that guarantee an $\mathcal{O}(n^{-1/2})$ regret bound without having to resort to a doubling trick.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A note on continuous-time online learning
In online learning, the data is provided in a sequential order, and the goal of the learner is to make online decisions to minimize overall regrets. This note is concerned with continuous-time models and algorithms for s…
Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or …
Identification of LTV Dynamical Models with Smooth or Discontinuous Time Evolution by means of Convex Optimization
We establish a connection between trend filtering and system identification which results in a family of new identification methods for linear, time-varying (LTV) dynamical models based on convex optimization. We demonst…
FrictionReinforcement LearningState Space ModelsSuboptimal Safety-Critical Control for Continuous Systems Using Prediction-Correction Online Optimization
This paper investigates the control barrier function (CBF) based safety-critical control for continuous nonlinear control affine systems using the more efficient online algorithms through time-varying optimization. The i…
Convex Risk Bounded Continuous-Time Trajectory Planning and Tube Design in Uncertain Nonconvex Environments
In this paper, we address the trajectory planning problem in uncertain nonconvex static and dynamic environments that contain obstacles with probabilistic location, size, and geometry. To address this problem, we provide…
Trajectory Planning