- 机器学习是否增加了额外的偏见?快速近似模型公平性
通过测量各种机器学习应用中的歧视水平,通过近似算法计算集合之间的距离以实现公平,提出了基于流形的 “谐波公平度量(HFM)” 和 “集合距离的近似算法(ApproxDist)”。
- 多层关联聚类
我们在这篇论文中建立了多层相关聚类,这是对相关聚类(Bansal 等人,FOCS'02)在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法(其中 L 是层数),然后研究了带有概率约束的一个重要 - CLIPPER+:一种用于稳健全局配准的快速极大团算法
CLIPPER + 是一种用于异常鲁棒的全局配准的寻找最大团的算法,通过近似求解最大团问题以提高计算效率和解决方案准确性,在标准图基准、合成和真实世界点云配准问题上表现出最高的准确性。
- 具有背景知识的高效 $k$- 中心聚类
在这项工作中,我们在广泛采用的 $k$- 中心聚类的基础上构建其输入的背景知识作为必连(ML)和禁连(CL)约束集,并通过使用一系列技术,包括反支配集、线性规划整体多面体和线性规划对偶,得出了第一个具有最佳比例 2 的约束 $k$- 中心的 - 竞争产品下的社交网络病毒营销
在一个定向网络中,通过开发新颖的证明技术,我们提供了一个有着最佳可能近似保证的多项式时间近似算法,同时利用目标函数的单调性和子模性以及蒙特卡洛方法破解了计算问题的艰难之处,并在各种真实和合成网络上的实验中证明了我们提出的算法胜过其他算法。此 - AAAI通过多样性促进反事实鲁棒性
通过报告多个反事实,可以提供一些有意义的鲁棒性保证,这篇论文提出了一种近似算法来选择最相关的解释,并在实验中证明了其在生成鲁棒性解释方面的改进。
- 通过 LP 分层的多维度尺度算法的准多项式时间算法
我们研究了多维缩放(Multi-dimensional Scaling,MDS)的 Kamada-Kawai 公式,提出了一种基于 Sherali-Adams 线性规划层次的近似算法,该算法实现了在目标维度下成本和时间复杂度之间的平衡,为高 - 线性行为克隆智能体的最佳教学
我们研究了 Linear Behavior Cloning(LBC)学习者的最佳教学方法。我们提出了一种名为 “Teach using Iterative Elimination(TIE)” 的教学算法,它实现了最佳的教学维度。然而,我们也 - 通过 Frank-Wolfe 的改进 Metarounding 算法
通过使用 metarounding 算法,我们提出了一种将线性优化的近似算法转化为同一类别的在线线性优化算法的新方法,该算法在理论和实践方面都更加高效。
- 大规模并行热图排序及其在可解释聚类中的应用
给定一组具有 $k$ 个标签的点,我们引入了热图排序问题,该问题在重新排序和合并点和维度的同时保留聚类(标签)。我们证明了该问题是 NP 难问题,并且在高度并行计算模型中给出了一个具有恒定轮数的固定参数算法,其中每台机器都具有子线性内存,且 - 图上 k - 中心问题的动态算法
提供了首个对动态图进行边更新的 k - 中心问题的高效算法
- 基于拟阵约束的 k 次次模最大化的快速算法
应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数,提出逼近算法来最大化满足单调和非单调 k - 次模函数,并提供了关于时间复杂度的结果,同时还介绍了针对总大小约束的快速算法。
- 背包问题:连通性、路径和最短路径
我们研究了具有图论约束的背包问题,证明了该问题是 NP 完全问题,并提出了一个在多项式时间内运行的算法以及一个近似算法。
- ICML公平范围聚类的近似算法
研究公平间距聚类问题,提供 O (1) 的近似算法在最多 k+2l 个中心中选择最小化聚类成本的一组中心,并仅在每个人口统计上最多违反 2 个加法项的上限。
- ICML适用于二元矩阵分解的快速(1+ε)近似算法
本研究提出了用于解决二元矩阵因式分解问题的高效近似算法,其中输入矩阵 A,矩阵的秩 k,一个精度参数 ε,并且其目标是将 A 近似为低秩因子 UV 的乘积。
- 任意 $p$- 范数的实验设计
本文研究实验设计问题的一般 p - 范数目标,证明了采用随机局部搜索方法可以为所有 p 提供一种统一的求解算法,同时提供了专门情况下已知最佳边界的漂亮插值。
- 通过范例的可解释聚类:复杂度和高效近似算法
该研究提出了一种可解释的基于设计聚类的方法,该方法不仅可以找到集群,还可以找到举例来解释每个集群。作者提供了两个近似算法,可以提供证明性能保证以及应用范围。实验结果表明,这项工作在涉及难以理解的深度图像和文本嵌入的领域中非常有用。
- ICML基于单调性不稳定的麦特罗伊德上的非单调子模最大化
该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题,在此问题中,目标是提取一个小型数据集的摘要,即使在对手删除一些元素后也包含高价值独立集,该研究提供了具有常数因子逼近比的近似算法,其中空间复杂度取决于拟阵的秩 k 和已删除元素 - 差分隐私部分集覆盖及其在设施位置方面的应用
以差分隐私为前提,对解决集合覆盖问题的可能性结果进行了研究,发现在部分集合覆盖问题中,这种难度结果会消失,从而提供了具有非平凡逼近保证的显式集合覆盖的不同隐私算法,并给出了百科拉蒂问题的私有(双目标)逼近算法,该问题是 $k$-center - 利用李雅普诺夫函数方法进行近似算法设计和分析:在子模最大化中的应用
本文提出了一种基于李雅普诺夫函数的逼近算法设计和分析的两阶段系统框架,第一阶段使用李雅普诺夫函数生成一个连续时间逼近算法,第二阶段将其转化为一个具有几乎相同逼近比和可证明时间复杂度的离散时间算法,旨在统一许多现有算法、指导设计和分析新算法,