Online Monotone Optimization

Understand

This paper presents a new framework for analyzing and designing no-regret algorithms for dynamic (possibly adversarial) systems.

• The proposed framework generalizes the popular online convex optimization framework and extends it to its natural limit allowing it to capture a notion of regret that is intuitive for more general problems such as those encountered in game theory and variational inequalities.
• The framework hinges on a special choice of a system-wide loss function we have developed.
• Using this framework, we prove that a simple update scheme provides a no-regret algorithm for monotone systems.