Compressed Least-Squares Regression
Compressed Least-Squares Regression
复制标题
DOI：
--
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Odalric-Ambrym Maillard;R. Munos
中科院分区：
文献类型：
--
作者：
Odalric-Ambrym Maillard;R. Munos
我们考虑使用投影到较低维度 M 的随机子空间，从 K 数据学习高维 N 线性空间中的回归函数的问题。从任何最小化（可能受到惩罚的）经验风险的算法，我们根据在高维空间（初始域）中构建的估计的超额风险，提供在投影子空间（压缩域）中计算的估计的超额风险的界限。我们表明，在压缩域而不是初始域中解决问题会减少估计误差，但代价是增加（但受控）近似误差。我们将分析应用于最小二乘 (LS) 回归，并根据 N、K 和 M 讨论所得“压缩最小二乘回归”(CLSR) 的过度风险和数值复杂性。当我们选择 M = O(√K) 时，我们表明 CLSR 的估计误差为 O(log K/ √K) 阶。
We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M. From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting "Compressed Least Squares Regression" (CLSR) in terms of N, K, and M. When we choose M = O(√K), we show that CLSR has an estimation error of order O(log K/ √K).