对比学习在各种自我监督的学习任务中取得了最先进的表现，甚至优于其监督的对应物。尽管其经验成功，但对为什么对比学习作品的理论认识仍然有限。在本文中，（i）我们证明，对比学习胜过AutoEncoder，一种经典无监督的学习方法，适用于特征恢复和下游任务;（ii）我们还说明标记数据在监督对比度学习中的作用。这为最近的发现提供了理论支持，即对标签对比学习的结果提高了域名下游任务中学识表的表现，但它可能会损害转移学习的性能。我们通过数值实验验证了我们的理论。

自我监督的表示学习解决辅助预测任务（称为借口任务），而不需要标记数据以学习有用的语义表示。这些借口任务仅使用输入特征，例如预测缺失的图像修补程序，从上下文中恢复图像的颜色通道，或者预测文本中的缺失单词;然而，预测该\ Texit {已知}信息有助于学习对下游预测任务的学习陈述。我们提供利用某些{\ EM重建}借口任务之间的统计连接的机制，以保证学习良好代表性。正式地，我们量化了借口任务的组件之间的近似独立性（标签和潜在变量的条件）允许我们学习可以通过训练在学习表示的顶部的线性层来解决下游任务的表示。我们证明了线性层即使对于复杂的地面真理函数类，也会产生小的近似误差，并且将急剧减少标记的样本复杂性。接下来，我们展示了我们方法的简单修改，导致非线性CCA，类似于流行的Simsiam算法，并显示了非线性CCA的类似保证。

自我监督学习中的最新作品通过依靠对比度学习范式来推动最先进的工作，该范式通过推动正面对或从同一班级中的类似示例来学习表示形式，同时将负面对截然不同。尽管取得了经验的成功，但理论基础是有限的 - 先前的分析假设鉴于同一类标签的正对有条件独立性，但是最近的经验应用使用了密切相关的正对（即同一图像的数据增强）。我们的工作分析了对比度学习，而无需在数据上使用增强图的新概念假设正对的有条件独立性。此图中的边缘连接相同数据的增强，而地面实际类别自然形成了连接的子图。我们提出了在人口增强图上执行光谱分解的损失，并且可以简洁地作为对神经净表示的对比学习目标。最小化此目标会导致在线性探针评估下具有可证明准确性的功能。通过标准的概括范围，在最大程度地减少训练对比度损失时，这些准确性也可以保证。从经验上讲，我们目标所学的功能可以匹配或胜过基准视觉数据集上的几个强基线。总的来说，这项工作为对比度学习提供了首次可证明的分析，在该学习中，线性探针评估的保证可以适用于现实的经验环境。

元学习或学习学习，寻求设计算法，可以利用以前的经验快速学习新技能或适应新环境。表示学习 - 用于执行元学习的关键工具 - 了解可以在多个任务中传输知识的数据表示，这在数据稀缺的状态方面是必不可少的。尽管最近在Meta-Leature的实践中感兴趣的兴趣，但缺乏元学习算法的理论基础，特别是在学习可转让陈述的背景下。在本文中，我们专注于多任务线性回归的问题 - 其中多个线性回归模型共享常见的低维线性表示。在这里，我们提供了可提供的快速，采样高效的算法，解决了（1）的双重挑战，从多个相关任务和（2）将此知识转移到新的，看不见的任务中的常见功能。两者都是元学习的一般问题的核心。最后，我们通过在学习这些线性特征的样本复杂性上提供信息定理下限来补充这些结果。

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.

自我监督的公制学习是一种成功的方法，用于从未标记的数据集学习距离。即使在度量学习阶段中没有使用来自下游任务的信息，所产生的距离广泛可用于改善各种距离的下游任务。为了进入这种方法，我们在理论上发展统计框架，从理论上研究自我监督的公制学习如何在多视图数据的上下文中利用下游任务。在此框架下，我们表明度量学习的目标距离满足下游任务的几个所需属性。另一方面，我们的研究表明，通过培养每个方向的重量，可以进一步提高目标距离。此外，我们的分析精确地表征了四个常用的下游任务的自我监督度量学习的改进：样本识别，两个样本测试，$ k $ -means群集，以及$ k $ -nearest邻居分类。作为副产品，我们提出了一种简单的自我监督度量学习的频谱方法，这是用于估计目标距离的计算上有效和最低限度。最后，提出了数值实验以支持纸张中的理论结果。

