Timezone: »

 
Poster
Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds
Raghav Somani · Chirag Gupta · Prateek Jain · Praneeth Netrapalli

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #63
in Thu Poster Session B »

This paper studies the problem of sparse regression where the goal is to learn a sparse vector that best optimizes a given objective function. Under the assumption that the objective function satisfies restricted strong convexity (RSC), we analyze orthogonal matching pursuit (OMP), a greedy algorithm that is used heavily in applications, and obtain support recovery result as well as a tight generalization error bound for OMP. Furthermore, we obtain lower bounds for OMP, showing that both our results on support recovery and generalization error are tight up to logarithmic factors. To the best of our knowledge, these support recovery and generalization bounds are the first such matching upper and lower bounds (up to logarithmic factors) for {\em any} sparse regression algorithm under the RSC assumption.

Keywords: Sparsity and Compressed Sensing · Regression
[ Paper]  [ Poster] 

Author Information

Raghav Somani (Microsoft Research Lab - India)

Theoretical Machine Learning enthusiast majorly interested in Optimization and Statistics.

Chirag Gupta (Carnegie Mellon University)
Prateek Jain (Microsoft Research)
Praneeth Netrapalli (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors