Online Linear Optimization via Smoothing
This work provides a theoretical foundation for analyzing regularization in online optimization algorithms, which is incremental but offers improved bounds for researchers in optimization and machine learning.
The paper tackles the analysis of Follow-the-Leader style algorithms in online linear optimization by showing that adding strongly convex penalties or stochastic perturbations corresponds to deterministic and stochastic smoothing, establishing an equivalence between Follow the Regularized Leader and Follow the Perturbed Leader. This leads to a new analysis framework that recovers and improves previous regret bounds for Follow the Perturbed Leader algorithms.
We present a new optimization-theoretic approach to analyzing Follow-the-Leader style algorithms, particularly in the setting where perturbations are used as a tool for regularization. We show that adding a strongly convex penalty function to the decision rule and adding stochastic perturbations to data correspond to deterministic and stochastic smoothing operations, respectively. We establish an equivalence between "Follow the Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness properties. This intuition leads to a new generic analysis framework that recovers and improves the previous known regret bounds of the class of algorithms commonly known as Follow the Perturbed Leader.