随机梯度下降(SGD)在实践中表现出强烈的算法正则化效应,该效果已被认为在现代机器学习方法的概括中起着重要作用。在这项工作中,我们试图在线性回归的更简单环境(包括量身范围的和过度参数化的制度)中理解这些问题,在此,我们的目标是对(未注册)平均SGD与(未注册的)平均SGD进行基于实例的敏锐比较。脊回归的明确正规化。对于一系列最小二乘问题的问题实例(在高维设置中是自然的),我们显示:(1)对于每个问题实例和每个脊参数(未注册)SGD,当时提供比对数的样本比提供的样本更多的样本时对于脊算法,概括的概括不及脊解决方案(提供SGD使用调谐常数步骤); (2)相反,存在(在这个宽阔的问题类中),其中最佳调整的脊回归需要比SGD更高的样本以具有相同的概括性能。综上所述,我们的结果表明,在对数因素上,SGD的概括性能总是不到脊回归的差异,而在各种过度参数的问题中,对于某些问题实例,实际上可能会更好。更普遍地,我们的结果表明,即使在更简单(过度参数化)凸设置中,算法正则化如何产生重要的后果。
translated by 谷歌翻译
随机梯度下降(SGD)已被证明在许多深度学习应用中都很好地概括了。在实践中,人们经常以几何衰减的步骤运行SGD,即,恒定的初始步骤,然后是多个几何步骤衰减,并将最后一个迭代用作输出。已知这种SGD几乎对经典有限维线性回归问题几乎是最佳的(Ge等,2019)。但是,在过度参数化设置中对SGD的最后一次迭代进行了彻底的分析。在本文中,我们对SGD的最后一个迭代风险界限进行了依赖问题的分析,并具有腐烂的步骤,以(过度参数化)线性回归问题。特别是,对于带有(尾部)几何衰减步骤的最后迭代SGD,我们证明了多余风险的上限和下限几乎匹配。此外,我们为最后一次迭代的SGD提供了多余的风险下限,并以多项式衰减的步骤进行了大小,并以实例的方式证明了几何腐烂的步骤的优势,这补充了先前工作中的最小值比较。
translated by 谷歌翻译
深度神经网络等现代机器学习系统通常高度参数化,以便它们可以完全符合嘈杂的培训数据,但它们仍然可以在实践中实现小的测试错误。在本文中,我们研究了线性分类问题的最大边缘分类器的“良性过度装备”现象。具体地,我们考虑从子高斯混合系统生成的数据,并为过参数化设置中的最大边距线性分类器提供紧密的风险。我们的结果精确地表征了线性分类问题中可能发生良性过度的条件,并改善以前的工作。它们也对过度参数化的逻辑回归有直接影响。
translated by 谷歌翻译
我们研究了协变量偏移下的线性回归,其中输入协变量的边际分布在源和目标域上有所不同,而在两个域中,给定输入协变量的输出的条件分布相似。我们根据针对此问题的目标数据(均由在线SGD进行的目标数据(均由在线SGD执行)进行预处理研究,研究了转移学习方法。我们为这种方法建立了尖锐的实例依赖性高风险上限和下限。我们的界限表明,对于大量的线性回归实例,使用$ O(n^2)$源数据(以及稀缺或无目标数据)转移学习与使用$ n $目标数据的监督学习一样有效。此外,我们表明,即使只有少量的目标数据,也可能会大大减少预处理所需的源数据量。我们的理论阐明了预处理的有效性和局限性以及对解决协变量转移问题的填补的好处。
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 谷歌翻译
我们研究了称为“乐观速率”(Panchenko 2002; Srebro等,2010)的统一收敛概念,用于与高斯数据的线性回归。我们的精致分析避免了现有结果中的隐藏常量和对数因子,这已知在高维设置中至关重要,特别是用于了解插值学习。作为一个特殊情况,我们的分析恢复了Koehler等人的保证。(2021年),在良性过度的过度条件下,严格地表征了低规范内插器的人口风险。但是,我们的乐观速度绑定还分析了具有任意训练错误的预测因子。这使我们能够在随机设计下恢复脊和套索回归的一些经典统计保障,并有助于我们在过度参数化制度中获得精确了解近端器的过度风险。
translated by 谷歌翻译
尽管深元学习取得了较高的经验成功,但对过度参数化元学习的理论理解仍然有限。本文研究了广泛使用的元学习方法,模型 - 静态元学习(MAML)的概括,该方法旨在找到快速适应新任务的良好初始化。在混合线性回归模型下,我们分析了在过度参数化方案中用SGD训练的MAML的泛化特性。我们为MAML的多余风险提供上限和下限,这捕获了SGD动力学如何影响这些泛化界限。通过如此敏锐的特征,我们进一步探讨了各种学习参数如何影响过度参数化MAML的概括能力,包括明确识别典型的数据和任务分布,这些数据和任务分布可以通过过度参数化来减少概括性错误,并表征适应性学习率对过量风险和过量风险的影响早期停车时间。我们的理论发现将通过实验进一步验证。
translated by 谷歌翻译
机器学习理论中的主要开放问题之一是表征过度参数化的政权中的概括,在该制度中,大多数传统的概括范围变得不一致。在许多情况下,它们的失败可以归因于掩盖训练算法与基础数据分布之间的关键相互作用。为了解决这一缺点,我们提出了一个名为兼容性的概念,该概念以与数据相关的和算法相关的方式定量地表征了概括。通过考虑整个训练轨迹并专注于早期迭代的迭代术,兼容性充分利用了算法信息,因此可以提供更好的概括保证。我们通过理论上研究与梯度下降过度参数化的线性回归设置的兼容性来验证这一点。具体而言,我们执行与数据相关的轨迹分析,并在这种设置下得出足够的兼容性条件。我们的理论结果表明,从兼容性的意义上讲,概括性对问题实例的限制明显弱,而不是上次迭代分析。
translated by 谷歌翻译
从数据中学习的方法取决于各种类型的调整参数,例如惩罚强度或步长大小。由于性能可以在很大程度上取决于这些参数,因此重要的是要比较估算器的类别 - 考虑规定的有限调谐参数集,而不是特别调谐的方法。在这项工作中,我们通过同类中最佳方法的相对性能研究方法类。我们考虑了线性回归的中心问题,即随机的各向同性地面真理,并研究了两种基本方法的估计性能,即梯度下降和脊回归。我们公布以下现象。 (1)对于一般设计,当经验数据协方差矩阵衰减的特征值缓慢,作为指数较不小于统一的功率定律时,恒定的梯度下降优于山脊回归。相反,如果特征值迅速衰减,则作为指数大于统一或指数的权力定律,我们表明山脊回归优于梯度下降。 (2)对于正交设计,我们计算了确切的最小值最佳估计器类别(达到最低最大最大最佳),这表明它等同于具有衰减学习率的梯度下降。我们发现山脊回归和梯度下降的次数均具有恒定的步长。我们的结果表明,统计性能可以在很大程度上取决于调整参数。特别是,虽然最佳调谐脊回归是我们设置中的最佳估计器,但当仅在有限的许多正则化参数上调整两种方法时,它可以用任意/无界数量的梯度下降来表现优于梯度下降。
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 谷歌翻译
神经网络模型的最新成功揭示了一种令人惊讶的统计现象:完全拟合噪声数据的统计模型可以很好地推广到看不见的测试数据。了解$ \ textit {良性过拟合} $的这种现象吸引了强烈的理论和经验研究。在本文中,我们考虑插值两层线性神经网络在平方损失上梯度流训练,当协变量满足亚高斯和抗浓度的特性时,在平方损耗上训练,并在多余的风险上获得界限,并且噪声是独立和次级高斯的。。通过利用最新的结果来表征该估计器的隐性偏见,我们的边界强调了初始化质量的作用以及数据协方差矩阵在实现低过量风险中的特性。
translated by 谷歌翻译
我们考虑与高斯数据的高维线性回归中的插值学习,并在类高斯宽度方面证明了任意假设类别中的内插器的泛化误差。将通用绑定到欧几里德常规球恢复了Bartlett等人的一致性结果。(2020)对于最小规范内插器,并确认周等人的预测。(2020)在高斯数据的特殊情况下,对于近乎最小常态的内插器。我们通过将其应用于单位来证明所界限的一般性,从而获得最小L1-NORM Interpoolator(基础追踪)的新型一致性结果。我们的结果表明,基于规范的泛化界限如何解释并用于分析良性过度装备,至少在某些设置中。
translated by 谷歌翻译
元学习在有限的监督数据中表现出了几次学习的巨大成功。在这些设置中,元模型通常被过度参数化。尽管常规的统计学习理论表明,过度参数化的模型倾向于过度合适,但经验证据表明,过度参数化的元学习方法仍然很好地工作 - 这种现象通常称为``良性过度拟合''。我们了解这种现象,我们专注于元学习设置,我们将具有挑战性的嵌套结构称为嵌套的元学习,并在过度参数化的元学习模型下分析其泛化性能。尽管我们的分析使用了相对可牵引的线性模型,但我们的理论有助于理解数据异质性,模型适应和良性过度适应嵌套元学习任务之间的微妙相互作用。我们通过数值模拟证实了我们的理论主张。
translated by 谷歌翻译
本文研究了随机梯度下降(SGD)优化的高尺寸中随机特征(RF)回归的概过特性。在该制度中,我们在恒定和自适应阶梯大小的SGD设置下得出了RF回归的精确非渐近误差界,并观察了理论上和经验的双重血管现象。我们的分析显示了如何应对多种随机性源的初始化,标签噪声和数据采样(以及随机梯度),没有闭合形式解决方案,并且还超出了普通使用的高斯/球面数据假设。我们的理论结果表明,通过SGD训练,RF回归仍然概括为插值学习,并且能够通过方差的单位和单调的偏差减小来表征双重血迹行为。此外,我们还证明,与精确的最小规范内插器相比,恒定的步长SGD设置在与精确的最小规范内插器相比时不会损失收敛速度,作为在实践中使用SGD的理论典范。
translated by 谷歌翻译
我们在对数损失下引入条件密度估计的过程,我们调用SMP(样本Minmax预测器)。该估算器最大限度地减少了统计学习的新一般过度风险。在标准示例中,此绑定量表为$ d / n $,$ d $ d $模型维度和$ n $ sample大小,并在模型拼写条目下批判性仍然有效。作为一个不当(超出型号)的程序,SMP在模型内估算器(如最大似然估计)的内部估算器上,其风险过高的风险降低。相比,与顺序问题的方法相比,我们的界限删除了SubOltimal $ \ log n $因子,可以处理无限的类。对于高斯线性模型,SMP的预测和风险受到协变量的杠杆分数,几乎匹配了在没有条件的线性模型的噪声方差或近似误差的条件下匹配的最佳风险。对于Logistic回归,SMP提供了一种非贝叶斯方法来校准依赖于虚拟样本的概率预测,并且可以通过解决两个逻辑回归来计算。它达到了$ O的非渐近风险((d + b ^ 2r ^ 2)/ n)$,其中$ r $绑定了特征的规范和比较参数的$ B $。相比之下,在模型内估计器内没有比$ \ min达到更好的速率({b r} / {\ sqrt {n}},{d e ^ {br} / {n})$。这为贝叶斯方法提供了更实用的替代方法,这需要近似的后部采样,从而部分地解决了Foster等人提出的问题。 (2018)。
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 谷歌翻译
强大的机器学习模型的开发中的一个重要障碍是协变量的转变,当训练和测试集的输入分布时发生的分配换档形式在条件标签分布保持不变时发生。尽管现实世界应用的协变量转变普遍存在,但在现代机器学习背景下的理论理解仍然缺乏。在这项工作中,我们检查协变量的随机特征回归的精确高尺度渐近性,并在该设置中提出了限制测试误差,偏差和方差的精确表征。我们的结果激发了一种自然部分秩序,通过协变速转移,提供足够的条件来确定何时何时损害(甚至有助于)测试性能。我们发现,过度分辨率模型表现出增强的协会转变的鲁棒性,为这种有趣现象提供了第一个理论解释之一。此外,我们的分析揭示了分销和分发外概率性能之间的精确线性关系,为这一令人惊讶的近期实证观察提供了解释。
translated by 谷歌翻译
我们研究了差异私有线性回归的问题,其中每个数据点都是从固定的下高斯样式分布中采样的。我们提出和分析了一个单次迷你批次随机梯度下降法(DP-AMBSSGD),其中每次迭代中的点都在没有替换的情况下进行采样。为DP添加了噪声,但噪声标准偏差是在线估计的。与现有$(\ epsilon,\ delta)$ - 具有子最佳错误界限的DP技术相比,DP-AMBSSGD能够在关键参数(如多维参数)(如多维参数)等方面提供几乎最佳的错误范围$,以及观测值的噪声的标准偏差$ \ sigma $。例如,当对$ d $二维的协变量进行采样时。从正常分布中,然后由于隐私而引起的DP-AMBSSGD的多余误差为$ \ frac {\ sigma^2 d} {n} {n}(1+ \ frac {d} {\ epsilon^2 n})$,即当样本数量$ n = \ omega(d \ log d)$,这是线性回归的标准操作制度时,错误是有意义的。相比之下,在此设置中现有有效方法的错误范围为:$ \ mathcal {o} \ big(\ frac {d^3} {\ epsilon^2 n^2} \ big)$,即使是$ \ sigma = 0 $。也就是说,对于常量的$ \ epsilon $,现有技术需要$ n = \ omega(d \ sqrt {d})$才能提供非平凡的结果。
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 谷歌翻译
我们在高尺寸和非渐近环境下研究了双组分各向异性高斯混合模型下的监督聚类问题。我们首先导出较低和匹配的上限,以获得本框架中的群集风险。我们还表明,在高维制度中,线性判别分析(LDA)分类器在最低限度的识别中出现在次优。接下来,我们精确地表征了$ \ ell_2 $ -regulared监督最小二乘分类器的风险。我们推断了内插解决方案可能在噪声的协方差结构上的温和假设下优于正则化分类器。我们的分析还表明,当信号与协方差的“清洁”部分对齐时,插值可能是对噪声的协方差的损坏,以适当地定义对准的正确概念。据我们所知,这种特殊的现象尚未在与插值相关的迅速增长的文学中进行调查。我们得出结论,插值不仅是良性的,而且也可以是最佳的,并且在某些情况下是强大的。
translated by 谷歌翻译