Regret and competitive ratio are two widely used performance measures for online algorithms, and have inspired practical algorithms with qualitatively different characters - the former espouses near-competitiveness against a restricted policy class; the latter aspires to a more forgiving multiplicatively suboptimal guarantee, but against the stronger baseline of an (unrestricted) offline-optimal policy. In typical settings, good performance in one of these dimensions happens at the exclusion of the other. For the problem of online (nonstochastic) control where a linear system is subject to arbitrary perturbations, we show how these two objectives may be achieved simultaneously by a computationally efficient algorithm. Underlying this result is a striking structural fact that any (appropriately qualified) low-regret learner attains a near-optimal competitive ratio. The talk discusses further implications of this result.

Karan Singh is an Assistant Professor of Operations Research in the Tepper School of Business at Carnegie Mellon University. Drawing from the toolkits of optimization and learning theory, his research addresses algorithmic challenges in feedback-driven interactive learning, spanning both prediction and control. He completed his PhD in Computer Science at Princeton University, where he was awarded the Porter Ogden Jacobus Fellowship. Before joining CMU, he spent an year at Microsoft Research in Redmond as a postdoctoral researcher.

Personal webpage