在线动态次模优化
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
研究了在线环境下的通用拟阵约束下的单调子模最大化问题,证明了一大类子模函数在在线凸优化问题中的优化等价性,通过合适的舍入方案,实现了在组合优化中达到次线性后悔的 OCO 算法。同时,该规约也适用于多种不同版本的在线学习问题,包括动态后悔、游走和乐观学习等。
Sep, 2023
本文提出了一种投影 - 无关算法 POBGA,通过在线提升梯度上升算法、不可行的投影技术和阻塞技术的新颖组合,以及分散设置的变体,有效地缩短了由先前算法 Mono-FW 降低的后悔下限,并将通信复杂度从 O(T)降低到 O(√T)。
May, 2023
该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe,用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现,通过随机梯度估算和孪生逼近算法来降低收敛难度。
Feb, 2018
提出了一种名为近端在线梯度下降(OGD)算法,用于解决具有不同 iable loss 函数和不可区分正则化器的复合目标函数的非可区分动态优化问题,该算法适用于在线学习框架,并允许损失函数的梯度存在误差。
Jun, 2018
本研究考虑了在线连续 DR-submodular 最大化问题,采用了随机线性长期约束,并提出了在线 Lagrangian Frank-Wolfe(OLFW)算法来解决这类问题,得到了期望和高概率下的次线性后悔上限和次线性约束违规上限。
May, 2020
该论文探讨了在线凸优化涉及敌对损失函数和敌对约束的情况,开发了一种修改的在线鞍点(MOSP)方案,并在动态网络资源分配任务中进行了应用,证明了其相对于梯度方法的性能优势。
Jan, 2017
本研究在完全动态的环境下,旨在最大化基数约束下的单调子模函数,研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法,并结合经验研究证明了算法性能的优越性。
Jun, 2020
文章提出了一种基于离散半微分的无约束和有约束子模函数优化的实用强大新框架,旨在为子模最小化和最大化问题提供统一的范例,并为解决这些问题提供了新的算法,该算法能够多次计算和高效率优化子模半梯度。作者还分析了该算法的理论性质,并进行了支撑的经验实验,证明其在最大化问题上的优秀表现。
Aug, 2013
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界,优于 Mahdavi 等(2012 年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015