Robust Structured Statistical Estimation via Conditional Gradient Type
  Methods
  Structured statistical estimation problems are often solved by Conditional
Gradient (CG) type methods to avoid the computationally expensive projection
operation. However, the existing CG type methods are not robust to data
corruption. To address this, we propose to robustify CG type methods against
Huber's corruption model and heavy-tailed data. First, we show that the two
Pairwise CG methods are stable, i.e., do not accumulate error. Combined with
robust mean gradient estimation techniques, we can therefore guarantee
robustness to a wide class of problems, but now in a projection-free
algorithmic framework. Next, we consider high dimensional problems. Robust mean
estimation based approaches may have an unacceptably high sample complexity.
When the constraint set is a $\ell_0$ norm ball,
Iterative-Hard-Thresholding-based methods have been developed recently. Yet
extension is non-trivial even for general sets with $O(d)$ extreme points. For
setting where the feasible set has $O(\text{poly}(d))$ extreme points, we
develop a novel robustness method, based on a new condition we call the Robust
Atom Selection Condition (RASC). When RASC is satisfied, our method converges
linearly with a corresponding statistical error, with sample complexity that
scales correctly in the sparsity of the problem, rather than the ambient
dimension as would be required by any approach based on robust mean estimation.
