Summary
This paper studies algorithmic fairness from a learning theoretic lens, specifically extensions of the recent notion omniprediction by Gopalan et al and its connections to to agnostic learning - multicalibration is sufficient to obtain omniprediction and guarantee agnostic learning for all convex loss functions simultaneously. The main contributions are in introducing a new learning paradigm called Swap Agnostic Learning (SAL), and subsequently new notions of "swap" omniprediction and multicalibration in a similar vein, and proving that they are all equivalent. The authors show that the standard multicalibration algorithm of Herbert-Johnson et al. in fact guarantees swap multicalibration algorithm, and consequently can also be used to obtain a SAL guarantee.
The contributions all hinge on the introduction of the new learning task - swap agnostic learning. SAL requires, informally, that a predictor plays a hypothesis h such that on any level set of their predictor - i.e. set of all x's such that h(x) = v for some fixed v - they have no incentive to change their predictions to any other hypothesis from the hypothesis class on that set. This contrasts the standard agnostic learning which says that the predictor is competitive with the same, single error-minimizing hypothesis in expectation over all the level sets.
The swap notion of omniprediction is similar. A standard omnipredictor for a class of losses L and hypothesis C is a predictor that can be post-processed (in a way that depends on the chosen loss from L) such that it is competitive with the best hypothesis for each loss in L simultaneously. The swap variant requires that the omnipredictor be competitive (up to a level-set dependent post-processing) the best hypothesis on each level set for any assignment of loss functions to level sets.
Section 3 proceeds with the proof of equivalence between these three notions and a brief explanation of how the standard McBoost multiwcalibration algorithm in fact satisfies swap multicalibration, and consequently can be used to achieve the other two swap notions.
Strengths
This paper makes a significant contribution in the area of omniprediction and multicalibration, which are currently popular topics in the study of algorithmic fairness. The newly introduced notion of SAL is interesting and provides a complete picture of the connections between the swap variants of mutlicalibration, omniprediction, and agnostic learning.
Though the content is technically and notationally dense, the presentation is clear.
Weaknesses
A minor suggestion is that if possible, adding a bit of exposition to the swap omniprediction definition to guide the reader through all the moving parts would be helpful. It feels a little trickier to parse than the swap multi calibration and swap agnostic learning definitions. Also, per the below question, maybe adding some exposition describing why these swap variants are natural / intuitive could be helpful.
Simiarly, in Section 3.1, if possible, proof sketches/intuition would be useful as well. There are maybe one or two parts where it is done but the section feels largely like a proof with limited expositional guidance.
Questions
I understand the technical conditions of swap AL, MC, omniprediction and how they are different from the standard notions, but I am slightly confused by the motivation. The original notions seem natural in some sense, is there a reason why these additional technical conditions for the swap variants are intuitive or useful - e.g. giving adversary the additional control down to the granularity of level sets? If I understand correctly, the analogous versions of connections established in this work for all of the "non-swap" notions of these learning tasks are already shown, so again I am slightly confused what the advantage of these swap variants are.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.