在本文中，我们提出了一种均匀抖动的一位量化方案，以进行高维统计估计。该方案包含截断，抖动和量化，作为典型步骤。作为规范示例，量化方案应用于三个估计问题：稀疏协方差矩阵估计，稀疏线性回归和矩阵完成。我们研究了高斯和重尾政权，假定重尾数据的基本分布具有有限的第二或第四刻。对于每个模型，我们根据一位量化的数据提出新的估计器。在高斯次级政权中，我们的估计器达到了对数因素的最佳最小速率，这表明我们的量化方案几乎没有额外的成本。在重尾状态下，虽然我们的估计量基本上变慢，但这些结果是在这种单位量化和重型尾部设置中的第一个结果，或者比现有可比结果表现出显着改善。此外，我们为一位压缩传感和一位矩阵完成的问题做出了巨大贡献。具体而言，我们通过凸面编程将一位压缩感传感扩展到次高斯甚至是重尾传感向量。对于一位矩阵完成，我们的方法与标准似然方法基本不同，并且可以处理具有未知分布的预量化随机噪声。提出了有关合成数据的实验结果，以支持我们的理论分析。

现代神经网络通常以强烈的过度构造状态运行：它们包含许多参数，即使实际标签被纯粹随机的标签代替，它们也可以插入训练集。尽管如此，他们在看不见的数据上达到了良好的预测错误：插值训练集并不会导致巨大的概括错误。此外，过度散色化似乎是有益的，因为它简化了优化景观。在这里，我们在神经切线（NT）制度中的两层神经网络的背景下研究这些现象。我们考虑了一个简单的数据模型，以及各向同性协变量的矢量，$ d $尺寸和$ n $隐藏的神经元。我们假设样本量$ n $和尺寸$ d $都很大，并且它们在多项式上相关。我们的第一个主要结果是对过份术的经验NT内核的特征结构的特征。这种表征意味着必然的表明，经验NT内核的最低特征值在$ ND \ gg n $后立即从零界限，因此网络可以在同一制度中精确插值任意标签。我们的第二个主要结果是对NT Ridge回归的概括误差的表征，包括特殊情况，最小值-ULL_2 $ NORD插值。我们证明，一旦$ nd \ gg n $，测试误差就会被内核岭回归之一相对于无限宽度内核而近似。多项式脊回归的误差依次近似后者，从而通过与激活函数的高度组件相关的“自我诱导的”项增加了正则化参数。多项式程度取决于样本量和尺寸（尤其是$ \ log n/\ log d $）。

我们调查与高斯的混合的数据分享共同但未知，潜在虐待协方差矩阵的数据。我们首先考虑具有两个等级大小的组件的高斯混合，并根据最大似然估计导出最大切割整数程序。当样品的数量在维度下线性增长时，我们证明其解决方案实现了最佳的错误分类率，直到对数因子。但是，解决最大切割问题似乎是在计算上棘手的。为了克服这一点，我们开发了一种高效的频谱算法，该算法达到最佳速率，但需要一种二次样本量。虽然这种样本复杂性比最大切割问题更差，但我们猜测没有多项式方法可以更好地执行。此外，我们收集了支持统计计算差距存在的数值和理论证据。最后，我们将MAX-CUT程序概括为$ k $ -means程序，该程序处理多组分混合物的可能性不平等。它享有相似的最优性保证，用于满足运输成本不平等的分布式的混合物，包括高斯和强烈的对数的分布。

对于由缺陷线性回归中的标签噪声引起的预期平均平方概率，我们证明了无渐近分布的下限。我们的下部结合概括了过度公共数据（内插）制度的类似已知结果。与最先前的作品相比，我们的分析适用于广泛的输入分布，几乎肯定的全排列功能矩阵，允许我们涵盖各种类型的确定性或随机特征映射。我们的下限是渐近的锐利，暗示在存在标签噪声时，缺陷的线性回归不会在任何这些特征映射中围绕内插阈值进行良好的。我们详细分析了强加的假设，并为分析（随机）特征映射提供了理论。使用此理论，我们可以表明我们的假设对于具有（Lebesgue）密度的输入分布以及随机深神经网络给出的特征映射，具有Sigmoid，Tanh，SoftPlus或Gelu等分析激活功能。作为进一步的例子，我们示出了来自随机傅里叶特征和多项式内核的特征映射也满足我们的假设。通过进一步的实验和分析结果，我们补充了我们的理论。

