Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation
Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation
复制标题
DOI：
10.48550/arxiv.2206.01167
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Adarsh Barik;J. Honorio
中科院分区：
文献类型：
--
作者：
Adarsh Barik;J. Honorio
在本文中，我们研究了稀疏混合线性回归问题的未标记的数据集，从两个不同的回归参数向量的线性测量产生。由于数据是未标记的，我们的任务不仅是找出回归参数向量的良好近似，而且要正确标记数据集。在其原始形式中，该问题是NP-难的。解决此问题的最流行算法（例如期望最大化）往往会陷入局部最小值。我们提供了一个新的不变凸松弛这个棘手的问题，导致一个解决方案，可证明的理论保证。这种松弛使得能够准确地恢复数据标签。此外，我们恢复的回归参数向量的支持和符号匹配的真实参数向量的密切近似。我们的配方使用精心构造的原始对偶证人框架的不变凸问题。此外，我们表明，我们的方法的样本复杂度是对数的回归参数向量的维数。
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 not only to figure out a good approximation of the regression parameter vectors but also to 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 a close approximation of the 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.