Nov, 2023

在线长期受限优化

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

    研究基于非凸损失的在线学习问题，证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率，进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。

    Mar, 2019

  • 通过平滑实现在线线性优化

    本文介绍了一种新的优化理论方法，用于分析使用扰动作为正则化工具实现 Follow-the-Leader 程序的特定设置，该方法包括添加强凸罚函数到决策规则和添加随机扰动到数据的方法，并在 Follow the Regularized Leader 和 Follow the Perturbed Leader 之间建立了等价关系，从而得出了一个可以恢复和改进先前已知后悔上限的算法类 Follow the Perturbed Leader 的通用分析框架。

    May, 2014

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

    提出了一种适应性在线梯度下降算法，用于解决具有长期约束的在线凸优化问题，可以处理任意凸约束，该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界，优于 Mahdavi 等（2012 年）最好的已知累积遗憾界，该算法的性能已在实践中得到验证。

    Dec, 2015

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

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

    Nov, 2011

  • 随机行走扰动预测

    本文提出了一种基于扰动随从最优策略算法版本，可以将累积损失通过独立的对称随机游动进行扰动，预测者能够实现期望遗憾最优阶 O (sqrt (n log N)), 且预测者的改变在预期下最多为 O (sqrt (n log N))，同时拓展分析在线组合优化，表明即使在更一般的情况下，预测者也很少在专家之间切换，同时达到近乎最优的遗憾级别。

    Feb, 2013

  • 随机约束下的在线原始 - 对偶镜像下降

    本文研究具有随机约束的在线凸优化问题，提出了一种新的原始 - 对偶镜像下降算法，其可以在不需要 Slater 条件的情况下达到与先前的方法相似的性能并允许等式约束。

    Aug, 2019

  • 动态环境下的在线优化：强凸问题改进遗憾率

    本文提出一种基于在线梯度下降方法的动态调参算法，以降低动态遗憾（dynamic regret），进而优化强凸且未知动力学的损失函数。

    Mar, 2016

  • 高效使用近似算法的在线线性优化

    本文讨论在线线性优化问题，考虑可行操作集通过近似线性优化预言机具有 α 乘性逼近保证的情况，给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度，同时得到了常数 c>0 的 alpha 遗憾界。

    Sep, 2017

  • 基于随机累积约束的在线 DR 子模最大化

    本研究考虑了在线连续 DR-submodular 最大化问题，采用了随机线性长期约束，并提出了在线 Lagrangian Frank-Wolfe（OLFW）算法来解决这类问题，得到了期望和高概率下的次线性后悔上限和次线性约束违规上限。

    May, 2020

  • 有约束的在线两阶段随机优化：具有（和不具有）预测的算法

    我们考虑了一个在线两阶段随机优化问题，有关于 T 个周期的长期约束。我们通过对抗学习算法开发了在线两阶段问题的在线算法，同时，我们的算法的遗憾界可以降低到嵌入对抗式学习算法的遗憾界。基于这个框架，在不同的设置下，我们得到了新的结果。

    Jan, 2024