Sparse Convex Optimization via Adaptively Regularized Hard Thresholding
  The goal of Sparse Convex Optimization is to optimize a convex function $f$
under a sparsity constraint $s\leq s^*\gamma$, where $s^*$ is the target number
of non-zero entries in a feasible solution (sparsity) and $\gamma\geq 1$ is an
approximation factor. There has been a lot of work to analyze the sparsity
guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP),
Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number
$\kappa$. The best known algorithms guarantee to find an approximate solution
of value $f(x^*)+\epsilon$ with the sparsity bound of $\gamma =
O\left(\kappa\min\left\{\log \frac{f(x^0)-f(x^*)}{\epsilon},
\kappa\right\}\right)$, where $x^*$ is the target solution. We present a new
Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes
significant progress on this problem by bringing the bound down to
$\gamma=O(\kappa)$, which has been shown to be tight for a general class of
algorithms including LASSO, OMP, and IHT. This is achieved without significant
sacrifice in the runtime efficiency compared to the fastest known algorithms.
We also provide a new analysis of OMP with Replacement (OMPR) for general $f$,
under the condition $s > s^* \frac{\kappa^2}{4}$, which yields Compressed
Sensing bounds under the Restricted Isometry Property (RIP). When compared to
other Compressed Sensing approaches, it has the advantage of providing a strong
tradeoff between the RIP condition and the solution sparsity, while working for
any general function $f$ that meets the RIP condition.
