机器学习理论中的主要开放问题之一是表征过度参数化的政权中的概括,在该制度中,大多数传统的概括范围变得不一致。在许多情况下,它们的失败可以归因于掩盖训练算法与基础数据分布之间的关键相互作用。为了解决这一缺点,我们提出了一个名为兼容性的概念,该概念以与数据相关的和算法相关的方式定量地表征了概括。通过考虑整个训练轨迹并专注于早期迭代的迭代术,兼容性充分利用了算法信息,因此可以提供更好的概括保证。我们通过理论上研究与梯度下降过度参数化的线性回归设置的兼容性来验证这一点。具体而言,我们执行与数据相关的轨迹分析,并在这种设置下得出足够的兼容性条件。我们的理论结果表明,从兼容性的意义上讲,概括性对问题实例的限制明显弱,而不是上次迭代分析。
translated by 谷歌翻译
随机梯度下降(SGD)已被证明在许多深度学习应用中都很好地概括了。在实践中,人们经常以几何衰减的步骤运行SGD,即,恒定的初始步骤,然后是多个几何步骤衰减,并将最后一个迭代用作输出。已知这种SGD几乎对经典有限维线性回归问题几乎是最佳的(Ge等,2019)。但是,在过度参数化设置中对SGD的最后一次迭代进行了彻底的分析。在本文中,我们对SGD的最后一个迭代风险界限进行了依赖问题的分析,并具有腐烂的步骤,以(过度参数化)线性回归问题。特别是,对于带有(尾部)几何衰减步骤的最后迭代SGD,我们证明了多余风险的上限和下限几乎匹配。此外,我们为最后一次迭代的SGD提供了多余的风险下限,并以多项式衰减的步骤进行了大小,并以实例的方式证明了几何腐烂的步骤的优势,这补充了先前工作中的最小值比较。
translated by 谷歌翻译
尽管深元学习取得了较高的经验成功,但对过度参数化元学习的理论理解仍然有限。本文研究了广泛使用的元学习方法,模型 - 静态元学习(MAML)的概括,该方法旨在找到快速适应新任务的良好初始化。在混合线性回归模型下,我们分析了在过度参数化方案中用SGD训练的MAML的泛化特性。我们为MAML的多余风险提供上限和下限,这捕获了SGD动力学如何影响这些泛化界限。通过如此敏锐的特征,我们进一步探讨了各种学习参数如何影响过度参数化MAML的概括能力,包括明确识别典型的数据和任务分布,这些数据和任务分布可以通过过度参数化来减少概括性错误,并表征适应性学习率对过量风险和过量风险的影响早期停车时间。我们的理论发现将通过实验进一步验证。
translated by 谷歌翻译
随机梯度下降(SGD)在实践中表现出强烈的算法正则化效应,该效果已被认为在现代机器学习方法的概括中起着重要作用。在这项工作中,我们试图在线性回归的更简单环境(包括量身范围的和过度参数化的制度)中理解这些问题,在此,我们的目标是对(未注册)平均SGD与(未注册的)平均SGD进行基于实例的敏锐比较。脊回归的明确正规化。对于一系列最小二乘问题的问题实例(在高维设置中是自然的),我们显示:(1)对于每个问题实例和每个脊参数(未注册)SGD,当时提供比对数的样本比提供的样本更多的样本时对于脊算法,概括的概括不及脊解决方案(提供SGD使用调谐常数步骤); (2)相反,存在(在这个宽阔的问题类中),其中最佳调整的脊回归需要比SGD更高的样本以具有相同的概括性能。综上所述,我们的结果表明,在对数因素上,SGD的概括性能总是不到脊回归的差异,而在各种过度参数的问题中,对于某些问题实例,实际上可能会更好。更普遍地,我们的结果表明,即使在更简单(过度参数化)凸设置中,算法正则化如何产生重要的后果。
translated by 谷歌翻译
The phenomenon of benign overfitting is one of the key mysteries uncovered by deep learning methodology: deep neural networks seem to predict well, even with a perfect fit to noisy training data. Motivated by this phenomenon, we consider when a perfect fit to training data in linear regression is compatible with accurate prediction. We give a characterization of linear regression problems for which the minimum norm interpolating prediction rule has near-optimal prediction accuracy. The characterization is in terms of two notions of the effective rank of the data covariance. It shows that overparameterization is essential for benign overfitting in this setting: the number of directions in parameter space that are unimportant for prediction must significantly exceed the sample size. By studying examples of data covariance properties that this characterization shows are required for benign overfitting, we find an important role for finite-dimensional data: the accuracy of the minimum norm interpolating prediction rule approaches the best possible accuracy for a much narrower range of properties of the data distribution when the data lies in an infinite dimensional space versus when the data lies in a finite dimensional space whose dimension grows faster than the sample size.
translated by 谷歌翻译
In many modern applications of deep learning the neural network has many more parameters than the data points used for its training. Motivated by those practices, a large body of recent theoretical research has been devoted to studying overparameterized models. One of the central phenomena in this regime is the ability of the model to interpolate noisy data, but still have test error lower than the amount of noise in that data. arXiv:1906.11300 characterized for which covariance structure of the data such a phenomenon can happen in linear regression if one considers the interpolating solution with minimum $\ell_2$-norm and the data has independent components: they gave a sharp bound on the variance term and showed that it can be small if and only if the data covariance has high effective rank in a subspace of small co-dimension. We strengthen and complete their results by eliminating the independence assumption and providing sharp bounds for the bias term. Thus, our results apply in a much more general setting than those of arXiv:1906.11300, e.g., kernel regression, and not only characterize how the noise is damped but also which part of the true signal is learned. Moreover, we extend the result to the setting of ridge regression, which allows us to explain another interesting phenomenon: we give general sufficient conditions under which the optimal regularization is negative.
translated by 谷歌翻译
现代神经网络通常以强烈的过度构造状态运行:它们包含许多参数,即使实际标签被纯粹随机的标签代替,它们也可以插入训练集。尽管如此,他们在看不见的数据上达到了良好的预测错误:插值训练集并不会导致巨大的概括错误。此外,过度散色化似乎是有益的,因为它简化了优化景观。在这里,我们在神经切线(NT)制度中的两层神经网络的背景下研究这些现象。我们考虑了一个简单的数据模型,以及各向同性协变量的矢量,$ d $尺寸和$ n $隐藏的神经元。我们假设样本量$ n $和尺寸$ d $都很大,并且它们在多项式上相关。我们的第一个主要结果是对过份术的经验NT内核的特征结构的特征。这种表征意味着必然的表明,经验NT内核的最低特征值在$ ND \ gg n $后立即从零界限,因此网络可以在同一制度中精确插值任意标签。我们的第二个主要结果是对NT Ridge回归的概括误差的表征,包括特殊情况,最小值-ULL_2 $ NORD插值。我们证明,一旦$ nd \ gg n $,测试误差就会被内核岭回归之一相对于无限宽度内核而近似。多项式脊回归的误差依次近似后者,从而通过与激活函数的高度组件相关的“自我诱导的”项增加了正则化参数。多项式程度取决于样本量和尺寸(尤其是$ \ log n/\ log d $)。
translated by 谷歌翻译
深度神经网络等现代机器学习系统通常高度参数化,以便它们可以完全符合嘈杂的培训数据,但它们仍然可以在实践中实现小的测试错误。在本文中,我们研究了线性分类问题的最大边缘分类器的“良性过度装备”现象。具体地,我们考虑从子高斯混合系统生成的数据,并为过参数化设置中的最大边距线性分类器提供紧密的风险。我们的结果精确地表征了线性分类问题中可能发生良性过度的条件,并改善以前的工作。它们也对过度参数化的逻辑回归有直接影响。
translated by 谷歌翻译
现代神经网络通常具有很大的表现力,并且可以接受训练以使培训数据过高,同时仍能达到良好的测试性能。这种现象被称为“良性过度拟合”。最近,从理论角度出现了一系列研究“良性过度拟合”的作品。但是,它们仅限于线性模型或内核/随机特征模型,并且仍然缺乏关于何时以及如何在神经网络中发生过度拟合的理论理解。在本文中,我们研究了训练两层卷积神经网络(CNN)的良性过度拟合现象。我们表明,当信噪比满足一定条件时,通过梯度下降训练的两层CNN可以实现任意小的训练和测试损失。另一方面,当这种情况无法成立时,过度拟合就会有害,并且获得的CNN只能实现恒定的测试损失。这些共同证明了由信噪比驱动的良性过度拟合和有害过度拟合之间的急剧过渡。据我们所知,这是第一部精确地表征良性过度拟合在训练卷积神经网络中的条件的工作。
translated by 谷歌翻译
我们考虑与高斯数据的高维线性回归中的插值学习,并在类高斯宽度方面证明了任意假设类别中的内插器的泛化误差。将通用绑定到欧几里德常规球恢复了Bartlett等人的一致性结果。(2020)对于最小规范内插器,并确认周等人的预测。(2020)在高斯数据的特殊情况下,对于近乎最小常态的内插器。我们通过将其应用于单位来证明所界限的一般性,从而获得最小L1-NORM Interpoolator(基础追踪)的新型一致性结果。我们的结果表明,基于规范的泛化界限如何解释并用于分析良性过度装备,至少在某些设置中。
translated by 谷歌翻译
本文研究了随机梯度下降(SGD)优化的高尺寸中随机特征(RF)回归的概过特性。在该制度中,我们在恒定和自适应阶梯大小的SGD设置下得出了RF回归的精确非渐近误差界,并观察了理论上和经验的双重血管现象。我们的分析显示了如何应对多种随机性源的初始化,标签噪声和数据采样(以及随机梯度),没有闭合形式解决方案,并且还超出了普通使用的高斯/球面数据假设。我们的理论结果表明,通过SGD训练,RF回归仍然概括为插值学习,并且能够通过方差的单位和单调的偏差减小来表征双重血迹行为。此外,我们还证明,与精确的最小规范内插器相比,恒定的步长SGD设置在与精确的最小规范内插器相比时不会损失收敛速度,作为在实践中使用SGD的理论典范。
translated by 谷歌翻译
我们研究了称为“乐观速率”(Panchenko 2002; Srebro等,2010)的统一收敛概念,用于与高斯数据的线性回归。我们的精致分析避免了现有结果中的隐藏常量和对数因子,这已知在高维设置中至关重要,特别是用于了解插值学习。作为一个特殊情况,我们的分析恢复了Koehler等人的保证。(2021年),在良性过度的过度条件下,严格地表征了低规范内插器的人口风险。但是,我们的乐观速度绑定还分析了具有任意训练错误的预测因子。这使我们能够在随机设计下恢复脊和套索回归的一些经典统计保障,并有助于我们在过度参数化制度中获得精确了解近端器的过度风险。
translated by 谷歌翻译
尽管已经取得了重大的理论进步,但揭示了过度参数化神经网络的概括之谜仍然难以捉摸。在本文中,我们通过利用算法稳定性的概念来研究浅神经网络(SNN)的概括行为。我们考虑梯度下降(GD)和随机梯度下降(SGD)来训练SNN,因为这两者都通过通过早期停止来平衡优化和概括来发展一致的多余风险范围。与现有的GD分析相比,我们的新分析需要放松的过度参数化假设,并且还适用于SGD。改进的关键是更好地估计经验风险的Hessian矩阵的最小特征值,以及通过提供对其迭代材料的精制估计,沿GD和SGD的轨迹沿GD和SGD的轨迹进行了更好的估计。
translated by 谷歌翻译
了解随机梯度下降(SGD)的隐式偏见是深度学习的关键挑战之一,尤其是对于过度透明的模型,损失功能的局部最小化$ l $可以形成多种多样的模型。从直觉上讲,SGD $ \ eta $的学习率很小,SGD跟踪梯度下降(GD),直到它接近这种歧管为止,梯度噪声阻止了进一步的收敛。在这样的政权中,Blanc等人。 (2020)证明,带有标签噪声的SGD局部降低了常规术语,损失的清晰度,$ \ mathrm {tr} [\ nabla^2 l] $。当前的论文通过调整Katzenberger(1991)的想法提供了一个总体框架。它原则上允许使用随机微分方程(SDE)描述参数的限制动力学的SGD围绕此歧管的正规化效应(即“隐式偏见”)的正则化效应,这是由损失共同确定的功能和噪声协方差。这产生了一些新的结果:(1)与Blanc等人的局部分析相比,对$ \ eta^{ - 2} $ steps有效的隐性偏差进行了全局分析。 (2020)仅适用于$ \ eta^{ - 1.6} $ steps和(2)允许任意噪声协方差。作为一个应用程序,我们以任意大的初始化显示,标签噪声SGD始终可以逃脱内核制度,并且仅需要$ o(\ kappa \ ln d)$样本用于学习$ \ kappa $ -sparse $ -sparse yroverparame parametrized linearized Linear Modal in $ \ Mathbb {r}^d $(Woodworth等,2020),而GD在内核制度中初始化的GD需要$ \ omega(d)$样本。该上限是最小值的最佳,并改善了先前的$ \ tilde {o}(\ kappa^2)$上限(Haochen等,2020)。
translated by 谷歌翻译
微调是深度学习的常见做法,使用相对较少的训练数据来实现卓越的普遍性导致下游任务。虽然在实践中广泛使用,但它缺乏强烈的理论理解。我们分析了若干架构中线性教师的回归的本方案的样本复杂性。直观地,微调的成功取决于源任务与目标任务之间的相似性,但是测量它是非微不足道的。我们表明相关措施考虑了源任务,目标任务和目标数据的协方差结构之间的关系。在线性回归的设置中,我们表明,在现实的情况下,当上述措施低时,在实际设置下,显着的样本复杂性降低是合理的。对于深线性回归,我们在用预制权重初始化网络时,我们提出了关于基于梯度训练的感应偏差的新颖结果。使用此结果,我们显示此设置的相似度量也受网络深度的影响。我们进一步在浅relu模型上显示结果,并分析了在源和目标任务中的样本复杂性的依赖性。我们经验证明了我们对合成和现实数据的结果。
translated by 谷歌翻译
Influence diagnostics such as influence functions and approximate maximum influence perturbations are popular in machine learning and in AI domain applications. Influence diagnostics are powerful statistical tools to identify influential datapoints or subsets of datapoints. We establish finite-sample statistical bounds, as well as computational complexity bounds, for influence functions and approximate maximum influence perturbations using efficient inverse-Hessian-vector product implementations. We illustrate our results with generalized linear models and large attention based models on synthetic and real data.
translated by 谷歌翻译
在本文中,我们利用过度参数化来设计高维单索索引模型的无规矩算法,并为诱导的隐式正则化现象提供理论保证。具体而言,我们研究了链路功能是非线性且未知的矢量和矩阵单索引模型,信号参数是稀疏向量或低秩对称矩阵,并且响应变量可以是重尾的。为了更好地理解隐含正规化的角色而没有过度的技术性,我们假设协变量的分布是先验的。对于载体和矩阵设置,我们通过采用分数函数变换和专为重尾数据的强大截断步骤来构造过度参数化最小二乘损耗功能。我们建议通过将无规则化的梯度下降应用于损耗函数来估计真实参数。当初始化接近原点并且步骤中足够小时,我们证明了所获得的解决方案在载体和矩阵案件中实现了最小的收敛统计速率。此外,我们的实验结果支持我们的理论调查结果,并表明我们的方法在$ \ ell_2 $ -staticatisticated率和变量选择一致性方面具有明确的正则化的经验卓越。
translated by 谷歌翻译
我们重新审视GD的平均算法稳定性,用于训练过度的浅色神经网络,并证明没有NTK或PL假设的新的泛化和过度的风险范围。特别是,我们显示Oracle类型的界限,揭示了GD的泛化和过度风险由具有最短GD路径的插值网络从初始化(从某种意义上是具有最小相对规范的内插网络)来控制。虽然这是封闭式嵌入式嵌入式的,但我们的证据直接适用于GD培训的网络,而无需中间结石。与此同时,通过在这里开发的放松Oracle不等式,我们以简单的方式恢复基于NTK的风险范围,这表明我们的分析更加紧张。最后,与大多数基于NTK的分析不同,我们专注于带标签噪声的回归,并显示早期停止的GD是一致的。
translated by 谷歌翻译
我们证明了由例如He等人提出的广泛使用的方法。(2015年)并使用梯度下降对最小二乘损失进行训练并不普遍。具体而言,我们描述了一大批一维数据生成分布,较高的概率下降只会发现优化景观的局部最小值不好,因为它无法将其偏离偏差远离其初始化,以零移动。。事实证明,在这些情况下,即使目标函数是非线性的,发现的网络也基本执行线性回归。我们进一步提供了数值证据,表明在实际情况下,对于某些多维分布而发生这种情况,并且随机梯度下降表现出相似的行为。我们还提供了有关初始化和优化器的选择如何影响这种行为的经验结果。
translated by 谷歌翻译
神经网络模型的最新成功揭示了一种令人惊讶的统计现象:完全拟合噪声数据的统计模型可以很好地推广到看不见的测试数据。了解$ \ textit {良性过拟合} $的这种现象吸引了强烈的理论和经验研究。在本文中,我们考虑插值两层线性神经网络在平方损失上梯度流训练,当协变量满足亚高斯和抗浓度的特性时,在平方损耗上训练,并在多余的风险上获得界限,并且噪声是独立和次级高斯的。。通过利用最新的结果来表征该估计器的隐性偏见,我们的边界强调了初始化质量的作用以及数据协方差矩阵在实现低过量风险中的特性。
translated by 谷歌翻译