本文提出了一种适用于分布式计算的子模函数最大化方法GreeDi,该方法可在MapReduce框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
该论文提出了一种基于图分割的分布式计算算法,其可以有效降低数据分布式处理过程中的通信成本,实验结果表明该算法能够在机器学习系统中实现1.6倍的加速,并且消除90%的网络通信。
May, 2015
本文提出了新的算法解决通过分配数据任务和负载均衡来实现大规模机器学习的submodular partitioning问题,并在图像分割中也取得了很好的表现。
Oct, 2015
该篇论文提出了一种针对固定容量的分布式子模型最大化的框架,应用于广泛的算法和约束条件,并且为任何可用容量提供近似因子的理论保证,并在多个数据集上进行了实证评估,表现竞争性与中心化贪婪算法相当。
May, 2016
研究单调子模函数下的最大值问题以及约束条件下的问题,提出了一个随机的动态算法,并给出了一个高效的数据结构来处理发生了添加和删除变化的值,该算法能够提供一个4近似解。
May, 2023
非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近
Aug, 2023
在机器学习中,基于 matroid 约束的子模最大化是一个具有各种应用的基本问题。最近,已经在有限制条件下的流式和离线设置下考虑了基于基数约束的子模最大化中的公平性,但对于更一般的 matroid 约束问题,只有在流式设置下且只考虑单调目标。本文通过提出各种算法和不可能性结果,在质量、公平性和广泛性之间提供了不同的权衡。
Dec, 2023
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
我们描述了一种并行的近似算法,用于在分布式内存多处理器上最大化满足遗传约束的单调次模函数。
Mar, 2024