A continuous-time approach to online optimization
From MaRDI portal
(Redirected from Publication:520967)
Abstract: 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 regret bound without having to resort to a doubling trick.
Recommendations
- Logarithmic Regret Algorithms for Online Convex Optimization
- Logarithmic regret algorithms for online convex optimization
- Continuous time learning algorithms in optimization and game theory
- A generalized online mirror descent with applications to classification and regression
- Regret-based continuous-time dynamics.
Cites work
- scientific article; zbMATH DE number 3128728 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1233801 (Why is no real title available?)
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- A game of prediction with expert advice
- Adaptive and self-confident on-line learning algorithms
- Analysis of two gradient-based algorithms for on-line regression
- Conditional universal consistency.
- Consistency and cautious fictitious play
- Consistency of vanishingly smooth fictitious play
- Convex Analysis
- Exponential weight algorithm in continuous time
- Exponentiated gradient versus gradient descent for linear predictors
- How to use expert advice
- Microeconomic theory
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- On the Global Convergence of Stochastic Fictitious Play
- Online learning and online convex optimization
- Prediction by Categorical Features: Generalization Properties and Application to Feature Ranking
- Prediction, Learning, and Games
- Primal-dual subgradient methods for convex problems
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Regularization techniques for learning with matrices
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic Approximations and Differential Inclusions, Part II: Applications
- The weighted majority algorithm
- Variational Analysis
Cited in
(18)- Learning in nonatomic games. I: Finite action spaces and population games
- Replicator dynamics: old and new
- Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima
- Online Optimization with Uncertain Information
- On the Value of Objective Function Adaptation in Online Optimisation
- On the convergence of gradient-like flows with noisy gradient input
- scientific article; zbMATH DE number 7626738 (Why is no real title available?)
- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Online BP functions maximization
- Learning in games via reinforcement and regularization
- Introduction to Online Convex Optimization
- Exploration-exploitation in multi-agent learning: catastrophe theory meets game theory
- Continuous time learning algorithms in optimization and game theory
- Asymmetric replicator dynamics on Polish spaces: invariance, stability, and convergence
- From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory
- A survey of gradient methods for solving nonlinear optimization
- Scale-free algorithms for online linear optimization
- No-regret algorithms in on-line learning, games and convex optimization
This page was built for publication: A continuous-time approach to online optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520967)
