Online Non-Convex Learning: Following the Perturbed Leader Is Optimal
Abstract
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”.
Cite
Text
Suggala and Netrapalli. "Online Non-Convex Learning: Following the Perturbed Leader Is Optimal." Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.Markdown
[Suggala and Netrapalli. "Online Non-Convex Learning: Following the Perturbed Leader Is Optimal." Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.](https://mlanthology.org/alt/2020/suggala2020alt-online/)BibTeX
@inproceedings{suggala2020alt-online,
title = {{Online Non-Convex Learning: Following the Perturbed Leader Is Optimal}},
author = {Suggala, Arun Sai and Netrapalli, Praneeth},
booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory},
year = {2020},
pages = {845-861},
volume = {117},
url = {https://mlanthology.org/alt/2020/suggala2020alt-online/}
}