Multi-group Agnostic PAC Learnability
Multi-group Agnostic PAC Learnability
复制标题
多组不可知 PAC 的可学习性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
G. Yona
中科院分区：
文献类型：
--
作者：
G. Rothblum;G. Yona
不可知论的PAC学习算法找到了一种与基准假设类别中最佳预测指标竞争的预测因子，在该类别中，竞争性相对于给定的损失函数衡量了。作为受保护的人群群体。 ClassH和A（可能）富含亚组G的集合，目标是学习一个单个预测因子，以使每个组G∈G所经历的损失并不大于H.在自然条件下，该组可能的最佳损失。我们提供了保证存在任何此类损失功能的损失函数的表征。 Collection G.我们的结果统一并扩展了多组公平文献的先前正面和负面结果，该文献适用于特定的损失函数。
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 classH 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.
登录
查看更多内容
DOI：
--
发表时间：
2018-07
期刊：
--
影响因子：
--
作者：
Úrsula Hébert-Johnson;Michael P. Kim;Omer Reingold;G. Rothblum
通讯作者：
Úrsula Hébert-Johnson;Michael P. Kim;Omer Reingold;G. Rothblum
在线多重学习：均值、矩和预测区间
DOI：
--
发表时间：
2022
期刊：
Innovations in Theoretical Computer Science (ITCS
影响因子：
--
作者：
Varun Gupta;Christopher Jung;Georgy Noarov;Mallesh M. Pai;Aaron Roth
通讯作者：
Aaron Roth
用于不确定性估计的矩多重校准
DOI：
--
发表时间：
2021
期刊：
Conference on Learning Theory (COLT
影响因子：
--
作者：
Jung, Christopher;Lee, Changhwa;Pai, Mallesh M;Roth, Aaron;Vohra, Rakesh
通讯作者：
Vohra, Rakesh
从结果中学习：基于证据的排名
DOI：
10.1109/focs.2019.00016
发表时间：
2019
期刊：
60th IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Dwork, Cynthia;Kim, Michael P.;Reingold, Omer;Rothblum, Guy N.;Yona, Gal
通讯作者：
Yona, Gal