Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications
This work addresses the challenge of online learning in vector-valued games for researchers and practitioners in machine learning, offering a general framework with applications in areas like calibration and regret minimization, though it is incremental in building on prior optimization and game theory concepts.
The paper tackles the problem of online minimax multiobjective optimization in non-convex-concave games by introducing a simple algorithm that competes with an adversary forced to act first, achieving optimal diminishing regret. It demonstrates the framework's utility by deriving optimal bounds and efficient algorithms for domains like multicalibration and Blackwell's approachability, and shows a new application with exponentially improved dependence on the number of forecasters in multicalibeating.
We introduce a simple but general online learning framework in which a learner plays against an adversary in a vector-valued game that changes every round. Even though the learner's objective is not convex-concave (and so the minimax theorem does not apply), 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 framework by using it to (re)derive optimal bounds and efficient algorithms across a variety of domains, ranging from multicalibration to a large set of no regret algorithms, to a variant of Blackwell's approachability theorem for polytopes with fast convergence rates. As a new application, we show how to ``(multi)calibeat'' an arbitrary collection of forecasters -- achieving an exponentially improved dependence on the number of models we are competing against, compared to prior work.