实验设计的近似超模性界
本文提出自适应子模性的概念,将子模集函数推广到自适应策略,并使用自适应贪心算法解决具有不确定性结果的随机优化问题,通过使用懒惰评估方法显著加快了算法。通过提供子模目标的几个示例,包括传感器放置,病毒营销和主动学习,证明了自适应子模性的实用性。
Mar, 2010
研究了Greedy算法在非子模不减集函数基数约束最大化中的性能,并证明了在一些重要的非子模函数如贝叶斯A-最优目标函数中,该算法具有很强的经验性能。我们以广义曲率α和子模性比率γ的组合为特点,证明了其理论保证,特别地,对于基数约束最大化,我们证明了Greedy算法具有紧密的近似保证为1/α(1-e^(-γα))。另外,我们还限制了在几个重要的真实世界目标中子模性比率和曲率,包括贝叶斯A-最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。
Mar, 2017
本文介绍了针对具有限制条件的子模函数进行最大化的两种算法——Repeated Greedy和Sample Greedy,并比较了这两种算法在电影推荐方面的表现。结果表明,Sample Greedy在保证效用相同的情况下,性能至少比最佳基线提高了两个数量级。
Apr, 2017
本文提出了一个多项式时间的遗憾最小化框架,以在所有统计效率计算标准上,用只有O(p/ε^2)个设计点实现(1+ε)近似,并与传统算法作比较,本算法实现了D/E/G效率最优可行化的(1+ε)近似。
Nov, 2017
本文提出了一个新的实验设计框架,用于解决隐式模型中的优化资源分配问题,采用了先前不可行的参数和数据之间的互信息作为效用函数,并使用基于贝叶斯优化的方法解决最优设计问题。
Oct, 2018
本文提出了一种全概率梯度方法来解决贝叶斯最优实验设计的问题,该方法利用变分下界来进行预期信息增益的优化,并提供多种变分目标,最终表现出比现有方法在高维设计优化中更有效的性能。
Nov, 2019
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023
从候选池中选择$k$个实验以最大化所选子集与潜在参数之间的互信息,并通过基于Log-Sobolev不等式构建的计算廉价的互信息下界提出了贪婪方法,这对于非线性/非高斯环境中的互信息评估而言具有计算复杂性的问题具有优于随机选择策略、高斯近似和嵌套Monte Carlo(NMC)估计的性能,包括在具有非加性噪声的非线性模型的最优设计。
Feb, 2024
贪婪算法的自适应子模块覆盖近似比率至少为1.3 *(1 + ln Q),这篇论文否定了Golovin-Krause在``自适应子模块性:主动学习和随机优化的新方法''中宣称相同算法具有(1 + ln Q)^2近似比率的先前结果。
May, 2024