我们研究了称为“乐观速率”（Panchenko 2002; Srebro等，2010）的统一收敛概念，用于与高斯数据的线性回归。我们的精致分析避免了现有结果中的隐藏常量和对数因子，这已知在高维设置中至关重要，特别是用于了解插值学习。作为一个特殊情况，我们的分析恢复了Koehler等人的保证。（2021年），在良性过度的过度条件下，严格地表征了低规范内插器的人口风险。但是，我们的乐观速度绑定还分析了具有任意训练错误的预测因子。这使我们能够在随机设计下恢复脊和套索回归的一些经典统计保障，并有助于我们在过度参数化制度中获得精确了解近端器的过度风险。

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

套索是一种高维回归的方法，当时，当协变量$ p $的订单数量或大于观测值$ n $时，通常使用它。由于两个基本原因，经典的渐近态性理论不适用于该模型：$（1）$正规风险是非平滑的； $（2）$估算器$ \ wideHat {\ boldsymbol {\ theta}} $与true参数vector $ \ boldsymbol {\ theta}^*$无法忽略。结果，标准的扰动论点是渐近正态性的传统基础。另一方面，套索估计器可以精确地以$ n $和$ p $大，$ n/p $的订单为一。这种表征首先是在使用I.I.D的高斯设计的情况下获得的。协变量：在这里，我们将其推广到具有非偏差协方差结构的高斯相关设计。这是根据更简单的``固定设计''模型表示的。我们在两个模型中各种数量的分布之间的距离上建立了非反应界限，它们在合适的稀疏类别中均匀地固定在信号上$ \ boldsymbol {\ theta}^*$。作为应用程序，我们研究了借助拉索的分布，并表明需要校正程度对于计算有效的置信区间是必要的。

