首页 → 数学

变量选择困难

Variable Selection is Hard
课程网址: https://videolectures.net/videos/colt2015_thaler_variable_selecti...  
主讲教师: Justin Thaler
开课单位: 信息不详。欢迎您在右侧留言补充。
开课时间: 2025-02-04
课程语种: 英语
中文简介:
稀疏线性回归的变量选择问题是，给定一个m x p矩阵B和一个目标向量y，找到一个稀疏向量x，使得Bx近似等于y。假设一个标准复杂度假设，我们证明没有多项式时间算法可以找到一个k'-稀疏x，其中||Bx-y||^2<=h(m,p)，其中k'=k*2^{log^{1- δ}p}$和h(m,p)=p^{C_1} m ^ {1 - c_2}，其中>0，C_1>0， C_2>0是任意的。即使在保证存在未知的k-稀疏向量x^*满足B x^* = y的情况下，这也是正确的。对于数据被噪声破坏的问题的统计版本，我们证明了类似的结果。据作者所知，这些是稀疏回归的第一个硬度结果，适用于算法同时具有k' b> k和h(m,p)>0。
课程简介: Variable selection for sparse linear regression is the problem of finding, given an m x p matrix B and a target vector y, a sparse vector x such that Bx approximately equals y. Assuming a standard complexity hypothesis, we show that no polynomial-time algorithm can find a k'-sparse x with ||Bx-y||^2<=h(m,p), where k'=k*2^{log^{1-delta}p}$ and h(m,p)=p^{C_1} m^{1-C_2}, where delta>0, C_1>0, and C_2>0 are arbitrary. This is true even under the promise that there is an unknown k-sparse vector x^* satisfying B x^* = y. We prove a similar result for a statistical version of the problem in which the data are corrupted by noise. To the authors' knowledge, these are the first hardness results for sparse regression that apply when the algorithm simultaneously has k'>k and h(m,p)>0.
关 键 词: 稀疏向量; 线性回归; 稀疏回归
课程来源: 视频讲座网
数据采集: 2025-03-23：zsp
最后编审: 2025-03-23：zsp
阅读次数: 153

纠错/补充/评论/留言
评论/留言 纠错/补充
验证算术题： 6 + 4 =