Google Research

Consistent Online Optimization: Convex and Submodular

aistats (2019)


Modern online learning algorithms achieve low (sublinear) regret in a variety of diverse settings. These algorithms, however, update their solution at every time step. While, these updates are computationally efficient, the very requirement of frequent updates makes the algorithms untenable in some practical applications. In this work we look for online learning algorithms that update a sublinear number of times. We give a meta algorithm based on non-homogeneous Poisson Processes that gives a smooth trade- off between final regret and frequency of updates. Empirically, we show that in many cases we can significantly reduce the number at a minimal increase in regret.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work