# Online Monotone Optimization

arXiv: https://arxiv.org/abs/1608.07888 · HTML: https://mlsanity.com/paper/1608.07888/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2016.

## Built on by (most cited first, 2 of 2)

- [A Unified Analysis Method for Online Optimization in Normed Vector Space](https://mlsanity.com/paper/2112.12134/) (2021)
- [Smoothed Online Combinatorial Optimization Using Imperfect Predictions](https://mlsanity.com/paper/2204.10979/) (2022)

## Abstract (arXiv)

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. While previous results in game theory prove individual agents can enjoy unilateral no-regret guarantees, our result proves monotonicity sufficient for guaranteeing no-regret when considering the adjustments of multiple agent strategies in parallel. Furthermore, to our knowledge, this is the first framework to provide a suitable notion of regret for variational inequalities. Most importantly, our proposed framework ensures monotonicity a sufficient condition for employing multiple online learners safely in parallel.