December 5, 2019 –

News
 DATAMOVE/POLARIS BBQ 2019 2019/06/14
 POLARIS Bootcamp (May 2019) 2019/05/24
 slides of Andras Gyorgy 2016/01/15
 kickoff meeting on Feb. 11 2016/01/13
Next seminars
 2:00 pm – 3:00 pm, November 21, 2019 – vivien Quema
 2:00 pm – 3:00 pm, December 5, 2019 – Compression of scientific Data, by Franck Cappello
 2:00 pm – 4:00 pm, December 12, 2019 – Soutenance de These de Stephan Plassart
Events
November 2019 MMonday TTuesday WWednesday TThursday FFriday SSaturday SSunday 28October 28, 2019 29October 29, 2019 30October 30, 2019 31October 31, 2019 1November 1, 2019 2November 2, 2019 3November 3, 2019 4November 4, 2019 5November 5, 2019 6November 6, 2019 7November 7, 2019 8November 8, 2019 9November 9, 2019 10November 10, 2019 11November 11, 2019 12November 12, 2019 13November 13, 2019 14November 14, 2019 Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution by Paul Duetting (Google, switzerland)
Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution by Paul Duetting (Google, switzerland)November 14, 2019 –
Bâtiment IMAG (406)SaintMartind'Hères, 38400France(ACM EC 2019 Best Full Paper Award)
A central object in optimal stopping theory is the singlechoice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1,..., Xn drawn independently from a distribution F, the goal is to choose a stopping time τ so as to maximize α such that for all distributions F we have E[Xτ] ≥ α · E[maxt Xt]. What makes this problem challenging is that the decision whether τ = t may only depend on the values of the random variables X1,..., Xt and on the distribution F. For a long time the best known bound for the problem had been α ≥ 1 − 1/e ≈ 0.632, but quite recently a tight bound of α ≈ 0.745 was obtained. The case where F is unknown, such that the decision whether τ = t may depend only on the values of the random variables X1,..., Xt, is equally well motivated but has received much less attention. A straightforward guarantee for this case of α ≥ 1/e ≈ 0.368 can be derived from the solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F , and show that even with o(n) samples α ≤ 1/e. On the other hand, n samples allow for a significant improvement, while O(n2) samples are equivalent to knowledge of the distribution: specifically, with n samples α ≥ 1 − 1/e ≈ 0.632 and α ≤ ln(2) ≈ 0.693, and with O(n2) samples α ≥ 0.745 − ϵ for any ϵ > 0.
Joint work with Jose Correa (Universidad de Chile), Felix Fischer (Queen Mary), and Kevin Schewior (ENS Paris)
15November 15, 2019 16November 16, 2019 17November 17, 2019 18November 18, 2019 19November 19, 2019 20November 20, 2019 21November 21, 2019 vivien Quema
vivien QuemaNovember 21, 2019 –
TBA
22November 22, 2019 23November 23, 2019 24November 24, 2019 25November 25, 2019 26November 26, 2019 27November 27, 2019 28November 28, 2019 29November 29, 2019 30November 30, 2019 1December 1, 2019 Meta