[YPNG] YPNG for Friday 17 April 2015

[Sekhar Tatikonda]

Hi Everyone,

This Friday Patrick Rebeschini will talk about:

Title:
On the role of the Hessian of submodular functions.

Abstract:
Submodular functions are set functions characterized by the property 
that the
difference in the value of the function when an element is added to a 
set, the
so-called marginal gain, decreases as the cardinality of the set 
increases. While
the role of submodularity is well-understood in the domain of 
optimization, it
has yet to be established in the realm of probability. In this work we 
address the
problem of probabilistic inference for log-submodular point processes. 
We show
that if the difference of marginal gains evaluated at sets differing 
only by a single
element j decreases fast enough as a function of the element i being 
added, then
it is possible to design fast mixing Markov Chain Monte Carlo estimators 
of marginal
distributions with dimension-free error bounds.

The condition for fast mixing that we derive is equivalent to a 
dimension-free uniform
control on the L-infinity norm of the (discrete) Hessian of submodular 
functions. To
the best of our knowledge, our results are the first to emphasize the 
importance of
the Hessian of submodular functions, which has not been previously 
considered even
in the optimization domain. (Joint work with Amin Karbasi)

See you Friday at 11am in the Stat's classroom.

Regards,
sekhar