子模集约束下的公平性最大化

Dec, 2023

Fairness in Submodular Maximization over a Matroid Constraint

Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, Thuy-Duong Vuong

TL;DR在机器学习中，基于 matroid 约束的子模最大化是一个具有各种应用的基本问题。最近，已经在有限制条件下的流式和离线设置下考虑了基于基数约束的子模最大化中的公平性，但对于更一般的 matroid 约束问题，只有在流式设置下且只考虑单调目标。本文通过提出各种算法和不可能性结果，在质量、公平性和广泛性之间提供了不同的权衡。

Abstract

submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attribut

发现论文，激发创造

分布式次模最大化的新框架

通过将现有算法从顺序设定应用到分布式设定，仅利用恒定数量的MapReduce循环，在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。

Jul, 2015

做更少，得更多：带子采样的流式子模最大化

该论文提出了首个一次遍历的流算法，用于求解子模最大化问题，采用数据采样，能够在各种情况下获得最紧密的逼近保证，同时具有最小的内存占用和对函数评估数量的最低要求，试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高50倍以上

Feb, 2018

从数据流中公平且代表性地选择子集

本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题，并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。

Oct, 2020

通过随机化实现子模函数最大化的长期公平性

通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。

Apr, 2023

在Matroid约束下流式子模最大化中的公平性

论文研究流式子模最大化算法中公平性的应用，提出了针对劣模最大化算法的公平机器学习算法，包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后，通过社会网络中的最大覆盖，电影推荐和样本聚类等应用的实验验证了其有效性。

May, 2023

基于拟阵的全动态次模最大化

研究单调子模函数下的最大值问题以及约束条件下的问题，提出了一个随机的动态算法，并给出了一个高效的数据结构来处理发生了添加和删除变化的值，该算法能够提供一个4近似解。

May, 2023

基于动态规划的拟阵子模最大化算法

针对子模最大化问题，本文提出了一种动态算法，该算法对于给定序列的插入和删除操作，维护了一个在任一时间点上具有 4+ε 近似度的子系统，其参数化为 matroid 约束的秩 k，并且查找复杂度与序列长度无关；同时，我们还探讨了基于基数约束的子模最大化问题的动态算法。

Jun, 2023

非单调次模最大化的实用并行算法

非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近

Aug, 2023

一致子模最大化

在具有一致性约束的动态环境中，我们研究了在基数约束下最大化单调次模函数，其在数据挖掘和机器学习中有多个应用。我们提供了在此场景中具有一致性和逼近质量之间不同权衡的算法。实验证明我们算法在真实世界实例中的有效性。

May, 2024

公平子模块覆盖

研究了具有公平性子模函数覆盖的子模函数优化问题，提出离散和连续算法实现了近似比例，同时通过实证评估证明了算法在最大覆盖实例上的有效性。

Jul, 2024