我们研究了非参数脊的最小二乘的学习属性。特别是，我们考虑常见的估计人的估计案例，由比例依赖性内核定义，并专注于规模的作用。这些估计器内插数据，可以显示规模来通过条件号控制其稳定性。我们的分析表明，这是不同的制度，具体取决于样本大小，其尺寸与问题的平滑度之间的相互作用。实际上，当样本大小小于数据维度中的指数时，可以选择比例，以便学习错误减少。随着样本尺寸变大，总体错误停止减小但有趣地可以选择规模，使得噪声引起的差异仍然存在界线。我们的分析结合了概率，具有来自插值理论的许多分析技术。

我们为在一般来源条件下的希尔伯特量表中的新型Tikhonov登记学习问题提供了最小的自适应率。我们的分析不需要在假设类中包含回归函数，并且最著名的是不使用传统的\ textit {先验{先验}假设。使用插值理论，我们证明了Mercer运算符的光谱可以在存在“紧密''$ l^{\ infty} $嵌入的存在的情况下，可以推断出合适的Hilbert鳞片的嵌入。我们的分析利用了新的傅立叶能力条件在某些参数制度中，修改后的Mercer运算符的最佳Lorentz范围空间。

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.

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.

在本文中，我们考虑了基于系数的正则分布回归，该回归旨在从概率措施中回归到复制的内核希尔伯特空间（RKHS）的实现响应（RKHS），该响应将正则化放在系数上，而内核被假定为无限期的。 。该算法涉及两个采样阶段，第一阶段样本由分布组成，第二阶段样品是从这些分布中获得的。全面研究了回归函数的不同规律性范围内算法的渐近行为，并通过整体操作员技术得出学习率。我们在某些温和条件下获得最佳速率，这与单级采样的最小最佳速率相匹配。与文献中分布回归的内核方法相比，所考虑的算法不需要内核是对称的和阳性的半明确仪，因此为设计不确定的内核方法提供了一个简单的范式，从而丰富了分布回归的主题。据我们所知，这是使用不确定核进行分配回归的第一个结果，我们的算法可以改善饱和效果。

我们解决了条件平均嵌入（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 $是有限维度。我们进一步建立了学习率的下限，这表明所获得的上限是最佳的。

许多监督的学习问题涉及高维数据，例如图像，文本或图形。为了能够有效地利用数据，它通常有用的是在手头的问题中利用某些几何前瞻，例如与换算，置换子组或稳定性的不变性。通过考虑球体上这些功能的球形谐波分解，我们研究了目标功能提出了这种不变性和稳定性特性的学习问题的样本复杂性。我们提供内核方法的非参数率的收敛速度，并且在与相应的非不变内核相比，在该组上使用不变内核时，通过等于组的大小的因子的提高。当样本大小足够大时，这些改进是有效的，其渐近行为取决于该组的光谱特性。最后，这些增益扩展到不变性组之外，还涵盖小变形的几何稳定性，这里被建模为排列的子集（不一定是子组）。

在本文中，我们研究了可分离的希尔伯特空间的回归问题，并涵盖了繁殖核希尔伯特空间的非参数回归。我们研究了一类光谱/正则化算法，包括脊回归，主成分回归和梯度方法。我们证明了最佳，高概率的收敛性在研究算法的规范变体方面，考虑到对假设空间的能力假设以及目标函数的一般源条件。因此，我们以最佳速率获得了几乎确定的收敛结果。我们的结果改善并推广了先前的结果，以填补了无法实现的情况的理论差距。

我们考虑通过复制内核希尔伯特空间的相关协方差操作员对概率分布进行分析。我们表明，冯·诺伊曼（Von Neumann）的熵和这些操作员的相对熵与香农熵和相对熵的通常概念密切相关，并具有许多特性。它们与来自概率分布的各种口径的有效估计算法结合在一起。我们还考虑了产品空间，并表明对于张量产品内核，我们可以定义互信息和联合熵的概念，然后可以完美地表征独立性，但只能部分条件独立。我们最终展示了这些新的相对熵概念如何导致对数分区函数的新上限，这些函数可以与变异推理方法中的凸优化一起使用，从而提供了新的概率推理方法家族。

本文研究了基于Laplacian Eigenmaps（Le）的基于Laplacian EIGENMAPS（PCR-LE）的主要成分回归的统计性质，这是基于Laplacian Eigenmaps（Le）的非参数回归的方法。 PCR-LE通过投影观察到的响应的向量$ {\ bf y} =（y_1，\ ldots，y_n）$ to to changbood图表拉普拉斯的某些特征向量跨越的子空间。我们表明PCR-Le通过SoboLev空格实现了随机设计回归的最小收敛速率。在设计密度$ P $的足够平滑条件下，PCR-le达到估计的最佳速率（其中已知平方$ l ^ 2 $ norm的最佳速率为$ n ^ { - 2s /（2s + d） ）} $）和健美的测试（$ n ^ { - 4s /（4s + d）$）。我们还表明PCR-LE是\ EMPH {歧管Adaptive}：即，我们考虑在小型内在维度$ M $的歧管上支持设计的情况，并为PCR-LE提供更快的界限Minimax估计（$ n ^ { - 2s /（2s + m）$）和测试（$ n ^ { - 4s /（4s + m）$）收敛率。有趣的是，这些利率几乎总是比图形拉普拉斯特征向量的已知收敛率更快;换句话说，对于这个问题的回归估计的特征似乎更容易，统计上讲，而不是估计特征本身。我们通过经验证据支持这些理论结果。

过度分化的神经网络倾向于完全符合嘈杂的训练数据，但在测试数据上概括。灵感来自这一实证观察，最近的工作试图了解在更简单的线性模型中的良性过度或无害插值的这种现象。以前的理论工作批判性地假设数据特征是统计独立的，或者输入数据是高维的;这会阻止具有结构化特征映射的一般非参数设置。在本文中，我们为再生内核希尔伯特空间中的上限回归和分类风险提供了一般和灵活的框架。关键贡献是我们的框架在数据革处矩阵上描述了精确的充分条件，在这种情况下发生无害的插值。我们的结果恢复了现有的独立功能结果（具有更简单的分析），但它们还表明，在更常规的环境中可能发生无害的插值，例如有界正常系统的功能。此外，我们的结果表明，以先前仅针对高斯特征的方式显示分类和回归性能之间的渐近分离。

光谱滤波理论是一个显着的工具，可以了解用核心学习的统计特性。对于最小二乘来，它允许导出各种正则化方案，其产生的速度超越风险的收敛率比Tikhonov正规化更快。这通常通过利用称为源和容量条件的经典假设来实现，这表征了学习任务的难度。为了了解来自其他损失功能的估计，Marteau-Ferey等。已经将Tikhonov正规化理论扩展到广义自助损失功能（GSC），其包含例如物流损失。在本文中，我们进一步逐步，并表明通过使用迭代的Tikhonov正规方案，可以实现快速和最佳的速率，该计划与优化中的近端点方法有本质相关，并克服了古典Tikhonov规范化的限制。

在这项工作中，我们考虑线性逆问题$ 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 $的分发的一些弱假设下，包括子高斯变量的情况。我们的界限保持在无限尺寸的空间中，从而表明更精细和更细的离散化不会使这个学习问题更加困难。结果通过数值模拟验证。

We consider the random feature ridge regression (RFRR) given by a two-layer neural network at random initialization. We study the non-asymptotic behaviors of the training error, cross-validations, and generalization error of RFRR with nearly orthogonal deterministic input data in the overparameterized regime, where the number of parameters $N$ is much larger than the sample size $n$. We respectively establish the concentrations of the training errors, cross-validations, and generalization errors of RFRR around their corresponding errors of kernel ridge regression (KRR). This KRR is defined by an expected kernel from a random feature map. We then approximate the performances of the KRR by a polynomial kernel matrix, whose degree only depends on the orthogonality among different input vectors. The degree of this polynomial kernel essentially determines the asymptotic behavior of RFRR and KRR. Our results hold for a general class of target functions and input data with weak approximate orthonormal properties among different data points. Based on these approximations and nearly orthogonality, we obtain a lower bound for the generalization error of RFRR.

由于数据的注释可以在大规模的实际问题中稀缺，利用未标记的示例是机器学习中最重要的方面之一。这是半监督学习的目的。从访问未标记数据的访问中受益，它很自然地弥漫将标记数据平稳地知识到未标记的数据。这诱导了Laplacian正规化的使用。然而，Laplacian正则化的当前实施遭受了几种缺点，特别是众所周知的维度诅咒。在本文中，我们提供了统计分析以克服这些问题，并揭示了具有所需行为的大型光谱滤波方法。它们通过（再现）内核方法来实现，我们提供了现实的计算指南，以使我们的方法可用于大量数据。

我们研究了估计回归函数的导数的问题，该函数的衍生物具有广泛的应用，作为未知函数的关键非参数功能。标准分析可以定制为特定的衍生订单，参数调整仍然是一个艰巨的挑战，尤其是对于高阶导数。在本文中，我们提出了一个简单的插入式内核脊回归（KRR）估计器，其非参数回归中具有随机设计，该设计广泛适用于多维支持和任意混合派生衍生物。我们提供了非反应分析，以统一的方式研究提出的估计量的行为，该估计量涵盖回归函数及其衍生物，从而在强$ l_ \ infty $ norm中导致一般核类中的一般内核的两个误差范围。在专门针对多个多项式衰减特征值核的具体示例中，提出的估计器将最小值的最佳速率恢复到估计H \ h \ offormions ofergarithmic因子的最佳速率。因此，在任何衍生词的顺序中都选择了调整参数。因此，提出的估计器享受\ textIt {插件属性}的衍生物，因为它会自动适应要估计的衍生物顺序，从而可以轻松地在实践中调整。我们的仿真研究表明，相对于几种现有方法蓝色的几种现有方法的有限样本性能有限，并证实了其最小值最优性的理论发现。

我们提出和研究内核偶联梯度方法（KCGM），并在可分离的希尔伯特空间上进行最小二乘回归的随机投影。考虑两种类型的随机草图和nyStr \“ {o} m子采样产生的随机投影，我们在适当的停止规则下证明了有关算法的规范变体的最佳统计结果。尤其是我们的结果表明，如果投影维度显示了投影维度与问题的有效维度成正比，带有随机草图的KCGM可以最佳地概括，同时获得计算优势。作为推论，我们在良好条件方面的经典KCGM得出了最佳的经典KCGM，因为目标函数可能不会不会在假设空间中。

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.

We study a class of dynamical systems modelled as Markov chains that admit an invariant distribution via the corresponding transfer, or Koopman, operator. While data-driven algorithms to reconstruct such operators are well known, their relationship with statistical learning is largely unexplored. We formalize a framework to learn the Koopman operator from finite data trajectories of the dynamical system. We consider the restriction of this operator to a reproducing kernel Hilbert space and introduce a notion of risk, from which different estimators naturally arise. We link the risk with the estimation of the spectral decomposition of the Koopman operator. These observations motivate a reduced-rank operator regression (RRR) estimator. We derive learning bounds for the proposed estimator, holding both in i.i.d. and non i.i.d. settings, the latter in terms of mixing coefficients. Our results suggest RRR might be beneficial over other widely used estimators as confirmed in numerical experiments both for forecasting and mode decomposition.

我们在对数损失下引入条件密度估计的过程，我们调用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）。