Linear Regression with Mismatched Data: A Provably Optimal Local Search Algorithm
Linear Regression with Mismatched Data: A Provably Optimal Local Search Algorithm
复制标题
不匹配数据的线性回归：一种可证明最优的局部搜索算法
DOI：
10.1007/978303073879231
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rahul Mazumder, Haoyue Wang
中科院分区：
文献类型：
--
作者：
Rahul Mazumder, Haoyue Wang
线性回归是统计学及相关领域的基本建模工具。在本文中，我们研究了线性回归的一个重要变体，其中预测变量-响应对部分不匹配。我们使用优化公式来同时学习基础回归系数和与不匹配相对应的排列。该问题的组合结构导致了计算挑战，并且我们不知道有任何算法可以解决该问题，同时具有理论保证和有吸引力的计算性能。为此，在本文中，我们提出并研究了一种简单的贪婪局部搜索算法。我们证明，在与样本和特征的数量相比的不匹配对的数量的适当缩放下，以及对协变量的某些假设；我们的局部搜索算法在无噪声设置下以线性收敛速度收敛到全局最优解。
Linear regression is a fundamental modeling tool in statistics and related fields. In this paper, we study an important variant of linear regression in which the predictor-response pairs are partially mismatched. We use an optimization formulation to simultaneously learn the underlying regression coefficients and the permutation corresponding to the mismatches. The combinatorial structure of the problem leads to computational challenges, and we are unaware of any algorithm for this problem with both theoretical guarantees and appealing computational performance. To this end, in this paper, we propose and study a simple greedy local search algorithm. We prove that under a suitable scaling of the number of mismatched pairs compared to the number of samples and features, and certain assumptions on the covariates; our local search algorithm converges to the global optimal solution with a linear convergence rate under the noiseless setting.