Fastest Identification in Linear Systems, Joint work with Yassir Jedra

Abstract:  We report recent results on two classical inference problems in linear systems. (i) In the first problem, we wish to identify the dynamics of a canonical linear time-invariant systems $x_{t+1}=Ax_t+\eta_{t+1}$ from an observed trajectory. We provide system-specific sample complexity lower bound satisfied by any $(\epsilon, \delta)$-PAC algorithm, i.e., yielding an estimation error less than $\epsilon$ with probability at least $1-\delta$. We further establish that the Ordinary Least Squares estimator achieves this fundamental limit. (ii) In the second inference problem, we aim at identifying the best arm in bandit optimization with linear rewards. We derive instance-specific sample complexity lower bounds for any $\delta$-PAC algorithm, and devise a simple track-and-stop algorithm achieving this lower bound. In both inference problems, the analysis relies on novel concentration results for the spectrum of the covariates matrix.

Speaker Bio: Alexandre Proutiere has been a professor in the Decision and Control System division at KTH, Stockholm Sweden since 2011. Before joining KTH he was a researcher at Microsoft Research (Cambridge) from 2007 to 2011, research engineer at France Telecom R&D from 2000 to 2006, Invited lecturer and researcher at the computer science department ENS Paris from 2004 to 2006. He received a PhD in Applied Mathematics from Ecole Polytechnique, graduated in Mathematiques from Ecole Normale Superieure. He also received an engineering degree from Telecom Paris, and is an engineer from Corps des Mines. He won the ACM Sigmetrics rising star award in 2009, ACM best papers awards at Sigmetrics 2004 and 2010, and Mobihoc 2009. His research interests are in probability and their applications, and more specifically today in learning in dynamical systems.

Join Zoom Meeting https://umich.zoom.us/j/97598571292

Meeting ID: 975 9857 1292

Passcode: XXXXXX (Will be sent via email to attendees)