Greedy methods, randomization approaches and multi-arm bandit algorithms
  for efficient sparsity-constrained optimization
  Several sparsity-constrained algorithms such as Orthogonal Matching Pursuit
or the Frank-Wolfe algorithm with sparsity constraints work by iteratively
selecting a novel atom to add to the current non-zero set of variables. This
selection step is usually performed by computing the gradient and then by
looking for the gradient component with maximal absolute entry. This step can
be computationally expensive especially for large-scale and high-dimensional
data. In this work, we aim at accelerating these sparsity-constrained
optimization algorithms by exploiting the key observation that, for these
algorithms to work, one only needs the coordinate of the gradient's top entry.
Hence, we introduce algorithms based on greedy methods and randomization
approaches that aim at cheaply estimating the gradient and its top entry.
Another of our contribution is to cast the problem of finding the best gradient
entry as a best arm identification in a multi-armed bandit problem. Owing to
this novel insight, we are able to provide a bandit-based algorithm that
directly estimates the top entry in a very efficient way. Theoretical
observations stating that the resulting inexact Frank-Wolfe or Orthogonal
Matching Pursuit algorithms act, with high probability, similarly to their
exact versions are also given. We have carried out several experiments showing
that the greedy deterministic and the bandit approaches we propose can achieve
an acceleration of an order of magnitude while being as efficient as the exact
gradient when used in algorithms such as OMP, Frank-Wolfe or CoSaMP.
