Multi-group Agnostic PAC Learnability

Guy N Rothblum, Gal Yona
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9107-9115, 2021.

Abstract

An agnostic PAC learning algorithm finds a predictor that is competitive with the best predictor in a benchmark hypothesis class, where competitiveness is measured with respect to a given loss function. However, its predictions might be quite sub-optimal for structured subgroups of individuals, such as protected demographic groups. Motivated by such fairness concerns, we study “multi-group agnostic PAC learnability”: fixing a measure of loss, a benchmark class \H and a (potentially) rich collection of subgroups \G, the objective is to learn a single predictor such that the loss experienced by every group g∈\G is not much larger than the best possible loss for this group within \H. Under natural conditions, we provide a characterization of the loss functions for which such a predictor is guaranteed to exist. For any such loss function we construct a learning algorithm whose sample complexity is logarithmic in the size of the collection \G. Our results unify and extend previous positive and negative results from the multi-group fairness literature, which applied for specific loss functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-rothblum21a, title = {Multi-group Agnostic PAC Learnability}, author = {Rothblum, Guy N and Yona, Gal}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9107--9115}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/rothblum21a/rothblum21a.pdf}, url = {https://proceedings.mlr.press/v139/rothblum21a.html}, abstract = {An agnostic PAC learning algorithm finds a predictor that is competitive with the best predictor in a benchmark hypothesis class, where competitiveness is measured with respect to a given loss function. However, its predictions might be quite sub-optimal for structured subgroups of individuals, such as protected demographic groups. Motivated by such fairness concerns, we study “multi-group agnostic PAC learnability”: fixing a measure of loss, a benchmark class $\H$ and a (potentially) rich collection of subgroups $\G$, the objective is to learn a single predictor such that the loss experienced by every group $g \in \G$ is not much larger than the best possible loss for this group within $\H$. Under natural conditions, we provide a characterization of the loss functions for which such a predictor is guaranteed to exist. For any such loss function we construct a learning algorithm whose sample complexity is logarithmic in the size of the collection $\G$. Our results unify and extend previous positive and negative results from the multi-group fairness literature, which applied for specific loss functions.} }
Endnote
%0 Conference Paper %T Multi-group Agnostic PAC Learnability %A Guy N Rothblum %A Gal Yona %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-rothblum21a %I PMLR %P 9107--9115 %U https://proceedings.mlr.press/v139/rothblum21a.html %V 139 %X An agnostic PAC learning algorithm finds a predictor that is competitive with the best predictor in a benchmark hypothesis class, where competitiveness is measured with respect to a given loss function. However, its predictions might be quite sub-optimal for structured subgroups of individuals, such as protected demographic groups. Motivated by such fairness concerns, we study “multi-group agnostic PAC learnability”: fixing a measure of loss, a benchmark class $\H$ and a (potentially) rich collection of subgroups $\G$, the objective is to learn a single predictor such that the loss experienced by every group $g \in \G$ is not much larger than the best possible loss for this group within $\H$. Under natural conditions, we provide a characterization of the loss functions for which such a predictor is guaranteed to exist. For any such loss function we construct a learning algorithm whose sample complexity is logarithmic in the size of the collection $\G$. Our results unify and extend previous positive and negative results from the multi-group fairness literature, which applied for specific loss functions.
APA
Rothblum, G.N. & Yona, G.. (2021). Multi-group Agnostic PAC Learnability. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9107-9115 Available from https://proceedings.mlr.press/v139/rothblum21a.html.

Related Material