Dec, 2015

带长期约束的在线凸优化自适应算法

PDF
TL;DR提出了一种适应性在线梯度下降算法，用于解决具有长期约束的在线凸优化问题，可以处理任意凸约束，该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界，优于 Mahdavi 等（2012 年）最好的已知累积遗憾界，该算法的性能已在实践中得到验证。
adaptive online gradient descent algorithmonline convex optimizationlong-term constraintscumulative regret boundsconvex losses
发现论文，激发创造
  • 累积约束的在线凸优化

    该研究提出了一种在线凸优化算法，其可以处理特定类型的累计平方约束违规问题，以及为凸目标导出了另类的后悔边界，并针对强凸目标提出了改进的后悔边界，并在数值实验中说明了该算法的效果。

    Feb, 2018

  • 将后悔换成效率：具有长期限制条件的在线凸优化

    本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题，提出了一种有效的算法，可以实现收敛性较好的结果。同时，本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。

    Nov, 2011

  • 约束在线凸优化的梯度变差限制

    本文研究带复杂约束条件下在线凸优化问题，提出了一种基于镜像投影算法的新算法，可以在任何范数空间中实现低后悔和低约束违反度。

    Jun, 2020

  • 在线凸优化的自适应边界优化

    本文提出了一种新的在线凸优化算法，该算法根据迄今为止观察到的损失函数自适应地选择其正则化函数，其遗憾界是最坏情况下最优的，并且对于某些实际损失函数类别，它们比现有界限好得多。此算法不需要事先了解问题实例的结构，但提供了一定程度的竞争保证，并在范围内提供了一定程度的界限。

    Feb, 2010

  • 无投影在线凸优化与时变约束

    在线凸优化中，考虑具有对抗性时变约束的情景，在这种情况下，行动必须相对于固定约束集是可行的，同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法，通过线性优化预言机（LOO）访问这个集合来保证在一个长度为 T 的序列上，通过总共 T 次对 LOO 的调用，相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$，对于约束的违反是 $O (T^{7/8})$（忽略除了 $T$ 以外的所有量）。尤其地，这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法，它仅需要对软约束进行一阶预言机访问，并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景，并在期望上获得了类似的边界（作为 $T$ 的函数）。

    Feb, 2024

  • 在线长期受限优化

    提出和分析一种新型的 Follow-the-Perturbed-Leader 类型算法，用于在线方式解决一般的长期受约束的优化问题，其中目标和约束不一定是凸的。通过将随机线性扰动和强凸扰动分别引入原始和对偶方向，搜索全局极小极大点作为解决方案，并基于两个特定的预期静态累积遗憾定义，推导出这类问题的第一个次线性 $O (T^{8/9})$ 遗憾复杂度。该算法应用于解决长期（风险）受约束的河流污染源辨识问题，验证了理论结果的有效性，并表现出比现有方法更优越的性能。

    Nov, 2023

  • 具有对抗约束的在线凸优化的严格界

    有关在线凸优化和约束在线凸优化的一篇研究论文，证明了一个在线策略可以同时实现 O (√T) 的遗憾和 θ̃(√T) 的累积约束违规，通过将 AdaGrad 算法的自适应遗憾界与 Lyapunov 优化相结合，达到了这一结果。

    May, 2024

  • 多点带约束的强化凸优化反馈

    本文研究带有约束的赌博性凸优化问题，在部分信息的损失函数下，学习者旨在生成一系列决策，使得累计损失减少，同时累计违约累积也在减少。我们采用累计硬约束违反作为约束违反的指标，并提出了一种基于罚函数的近端梯度下降方法，能够在凸损失函数和时变约束下实现次线性增长的遗憾和累计硬约束违反界限。

    Oct, 2023

  • 时变约束在线凸优化

    本文研究了具有时间变化的约束条件的在线凸优化问题，并提出了一种算法，其收敛性具有一定的时间复杂度，并且可以在没有先验知识的情况下达到无偏的最优解。

    Feb, 2017

  • 渐进变化的通用在线学习：多层在线集成方法

    本文提出了基于多层在线集成的在线凸优化方法，具有两种不同的适应性水平，并针对强凸、指数 - 凹和凸损失函数分别获得了收敛等效性和遗憾上界。

    Jul, 2023