通过多项式估计进行随机子模最大化
本文提出自适应子模性的概念,将子模集函数推广到自适应策略,并使用自适应贪心算法解决具有不确定性结果的随机优化问题,通过使用懒惰评估方法显著加快了算法。通过提供子模目标的几个示例,包括传感器放置,病毒营销和主动学习,证明了自适应子模性的实用性。
Mar, 2010
本文研究了许多学习应用中天然存在的连续子模函数的最大化问题,证明了随机投影梯度方法在凸约束下可以提供强的逼近保证,然后将其应用于随机子模函数的最大化问题,最后通过实验证明了该方法的有效性和实用性。
Aug, 2017
该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化,通过将扩展线性化处理并通过向上投影处理,得到离散解,针对加权覆盖函数进行研究,实验表明,该方法在保证最优近似率的同时,大幅降低了计算成本。
Nov, 2017
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
本文研究了 DR-次模连续函数在最大化过程中的基本问题,并在凸集合的不同类型下提出了一系列在线算法,用于最小化在线非单调 DR-次模函数。在实验中表现良好并为机器学习领域中有关问题提供了新的解决方案。
Sep, 2019
本研究考虑了在线连续DR-submodular最大化问题,采用了随机线性长期约束,并提出了在线Lagrangian Frank-Wolfe(OLFW)算法来解决这类问题,得到了期望和高概率下的次线性后悔上限和次线性约束违规上限。
May, 2020
本文研究了随机连续子模最大化问题,在离线和在线两种场景下提出了一种基于 boosting 方法的算法,有效地解决了 DR-submodular 目标函数的最大化问题,并在对抗性环境下讨论了梯度反馈的在线情况。数值实验验证了算法的有效性。
Jan, 2022
研究单调子模函数下的最大值问题以及约束条件下的问题,提出了一个随机的动态算法,并给出了一个高效的数据结构来处理发生了添加和删除变化的值,该算法能够提供一个4近似解。
May, 2023
研究了在线环境下的通用拟阵约束下的单调子模最大化问题,证明了一大类子模函数在在线凸优化问题中的优化等价性,通过合适的舍入方案,实现了在组合优化中达到次线性后悔的 OCO 算法。同时,该规约也适用于多种不同版本的在线学习问题,包括动态后悔、游走和乐观学习等。
Sep, 2023