Kernel-Based Methods for Bandit Convex Optimization
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Proposes a concrete bandit algorithm that replaces one-point gradient estimates with a kernel-based unbiased estimator built from a time-varying kernel (the core of a small Gaussian inside the exponential-weights distribution), proves variance control via convex domination and generalized Bernoulli-convolution constructions, and manages adversarial shifts by selective restarts and increasing learning rates. Claims an efficient (polynomial-time) procedure with regret roughly N^{9.5} sqrt(T), conjectures the optimal is N^{3/2} sqrt(T).
AI-written summary · about
chapters (9)
- 0:00Start
- 1:11Bandit Convex Optimization
- 7:50The Lemma for Exponential Weights
- 13:30One-Point Linear Regression
- 14:05The Loss Estimate
- 27:03Generalized Bernoulli Convolutions
- 28:02Generalize beyond Orac Convolution
- 29:00Natural Kernel
- 32:38The Bernoulli Convolution
related talks
30mFast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
01h 01mStochastic Bandits: Foundations and Current Perspectives
01h 21mAdversarial Bandits: Theory and Algorithms
01h 09mStochastic Bandits: Foundations and Current Perspectives
01h 18mOptimization I
22mOnline Learning and Bandits with Queried Hints
13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient Descent
57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization