Supervised learning models have been used in various domains such as lending,
college admission, face recognition, natural language processing, etc. However,
they may inherit pre-existing biases from training data and exhibit
discrimination against protected social groups. Various fairness notions have
been proposed to address unfairness issues. In this work, we focus on Equalized
Loss (EL), a fairness notion that requires the expected loss to be
(approximately) equalized across different groups. Imposing EL on the learning
process leads to a non-convex optimization problem even if the loss function is
convex, and the existing fair learning algorithms cannot properly be adopted to
find the fair predictor under the EL constraint. This paper introduces an
algorithm that can leverage off-the-shelf convex programming tools (e.g.,
CVXPY) to efficiently find the global optimum of this non-convex optimization.
In particular, we propose the ELminimizer algorithm, which finds the optimal
fair predictor under EL by reducing the non-convex optimization to a sequence
of convex optimization problems. We theoretically prove that our algorithm
finds the global optimal solution under certain conditions. Then, we support
our theoretical results through several empirical studies.

通过使用现成的凸规划工具（如 CVXPY），本文提出了 ELminimizer 算法，通过将非凸优化问题转化为一系列凸优化问题，高效地找到满足等效损失约束条件下的全局最优公平预测器，并通过多个实证研究支持我们的理论结果。

公平监督学习的损失平衡

Loss Balancing for Fair Supervised Learning

Given the widespread popularity of spectral clustering (SC) for partitioning
graph data, we study a version of constrained SC in which we try to incorporate
the fairness notion proposed by Chierichetti et al. (2017). According to this
notion, a clustering is fair if every demographic group is approximately
proportionally represented in each cluster. To this end, we develop variants of
both normalized and unnormalized constrained SC and show that they help find
fairer clusterings on both synthetic and real data. We also provide a rigorous
theoretical analysis of our algorithms on a natural variant of the stochastic
block model, where $h$ groups have strong inter-group connectivity, but also
exhibit a "natural" clustering structure which is fair. We prove that our
algorithms can recover this fair clustering with high probability.

本研究研究了一种受 Chierichetti 等人提出的公平原则约束的、用于对图形数据进行分区的谱聚类方法。我们开发了归一化和非归一化受约束谱聚类的变体，并证明它们可以在合成和真实数据上找到更公平的聚类结构。在一种自然环境变体的随机块模型上，我们对算法进行了严格的理论分析，并证明我们的算法可以以高概率恢复这种公平聚类。

具有公平约束的谱聚类的保证

Guarantees for Spectral Clustering with Fairness Constraints

We study the problem of computing maximin share guarantees, a recently
introduced fairness notion. Given a set of $n$ agents and a set of goods, the
maximin share of a single agent is the best that she can guarantee to herself,
if she would be allowed to partition the goods in any way she prefers, into $n$
bundles, and then receive her least desirable bundle. The objective then in our
problem is to find a partition, so that each agent is guaranteed her maximin
share. In settings with indivisible goods, such allocations are not guaranteed
to exist, so we resort to approximation algorithms. Our main result is a
$2/3$-approximation, that runs in polynomial time for any number of agents.
This improves upon the algorithm of Procaccia and Wang, which also produces a
$2/3$-approximation but runs in polynomial time only for a constant number of
agents. To achieve this, we redesign certain parts of their algorithm.
Furthermore, motivated by the apparent difficulty, both theoretically and
experimentally, in finding lower bounds on the existence of approximate
solutions, we undertake a probabilistic analysis. We prove that in randomly
generated instances, with high probability there exists a maximin share
allocation. This can be seen as a justification of the experimental evidence
reported in relevant works. Finally, we provide further positive results for
two special cases that arise from previous works. The first one is the
intriguing case of $3$ agents, for which it is already known that exact maximin
share allocations do not always exist (contrary to the case of $2$ agents). We
provide a $7/8$-approximation algorithm, improving the previously known result
of $3/4$. The second case is when all item values belong to $\{0, 1, 2\}$,
extending the $\{0, 1\}$ setting studied in Bouveret and Lema\^itre. We obtain
an exact algorithm for any number of agents in this case.

本文研究了计算最大最小份额保证的问题，提出了新的公平性概念并使用近似算法解决分配问题，证明了在随机生成的实例中存在最大最小份额分配的概率高，同时对两种特殊情况进行了正面的研究和改进。