Nov, 2017

大规模下具有删除鲁棒性的子模最大化

HTML
PDF
TL;DR本文主要研究如何在保护用户隐私和确保公平性的同时，高效地从大型用户生成的数据集中提取有用信息。该问题被描述成删除鲁棒子模型最大化的一个实例，我们提出了第一种内存高效的集中式、流式和分布式方法，对任意数量的敌对删除具有常数逼近保证。我们对我们的算法在真实世界的应用进行了广泛评估，包括：（i）具有位置隐私限制的Uber接送点；（ii）收入预测和犯罪率预测的公平性限制的特征选择；以及(iii)由2,458,285个特征向量组成的人口普查数据的删除汇总结果的健壮性。
发现论文，激发创造
  • 随机化的威力：大规模数据集上的分布式子模最大化

    该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题，该算法可以并行运行并且提供可证明的常数近似保证，即使在单个机器上无法解决的问题也可以通过该算法高效地解决。

    Feb, 2015

  • 非子模目标强鲁棒性最大化

    研究了在最劣情况下，基于一个基数约束k最大化单调集合函数的删除问题，提出了一种新的算法Oblivious-Greedy，并对于更广泛的非凸优化问题证明了首个常数因子逼近保证，通过提出新的度量参数，如逆曲率，证明了这些结果适用于线性区域，并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。

    Feb, 2018

  • 满足背包约束的敌对鲁棒次模最大化

    该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

    May, 2019

  • 下降至删除: 基于梯度的机器遗忘方法

    本文研究了凸模型的数据删除问题，通过利用凸优化和水库取样技术，我们提出了第一个能够处理任意长的对抗性更新序列的数据删除算法，并承诺每次删除的运行时间和稳态误差均不随更新序列的长度而增长。此外，我们还引入了几个新的概念区分。我们可以要求删除后，整个优化算法维护的状态与重新训练应该获得的状态在统计上难以区分，也可以要求仅使可观测输出在统计上难以区分。在这种较弱的删除标准下，我们能够给出更有效的删除算法。

    Jul, 2020

  • 自适应机器遗忘

    本文从差分隐私入手，使用最大信息原理和以往相关工作中对于非自适应删除序列的保证，将针对自适应序列的删除保证推导为针对非自适应删除序列的删除保证，从而为数据删除算法提供了极大的灵活性。实验分析指出该算法能够针对各种模型和训练方法给出强有力的删除保证，并应用在CIFAR-10、MNIST、Fashion-MNIST等数据集上的SISA算法攻击中。

    Jun, 2021

  • 基于拟阵的删除鲁棒子模型最大化

    本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。

    Jan, 2022

  • 基于单调性不稳定的麦特罗伊德上的非单调子模最大化

    该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题，在此问题中，目标是提取一个小型数据集的摘要，即使在对手删除一些元素后也包含高价值独立集，该研究提供了具有常数因子逼近比的近似算法，其中空间复杂度取决于拟阵的秩k和已删除元素的数量d。

    Aug, 2022

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

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

    Apr, 2023

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

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

    May, 2023

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

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

    Dec, 2023