我们提出和研究内核偶联梯度方法(KCGM),并在可分离的希尔伯特空间上进行最小二乘回归的随机投影。考虑两种类型的随机草图和nyStr \“ {o} m子采样产生的随机投影,我们在适当的停止规则下证明了有关算法的规范变体的最佳统计结果。尤其是我们的结果表明,如果投影维度显示了投影维度与问题的有效维度成正比,带有随机草图的KCGM可以最佳地概括,同时获得计算优势。作为推论,我们在良好条件方面的经典KCGM得出了最佳的经典KCGM,因为目标函数可能不会不会在假设空间中。
translated by 谷歌翻译
在本文中,我们研究了可分离的希尔伯特空间的回归问题,并涵盖了繁殖核希尔伯特空间的非参数回归。我们研究了一类光谱/正则化算法,包括脊回归,主成分回归和梯度方法。我们证明了最佳,高概率的收敛性在研究算法的规范变体方面,考虑到对假设空间的能力假设以及目标函数的一般源条件。因此,我们以最佳速率获得了几乎确定的收敛结果。我们的结果改善并推广了先前的结果,以填补了无法实现的情况的理论差距。
translated by 谷歌翻译
在本文中,我们考虑了基于系数的正则分布回归,该回归旨在从概率措施中回归到复制的内核希尔伯特空间(RKHS)的实现响应(RKHS),该响应将正则化放在系数上,而内核被假定为无限期的。 。该算法涉及两个采样阶段,第一阶段样本由分布组成,第二阶段样品是从这些分布中获得的。全面研究了回归函数的不同规律性范围内算法的渐近行为,并通过整体操作员技术得出学习率。我们在某些温和条件下获得最佳速率,这与单级采样的最小最佳速率相匹配。与文献中分布回归的内核方法相比,所考虑的算法不需要内核是对称的和阳性的半明确仪,因此为设计不确定的内核方法提供了一个简单的范式,从而丰富了分布回归的主题。据我们所知,这是使用不确定核进行分配回归的第一个结果,我们的算法可以改善饱和效果。
translated by 谷歌翻译
We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nystrom approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to extend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector machines. This unified analysis requires developing new proofs, that use different technical tools, such as sub-gaussian inputs, to achieve fast rates. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance.
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 谷歌翻译
在这项工作中,我们考虑线性逆问题$ y = ax + \ epsilon $,其中$ a \ colon x \ to y $是可分离的hilbert spaces $ x $和$ y $之间的已知线性运算符,$ x $。 $ x $和$ \ epsilon $中的随机变量是$ y $的零平均随机过程。该设置涵盖成像中的几个逆问题,包括去噪,去束和X射线层析造影。在古典正规框架内,我们专注于正则化功能的情况下未能先验,而是从数据中学习。我们的第一个结果是关于均方误差的最佳广义Tikhonov规则器的表征。我们发现它完全独立于前向操作员$ a $,并仅取决于$ x $的平均值和协方差。然后,我们考虑从两个不同框架中设置的有限训练中学习常规程序的问题:一个监督,根据$ x $和$ y $的样本,只有一个无人监督,只基于$ x $的样本。在这两种情况下,我们证明了泛化界限,在X $和$ \ epsilon $的分发的一些弱假设下,包括子高斯变量的情况。我们的界限保持在无限尺寸的空间中,从而表明更精细和更细的离散化不会使这个学习问题更加困难。结果通过数值模拟验证。
translated by 谷歌翻译
我们研究了非参数脊的最小二乘的学习属性。特别是,我们考虑常见的估计人的估计案例,由比例依赖性内核定义,并专注于规模的作用。这些估计器内插数据,可以显示规模来通过条件号控制其稳定性。我们的分析表明,这是不同的制度,具体取决于样本大小,其尺寸与问题的平滑度之间的相互作用。实际上,当样本大小小于数据维度中的指数时,可以选择比例,以便学习错误减少。随着样本尺寸变大,总体错误停止减小但有趣地可以选择规模,使得噪声引起的差异仍然存在界线。我们的分析结合了概率,具有来自插值理论的许多分析技术。
translated by 谷歌翻译
内核方法是强大的学习方法,允许执行非线性数据分析。尽管它们很受欢迎,但在大数据方案中,它们的可伸缩性差。已经提出了各种近似方法,包括随机特征近似,以减轻问题。但是,除了内核脊回归外,大多数这些近似内核方法的统计一致性尚不清楚,其中已证明随机特征近似不仅在计算上有效,而且在统计上与最小值最佳收敛速率一致。在本文中,我们通过研究近似KPCA的计算和统计行为之间的权衡,研究了内核主成分分析(KPCA)中随机特征近似的功效。我们表明,与KPCA相比,与KPCA相比,与KPCA相比,近似KPCA在与基于内核函数基于其对相应的特征面积的投影相关的误差方面是有效的。该分析取决于伯恩斯坦类型的不平等现象,对自我偶和式希尔伯特·史克米特(Hilbert-Schmidt)操作员价值u统计量的运营商和希尔伯特·史克米特(Hilbert-Schmidt)规范取决于独立利益。
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 谷歌翻译
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 谷歌翻译
我们解决了条件平均嵌入(CME)的内核脊回归估算的一致性,这是给定$ y $ x $的条件分布的嵌入到目标重现内核hilbert space $ hilbert space $ hilbert Space $ \ Mathcal {H} _y $ $ $ $ 。 CME允许我们对目标RKHS功能的有条件期望,并已在非参数因果和贝叶斯推论中使用。我们解决了错误指定的设置,其中目标CME位于Hilbert-Schmidt操作员的空间中,该操作员从$ \ Mathcal {H} _X _x $和$ L_2 $和$ \ MATHCAL {H} _Y $ $之间的输入插值空间起作用。该操作员的空间被证明是新定义的矢量值插值空间的同构。使用这种同构,我们在未指定的设置下为经验CME估计量提供了一种新颖的自适应统计学习率。我们的分析表明,我们的费率与最佳$ o(\ log n / n)$速率匹配,而无需假设$ \ Mathcal {h} _y $是有限维度。我们进一步建立了学习率的下限,这表明所获得的上限是最佳的。
translated by 谷歌翻译
我们解决了在没有观察到的混杂的存在下的因果效应估计的问题,但是观察到潜在混杂因素的代理。在这种情况下,我们提出了两种基于内核的方法,用于非线性因果效应估计:(a)两阶段回归方法,以及(b)最大矩限制方法。我们专注于近端因果学习设置,但是我们的方法可以用来解决以弗雷霍尔姆积分方程为特征的更广泛的逆问题。特别是,我们提供了在非线性环境中解决此问题的两阶段和矩限制方法的统一视图。我们为每种算法提供一致性保证,并证明这些方法在合成数据和模拟现实世界任务的数据上获得竞争结果。特别是,我们的方法优于不适合利用代理变量的早期方法。
translated by 谷歌翻译
本文为信号去噪提供了一般交叉验证框架。然后将一般框架应用于非参数回归方法,例如趋势过滤和二元推车。然后显示所得到的交叉验证版本以获得最佳调谐的类似物所熟知的几乎相同的收敛速度。没有任何先前的趋势过滤或二元推车的理论分析。为了说明框架的一般性,我们还提出并研究了两个基本估算器的交叉验证版本;套索用于高维线性回归和矩阵估计的奇异值阈值阈值。我们的一般框架是由Chatterjee和Jafarov(2015)的想法的启发,并且可能适用于使用调整参数的广泛估算方法。
translated by 谷歌翻译
我们考虑与高斯数据的高维线性回归中的插值学习,并在类高斯宽度方面证明了任意假设类别中的内插器的泛化误差。将通用绑定到欧几里德常规球恢复了Bartlett等人的一致性结果。(2020)对于最小规范内插器,并确认周等人的预测。(2020)在高斯数据的特殊情况下,对于近乎最小常态的内插器。我们通过将其应用于单位来证明所界限的一般性,从而获得最小L1-NORM Interpoolator(基础追踪)的新型一致性结果。我们的结果表明,基于规范的泛化界限如何解释并用于分析良性过度装备,至少在某些设置中。
translated by 谷歌翻译
尽管有许多有吸引力的财产,但内核方法受到维度的诅咒受到严重影响。例如,在$ \ mathbb {r} ^ d $的内部产品内核的情况下,再现内核希尔伯特空间(RKHS)规范对于依赖于小方向子集(RIDGE函数)的功能往往非常大。相应地,使用内核方法难以学习这样的功能。这种观察结果有动力研究内核方法的概括,由此rkhs规范 - 它等同于加权$ \ ell_2 $ norm - 被加权函数$ \ ell_p $ norm替换,我们将其称为$ \ mathcal {f} _p $ norm。不幸的是,这些方法的陶油是不清楚的。内核技巧不可用,最大限度地减少这些规范要求解决无限维凸面问题。我们将随机特征近似于这些规范,表明,对于$ p> 1 $,近似于原始学习问题所需的随机功能的数量是由样本大小的多项式的上限。因此,使用$ \ mathcal {f} _p $ norms在这些情况下是易行的。我们介绍了一种基于双重均匀浓度的证明技术,这可以对超分子化模型的研究更广泛。对于$ p = 1 $,我们对随机功能的保证近似分解。我们证明了使用$ \ mathcal {f} _1 $ norm的学习是在随机减少的$ \ mathsf {np} $ - 基于噪音的半个空间问题的问题。
translated by 谷歌翻译
神经网络模型的最新成功揭示了一种令人惊讶的统计现象:完全拟合噪声数据的统计模型可以很好地推广到看不见的测试数据。了解$ \ textit {良性过拟合} $的这种现象吸引了强烈的理论和经验研究。在本文中,我们考虑插值两层线性神经网络在平方损失上梯度流训练,当协变量满足亚高斯和抗浓度的特性时,在平方损耗上训练,并在多余的风险上获得界限,并且噪声是独立和次级高斯的。。通过利用最新的结果来表征该估计器的隐性偏见,我们的边界强调了初始化质量的作用以及数据协方差矩阵在实现低过量风险中的特性。
translated by 谷歌翻译
我们为在一般来源条件下的希尔伯特量表中的新型Tikhonov登记学习问题提供了最小的自适应率。我们的分析不需要在假设类中包含回归函数,并且最著名的是不使用传统的\ textit {先验{先验}假设。使用插值理论,我们证明了Mercer运算符的光谱可以在存在“紧密''$ l^{\ infty} $嵌入的存在的情况下,可以推断出合适的Hilbert鳞片的嵌入。我们的分析利用了新的傅立叶能力条件在某些参数制度中,修改后的Mercer运算符的最佳Lorentz范围空间。
translated by 谷歌翻译
我们在随机特征矩阵的条件数上提供(高概率)界限。特别是,我们表明,如果复杂性比率$ \ frac {n} $ where $ n $是n $ with n $ wore $ n $是$ m $的数量,如$ \ log ^ {-1}( n)$或$ \ log(m)$,然后随机功能矩阵很好。该结果在没有正则化的情况下保持并且依赖于在随机特征矩阵的相关组件之间建立各种浓度界限。另外,我们在随机特征矩阵的受限等距常数上获得界限。我们证明了使用随机特征矩阵的回归问题相关的风险表现出双重下降现象,并且这是条件数的双缩小行为的效果。风险范围包括使用最小二乘问题的underParamedAimed设置和使用最小规范插值问题或稀疏回归问题的过次参数化设置。对于最小二乘或稀疏的回归案例,我们表明风险降低为$ M $和$ N $增加,即使在存在有限或随机噪声时也是如此。风险绑定与文献中的最佳缩放匹配,我们的结果中的常量是显式的,并且独立于数据的维度。
translated by 谷歌翻译
我们研究了称为“乐观速率”(Panchenko 2002; Srebro等,2010)的统一收敛概念,用于与高斯数据的线性回归。我们的精致分析避免了现有结果中的隐藏常量和对数因子,这已知在高维设置中至关重要,特别是用于了解插值学习。作为一个特殊情况,我们的分析恢复了Koehler等人的保证。(2021年),在良性过度的过度条件下,严格地表征了低规范内插器的人口风险。但是,我们的乐观速度绑定还分析了具有任意训练错误的预测因子。这使我们能够在随机设计下恢复脊和套索回归的一些经典统计保障,并有助于我们在过度参数化制度中获得精确了解近端器的过度风险。
translated by 谷歌翻译
在最近的研究中,分布式学习和随机特征的概括特性假设在假设空间中存在目标概念。但是,这种严格的条件不适用于更常见的情况。在本文中,使用精致的证明技术,我们首先将具有随机特征的分布式学习的最佳速率扩展到了不可算力的情况。然后,我们通过数据依赖性生成策略减少所需的随机特征的数量,并使用其他未标记的数据来改善允许的分区数量。理论分析表明,这些技术显着降低了计算成本,同时保留了标准假设下的最佳概括精度。最后,我们对模拟和实际数据集进行了几项实验,经验结果验证了我们的理论发现。
translated by 谷歌翻译