Abstract: We propose the ChaCha (Champion-Challengers) algorithm for making an online
choice of hyperparameters in online learning settings. ChaCha handles the
process of determining a champion and scheduling a set of `live' challengers
over time based on sample complexity bounds. It is guaranteed to have sublinear
regret after the optimal configuration is added into consideration by an
application-dependent oracle based on the champions. Empirically, we show that
ChaCha provides good performance across a wide array of datasets when
optimizing over featurization and hyperparameter decisions.