Home > About > Events & Seminars > Greedy Algorithms for Structurally Constrained High Dimensional Problems

Greedy Algorithms for Structurally Constrained High Dimensional Problems

Friday, February 3, 3PM – 4PM
ACE 6.304

Pradeep Ravikumar

Modern problems across science and engineering increasingly require high-dimensional models; with more parameters than observations. It is now well understood that statistically reliable inference is still possible under such high-dimensional settings, provided one restricts to constrained subclasses of models with particular low-dimensional structure. Examples include linear regression with sparsity constraints (compressed sensing), estimation of covariance or inverse covariance matrices, sparse principal component analysis, low-rank matrix estimation, and sparse additive non-parametric models. Over the past decade, there has been a strong body of work that have proposed statistical estimators for inferring such structurally constrained high-dimensional models, with strong statistical guarantees.

In this talk, we consider the computational facet of such estimation: could we provide a general computational scheme to solve any of the convex optimization problems that arise in such high-dimensional inference? We find that such a general computational scheme is indeed possible: specifically, we discuss and analyze a scheme based on a greedy strategy. Our framework not only unifies existing greedy algorithms that have been proposed for such high-dimensional problems by recovering them as special cases but also yields novel ones.

Hosted by Irene Gamba