BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Multiparametric Boltzmann tuning: on the crossroad of probability
and convex optimisation
DTSTART;VALUE=DATE-TIME:20211013T083000Z
DTEND;VALUE=DATE-TIME:20211013T093000Z
DTSTAMP;VALUE=DATE-TIME:20220813T114331Z
UID:indico-event-7011@indico.math.cnrs.fr
DESCRIPTION:Suppose that you want to randomly sample a complicated item\nf
rom a probability space\, defined by a context-free grammar with given\nfi
xed proportions of terminal letters. This problem is doable if the\nnumber
of letters is small\, but turns out to be #P-complete when the\nnumber of
letters is unbounded (this is harder than NP-hard in the\ncurrent hierarc
hy). In fact\, both enumeration and sampling problems\nare computationally
intractable in such a setting. However\, by\nslightly deforming the targe
t probability distribution to the\nso-called multiparametric Boltzmann dis
tribution\, you may get much\nfaster sampling algorithms\, provided that t
here is a tuning oracle for\nfinding the good target weights. In this talk
\, I will guide you\nthrough the concept of multiparametric Boltzmann samp
lers and will\nshow how we constructed a tuning oracle having a polynomial
time-space\ncomplexity using a convex optimisation procedure. If time per
mits\, we\nshall also discuss\n* the complexity of the exact-sampling algo
rithm by reduction to #2-sat\n* the notion of self-concordant barriers lea
ding to a fine complexity\nestimate of the tuning procedure\n* numerous ap
plications of Boltzmann samplers in combinatorics and beyond\n* the link b
etween Boltzmann tuning and maximum likelihood estimation\n* the software
package "Paganini" implementing our tuning concept.\n\nThis is a joint wor
k with Maciej Bendkowski and Olivier Bodini\,\naccepted to publication in
CPC in April 2021\n\nThe preprint is available at: https://arxiv.org/abs/2
002.12771\nOur software is on github: https://github.com/maciej-bendkowski
/paganini\nTutorial: https://paganini.readthedocs.io/en/latest/tutorial.ht
ml\n \n\nhttps://indico.math.cnrs.fr/event/7011/
LOCATION:IMB René Baire
URL:https://indico.math.cnrs.fr/event/7011/
END:VEVENT
END:VCALENDAR