• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Integer Programming and Combinatorial Optimization >Linear Regression with Mismatched Data: A Provably Optimal Local Search Algorithm
【24h】

Linear Regression with Mismatched Data: A Provably Optimal Local Search Algorithm

机译：具有不匹配数据的线性回归：一种可透明的最佳本地搜索算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：线性回归是统计和相关领域的基本建模工具。 在本文中，我们研究了一种重要的线性回归变体，其中预测器响应对部分不匹配。 我们使用优化制定来同时学习底层回归系数和与不匹配相对应的置换。 问题的组合结构导致计算挑战，我们没有通过理论担保和吸引力计算性能的任何算法。 为此，在本文中，我们提出并研究了一个简单的贪婪本地搜索算法。 我们证明，根据样品和特征的数量，与样品和特征的数量相比，在合适的比较缩放，以及协变量上的某些假设; 我们本地搜索算法会聚到全局最佳解决方案，在无噪声设置下具有线性收敛速率。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号