Tuesday, 13:45 - 14:10 h, Room: MA 004


Yudong Chen
Robust sparse regression and orthogonal matching pursuit

Coauthors: Constantine Caramanis, Shie Mannor


We consider support recovery in sparse regression, when some number n1 out of n+n1 total covariate/response pairs are arbitrarily corrupted. We are interested in understanding how many outliers, n1, we can tolerate, while identifying the correct support. As far as we know, neither standard outlier rejection techniques, nor recently developed robust regression algorithms (that focus only on corrupted response variables) provide guarantees on support recovery. Perhaps surprisingly, we also show that the natural brute force algorithm that searches over all subsets of n covariate/response pairs, and all subsets of possible support coordinates in order to minimize regression error, is remarkably poor, unable to correctly identify the support with even n1 = O(n/k) corrupted points, where k is the sparsity, and p is the dimension of the signal to be recovered. In this setting, we provide a simple algorithm that gives stronger performance guarantees, recovering the support with up to n1 = O(n/(√k log p)) corrupted points. Moreover, we compare our formulation with robust optimization, and demonstrate interesting connection and difference between them.


Talk 2 of the invited session Tue.2.MA 004
"Applications of robust optimization I" [...]
Cluster 20
"Robust optimization" [...]


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.