在负面的感知问题中，我们给出了$ n $数据点$（{\ boldsymbol x} _i，y_i）$，其中$ {\ boldsymbol x} _i $是$ d $ -densional vector和$ y_i \ in \ { + 1，-1 \} $是二进制标签。数据不是线性可分离的，因此我们满足自己的内容，以找到最大的线性分类器，具有最大的\ emph {否定}余量。换句话说，我们想找到一个单位常规矢量$ {\ boldsymbol \ theta} $，最大化$ \ min_ {i \ le n} y_i \ langle {\ boldsymbol \ theta}，{\ boldsymbol x} _i \ rangle $ 。这是一个非凸优化问题（它相当于在Polytope中找到最大标准矢量），我们在两个随机模型下研究其典型属性。我们考虑比例渐近，其中$ n，d \ to \ idty $以$ n / d \ to \ delta $，并在最大边缘$ \ kappa _ {\ text {s}}（\ delta）上证明了上限和下限）$或 - 等效 - 在其逆函数$ \ delta _ {\ text {s}}（\ kappa）$。换句话说，$ \ delta _ {\ text {s}}（\ kappa）$是overparametization阈值：以$ n / d \ le \ delta _ {\ text {s}}（\ kappa） - \ varepsilon $一个分类器实现了消失的训练错误，具有高概率，而以$ n / d \ ge \ delta _ {\ text {s}}（\ kappa）+ \ varepsilon $。我们在$ \ delta _ {\ text {s}}（\ kappa）$匹配，以$ \ kappa \ to - \ idty $匹配。然后，我们分析了线性编程算法来查找解决方案，并表征相应的阈值$ \ delta _ {\ text {lin}}（\ kappa）$。我们观察插值阈值$ \ delta _ {\ text {s}}（\ kappa）$和线性编程阈值$ \ delta _ {\ text {lin {lin}}（\ kappa）$之间的差距，提出了行为的问题其他算法。

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

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.

成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型，并且通过双下降现象和通过优化景观的结构特性，从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功，但也众所周知，这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下，它们在扰动输入（鲁棒泛化）上的性能也会比良性输入（标准概括）的最佳可达到的性能更糟糕。因此，必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中，我们将通过专注于随机特征回归模型（具有随机第一层权重的两层神经网络）来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度，其中样本量，输入维度和参数的数量彼此成比例地生长，并且当模型发生前列地训练时，可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果，表明对于普遍训练的随机特征模型，高度公正化可能会损害鲁棒泛化。

Wasserstein的分布在强大的优化方面已成为强大估计的有力框架，享受良好的样本外部性能保证，良好的正则化效果以及计算上可易处理的双重重新纠正。在这样的框架中，通过将最接近经验分布的所有概率分布中最接近的所有概率分布中最小化的最差预期损失来最大程度地减少估计量。在本文中，我们提出了一个在噪声线性测量中估算未知参数的Wasserstein分布稳定的M估计框架，我们专注于分析此类估计器的平方误差性能的重要且具有挑战性的任务。我们的研究是在现代的高维比例状态下进行的，在该状态下，环境维度和样品数量都以相对的速度进行编码，该速率以编码问题的下/过度参数化的比例。在各向同性高斯特征假设下，我们表明可以恢复平方误差作为凸 - 串联优化问题的解，令人惊讶的是，它在最多四个标量变量中都涉及。据我们所知，这是在Wasserstein分布强劲的M估计背景下研究此问题的第一项工作。

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

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.

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

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.

我们开发机器以设计有效的可计算和一致的估计，随着观察人数而达到零的估计误差，因为观察的次数增长，当面对可能损坏的答复，除了样本的所有品，除了每种量之外的ALL。作为具体示例，我们调查了两个问题：稀疏回归和主成分分析（PCA）。对于稀疏回归，我们实现了最佳样本大小的一致性$ n \ gtrsim（k \ log d）/ \ alpha ^ $和最佳错误率$ o（\ sqrt {（k \ log d）/（n \ cdot \ alpha ^ 2））$ N $是观察人数，$ D $是尺寸的数量，$ k $是参数矢量的稀疏性，允许在数量的数量中为逆多项式进行逆多项式样品。在此工作之前，已知估计是一致的，当Inliers $ \ Alpha $ IS $ O（1 / \ log \ log n）$，即使是（非球面）高斯设计矩阵时也是一致的。结果在弱设计假设下持有，并且在这种一般噪声存在下仅被D'Orsi等人最近以密集的设置（即一般线性回归）显示。 [DNS21]。在PCA的上下文中，我们在参数矩阵上的广泛尖端假设下获得最佳错误保证（通常用于矩阵完成）。以前的作品可以仅在假设下获得非琐碎的保证，即与最基于的测量噪声以$ n $（例如，具有方差1 / n ^ 2 $的高斯高斯）。为了设计我们的估算，我们用非平滑的普通方（如$ \ ell_1 $ norm或核规范）装备Huber丢失，并以一种新的方法来分析损失的新方法[DNS21]的方法[DNS21]。功能。我们的机器似乎很容易适用于各种估计问题。

在因果推理和强盗文献中，基于观察数据的线性功能估算线性功能的问题是规范的。我们分析了首先估计治疗效果函数的广泛的两阶段程序，然后使用该数量来估计线性功能。我们证明了此类过程的均方误差上的非反应性上限：这些边界表明，为了获得非反应性最佳程序，应在特定加权$ l^2 $中最大程度地估算治疗效果的误差。 -规范。我们根据该加权规范的约束回归分析了两阶段的程序，并通过匹配非轴突局部局部最小值下限，在有限样品中建立了实例依赖性最优性。这些结果表明，除了取决于渐近效率方差之外，最佳的非质子风险除了取决于样本量支持的最富有函数类别的真实结果函数与其近似类别之间的加权规范距离。

算法高斯化是一种现象，当使用随机素描或采样方法生成较小的大数据集的较小表示时，可能会出现的现象：对于某些任务，已经观察到这些草图表示表现出许多可靠的性能特征，这些性能是在数据样本中出现的，这些性能来自次高斯随机设计，是一个强大的数据分布统计模型。但是，这种现象仅研究了特定的任务和指标，或依靠计算昂贵的方法。我们通过为平均值提供用于高斯数据分布的算法框架来解决这一问题，并证明可以有效构建几乎无法区分的数据草图（与亚高斯随机设计有关的总变化距离）。特别是，依靠最近引入的素描技术称为杠杆得分稀疏（少）嵌入，我们表明一个人可以构造$ n \ times d $矩阵$ a $的$ n \ times d $ sketch of $ n \ times d $ n \ ll n $，几乎与次高斯设计几乎没有区别$ a $中的非零条目的数量。结果，可以直接适用于我们的草图框架，可直接适用于我们的草图框架。我们通过对草图最小二乘正方形的新近似保证进行了说明。

对于高维和非参数统计模型，速率最优估计器平衡平方偏差和方差是一种常见的现象。虽然这种平衡被广泛观察到，但很少知道是否存在可以避免偏差和方差之间的权衡的方法。我们提出了一般的策略，以获得对任何估计方差的下限，偏差小于预先限定的界限。这表明偏差差异折衷的程度是不可避免的，并且允许量化不服从其的方法的性能损失。该方法基于许多抽象的下限，用于涉及关于不同概率措施的预期变化以及诸如Kullback-Leibler或Chi-Sque-diversence的信息措施的变化。其中一些不平等依赖于信息矩阵的新概念。在该物品的第二部分中，将抽象的下限应用于几种统计模型，包括高斯白噪声模型，边界估计问题，高斯序列模型和高维线性回归模型。对于这些特定的统计应用，发生不同类型的偏差差异发生，其实力变化很大。对于高斯白噪声模型中集成平方偏置和集成方差之间的权衡，我们将较低界限的一般策略与减少技术相结合。这允许我们将原始问题与估计的估计器中的偏差折衷联动，以更简单的统计模型中具有额外的对称性属性。在高斯序列模型中，发生偏差差异的不同相位转换。虽然偏差和方差之间存在非平凡的相互作用，但是平方偏差的速率和方差不必平衡以实现最小估计速率。

Testing the significance of a variable or group of variables $X$ for predicting a response $Y$, given additional covariates $Z$, is a ubiquitous task in statistics. A simple but common approach is to specify a linear model, and then test whether the regression coefficient for $X$ is non-zero. However, when the model is misspecified, the test may have poor power, for example when $X$ is involved in complex interactions, or lead to many false rejections. In this work we study the problem of testing the model-free null of conditional mean independence, i.e. that the conditional mean of $Y$ given $X$ and $Z$ does not depend on $X$. We propose a simple and general framework that can leverage flexible nonparametric or machine learning methods, such as additive models or random forests, to yield both robust error control and high power. The procedure involves using these methods to perform regressions, first to estimate a form of projection of $Y$ on $X$ and $Z$ using one half of the data, and then to estimate the expected conditional covariance between this projection and $Y$ on the remaining half of the data. While the approach is general, we show that a version of our procedure using spline regression achieves what we show is the minimax optimal rate in this nonparametric testing problem. Numerical experiments demonstrate the effectiveness of our approach both in terms of maintaining Type I error control, and power, compared to several existing approaches.

This paper investigates the stability of deep ReLU neural networks for nonparametric regression under the assumption that the noise has only a finite p-th moment. We unveil how the optimal rate of convergence depends on p, the degree of smoothness and the intrinsic dimension in a class of nonparametric regression functions with hierarchical composition structure when both the adaptive Huber loss and deep ReLU neural networks are used. This optimal rate of convergence cannot be obtained by the ordinary least squares but can be achieved by the Huber loss with a properly chosen parameter that adapts to the sample size, smoothness, and moment parameters. A concentration inequality for the adaptive Huber ReLU neural network estimators with allowable optimization errors is also derived. To establish a matching lower bound within the class of neural network estimators using the Huber loss, we employ a different strategy from the traditional route: constructing a deep ReLU network estimator that has a better empirical loss than the true function and the difference between these two functions furnishes a low bound. This step is related to the Huberization bias, yet more critically to the approximability of deep ReLU networks. As a result, we also contribute some new results on the approximation theory of deep ReLU neural networks.

我们研究只有历史数据时设计最佳学习和决策制定公式的问题。先前的工作通常承诺要进行特定的数据驱动配方，并随后尝试建立样本外的性能保证。我们以相反的方式采取了相反的方法。我们首先定义一个明智的院子棒，以测量任何数据驱动的公式的质量，然后寻求找到最佳的这种配方。在非正式的情况下，可以看到任何数据驱动的公式可以平衡估计成本与实际成本的接近度的量度，同时保证了样本外的性能水平。考虑到可接受的样本外部性能水平，我们明确地构建了一个数据驱动的配方，该配方比任何其他享有相同样本外部性能的其他配方都更接近真实成本。我们展示了三种不同的样本外绩效制度（超大型制度，指数状态和次指数制度）之间存在，最佳数据驱动配方的性质会经历相变的性质。最佳数据驱动的公式可以解释为超级稳定的公式，在指数方面是一种熵分布在熵上稳健的公式，最后是次指数制度中的方差惩罚公式。这个最终的观察揭示了这三个观察之间的令人惊讶的联系，乍一看似乎是无关的，数据驱动的配方，直到现在仍然隐藏了。

Popular iterative algorithms such as boosting methods and coordinate descent on linear models converge to the maximum $\ell_1$-margin classifier, a.k.a. sparse hard-margin SVM, in high dimensional regimes where the data is linearly separable. Previous works consistently show that many estimators relying on the $\ell_1$-norm achieve improved statistical rates for hard sparse ground truths. We show that surprisingly, this adaptivity does not apply to the maximum $\ell_1$-margin classifier for a standard discriminative setting. In particular, for the noiseless setting, we prove tight upper and lower bounds for the prediction error that match existing rates of order $\frac{\|\wgt\|_1^{2/3}}{n^{1/3}}$ for general ground truths. To complete the picture, we show that when interpolating noisy observations, the error vanishes at a rate of order $\frac{1}{\sqrt{\log(d/n)}}$. We are therefore first to show benign overfitting for the maximum $\ell_1$-margin classifier.