Optimal Online Learning using Potential Functions
This work addresses theoretical optimization in online learning algorithms, providing incremental improvements in regret analysis for researchers in machine learning theory.
The paper tackles the problem of designing optimal strategies for online learning by analyzing potential functions, showing that Brownian motion is the min-max optimal adversary strategy under certain conditions and that the Normal-Hedge potential yields the tightest regret bounds for the top ε-percentile.
We study a family of potential functions for online learning. We show that if the potential function has strictly positive derivatives of order 1-4 then the min-max optimal strategy for the adversary is Brownian motion. Using that fact we analyze different potential functions and show that the Normal-Hedge potential provides the tightest upper bounds on the cumulative regret of the top ε-percentile.