强凸平滑函数动态遗憾的改进分析
本研究关注在线凸优化的动态遗憾,通过探索称为路径变化的时间变化机制,提出了一些动态遗憾改进的变差上限,并证明他们在已有的下限条件下是最优的。
May, 2016
本文研究动态环境下的在线凸优化问题,通过提出一种自适应学习的方法 Ader,利用专家跟踪算法结合一组专家来最小化动态遗憾,并扩展到可用于表征比较器的动态模型序列的情形。
Oct, 2018
通过建立连续在线学习(COL)这种新的设置,连续轮次中在线损失函数的梯度会随着学习者的决策而连续变化,我们可以更完整地描述许多有趣的应用,特别地,证明了满足单调EPs(经济平衡问题)能够在COL中实现子线性的静态遗憾。 由此得出的启示是,我们提供了实现子线性动态遗憾的有效算法的条件,即使选择的损失在先验变化预算中没有适应性。 此外,我们还展示了一个从动态遗憾到静态遗憾和相关EP(经济平衡问题)收敛的COL之间的简化,从而允许我们分析许多现有算法的动态遗憾。
Feb, 2019
本文研究递归最小二乘算法中的遗忘因子对在线牛顿算法动态后悔的影响,对于指数凸和强凸目标,算法可实现动态后悔的界限,同时提出一种用于强凸函数的梯度下降步长规则以获得更高的计算效率。
Sep, 2019
本文提出了一种在线凸优化算法,该算法在非稳态环境中表现出优异的动态后悔表现,通过充分利用流畅性条件,能够在动态后悔中代替对T的依赖,而采用问题相关的数量:损失函数的梯度变化、比较序列的累积损失和前两个 term 的最小值,从而使问题的复杂度自适应问题的困难程度,即在简单问题上使界限更紧,同时保证了最坏情况下相同的界限。
Jul, 2020
使用先进的证明技术和Zinkevich-style动态遗憾最小化框架,本研究提出了一个强适应的在线学习算法,其总变化控制下的动态遗憾为O(n^(1/3)*C_n^(2/3)),并且可以扩展到局部自适应非参数回归问题中。
Apr, 2021
本文研究了强凸损失函数下的动态遗憾最小化框架,通过利用KKT条件所施加的许多新约束条件,我们回答了Baby和Wang 2021年提出的一个开放性问题,并展示了强适应算法在适当的学习设置下可以同时针对任何比较序列达到几乎最优的动态遗憾。此外,在处理非平滑损失和改善回避维度依赖性等方面,我们还取得了Baby和Wang 2021年工作的其他改进,并针对exp-concave损失和一个L∞受限决策集的特殊情况导出了几乎最优的动态遗憾率。
Jan, 2022
动态遗憾最小化在在线凸优化中是一个重要问题。本文提出了一个新的统一框架来分析和设计这些算法,证明了适应任意比较序列的动态遗憾达到O(根号下T总和的局部平滑化平方路径长度)的算法是可行的,并且提供了一个替代路径长度计算方式的新概念来实现更好的适应性。
Jun, 2024