Improved Regret Guarantees for Online Smooth Convex Optimization with Bandit Feedback

Published on 2011-05-063733 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