Theory and Methods for Recovering Structured Patterns in High Dimensional Data

Regression with a sparsity constraint plays a vital role in many machine learning and signal processing applications. The key idea of sparsity is that only a small subset of all features are needed for good predictions. This subset is indicated by the pattern of sparsity in the regression coefficient vector. In many applications, the sparsity patterns have special structures in which non-zero coefficients tend to be clustered according to similarities among the associated features. The group lasso is a well-known method for adaptively selecting whole groups of features at a time. However, this all-or-nothing group selection can be too restrictive in certain applications, especially in multi-task learning problems.

We are interested in a less restrictive form of structured sparsity, wherein (1) the available features can be organized into subsets according to a notion of similarity and (2) if a particular feature is useful in prediction, then other similar features may be useful. That is, we would like to encourage the selection of similar features, but not necessarily force the selection of all the features in a group. I will discuss a a new procedure called Sparse Overlapping Sets (SOS) lasso, a convex optimization that allows for this flexibility, effectively interpolating between the standard lasso and the overlapping group lasso. I will derive sample complexity bounds for the SOS lasso using tools from convex analysis and random matrix theory. The performance of SOS lasso will be demonstrated through empirical studies in multi-subject fMRI and genomics. I will also discuss extensions to account for more complex structure, and show some recent results in learning semantic information from images.

In the final part of my talk, I will motivate a new method to recover signals that are “simple” in a very general sense of the word. I will show how we adapt the method to solve the SOSlasso problem and its specializations, and also show some results on other problems of interest in machine learning and signal processing