BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CREST - ECPv4.9.9//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CREST
X-ORIGINAL-URL:http://crest.science
X-WR-CALDESC:Events for CREST
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20190331T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20191027T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20190923T140000
DTEND;TZID=Europe/Paris:20190923T151500
DTSTAMP:20191018T114425
CREATED:20190909T125631Z
LAST-MODIFIED:20190909T125631Z
UID:10068-1569247200-1569251700@crest.science
SUMMARY:Matthieu LERASLE (ENSAE) - "Pair Matching as a tricky bandit problem"
DESCRIPTION:\nThe Statistical Seminar: Every Monday at 2:00 pm. \nTime: 2:00 pm – 3:15 pm\nDate: 23th of September 2019\nPlace: Room 3001. \nMatthieu LERASLE (ENSAE) – “Pair Matching as a tricky bandit problem“ \nAbstract: \nThe pair-matching problem appears in many applications where one wants to discover good matches between pairs of individuals. \nThe set of individuals is represented by the nodes of a graph where the edges\, unobserved at first\, represents the good matches. \nA pair matching algorithm queries sequentially pairs of nodes and observes the presence/absence of edges. \nIts goal is to discover as many edges as possible with a fixed budget of queries. \nPair-matching is a particular instance of multi-armed bandit problem in which the arms are pairs of individuals and the rewards are edges linking these pairs. \nThis bandit problem is non- standard since each arm can only be played once. \nGiven this last constraint\, sublinear regret can be expected only if the graph presents some underlying structure. \nIn the talk\, I will show that sublinear regret is achievable in the case where the graph is generated according to a stochastic block model with two communities. \nOptimal regret bounds are computed for this pair-matching problem. \nThey exhibit a phase transition related to the Kesten-Stigund threshold for community detection in the stochastic block model. \nTo limit the concentration of queried pairs\, the pair-matching problem is also considered in the case where each node is constrained to be sampled less than a given amount of times. \nI will show how this constraint deteriorates optimal regret rates. \nThis talk is based on the submitted paper arXiv:1905.07342. \nOrganizers:\nCristina BUTUCEA\, Alexandre TSYBAKOV\, Julie JOSSE\, Eric MOULINES\, Mathieu ROSENBAUM \nSponsors:\nCREST-CMAP \n \n\n
URL:http://crest.science/event/matthieu-lerasle
CATEGORIES:Statistics
ATTACH;FMTTYPE=:
END:VEVENT
END:VCALENDAR