Estimation, Optimization, and Parallelism when Data is Sparse
Venue
Advances in Neural Information Processing Systems (NIPS) (2013)
Publication Year
2013
Authors
John C. Duchi, Michael I. Jordan, H. Brendan McMahan
BibTeX
Abstract
We study stochastic optimization problems when the \emph{data} is sparse, which is
in a sense dual to current perspectives on high-dimensional statistical learning
and optimization. We highlight both the difficulties---in terms of increased sample
complexity that sparse data necessitates---and the potential benefits, in terms of
allowing parallelism and asynchrony in the design of algorithms. Concretely, we
derive matching upper and lower bounds on the minimax rate for optimization and
learning with sparse data, and we exhibit algorithms achieving these rates. We also
show how leveraging sparsity leads to (still minimax optimal) parallel and
asynchronous algorithms, providing experimental evidence complementing our
theoretical results on several medium to large-scale learning tasks.
