平滑分段常数函数的在线优化
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
文章探讨带有噪声梯度反馈的非平稳随机优化框架,在比较序列变化的动态策略中,研究在线学习算法的动态后悔,并引入了 Total Variation ball 等新颖变分约束来建模比较序列,并基于基于小波的非参数回归理论,设计出一个多项式时间算法,并证明了该算法达到了几乎最优的动态后悔,该策略适应未知的半径。
Sep, 2020
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
我们研究具有 Lipschitz 损失的无约束在线线性优化问题,提出一种新的连续时间启发式算法,通过连续时间模型和离散时间对偶的方式实现渐进的梯度自适应和比较器范数自适应,克服了传统方法中梯度方差的缺陷并消除了未知 Lipschitz 常数的问题。
Sep, 2023
本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题,特别着重于高度平滑问题的凸优化问题,包括逻辑回归等。研究表明,相对于基于梯度的算法,高阶平滑性可用于改善估计速率,并精确地依赖于平滑度的程度,同时提出了此类算法可行性的上限。最后,作者还在在线优化设置中取得了类似的结果。
May, 2016
研究了具有预测模型的平滑在线组合优化问题,提出一种在线算法在规划窗口和开关代价之间实现平衡,通过对合成在线分布流问题进行实证,证明在累积规避中取得了显着的改进。
Apr, 2022
研究了具有随机协变量的非参数多臂赌博问题,考虑在不知道收益函数平滑度的情况下如何适应算法,并且提出了一种可以在决策过程中通过推断收益的平滑度以及利用现有策略的结构来实现平滑度自适应表现的算法,该算法在已知平滑度与未知平滑度的情况下都能够实现可接受的后悔率。
Oct, 2019