论文标题
稀疏的混合线性回归并保证：驯服invex松弛的棘手问题
Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation
论文作者
论文摘要
在本文中，我们研究了一个未标记的数据集上稀疏混合线性回归的问题，该数据集是从两个不同的回归参数矢量从线性测量产生的。由于数据未标记，因此我们的任务不仅要确定回归参数向量的良好近似值，而且还可以正确标记数据集。以其原始形式，此问题是NP-HARD。解决此问题的最流行算法（例如期望最大化）具有卡在本地最小值的趋势。我们为这个棘手的问题提供了一种新颖的invex松弛，这导致了具有可证明的理论保证的解决方案。这种放松可以精确恢复数据标签。此外，我们恢复了与支持和符号中的真实参数向量相匹配的回归参数向量的近似值。我们的配方为INVEX问题使用了精心构造的原始双重见证人框架。此外，我们表明我们方法的样本复杂性仅在回归参数向量的维度方面是对数。
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.
