Apr, 2018

随机条件梯度方法：从凸优化到子模最大化

PDF
TL;DR该论文提出了基于随机条件梯度方法的优化问题求解算法，用于解决大规模维度下的凸函数、连续子模型等多种问题，并证明了当问题维度高时，该方法较与传统的随机梯度下降法更加稳定，同时计算时间复杂度也得到了有效降低。
stochastic optimizationconvex functionsconditional gradient methodssubmodular maximizationstochastic gradients
发现论文，激发创造
  • 基于条件梯度方法的随机次模最大化：弥合差距

    研究连续子模最大化问题，通过提供新颖的算法并使用随机持续优化作为接口，在满足约束条件的情况下获得了紧密的逼近保证。

    Nov, 2017

  • 次模最大化的梯度方法

    本文研究了许多学习应用中天然存在的连续子模函数的最大化问题，证明了随机投影梯度方法在凸约束下可以提供强的逼近保证，然后将其应用于随机子模函数的最大化问题，最后通过实验证明了该方法的有效性和实用性。

    Aug, 2017

  • 基于随机模型的弱凸函数最小化

    本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

    Mar, 2018

  • 随机子模极大化：覆盖函数的情形

    该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化，通过将扩展线性化处理并通过向上投影处理，得到离散解，针对加权覆盖函数进行研究，实验表明，该方法在保证最优近似率的同时，大幅降低了计算成本。

    Nov, 2017

  • 通过多项式估计进行随机子模最大化

    本研究以连续贪心算法为基础，研究了具有一般性骨架约束的随机子模最大化问题，主要应用于在线学习，团队形成，设施位置，影响最大化，主动学习和感知目标函数。实验表明，使用多项式梯度估计代替样本估计，可有效减少随机性并缩短执行时间。

    Mar, 2023

  • 在线连续子模最大化

    本文研究一种在线优化过程，其中目标函数不是凸函数（也不是凹函数），而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体，它可以访问目标函数的全梯度，并证明它对未来最佳可行解的（1-1/e）- 近似具有 O（T 的平方根）的遗憾界。对于只能获得梯度的无偏估计的情况，我们还提出了在线随机梯度上升算法，并证明它也具有 O（T 的平方根）的遗憾界，但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数，并证明相同的次线性遗憾界。最后，在几个问题实例上演示了算法的效率，包括非凸 / 非凹二次规划，子模集函数的多线性扩展和 D - 最佳设计。

    Feb, 2018

  • 基于随机梯度的无需投影的在线优化：从凸性到次模性

    该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe，用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现，通过随机梯度估算和孪生逼近算法来降低收敛难度。

    Feb, 2018

  • 非光滑、非凸问题的近距离引导随机次梯度方法

    本文介绍了一种基于随机投影次梯度方法的弱凸（即均匀逼近正则）非光滑非凸函数的算法，并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度；这似乎是第一个针对弱凸函数类的随机次（或确定性）梯度法的收敛速度分析。

    Jul, 2017

  • 随机（近似）近端点法：收敛性，最优性和适应性

    本文提出了基于模型的方法，解决随机凸优化问题，并介绍了近似近端点（aProx）家族，包括随机次梯度、近端点和束方法。通过适当准确的建模方法，这些方法享有比传统方法更强的收敛性和鲁棒性保证，即使与随机次梯度方法相比，基于模型的方法通常增加很少甚至没有计算开销。

    Oct, 2018

  • 随机连续次模最大化：通过非遗忘函数增强

    本文研究了随机连续子模最大化问题，在离线和在线两种场景下提出了一种基于 boosting 方法的算法，有效地解决了 DR-submodular 目标函数的最大化问题，并在对抗性环境下讨论了梯度反馈的在线情况。数值实验验证了算法的有效性。

    Jan, 2022