Metadata only
Date
2018Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Modern stochastic optimization methods often rely on uniform sampling which is agnostic to the underlying characteristics of the data. This might degrade the convergence by yielding estimates that suffer from a high variance. A possible remedy is to employ non-uniform importance sampling techniques, which take the structure of the dataset into account. In this work, we investigate a recently proposed setting which poses variance reduction as an online optimization problem with bandit feedback. We devise a novel and efficient algorithm for this setting that finds a sequence of importance sampling distributions competitive with the best fixed distribution in hindsight, the first result of this kind. While we present our method for sampling data points, it naturally extends to selecting coordinates or even blocks of thereof. Empirical validations underline the benefits of our method in several settings. Show more
Publication status
publishedExternal links
Book title
Proceedings of the 31st Conference On Learning Theory (COLT 2018)Journal / series
Proceedings of Machine Learning ResearchVolume
Pages / Article No.
Publisher
PMLREvent
Subject
importance sampling; variance reduction; bandit feedback; empirical risk minimizationOrganisational unit
03908 - Krause, Andreas / Krause, Andreas
Funding
167212 - Scaling Up by Scaling Down: Big ML via Small Coresets (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics