Online Monotone Optimization
  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.
