Speaker: Yu-Xiang Wang

Abstract: I will talk about the problem of “sequential adaptive estimation”, where we want to come up with estimators that can accurately estimate a sequence of sequentially chosen parameters. This is related to the problem of Adaptive Data Analysis by Dwork et. al., 2015 (appeared in FOCS’14, NIPS’15 and then a Science article), but differs in that we consider the Gaussian sequence model that is more relevant to statistical literature. I will talk about upper bound through a simple mutual information argument due to Russo and Zou (AISTATS’16), highlighting the difficulties in generalizing beyond joint-Gaussianity; and talk about a matching lower bound that Jing, Steve and I worked out. I will try to go over the high level arguments of the rather challenging proof, and mention a few open problems. Lastly, I will highlight a surprising connection to “linear bandits”, which has been studied extensively over the past few years and discuss the intriguing implication of the interplay between the two fields.

References: - Dwork et. al. : FOCS, https://arxiv.org/abs/1411.2664, NIPS https://papers.nips.cc/paper/5993-generalization-in-adaptive-data-analysis-and-holdout-reuse.pdf - Russo and Zou paper: http://proceedings.mlr.press/v51/russo16.html - Hugely out-dated version our paper: https://arxiv.org/abs/1602.04287. The more recent reference is Chapter 10 of my thesis: https://www.dropbox.com/s/v4t7nf9ytqlu1hv/yuxiang-thesis-draft.pdf?dl=0, and the connection to bandits are partially written down on Page 293 onwards. - Stochastic linear bandits: http://banditalgs.com/2016/10/19/stochastic-linear-bandits/) - Adversarial linear bandits: http://banditalgs.com/2016/11/25/adversarial-linear-bandits-and-the-curious-case-of-the-unit-ball/