基于条件梯度方法的随机次模最大化:弥合差距
该论文提出了基于随机条件梯度方法的优化问题求解算法,用于解决大规模维度下的凸函数、连续子模型等多种问题,并证明了当问题维度高时,该方法较与传统的随机梯度下降法更加稳定,同时计算时间复杂度也得到了有效降低。
Apr, 2018
本文研究了许多学习应用中天然存在的连续子模函数的最大化问题,证明了随机投影梯度方法在凸约束下可以提供强的逼近保证,然后将其应用于随机子模函数的最大化问题,最后通过实验证明了该方法的有效性和实用性。
Aug, 2017
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
本文研究了随机连续子模最大化问题,在离线和在线两种场景下提出了一种基于 boosting 方法的算法,有效地解决了 DR-submodular 目标函数的最大化问题,并在对抗性环境下讨论了梯度反馈的在线情况。数值实验验证了算法的有效性。
Jan, 2022
该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化,通过将扩展线性化处理并通过向上投影处理,得到离散解,针对加权覆盖函数进行研究,实验表明,该方法在保证最优近似率的同时,大幅降低了计算成本。
Nov, 2017
我们提出了一种用于非凸约束条件随机优化问题的专门单时间尺度随机方法,其中包含一个 Lipschitz 平滑的外函数和一个广义可微分的内函数。该方法中,我们用一个丰富的参数模型来逼近内部条件期望,该模型的均方误差满足随机版本的 Lojasiewicz 条件。该模型由内部学习算法使用。我们的方法的主要特点在于,方法使用的方向可以通过每次迭代从联合分布中生成一个观测而产生无偏的随机估计,这使其适用于实时学习。然而,这些方向不是任何总体目标函数的梯度或亚梯度。我们利用微分包含的方法和特殊设计的 Lyapunov 函数以及 Bregman 距离的随机推广证明了该方法的收敛性,最后,通过数值实例证明了我们的方法的可行性。
May, 2024
本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题,建立了离散问题和连续松弛之间的强联系,并利用这种联系提出了近似算法和确定性技术,得到了很好的解决方案。
Jan, 2011