自适应次模覆盖问题的贪婪近似比的下界
本文提出自适应子模性的概念，将子模集函数推广到自适应策略，并使用自适应贪心算法解决具有不确定性结果的随机优化问题，通过使用懒惰评估方法显著加快了算法。通过提供子模目标的几个示例，包括传感器放置，病毒营销和主动学习，证明了自适应子模性的实用性。
Mar, 2010
本文研究两个新的优化问题——在满足子模下限的约束条件下最小化子模函数（子模覆盖）和在满足子模上限的约束条件下最大化子模函数（子模背包）。我们将这些问题表述为约束优化问题，并获得许多有界逼近保证。此外，我们证明了这两个问题的紧密关联，并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后，我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013
研究了具有预算约束的最坏情况自适应优化问题，证明了具有点位置次模性和点位置成本敏感次模性的效用函数的两个简单贪心算法不是近似最优的，但其中最优的贪心算法是近似最优的，可以用于解决有限预算下的主动学习问题。
Mar, 2016
研究了Greedy算法在非子模不减集函数基数约束最大化中的性能，并证明了在一些重要的非子模函数如贝叶斯A-最优目标函数中，该算法具有很强的经验性能。我们以广义曲率α和子模性比率γ的组合为特点，证明了其理论保证，特别地，对于基数约束最大化，我们证明了Greedy算法具有紧密的近似保证为1/α(1-e^(-γα))。另外，我们还限制了在几个重要的真实世界目标中子模性比率和曲率，包括贝叶斯A-最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。
Mar, 2017
针对大型数据集中贪心算法的运行时间会非常高的问题，本文介绍了2种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法，并且证明了弱次模性的泛化概念足以为这2种算法提供乘性逼近保证。同时，研究者还表明这些快速贪心逼近算法在人工数据和真实数据集上的性能要优于多个已有的基线算法。
Mar, 2017
本文介绍了针对具有限制条件的子模函数进行最大化的两种算法——Repeated Greedy和Sample Greedy，并比较了这两种算法在电影推荐方面的表现。结果表明，Sample Greedy在保证效用相同的情况下，性能至少比最佳基线提高了两个数量级。
Apr, 2017
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值，其中距离次模性的距离由参数γ衡量，该算法在实践中表现良好，并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
我们研究了自适应组合最大化问题，在机器学习中是一个核心挑战，并应用于主动学习以及其他许多领域。我们研究贝叶斯设置下，考虑最大化目标在基数约束和最小成本覆盖下。我们提供了新的综合近似保证，包括之前的结果，并且更加加强了它们。我们的近似保证同时支持最大增益比以及接近次模效用函数，包括了在基数约束和最小成本覆盖下的最大化保证。此外，我们对一种修改后的先验提供了近似保证，这对于获得独立于先验最小概率的主动学习保证至关重要。此外，我们发现了一种自适应选择策略的新参数，称之为“最大增益比”。我们展示了这个参数比之前近似保证中使用的贪婪近似参数要更加宽松，并展示了它可以提供比之前结果更强的近似保证。特别地，我们展示了最大增益比永远不会大于策略的贪婪近似因子，并且它可以大为缩小。这为自适应组合最大化中有用的策略特性提供了新的见解。
Apr, 2024