Online Linear Optimization via Smoothing
arXiv:1405.6076
Abstract
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.
COLT 2014
References in corpus (4)
Cited by in corpus (14)
- Online Learning: A Modern Introduction Using Convex Optimization
- An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
- Second-order Quantile Methods for Experts and Combinatorial Games
- Fighting Bandits with a New Kind of Smoothness
- First-order regret bounds for combinatorial semi-bandits
- Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits
- On the Equivalence between Online and Private Learnability beyond Binary Classification
- Efficient Projection-Free Online Convex Optimization with Membership Oracle
- On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
- Some performance considerations when using multi-armed bandit algorithms in the presence of missing data
- Randomized Exploration for Non-Stationary Stochastic Linear Bandits
- Fundamental Limits of Online Network-Caching
- Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
- LeadCache: Regret-Optimal Caching in Networks