Uncertainty and the Social Planner’s Problem: Why Sample Complexity Matters
Uncertainty and the Social Planner’s Problem: Why Sample Complexity Matters
复制标题
不确定性和社会规划者的问题：为什么样本复杂性很重要
DOI：
10.1145/3531146.3533243
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Cousins, Cyrus
中科院分区：
文献类型：
--
作者：
Cousins, Cyrus
福利衡量的是整个人口的总体效用，而不良则衡量的是总体负效用，社会规划者的问题可以是最大化前者或最小化后者。我们展示了新的边界上的期望和尾部概率估计的福利，医疗事故，和遗憾的每组（不）效用值，估计是从一个有限的样本从每个组。特别地，我们考虑估计单个函数的这些量（例如，分配或分类器），以及优化和限制假设类上的泛化误差（即，我们使用Rademacher平均值来量化过拟合）。然后，我们通过样本复杂性的透镜来研究算法的公平性，发现由于边缘化或少数群体往往没有得到充分的研究，因此可用的数据较少，社会规划者更有可能过度适应这些群体，因此即使是在训练中看起来公平的模型也可能系统地对这些群体产生偏见。我们认为，这种影响可以通过确保每组有足够的样本量来减轻，我们的样本复杂性分析表征了这些样本量。受这些结论的启发，我们提出了渐进采样算法，以有效地优化各种公平性目标。
Welfare measures overall utility across a population, whereas malfare measures overall disutility, and the social planner’s problem can be cast either as maximizing the former or minimizing the latter. We show novel bounds on the expectations and tail probabilities of estimators of welfare, malfare, and regret of per-group (dis)utility values, where estimates are made from a finite sample drawn from each group. In particular, we consider estimating these quantities for individual functions (e.g., allocations or classifiers) with standard probabilistic bounds, and optimizing and bounding generalization error over hypothesis classes (i.e., we quantify overfitting) using Rademacher averages. We then study algorithmic fairness through the lens of sample complexity, finding that because marginalized or minority groups are often understudied, and fewer data are therefore available, the social planner is more likely to overfit to these groups, thus even models that seem fair in training can be systematically biased against such groups. We argue that this effect can be mitigated by ensuring sufficient sample sizes for each group, and our sample complexity analysis characterizes these sample sizes. Motivated by these conclusions, we present progressive sampling algorithms to efficiently optimize various fairness objectives.
登录
查看更多内容
不可分割的混合甘露：关于 MMS PO 分配的可计算性
DOI：
10.1145/3465456.3467553
发表时间：
2021
期刊：
EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation
影响因子：
--
作者：
Kulkarni, Rucha;Mehta, Ruta;Taki, Setareh
通讯作者：
Taki, Setareh
DOI：
10.1145/3465456.3467617
发表时间：
2021-03
期刊：
Proceedings of the 22nd ACM Conference on Economics and Computation
影响因子：
--
作者：
Hoda Heidari;Solon Barocas;J. Kleinberg;K. Levy
通讯作者：
Hoda Heidari;Solon Barocas;J. Kleinberg;K. Levy
多组不可知 PAC 的可学习性
DOI：
--
发表时间：
2021
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
G. Rothblum;G. Yona
通讯作者：
G. Yona
DOI：
--
发表时间：
2020-06
期刊：
ArXiv
影响因子：
--
作者：
Preethi Lahoti;Alex Beutel;Jilin Chen;Kang Lee;Flavien Prost;Nithum Thain;Xuezhi Wang;Ed H. Chi
通讯作者：
Preethi Lahoti;Alex Beutel;Jilin Chen;Kang Lee;Flavien Prost;Nithum Thain;Xuezhi Wang;Ed H. Chi
DOI：
--
发表时间：
2020-07
期刊：
Proceedings of machine learning research
影响因子：
--
作者：
Natalia Martínez;Martín Bertrán;G. Sapiro
通讯作者：
Natalia Martínez;Martín Bertrán;G. Sapiro