[YPNG] YPNG for Friday 17 April 2015
sekhar.tatikonda at yale.edu
Tue Apr 14 19:46:58 EDT 2015
This Friday Patrick Rebeschini will talk about:
On the role of the Hessian of submodular functions.
Submodular functions are set functions characterized by the property
difference in the value of the function when an element is added to a
so-called marginal gain, decreases as the cardinality of the set
the role of submodularity is well-understood in the domain of
has yet to be established in the realm of probability. In this work we
problem of probabilistic inference for log-submodular point processes.
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
it is possible to design fast mixing Markov Chain Monte Carlo estimators
distributions with dimension-free error bounds.
The condition for fast mixing that we derive is equivalent to a
control on the L-infinity norm of the (discrete) Hessian of submodular
the best of our knowledge, our results are the first to emphasize the
the Hessian of submodular functions, which has not been previously
in the optimization domain. (Joint work with Amin Karbasi)
See you Friday at 11am in the Stat's classroom.
More information about the YPNG