我们考虑与高斯数据的高维线性回归中的插值学习，并在类高斯宽度方面证明了任意假设类别中的内插器的泛化误差。将通用绑定到欧几里德常规球恢复了Bartlett等人的一致性结果。（2020）对于最小规范内插器，并确认周等人的预测。（2020）在高斯数据的特殊情况下，对于近乎最小常态的内插器。我们通过将其应用于单位来证明所界限的一般性，从而获得最小L1-NORM Interpoolator（基础追踪）的新型一致性结果。我们的结果表明，基于规范的泛化界限如何解释并用于分析良性过度装备，至少在某些设置中。

随机奇异值分解（RSVD）是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $，原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数，$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中，我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性，即，观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $（频谱规范）和$ \ ell_ {2 \ to \ infty} $（最大行行列$ \ ell_2 $ norm）$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比（SNR）和功率迭代$ g $的数量。观察到一个相变现象，其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明，每当噪声矩阵满足一定的痕量生长条件时，这些相变发生的$ g $的阈值都会很清晰。最后，我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

In this paper, we study the trace regression when a matrix of parameters B* is estimated via the convex relaxation of a rank-regularized regression or via regularized non-convex optimization. It is known that these estimators satisfy near-optimal error bounds under assumptions on the rank, coherence, and spikiness of B*. We start by introducing a general notion of spikiness for B* that provides a generic recipe to prove the restricted strong convexity of the sampling operator of the trace regression and obtain near-optimal and non-asymptotic error bounds for the estimation error. Similar to the existing literature, these results require the regularization parameter to be above a certain theory-inspired threshold that depends on observation noise that may be unknown in practice. Next, we extend the error bounds to cases where the regularization parameter is chosen via cross-validation. This result is significant in that existing theoretical results on cross-validated estimators (Kale et al., 2011; Kumar et al., 2013; Abou-Moustafa and Szepesvari, 2017) do not apply to our setting since the estimators we study are not known to satisfy their required notion of stability. Finally, using simulations on synthetic and real data, we show that the cross-validated estimator selects a near-optimal penalty parameter and outperforms the theory-inspired approach of selecting the parameter.

本文提出了一项新的统计分析，旨在解释自然语言处理（NLP）中训练技术的最新成就。我们证明，当预训练任务的类（例如，蒙版语言模型任务中的不同单词）的类别足够多样化，从某种意义上说，最后一个线性层的最小奇异值在预训练中（表示为$ \ \ \ \ \ Tilde {\ nu} $）很大，然后预训练可以显着提高下游任务的样本效率。特别是，我们显示转移学习过量风险享受$ o \ left（\ frac {1} {\ tilde {\ nu} \ sqrt {n}} \ right）$ rate，与$ o \ left相比（\）标准监督学习中的frac {1} {\ sqrt {m}} \ right）$ rate。在这里，$ n $是预训练数据的数量，$ m $是下游任务中的数据数，通常是$ n \ gg m $。我们的证明依赖于矢量形式的rademacher复杂性链规则来拆卸复合函数类别和修改的自我符合条件。这些技术可能具有独立的兴趣。

这项调查旨在提供线性模型及其背后的理论的介绍。我们的目标是对读者进行严格的介绍，并事先接触普通最小二乘。在机器学习中，输出通常是输入的非线性函数。深度学习甚至旨在找到需要大量计算的许多层的非线性依赖性。但是，这些算法中的大多数都基于简单的线性模型。然后，我们从不同视图中描述线性模型，并找到模型背后的属性和理论。线性模型是回归问题中的主要技术，其主要工具是最小平方近似，可最大程度地减少平方误差之和。当我们有兴趣找到回归函数时，这是一个自然的选择，该回归函数可以最大程度地减少相应的预期平方误差。这项调查主要是目的的摘要，即线性模型背后的重要理论的重要性，例如分布理论，最小方差估计器。我们首先从三种不同的角度描述了普通的最小二乘，我们会以随机噪声和高斯噪声干扰模型。通过高斯噪声，该模型产生了可能性，因此我们引入了最大似然估计器。它还通过这种高斯干扰发展了一些分布理论。最小二乘的分布理论将帮助我们回答各种问题并引入相关应用。然后，我们证明最小二乘是均值误差的最佳无偏线性模型，最重要的是，它实际上接近了理论上的极限。我们最终以贝叶斯方法及以后的线性模型结束。

