Improved Regret Guarantees for Online Smooth Convex Optimization with Bandit Feedback

Published on Feb 4, 20253733 Views

Ankan Saha

The study of online convex optimization in the bandit setting was initiated by Kleinberg (2004) and Flaxman et al. (2005). Such a setting models a decision maker that has to make decisions in the

AISTATS 2011 - Ft. Lauderdale

Related categories

Presentation

Improved Regret Guarantees for OCO in Bandit Setting00:00

Introduction and Motivation00:09

Setting (1)00:14

Setting (2)00:19

Setting (3)00:24

Setting (4)00:34

Setting (5)01:01

Goal01:24

Full information Setting01:47

Projected gradient descent strategy02:09

Zinkevich's Algorithm (1)03:00

Zinkevich's Algorithm (2)03:14

Bandit Online Optimization (1)03:19

Bandit Online Optimization (2)03:46

Bandit Online Optimization (3)03:59

Unbiased gradient estimation (1)04:23

Unbiased gradient estimation (2)04:42

Problems with existing approach (1)05:11

Problems with existing approach (2)05:21

Problems with existing approach (3)05:23

Problems with existing approach (4)05:56

Convex Analysis Basics (1)06:10

Convex Analysis Basics (2)06:15

Convex Analysis Basics (3)06:32

Convex Analysis Basics (4)06:55

Upper approximant, Original objective07:06

Results for Subclasses of Convex functions(Full Information Setting) (1)07:22

Results for Subclasses of Convex functions(Full Information Setting) (2)07:32

Results for Subclasses of Convex functions(Full Information Setting) (3)07:52

Results for Subclasses of Convex functions(Full Information Setting) (4)08:21

Results for Bandit Setting (1)08:43

Results for Bandit Setting (2)08:46

Results for Bandit Setting (3)08:49

Results for Bandit Setting (4)08:54

New Approach (1)09:31

New Approach (2)10:31

K10:54

K, Dx (1)10:58

K, Dx (2)11:18

K, Dx (3)11:32

Combining Ideas (1)11:58

Combining Ideas (2)12:10

Combining Ideas (3)12:34

Algorithm (1)13:20

Algorithm (2)13:30

Algorithm (3)13:39

Algorithm (4)14:07

Algorithm (5)14:14

Algorithm (6)14:22

Algorithm (7)14:30

Proof Sketch14:42

Conclusions and Future Work (1)15:51

Conclusions and Future Work (2)16:01

Conclusions and Future Work (3)16:08

Conclusions and Future Work (4)16:14

Thank you16:39

References (1)16:40

References (2)16:41