0.25
0.5
0.75
1.25
1.5
1.75
2
A message-passing approach to stochastic optimization and inverse dynamical problems
Published on Oct 16, 20123233 Views
We will discuss how statistical physics techniques developed for the study of stochastic optimization problems can be used to design efficient algorithms for analyzing, controlling and activating ex
Related categories
Chapter list
A message-passing approach to stochastic optimization and inverse dynamical problems00:00
Two problems00:59
Motivation02:19
Plan of the talk02:45
We start with a simple to state problem (but hard to solve)03:13
A is sparse and random, τ = (0, 0, ..., 0, 0)03:57
Upper bound by first moment - 105:35
Upper bound by first moment - 205:37
Lower bound by weighted second moment - 106:07
Lower bound by weighted second moment - 206:08
Statistical physics of random CSP in brief06:43
Structure of solution-space07:52
Cavity method & Loopy Belief Propagation equations08:26
Exact if correlation decay holds09:03
Multiple clusters of optimal configurations09:57
Networks of constraints11:27
Some problems left open11:49
MP methods can be extremely effective for approximate SAMPLING and COUNTING12:35
Letʼs now consider an ensemble of CSP with random components13:45
Can be used to compute statistics over minima of a given random function15:13
A cavity / mean-field approach15:35
Stochastic optimization: General Problem16:02
More precisely17:09
Notable cases18:46
How would you solve the problem with MC?19:56
Our approach for two-stage problems20:24
Two-stage problem - 122:32
Two-stage problem - 223:48
Two-stage problem - 324:19
Two-stage problem - 424:42
Two-stage problem - 525:42
Two-stage problem - 626:05
Limitations of LP26:41
Multi-level optimization27:48
The average price of Anarchy28:34
Inverse deterministic dynamics for irreversible processes28:58
Activating extreme trajectories - 130:00
Activating extreme trajectories - 230:09
Deterministic dynamics in graphs30:37
Direct and Inverse problems31:03
Spread Problems32:08
An irreversible process33:33
Local Constraints34:19
Related problems34:46
The model35:23
Dual factor graph36:27
BP Equations37:21
Computable equations for K,Θ, T >> 137:41
MS Equations37:51
Directed times, two level optimization37:53
Some results for random regular graphs39:14
Activation transitions39:28
Rare trajectories40:20
Other methods41:09
Applications41:24
Epinions - 142:37
Epinions - 243:44
Stohastic model45:39
Blocking activation processes46:39