Sign inSign up
Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions thumbnail
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions

Published on Aug 20, 20151904 Views

Tengyuan Liang

We consider the problem of optimizing an approximately convex function over a bounded convex set in $\mathbb{R}^n$ using only function evaluations. The problem is reduced to sampling from an \emph{app

COLT 2015 - Paris

Related categories

Active LearningComputational Learning TheoryOn-line LearningReinforcement LearningSemi-supervised Learning

Chapter list

Escaping the Local Minima via Simulated Anncaling: Optimization of Approximately Convex Functions00:00
Untitled00:28
Why?01:53
What stochastic optimization approaches are available?02:50
Approach 103:23
Approach 203:40
Approach 304:55
Our Approach06:02
Noisy oracle to approximately convex oracle06:06
More general problem: approximately convex oracles06:47
Convex function f07:53
Oracle complexity09:14
Simulated annealing10:26
Reshaping/Rounding11:54
Hit-and-run12:20
Sample 1-dim nearly log-concave measure - 112:55
Sample 1-dim nearly log-concave measure - 213:10
Sample 1-dim nearly log-concave measure - 313:13
Sample 1-dim nearly log-concave measure - 413:35
Sample 1-dim nearly log-concave measure - 513:49
Lemma13:59
Evolution of distributions14:15
Lower bound on conductance15:02
Fast mixing15:35
Oracle complexity15:59
Escaping the local minima - 116:01
Escaping the local minima - 216:06
Escaping the local minima - 316:21
Escaping the local minima - 416:23
Escaping the local minima - 516:30
Better query complexitiy under additional assumptions16:41
Thanks16:54