On Uniform Convergence and Low-Norm Interpolation Learning
On Uniform Convergence and Low-Norm Interpolation Learning
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Lijia Zhou;Danica J. Sutherland;N. Srebro
中科院分区：
文献类型：
--
作者：
Lijia Zhou;Danica J. Sutherland;N. Srebro
我们考虑一个欠定噪声线性回归模型，其中最小范数插值预测是一致的，并问：可以统一收敛在一个规范球，或至少（以下Nagarajan和Kolter）的子集的一个规范球的算法选择一个典型的输入集，解释这一成功？我们表明，经验误差和总体误差之间的差异的一致边界不能显示规范球中的任何学习，也不能显示任何集合的一致性，即使是取决于确切算法和分布的集合。但我们认为，我们可以用一个稍微弱一点的，但标准的概念，零误差预测的一致收敛来解释最小范数的一致性。我们用它来约束低（但不是最小）范数插值预测的推广误差。
We consider an underdetermined noisy linear regression model where the minimum-norm interpolating predictor is known to be consistent, and ask: can uniform convergence in a norm ball, or at least (following Nagarajan and Kolter) the subset of a norm ball that the algorithm selects on a typical input set, explain this success? We show that uniformly bounding the difference between empirical and population errors cannot show any learning in the norm ball, and cannot show consistency for any set, even one depending on the exact algorithm and distribution. But we argue we can explain the consistency of the minimal-norm interpolator with a slightly weaker, yet standard, notion, uniform convergence of zero-error predictors. We use this to bound the generalization error of low- (but not minimal-) norm interpolating predictors.