图 书 馆
稀疏线性回归多项式时间算法性能的下界Lower bounds on the performance of polynomial-time algorithms for sparse linear regression |
|
| 课程网址: | http://videolectures.net/colt2014_zhang_algorithms/ |
| 主讲教师: | Yuchen Zhang |
| 开课单位: | 加州大学 |
| 开课时间: | 2014-07-15 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity. |
| 关 键 词: | 标准假设; 预测风险; 最优算法 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2022-12-07：chenjy |
| 最后编审: | 2022-12-07：chenjy |
| 阅读次数: | 24 |