Timezone: »

 
Spotlight
Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation
Adarsh Barik · Jean Honorio

Tue Jul 19 01:45 PM -- 01:50 PM (PDT) @ Hall G
in T: Learning/Deep Learning Theory »

In this paper, we study the problem of sparse mixed linear regression on an unlabeled dataset that is generated from linear measurements from two different regression parameter vectors. Since the data is unlabeled, our task is to not only figure out a good approximation of regression parameter vectors but also label the dataset correctly. In its original form, this problem is NP-hard. The most popular algorithms to solve this problem (such as Expectation-Maximization) have a tendency to stuck at local minima. We provide a novel invex relaxation for this intractable problem which leads to a solution with provable theoretical guarantees. This relaxation enables exact recovery of data labels. Furthermore, we recover close approximation of regression parameter vectors which match the true parameter vectors in support and sign. Our formulation uses a carefully constructed primal dual witnesses framework for the invex problem. Furthermore, we show that the sample complexity of our method is only logarithmic in terms of the dimension of the regression parameter vectors.

Keywords: T: Learning Theory

Author Information

Adarsh Barik (Purdue University)
Jean Honorio (Purdue University)

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

More from the Same Authors