Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
summary
Generalizes multi-armed bandits to convex optimization over the simplex with bandit feedback and proposes Upper-Confidence Frank-Wolfe: maintain per-coordinate confidence intervals, form an optimistic gradient, pick the coordinate minimizing that optimistic gradient, and perform a Frank–Wolfe step. Proves a generic O(1/√T) statistical rate that matches known linear (UCB) lower bounds up to logs, obtains 1/T fast rates under either corner gap conditions or strong convexity with an interior minimizer, and proves instance-dependent lower bounds showing adverse dependence on K.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 4:12Supermarket Example
- 5:51Optimal Strategy
- 6:22Other Applications
- 8:07Motivation
- 9:23Comparison Review
- 10:49FrankWolfe
- 14:56UpperConfidence
- 17:19Proof Elements
- 21:39Quadratic Term
- 22:33Fast Rates
- 24:08Summary
- 24:47Lower Bounds
- 27:08Conclusion
related talks
59mKernel-Based Methods for Bandit Convex Optimization
01h 01mStochastic Bandits: Foundations and Current Perspectives
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
01h 09mStochastic Bandits: Foundations and Current Perspectives
01h 21mAdversarial Bandits: Theory and Algorithms
29mPure Exploration Problems
27mOn the Complexity of Best Arm Identification in Multi-Armed Bandit Models
27mTalk by Ali Kavis (UT Austin)