BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A Near-Optimal Adaptive Algorithm for Estimating Binary Mixtures o
 f Unknown Coins - Jasper Lee (Brown University)
DTSTART:20200116T110000Z
DTEND:20200116T120000Z
UID:TALK137749@talks.cam.ac.uk
CONTACT:Dr Thomas Sauerwald
DESCRIPTION:Given a mixture between two populations of coins: "positive" c
 oins that have (unknown and potentially different) probabilities of heads 
 at least 1/2+Δ and "negative" coins with probabilities at most 1/2-Δ\, w
 e consider the task of estimating the fraction ρ of coins of each type to
  within additive error ε\, 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-adapt
 ive lower bound of Ω(ρ/ε²Δ²) shown in our paper\, except for the reg
 ime where ρ = ω(1/log 1/ε).\n\nThe fine-grained adaptive flavour of bot
 h our algorithm and lower bound contrasts with much previous work in distr
 ibutional testing and learning.\n\nJoint work with Paul Valiant\, availabl
 e on arXiv at https://arxiv.org/abs/1904.09228
LOCATION:Computer Laboratory\, Room FW09
END:VEVENT
END:VCALENDAR