Oct, 2017

结构稳健次模最大化：离线与在线算法

PDF
TL;DR本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法，旨在提高对次模优化的建模范围，尤其应用于单个或多个基序，背包以及具有分散鲁棒性的标准约束条件，该算法适用于离线和在线设置，并且在线问题的双标准解决方案具有 sub-linear 的遗憾。
发现论文，激发创造
  • 快速子模函数最大化

    本研究提出了一种基于新型搜索树数据结构的算法，可以高效地计算在线和离线子模函数最大值问题。

    May, 2023

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

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

    May, 2019

  • 约束 k 次模最大化的在线和流式算法

    本文提出了单遍流式和在线算法的受约束 k - 次模最大化，其中包含基数和背包约束限制，该算法可以提供不错的近似解和高效的解决方案，并在广告分配等应用实例上得到了验证。

    May, 2023

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

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

    Jul, 2015

  • 分布鲁棒子模最大化

    通过直接优化偏差和方差的组合，该研究通过展示如何进行具有理论保证的高效算法，从而在次模函数中进行分布式鲁棒优化（DRO），从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。

    Feb, 2018

  • 通过非对称技术来实现受限子模最大化

    本文研究了带有子模性目标函数的组合优化问题，提出了一种基于新技术的算法来优化多线性松弛问题，该算法避免了对称性等性质的需要，适用于约束问题，相比之前的算法，它具有更好的保证。

    Nov, 2016

  • 在线玄学最大化下的基合约束与学习分配应用

    本文提出了一种能够动态地为信息源进行排序，同时又能保证重复信息的减少不会影响子模函数的最优化问题算法，并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。

    Jul, 2014

  • 在线凸优化下的在线次模最大化

    研究了在线环境下的通用拟阵约束下的单调子模最大化问题，证明了一大类子模函数在在线凸优化问题中的优化等价性，通过合适的舍入方案，实现了在组合优化中达到次线性后悔的 OCO 算法。同时，该规约也适用于多种不同版本的在线学习问题，包括动态后悔、游走和乐观学习等。

    Sep, 2023

  • 分布式子模最大化

    本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

    Nov, 2014

  • 水平可扩展次模最大化

    该篇论文提出了一种针对固定容量的分布式子模型最大化的框架，应用于广泛的算法和约束条件，并且为任何可用容量提供近似因子的理论保证，并在多个数据集上进行了实证评估，表现竞争性与中心化贪婪算法相当。

    May, 2016