我们在具有固定设计的高维错误设置中分析主组件回归（PCR）。在适当的条件下，我们表明PCR始终以最小$ \ ell_2 $ -norm识别唯一模型，并且是最小的最佳模型。这些结果使我们能够建立非质子化的样本外预测，以确保提高最著名的速率。在我们的分析中，我们在样本外协变量之间引入了天然的线性代数条件，这使我们能够避免分布假设。我们的模拟说明了即使在协变量转移的情况下，这种条件对于概括的重要性。作为副产品，我们的结果还导致了合成控制文献的新结果，这是政策评估的主要方法。特别是，我们的minimax结果表明，在众多变体中，基于PCR的方法具有吸引力。据我们所知，我们对固定设计设置的预测保证在高维错误和合成控制文献中都是难以捉摸的。

即使是最精确的经济数据集也具有嘈杂，丢失，离散化或私有化的变量。实证研究的标准工作流程涉及数据清理，然后是数据分析，通常忽略数据清洁的偏差和方差后果。我们制定了具有损坏数据的因果推理的半造型模型，以包括数据清洁和数据分析。我们提出了一种新的数据清洁，估计和推理的新的端到端程序，以及数据清洁调整的置信区间。通过有限的示例参数，我们证明了因果关系参数的估算器的一致性，高斯近似和半游戏效率。 Gaussian近似的速率为N ^ { - 1/2} $，如平均治疗效果，如平均治疗效果，并且优雅地为当地参数劣化，例如特定人口统计的异构治疗效果。我们的关键假设是真正的协变量是较低的等级。在我们的分析中，我们为矩阵完成，统计学习和半统计统计提供了非对症的理论贡献。我们验证了数据清洁调整的置信区间隔的覆盖范围校准，以类似于2020年美国人口普查中实施的差异隐私。

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

随机奇异值分解（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的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

