A continuous-time approach to online optimization

DOI10.3934/JDG.2017008zbMATH Open1359.90095arXiv1401.6956OpenAlexW2964294891WikidataQ60142047 ScholiaQ60142047MaRDI QIDQ520967FDOQ520967

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 6 April 2017

Published in: Journal of Dynamics and Games (Search for Journal in Brave)

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 $mathcalO(n^{-1/2})$ regret bound without having to resort to a doubling trick.

Full work available at URL: https://arxiv.org/abs/1401.6956

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.

zbMATH Keywords

online optimizationconvex optimizationcontinuous timeregret minimizationmirror descentgradient descent

Mathematics Subject Classification ID

Convex programming (90C25)

Cites Work

• Variational Analysis
• Prediction, Learning, and Games
• Title not available (Why is that?)
• Primal-dual subgradient methods for convex problems
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Robust Stochastic Approximation Approach to Stochastic Programming
• Title not available (Why is that?)
• Convex Analysis
• Microeconomic theory
• The weighted majority algorithm
• Online learning and online convex optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Consistency and cautious fictitious play
• Exponential weight algorithm in continuous time
• Prediction by Categorical Features: Generalization Properties and Application to Feature Ranking
• How to use expert advice
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• On the Global Convergence of Stochastic Fictitious Play
• Conditional universal consistency.
• Stochastic Approximations and Differential Inclusions, Part II: Applications
• Regularization techniques for learning with matrices
• Exponentiated gradient versus gradient descent for linear predictors
• 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
• Consistency of vanishingly smooth fictitious play

Cited In (18)

• Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima
• Learning in nonatomic games. I: Finite action spaces and population games
• Replicator dynamics: old and new
• 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
• Title not available (Why is that?)
• 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)