Online Multiobjective Minimax Optimization and Applications
  We introduce a simple but general online learning framework, in which at
every round, an adaptive adversary introduces a new game, consisting of an
action space for the learner, an action space for the adversary, and a vector
valued objective function that is convex-concave in every coordinate. The
learner and the adversary then play in this game. The learner's goal is to play
so as to minimize the maximum coordinate of the cumulative vector-valued loss.
The resulting one-shot game is not convex-concave, and so the minimax theorem
does not apply. Nevertheless, we give a simple algorithm that can compete with
the setting in which the adversary must announce their action first, with
optimally diminishing regret.
  We demonstrate the power of our simple framework by using it to derive
optimal bounds and algorithms across a variety of domains. This includes no
regret learning: we can recover optimal algorithms and bounds for minimizing
external regret, internal regret, adaptive regret, multigroup regret,
subsequence regret, and a notion of regret in the sleeping experts setting.
Next, we use it to derive a variant of Blackwell's Approachability Theorem,
which we term "Fast Polytope Approachability". Finally, we are able to recover
recently derived algorithms and bounds for online adversarial multicalibration
and related notions (mean-conditioned moment multicalibration, and prediction
interval multivalidity).
