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