无约束在线凸优化的无悔算法
本文提出了解决约束在线凸优化问题的框架。通过将问题转化为在线凸 - 凹优化问题,提出了一种有效的算法,可以实现收敛性较好的结果。同时,本文还为从中提取多点强化信号的约束在线凸优化问题提供了解决方案。
Nov, 2011
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
我们提出了一种在线凸优化算法 (RescaledExp),该算法在无约束设置下实现了最优的后悔,并没有先验知识任何损失函数的界限。我们证明了一个下界,说明现有算法在损失函数需要已知界限的情况下与不需要这种知识的任何算法之间存在指数分离。RescaledExp 在迭代次数方面与这个下界是一致的。RescaledExp 自然无超参数,并且我们通过实验证明它可以匹配需要超参数优化的之前的优化算法。
Mar, 2017
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
本文研究了无约束在线线性优化博弈中最小化后悔的算法,其中对于一个有界比较器集合,得到了该博弈的解及其渐进行为,同时针对更宽松的惩罚函数提出了相应的算法并得到了渐进解。
Feb, 2013
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界,优于 Mahdavi 等(2012 年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015
我们设计了一种在线线性优化算法,其具有最佳的遗憾度,并且不需要知道损失向量范数的上界或下界。通过尺度不变性,我们实现了对损失向量范数的适应性,即使损失向量序列乘以任意正常数,我们的算法仍会做出完全相同的决策。我们的算法适用于任何有界或无界决策集。对于无界决策集,这是第一个真正自适应的在线线性优化算法。
Feb, 2015
本文提出了一种新的在线凸优化算法,该算法根据迄今为止观察到的损失函数自适应地选择其正则化函数,其遗憾界是最坏情况下最优的,并且对于某些实际损失函数类别,它们比现有界限好得多。此算法不需要事先了解问题实例的结构,但提供了一定程度的竞争保证,并在范围内提供了一定程度的界限。
Feb, 2010
本文提出了一种新的在线学习模式,可以处理无界域和非 Lipschitz 损失的问题,并开发了新的基于套索的在线学习算法,同时利用此算法开发了新的鞍点优化算法,在无界域中实现对偶间隙的收敛;最终提供了第一个实现非 Lipschitz 损失下的动态遗憾度的算法,以及匹配的下界。
Jun, 2023