BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CREST - ECPv5.1.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CREST
X-ORIGINAL-URL:https://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:20220518T105528
CREATED:20190909T145631Z
LAST-MODIFIED:20190909T145631Z
UID:12319-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:https://crest.science/event/matthieu-lerasle/
CATEGORIES:Statistics
ATTACH;FMTTYPE=:
END:VEVENT
END:VCALENDAR