Network data are ubiquitous in modern machine learning, with tasks of interest including node classification, node clustering and link prediction. A frequent approach begins by learning an Euclidean embedding of the network, to which algorithms developed for vector-valued data are applied. For large networks, embeddings are learned using stochastic gradient methods where the sub-sampling scheme can be freely chosen. Despite the strong empirical performance of such methods, they are not well understood theoretically. Our work encapsulates representation methods using a subsampling approach, such as node2vec, into a single unifying framework. We prove, under the assumption that the graph is exchangeable, that the distribution of the learned embedding vectors asymptotically decouples. Moreover, we characterize the asymptotic distribution and provided rates of convergence, in terms of the latent parameters, which includes the choice of loss function and the embedding dimension. This provides a theoretical foundation to understand what the embedding vectors represent and how well these methods perform on downstream tasks. Notably, we observe that typically used loss functions may lead to shortcomings, such as a lack of Fisher consistency.

Classical asymptotic theory for statistical inference usually involves calibrating a statistic by fixing the dimension $d$ while letting the sample size $n$ increase to infinity. Recently, much effort has been dedicated towards understanding how these methods behave in high-dimensional settings, where $d$ and $n$ both increase to infinity together. This often leads to different inference procedures, depending on the assumptions about the dimensionality, leaving the practitioner in a bind: given a dataset with 100 samples in 20 dimensions, should they calibrate by assuming $n \gg d$, or $d/n \approx 0.2$? This paper considers the goal of dimension-agnostic inference; developing methods whose validity does not depend on any assumption on $d$ versus $n$. We introduce an approach that uses variational representations of existing test statistics along with sample splitting and self-normalization to produce a new test statistic with a Gaussian limiting distribution, regardless of how $d$ scales with $n$. The resulting statistic can be viewed as a careful modification of degenerate U-statistics, dropping diagonal blocks and retaining off-diagonal blocks. We exemplify our technique for some classical problems including one-sample mean and covariance testing, and show that our tests have minimax rate-optimal power against appropriate local alternatives. In most settings, our cross U-statistic matches the high-dimensional power of the corresponding (degenerate) U-statistic up to a $\sqrt{2}$ factor.

数据增强在大型神经网络的培训中很受欢迎；但是，目前，关于如何使用增强数据的不同算法选择之间没有明确的理论比较。在本文中，我们朝这个方向迈出了一步 - 我们首先提出了对线性回归的简单新颖的分析，该分析具有标签不变性增强，这表明数据增强一致性（DAC）本质上比对增强数据的经验风险最小化更为有效（DA- erm）。然后将分析扩展到误指定的增强（即更改标签的增强），这再次证明了DAC比DA-MERM的优点。此外，我们将分析扩展到非线性模型（例如神经网络）并呈现泛化范围。最后，我们使用CIFAR-100和WIDERESNET进行DAC和DA-MER之间的DAC和DA-MER之间进行干净和苹果对比较的实验；这些共同证明了DAC的效果。

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

尽管深元学习取得了较高的经验成功，但对过度参数化元学习的理论理解仍然有限。本文研究了广泛使用的元学习方法，模型 - 静态元学习（MAML）的概括，该方法旨在找到快速适应新任务的良好初始化。在混合线性回归模型下，我们分析了在过度参数化方案中用SGD训练的MAML的泛化特性。我们为MAML的多余风险提供上限和下限，这捕获了SGD动力学如何影响这些泛化界限。通过如此敏锐的特征，我们进一步探讨了各种学习参数如何影响过度参数化MAML的概括能力，包括明确识别典型的数据和任务分布，这些数据和任务分布可以通过过度参数化来减少概括性错误，并表征适应性学习率对过量风险和过量风险的影响早期停车时间。我们的理论发现将通过实验进一步验证。