近似消息传递（AMP）是解决高维统计问题的有效迭代范式。但是，当迭代次数超过$ o \ big（\ frac {\ log n} {\ log log \ log \ log n} \时big）$（带有$ n $问题维度）。为了解决这一不足，本文开发了一个非吸附框架，用于理解峰值矩阵估计中的AMP。基于AMP更新的新分解和可控的残差项，我们布置了一个分析配方，以表征在存在独立初始化的情况下AMP的有限样本行为，该过程被进一步概括以进行光谱初始化。作为提出的分析配方的两个具体后果：（i）求解$ \ mathbb {z} _2 $同步时，我们预测了频谱初始化AMP的行为，最高为$ o \ big（\ frac {n} {\ mathrm {\ mathrm { poly} \ log n} \ big）$迭代，表明该算法成功而无需随后的细化阶段（如最近由\ citet {celentano2021local}推测）; （ii）我们表征了稀疏PCA中AMP的非反应性行为（在尖刺的Wigner模型中），以广泛的信噪比。

特征向量扰动分析在各种数据科学应用中起着至关重要的作用。然而，大量的先前作品着重于建立$ \ ell_ {2} $ eigenVector扰动边界，这些范围通常在解决依赖特征向量的细粒度行为的任务方面非常不足。本文通过研究未知特征向量的线性函数的扰动来取得进展。在存在高斯噪声的情况下，着重于两个基本问题 - 矩阵denoising和主成分分析 - 我们开发了一个统计理论的套件，该理论表征了未知特征向量的任意线性函数的扰动。为了减轻自然``插件''估计器固有的不可忽略的偏见问题，我们开发了偏低的估计器，即（1）（1）为场景家庭实现最小的下限（模仿某些对数因素），并且（2）可以以数据驱动的方式计算，而无需样品分裂。值得注意的是，即使相关的特征间隙{\ em少于先前的统计理论所要求的，提出的估计器几乎是最佳的最佳选择。

我们介绍和分析了多元奇异频谱分析（MSSA）的变体，这是一种流行的时间序列方法，用于启用和预测多元时间序列。在我们介绍的时空因素模型下，给定$ n $时间序列和$ t $观测时间序列，我们为插补和样本外预测均有效地扩展为$ 1 / \ sqrt，为预测和样本预测有效地缩放均值{\ min（n，t）t} $。这是一个改进：（i）$ 1 /\ sqrt {t} $ SSA的错误缩放，MSSA限制对单变量时间序列； （ii）$ 1/\ min（n，t）$对于不利用数据中时间结构的矩阵估计方法的错误缩放。我们引入的时空模型包括：谐波，多项式，可区分的周期函数和持有人连续函数的任何有限总和和产物。在时空因素模型下，我们的样本外预测结果可能对在线学习具有独立的兴趣。从经验上讲，在基准数据集上，我们的MSSA变体通过最先进的神经网络时间序列方法（例如，DEEPAR，LSTM）竞争性能，并且明显优于诸如矢量自动化（VAR）之类的经典方法。最后，我们提出了MSSA的扩展：（i）估计时间序列的时变差异的变体； （ii）一种张量变体，对于$ n $和$ t $的某些制度具有更好的样本复杂性。

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

在本文中，我们利用过度参数化来设计高维单索索引模型的无规矩算法，并为诱导的隐式正则化现象提供理论保证。具体而言，我们研究了链路功能是非线性且未知的矢量和矩阵单索引模型，信号参数是稀疏向量或低秩对称矩阵，并且响应变量可以是重尾的。为了更好地理解隐含正规化的角色而没有过度的技术性，我们假设协变量的分布是先验的。对于载体和矩阵设置，我们通过采用分数函数变换和专为重尾数据的强大截断步骤来构造过度参数化最小二乘损耗功能。我们建议通过将无规则化的梯度下降应用于损耗函数来估计真实参数。当初始化接近原点并且步骤中足够小时，我们证明了所获得的解决方案在载体和矩阵案件中实现了最小的收敛统计速率。此外，我们的实验结果支持我们的理论调查结果，并表明我们的方法在$ \ ell_2 $ -staticatisticated率和变量选择一致性方面具有明确的正则化的经验卓越。

Higher-order multiway data is ubiquitous in machine learning and statistics and often exhibits community-like structures, where each component (node) along each different mode has a community membership associated with it. In this paper we propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel positing that memberships need not be discrete, but instead are convex combinations of latent communities. We establish the identifiability of our model and propose a computationally efficient estimation procedure based on the higher-order orthogonal iteration algorithm (HOOI) for tensor SVD composed with a simplex corner-finding algorithm. We then demonstrate the consistency of our estimation procedure by providing a per-node error bound, which showcases the effect of higher-order structures on estimation accuracy. To prove our consistency result, we develop the $\ell_{2,\infty}$ tensor perturbation bound for HOOI under independent, possibly heteroskedastic, subgaussian noise that may be of independent interest. Our analysis uses a novel leave-one-out construction for the iterates, and our bounds depend only on spectral properties of the underlying low-rank tensor under nearly optimal signal-to-noise ratio conditions such that tensor SVD is computationally feasible. Whereas other leave-one-out analyses typically focus on sequences constructed by analyzing the output of a given algorithm with a small part of the noise removed, our leave-one-out analysis constructions use both the previous iterates and the additional tensor structure to eliminate a potential additional source of error. Finally, we apply our methodology to real and simulated data, including applications to two flight datasets and a trade network dataset, demonstrating some effects not identifiable from the model with discrete community memberships.

本文研究了聚类基质值观测值的计算和统计限制。我们提出了一个低级别的混合模型（LRMM），该模型适用于经典的高斯混合模型（GMM）来处理基质值观测值，该观测值假设人口中心矩阵的低级别。通过集成Lloyd算法和低级近似值设计了一种计算有效的聚类方法。一旦定位良好，该算法将快速收敛并达到最小值最佳的指数型聚类错误率。同时，我们表明一种基于张量的光谱方法可提供良好的初始聚类。与GMM相当，最小值最佳聚类错误率是由分离强度（即种群中心矩阵之间的最小距离）决定的。通过利用低级度，提出的算法对分离强度的要求较弱。但是，与GMM不同，LRMM的统计难度和计算难度的特征是信号强度，即最小的人口中心矩阵的非零奇异值。提供了证据表明，即使信号强度不够强，即使分离强度很强，也没有多项式时间算法是一致的。在高斯以下噪声下进一步证明了我们低级劳埃德算法的性能。讨论了LRMM下估计和聚类之间的有趣差异。通过全面的仿真实验证实了低级劳埃德算法的优点。最后，我们的方法在现实世界数据集的文献中优于其他方法。

我们开发机器以设计有效的可计算和一致的估计，随着观察人数而达到零的估计误差，因为观察的次数增长，当面对可能损坏的答复，除了样本的所有品，除了每种量之外的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]。功能。我们的机器似乎很容易适用于各种估计问题。

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

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.

本文为信号去噪提供了一般交叉验证框架。然后将一般框架应用于非参数回归方法，例如趋势过滤和二元推车。然后显示所得到的交叉验证版本以获得最佳调谐的类似物所熟知的几乎相同的收敛速度。没有任何先前的趋势过滤或二元推车的理论分析。为了说明框架的一般性，我们还提出并研究了两个基本估算器的交叉验证版本;套索用于高维线性回归和矩阵估计的奇异值阈值阈值。我们的一般框架是由Chatterjee和Jafarov（2015）的想法的启发，并且可能适用于使用调整参数的广泛估算方法。

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

This paper studies the quantization of heavy-tailed data in some fundamental statistical estimation problems, where the underlying distributions have bounded moments of some order. We propose to truncate and properly dither the data prior to a uniform quantization. Our major standpoint is that (near) minimax rates of estimation error are achievable merely from the quantized data produced by the proposed scheme. In particular, concrete results are worked out for covariance estimation, compressed sensing, and matrix completion, all agreeing that the quantization only slightly worsens the multiplicative factor. Besides, we study compressed sensing where both covariate (i.e., sensing vector) and response are quantized. Under covariate quantization, although our recovery program is non-convex because the covariance matrix estimator lacks positive semi-definiteness, all local minimizers are proved to enjoy near optimal error bound. Moreover, by the concentration inequality of product process and covering argument, we establish near minimax uniform recovery guarantee for quantized compressed sensing with heavy-tailed noise.

We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an additive $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.

This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the 1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.

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