具有未知延迟的在线顺序决策
提供了乐观镜面下降算法的几个应用:将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题;将其用于有限零和矩阵博弈中,为两个强耦合玩家提供最小化最大值均衡的渐进速率 O((log T)/T);再考虑问题的部分信息版本并将结果应用于凸规划,展示了近似最大流问题的简单算法。
Nov, 2013
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O(n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
本文介绍了在线学习的基本概念和现代在线凸优化的视角,并针对凸丢失,在欧几里得和非欧几里得环境中介绍了一阶和二阶算法。同时,还特别关注了算法参数调优和在无界域上的学习,并介绍了对非凸损失的处理方法和信息缺失的决策问题中的多臂赌博机问题。
Dec, 2019
研究在线学习中的非约束非子模最小化问题,并提出了一种基于梯度下降算法的解决方案,其中考虑了非子模函数特殊结构和成本的时滞,证明了算法在静态和延迟情况下的遗憾保证。
May, 2022
本文提出了一个新的在线凸优化框架,能够利用过去的决策历史对当前损失进行建模,并引入了“p有效内存容量”来量化过去决策对当前损失的最大影响。在此框架下,证明了一些政策遗憾的较好上界,并展示了该框架对于各种在线学习任务的适用性。
Oct, 2022
本文提出了Follow The Regularized Leader(FTRL)算法并应用于在线学习中,通过分离延迟反馈成本和赌博反馈成本,得出了在三种不同的情况下的新结果,包括组合半赌博、带延迟的对抗Markov决策过程以及带权值的线性赌博。我们的新型遗憾分解显示FTRL在正则化程序的Hessian矩阵上的温和假设下,可在多轮中保持稳定,并为线性赌徒提供了一种有效算法和接近最优的遗憾限制。
May, 2023
研究了非平稳环境下具任意延迟的在线凸优化问题,提出了一个简单的算法 DOGD,通过运用多个学习率的 DOGD,并跟踪最佳 one 的延迟性能,将动态遗憾边界降至 O(根号下d*T*(P_T+1)) 和 O(根号下S(1+P_T)),并毫无例外地证明了这是最优的。
May, 2023
本研究中,我们在边缘学习方面进行了调查,探讨了在线凸优化问题下的对抗性延迟反馈,提出了两种无投影算法,用于集中式和分布式环境中,通过与现有方法在真实世界问题上的比较,我们理论上和实验证明了算法的性能,实现了延迟环境中 OCO 问题的 O(√B) 的后悔界。
Feb, 2024
本研究分析了在线凸优化问题在不同情境下的处理方法,并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板,同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外,通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较,我们证明了可以在面对不可避免对手时,设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此,我们提出了将一阶算法转换为零阶算法,并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化,如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析,我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。
Feb, 2024
我们研究了具有延迟反馈的强凸波段优化问题,通过精细地利用延迟波段反馈的阻塞更新机制,我们的算法改进了损失边界并将其与延迟设置下的传统波段梯度下降(BGD)算法相匹配。
Feb, 2024