在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe,用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现,通过随机梯度估算和孪生逼近算法来降低收敛难度。
Feb, 2018
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
本文介绍了在曲面上进行在线几何凸优化时如何通过投影自由算法,在有分离预言机或线性优化预言机的情况下实现亚线性后悔保证。
May, 2023
本文研究带复杂约束条件下在线凸优化问题,提出了一种基于镜像投影算法的新算法,可以在任何范数空间中实现低后悔和低约束违反度。
Jun, 2020
该论文研究了随机受限多层优化的无投影算法。介绍了新的无投影方差缩减算法并分析了它们在不同条件下的复杂性,包括梯度映射和 Frank-Wolfe 间隙准则,并通过分阶段适应进一步获得了凸函数和强凸函数的复杂性,数值实验证明了该方法的有效性。
Jun, 2024
本论文提出采用 Frank-Wolfe 技术的高效在线学习算法,避免了投影步骤,同时在在线凸优化方面获得了一系列遗憾界,特别是在随机在线平滑凸优化方面。此外,我们的算法具有参数自由性和产生稀疏决策的优点,并将算法应用到协作过滤的计算密集型应用中,并在标准数据集上显示出理论上的改进。
Jun, 2012
本文研究具有随机约束的在线凸优化问题,提出了一种新的原始 - 对偶镜像下降算法,其可以在不需要 Slater 条件的情况下达到与先前的方法相似的性能并允许等式约束。
Aug, 2019
本文提出了一种新的在线凸优化投影免费算法,并通过利用牛顿迭代的稳定性来计算逆海森矩阵以获得具有最先进遗憾边界的新的高效算法。
Jun, 2023
研究了在线学习问题中的限制,提出了基于 Follow-the-Perturbed-Leader 的投影法之外的高效项目方法,其保证了平滑成本函数和每个迭代中一个线性优化计算的一般在线凸优化中的 $T ^ {2/3}$ 后悔界。
Jan, 2020