Online Non-Convex Learning: Following the Perturbed Leader is Optimal
Online Non-Convex Learning: Following the Perturbed Leader is Optimal
复制标题
DOI：
--
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
A. Suggala;Praneeth Netrapalli
中科院分区：
文献类型：
--
作者：
A. Suggala;Praneeth Netrapalli
我们研究具有非凸损失的在线学习问题，其中学习者可以访问离线优化预言。我们表明，经典的跟随扰动领导者（FTPL）算法实现了最优的后悔率为O（T^{-1/2}）$在此设置。这改进了之前FTPL最著名的后悔率O（T^{-1/3}）$。我们进一步表明，乐观的FTPL变体实现更好的后悔界限时，学习者遇到的损失序列是“可预测的”。
We study the problem of online learning with non-convex losses, where the learner has access to an offline optimization oracle. We show that the classical Follow the Perturbed Leader (FTPL) algorithm achieves optimal regret rate of $O(T^{-1/2})$ in this setting. This improves upon the previous best-known regret rate of $O(T^{-1/3})$ for FTPL. We further show that an optimistic variant of FTPL achieves better regret bounds when the sequence of losses encountered by the learner is `predictable'.