高效牛顿迭代算法实现无投影在线凸优化
本文提出了两种有效的投影不等式在线方法 ORGFW 和 MORGFW 来解决随机和对抗性在线凸优化问题,并采用递归梯度估计器达到了优秀的后悔度边界(至多对数因子),同时具有低的每次迭代计算成本。实验结果表明,在效率方面,与现有技术相比,所提出的方法更加高效。
Oct, 2019
该论文提出了一种新颖的元 Frank-Wolfe 算法及其简化版 One-Shot-Frank-Wolfe,用于对在线优化进行全局和子模最优解的快速求解。其方法基于梯度下降实现,通过随机梯度估算和孪生逼近算法来降低收敛难度。
Feb, 2018
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
研究了在线学习问题中的限制,提出了基于 Follow-the-Perturbed-Leader 的投影法之外的高效项目方法,其保证了平滑成本函数和每个迭代中一个线性优化计算的一般在线凸优化中的 $T ^ {2/3}$ 后悔界。
Jan, 2020
通过黑匣子减少,我们使用简化域上定义的替代损失函数,构建了一种只需要进行一次投影的通用 OCO 算法,对于一轮在线问题,我们维护每种类型函数的一组专家,并通过元算法聚合他们的预测。我们的方法的关键在于针对强凸函数设计的专家损失函数,并通过创新地将遗憾分解为元遗憾和专家遗憾,从而对替代损失函数的遗憾和原损失函数的遗憾之间的差异进行了严格的研究,并在强凸性条件下仔细控制了元遗憾。通过这种方式,我们建立了一轮中的通用凸函数、指数凹函数和强凸函数的最优遗憾上界,并通过增强专家损失函数来利用光滑性质,从而证明了我们的算法可以达到多种类型的凸函数和光滑函数的小损失遗憾。
May, 2024
本文提出一种基于条件梯度法的 projection-free 的算法,通过线性优化预测每一轮的动作并达到了 $O (T^{3/4})$ 的预期最小化损失 (expected regret)。
Oct, 2019
本研究中,我们在边缘学习方面进行了调查,探讨了在线凸优化问题下的对抗性延迟反馈,提出了两种无投影算法,用于集中式和分布式环境中,通过与现有方法在真实世界问题上的比较,我们理论上和实验证明了算法的性能,实现了延迟环境中 OCO 问题的 O (√B) 的后悔界。
Feb, 2024