BriefGPT - AI 论文速递
·
利用可行集的曲率在在线凸优化中获得快速速率
💡
原文中文，约400字，阅读约需1分钟。
📝
内容提要
本文介绍了在线多梯度下降算法（OMGD）在有限信息环境中的应用，解决了带有二次和线性切换成本的问题。研究证明OMGD算法在二次切换成本问题中具有竞争比为至多4(L+5)+(16(L+5))/μ。对于有界信息环境中的在线算法，其竞争比的上界和下界分别为max{Ω(L), Ω(L/√μ)}。OMGD算法实现了有限信息环境下的动态最优遗憾，并且对于线性切换成本，其竞争比的上界取决于问题实例的路径长度、平方路径长度以及L、μ，并且被证明是任何在线算法能够达到的最佳竞争比。因此，在有限信息环境中，二次和线性切换成本的最优竞争比基本上是不同的。
🎯
关键要点
- 本文讨论了在线多梯度下降算法（OMGD）在有限信息环境中的应用。
- OMGD算法解决了带有二次和线性切换成本的问题。
- 研究证明OMGD算法在二次切换成本问题中的竞争比为至多4(L+5)+(16(L+5))/μ。
- 对于有界信息环境中的在线算法，其竞争比的上界和下界分别为max{Ω(L), Ω(L/√μ)}。
- OMGD算法实现了有限信息环境下的动态最优遗憾。
- 对于线性切换成本，OMGD算法的竞争比上界取决于路径长度、平方路径长度以及L、μ。
- OMGD算法的竞争比被证明是任何在线算法能够达到的最佳竞争比。
- 在有限信息环境中，二次和线性切换成本的最优竞争比基本上是不同的。
➡️
