Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to
  Non-smooth Concave Maximization
  Iterative Hard Thresholding (IHT) is a class of projected gradient descent
methods for optimizing sparsity-constrained minimization models, with the best
known efficiency and scalability in practice. As far as we know, the existing
IHT-style methods are designed for sparse minimization in primal form. It
remains open to explore duality theory and algorithms in such a non-convex and
NP-hard problem setting. In this paper, we bridge this gap by establishing a
duality theory for sparsity-constrained minimization with $\ell_2$-regularized
loss function and proposing an IHT-style algorithm for dual maximization. Our
sparse duality theory provides a set of sufficient and necessary conditions
under which the original NP-hard/non-convex problem can be equivalently solved
in a dual formulation. The proposed dual IHT algorithm is a super-gradient
method for maximizing the non-smooth dual objective. An interesting finding is
that the sparse recovery performance of dual IHT is invariant to the Restricted
Isometry Property (RIP), which is required by virtually all the existing primal
IHT algorithms without sparsity relaxation. Moreover, a stochastic variant of
dual IHT is proposed for large-scale stochastic optimization. Numerical results
demonstrate the superiority of dual IHT algorithms to the state-of-the-art
primal IHT-style algorithms in model estimation accuracy and computational
efficiency.
