BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Monday Seminar : Stochastic belief propagation: Low-complexity 
 message-passing with rigorous guarantees
DTSTART:20111213T161500
DTSTAMP:20260916T054217Z
UID:3f6c694c70b60bf5817f21603b9c230331b46ce8530f3f428ce5bd37
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Martin Wainwright\, UC Berkeley\, USA - Invited by Prof.
  Rüdiger Urbanke\nAbstract Graphical models play an important role in man
 y areas\, including statistical signal processing\, coding and communicati
 on theory\, computer vision\, and sensor networks.  The sum-product or be
 lief propagation (BP) algorithm is a widely-used message-passing technique
  for computing marginal distributions in such models.  When applied to a 
 graphical model with pairwise interactions\, the complexity of the BP upda
 te scales quadratically in the state dimension d\, and requires transmissi
 on of a (d-1)-dimensional vector of real numbers (messages) to its neighbo
 rs. Since various applications involve very large state dimensions\, such 
 computation and communication complexities can be prohibitively complex. W
 e propose a low-complexity variant of belief propagation\, referred to as 
 stochastic belief propagation (SBP)\, based on adaptive randomization.  T
 he SBP updates reduce the computational complexity (per iteration) from qu
 adratic to linear in $d$\, without assuming any particular structure of th
 e potentials\, and also reduce the communication complexity significantly\
 , requiring only $log d$ bits per edge. We establish a number of theoretic
 al guarantees for the performance of SBP\, showing almost sure convergence
  to the exact BP fixed point for any tree-structured graph\, and for any g
 raphical model with cycles satisfying a contractivity condition\, as well 
 as non-asymptotic guarantees on the convergence rate that are inverse-poly
 nomial in iteration number. Based on joint work with Nima Noorshams. Arxiv
  preprint: http://arxiv.org/abs/1111.1020 Biography
LOCATION:INR 219
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR