Timezone: »

 
Poster
Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications
Daniel Lee · Georgy Noarov · Mallesh Pai · Aaron Roth

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #314
in Poster Session 6 »

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.

Author Information

Daniel Lee (University of Pennsylvania => Susquehanna International Group)

I'm a student/researcher interested in learning theory and fairness in ML; currently doing a stint in quantitative finance before applying to PhD.

Georgy Noarov (School of Engineering and Applied Science, University of Pennsylvania)
Mallesh Pai (Rice University)
Aaron Roth (University of Pennsylvania)

More from the Same Authors