Online Optimization and Learning Under Long-Term Convex Constraints and Objectives
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Presents concrete algorithms that turn long-term convex constraints and concave objectives into repeated linear goals using Fenchel conjugate linearization and an online convex optimization black box, proving O(1/√T) regret (and log T / T under smoothness with Frank–Wolfe). For online packing this yields 1−ε competitive ratio when budgets satisfy B ≥ Θ((log n)/ε^2); bandit versions use confidence ellipsoids and optimistic arm selection, need larger budgets (e.g. ~n T^{3/4}) for contextual cases, and estimate scale Z or OPT from a small sample via one LP.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:07Online Packing Problem
- 2:12Online Packing Example
- 3:08Stochastic Models
- 4:33Related Work
- 6:11Online Stochastic Convex Programming
- 9:47Online Convex Optimization
- 23:33Blackbox Algorithm
- 24:38Bandits
- 27:10Linear contextual bandits
- 28:56Beam goal
- 29:58Main idea
- 32:32Summary
related talks
44mParsimonious Learning-Augmented Algorithms
43mContextual Inverse Optimization: Offline and Online Learning
41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
30mFast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
41mCompetitive Algorithms for Online Control
01h 08mData Driven Optimization Models and Algorithms
48mA Simple Condition for Constant Regret in Online Decision-Making