BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Cambridge Algorithms talks
SUMMARY:A Near-Optimal Adaptive Algorithm for Estimating B
inary Mixtures of Unknown Coins - Jasper Lee (Brow
n University)
DTSTART;TZID=Europe/London:20200116T110000
DTEND;TZID=Europe/London:20200116T120000
UID:TALK137749AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/137749
DESCRIPTION:Given a mixture between two populations of coins:
"positive" coins that have (unknown and potentiall
y different) probabilities of heads at least 1/2+Δ
and "negative" coins with probabilities at most 1
/2-Δ\, we consider the task of estimating the frac
tion ρ of coins of each type to within additive er
ror ε\, with a constant probability of success.\n\
nIn this talk\, we will focus on the construction
of an algorithm with sample complexity O((ρ/ε²Δ²)(
1+ρ log 1/ε))\, which matches the fully-adaptive l
ower bound of Ω(ρ/ε²Δ²) shown in our paper\, excep
t for the regime where ρ = ω(1/log 1/ε).\n\nThe fi
ne-grained adaptive flavour of both our algorithm
and lower bound contrasts with much previous work
in distributional testing and learning.\n\nJoint w
ork with Paul Valiant\, available on arXiv at http
s://arxiv.org/abs/1904.09228
LOCATION:Computer Laboratory\, Room FW09
CONTACT:Dr Thomas Sauerwald
END:VEVENT
END:VCALENDAR