UCSB CS Theory Colloquium Series
Fall 2021
|
Friday, November 19, 2pm, Phelps 2510 2pm: Dheeraj Baby (UC Santa Barbara) Title: Optimal Dynamic Regret in Exp-Concave Online Learning Abstract: We consider the problem of dynamic regret minimization in non-stationary online learning, where we aim to design an online learner whose performance is closely comparable to that of a sequence of time varying (and potentially optimal) decisions in hindsight. We show that under a broad family of exp-concave (or strongly convex) losses, a Strongly Adaptive online learner achieves the optimal dynamic regret rate. Moreover, this rate is attained without any prior knowledge of the degree of non-stationarity in the environment. Our new proof techniques make elegant use of the intricate structures of the primal and dual variables imposed by the KKT conditions and could be of independent interest. Finally, we apply our results to the classical statistical problem of locally adaptive non-parametric regression and obtain a stronger and more flexible algorithm that does not require any statistical assumptions or any hyperparameter tuning. 3:15pm: Alex Meiburg (UC Santa Barbara) Title: Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography Abstract: Quantum State Tomography is the task of estimating a quantum state, given many measurements in different bases. We discuss a few variants of what exactly “estimating a quantum state” means, including maximum likelihood estimation and computing a Bayesian average. We show that, when the measurements are fixed, this problem is NP-Hard to approximate within any constant factor. In the process, we find that it reduces to the problem of approximately computing the permanent of a Hermitian positive semidefinite (HPSD) matrix. This implies that HPSD permanents are also NP-Hard to approximate, resolving a standing question with applications in quantum information and BosonSampling. |