张量，即多线性函数，是机器学习算法的基本构建块。为了训练大型数据集，通常在工人之间分配计算是普遍的做法。但是，Stragglers和其他故障会严重影响性能和整体训练时间。减轻这些故障的新型策略是使用编码计算。我们引入了一个新的指标，用于分析，称为典型的恢复阈值，该指标重点介绍了最可能的事件，并提供了新颖的分布式编码张量操作的结构，这些操作是最佳的。我们表明，我们的一般框架涵盖了许多其他计算方案和指标作为特殊情况。特别是，我们证明，当噪声的概率（即故障）等于零时，可以将恢复阈值和张量排名作为典型恢复阈值的特殊情况，从而提供无噪声计算的噪声概括为零。一个偶然的结果。这些定义远非纯粹是理论上的结构，而是使我们实现了实用的随机代码结构，即局部随机的P-ADIC合金代码，这些代码相对于措施是最佳的。我们分析了在Amazon EC2上进行的实验，并确定它们比实际上许多其他基准计算方案更快，更稳定，正如理论上所预测的那样。

编码的分布式计算已成为在大型数据集上执行梯度下降以减轻散乱者和其他故障的常见实践。本文提出了一种新的算法，该算法编码了部分导数本身，并通过对代码字上的衍生代码字进行有损压缩来优化代码，从而最大程度地提高代码字中包含的信息，同时最大程度地减少代码字之间的信息。在优化研究中观察到的事实是，在基于梯度下降的学习算法中，这是在优化研究中观察到的事实的几何后果，因为它有助于避免过度拟合和局部最小值。这与当前在分布式编码计算上进行的许多常规工作相反，该计算的重点是从工人那里恢复所有数据。第二个贡献是，编码方案的低重量性质允许进行异步梯度更新，因为该代码可以迭代地解码。即，可以立即将工人的任务更新到较大的梯度中。方向衍生物始终是方向向量的线性函数。因此，我们的框架很健壮，因为它可以将线性编码技术应用于一般的机器学习框架，例如深神经网络。

We consider distributed learning in the presence of slow and unresponsive worker nodes, referred to as stragglers. In order to mitigate the effect of stragglers, gradient coding redundantly assigns partial computations to the worker such that the overall result can be recovered from only the non-straggling workers. Gradient codes are designed to tolerate a fixed number of stragglers. Since the number of stragglers in practice is random and unknown a priori, tolerating a fixed number of stragglers can yield a sub-optimal computation load and can result in higher latency. We propose a gradient coding scheme that can tolerate a flexible number of stragglers by carefully concatenating gradient codes for different straggler tolerance. By proper task scheduling and small additional signaling, our scheme adapts the computation load of the workers to the actual number of stragglers. We analyze the latency of our proposed scheme and show that it has a significantly lower latency than gradient codes.

使用分布式学习培训具有大数据集的复杂模型的主要挑战之一是处理陷阱效果。作为解决方案，最近提出了对计算任务有效地增加了冗余的编码计算。在该技术中，跨数据集使用编码，并且计算在编码数据上完成，使得具有特定大小的工作节点的任意子集的结果足以恢复最终结果。这些方法的主要挑战是（1）它们仅限于多项式函数计算，（2）服务器子集的大小，我们需要等待数据集大小的乘法和模型复杂性的乘法（多项式的程度），其可能过大，（3）它们对实际数字的计算不是数值稳定的。在本文中，我们将Berrut近似编码计算（BACC）提出，作为替代方法，其不限于多项式函数计算。此外，主节点可以使用可用工作人员节点的任何任意子集的结果大致计算最终结果。近似方法被证明具有低计算复杂性的数值稳定。另外，理论上建立近似的准确性并通过仿真验证导致不同的设置，例如分布式学习问题。特别地，BACC用于在一组服务器上训练深度神经网络，这在收敛速率方面优于重复计算（重复编码）。

编码的计算技术为分布式计算中的贸易管理者提供鲁棒性。但是，大多数现有计划都需要精确地配置争吵行为，并忽略通过谋杀工人执行的计算。此外，这些方案通常被设计为准确地恢复所需的计算结果，而在许多机器学习和迭代优化算法中，已知更快的近似解决方案导致整体收敛时间的改善。在本文中，我们首先引入一种新的编码矩阵 - 向量乘法方案，称为组成的编码计算，其中部分恢复（CCPR），这有利于编码和未编码的计算方案的优点，并减少了计算时间和解码复杂度允许在准确性和计算速度之间进行权衡。然后，我们通过提出具有部分恢复的编码通信方案来扩展这种方法来分发更多一般计算任务，其中在传送之前编码由工人计算的子任务的结果。大型线性回归任务的数值模拟确认了所提出的分布式计算方案的优势，在计算准确性和延迟之间的权衡方面具有部分恢复。

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M . Can we complete the matrix and recover the entries that we have not seen?We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys m ≥ C n 1.2 r log n for some positive numerical constant C, then with very high probability, most n × n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets.This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed-either explicitly or implicitly-to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m × n matrix. (i) For a dense input matrix, randomized algorithms require O(mn log(k)) floating-point operations (flops) in contrast with O(mnk) for classical algorithms. (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multi-processor architectures. (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.

Crowdsourcing system has emerged as an effective platform for labeling data with relatively low cost by using non-expert workers. Inferring correct labels from multiple noisy answers on data, however, has been a challenging problem, since the quality of the answers varies widely across tasks and workers. Many existing works have assumed that there is a fixed ordering of workers in terms of their skill levels, and focused on estimating worker skills to aggregate the answers from workers with different weights. In practice, however, the worker skill changes widely across tasks, especially when the tasks are heterogeneous. In this paper, we consider a new model, called $d$-type specialization model, in which each task and worker has its own (unknown) type and the reliability of each worker can vary in the type of a given task and that of a worker. We allow that the number $d$ of types can scale in the number of tasks. In this model, we characterize the optimal sample complexity to correctly infer the labels within any given accuracy, and propose label inference algorithms achieving the order-wise optimal limit even when the types of tasks or those of workers are unknown. We conduct experiments both on synthetic and real datasets, and show that our algorithm outperforms the existing algorithms developed based on more strict model assumptions.

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

在当前的嘈杂中间尺度量子（NISQ）时代，量子机学习正在成为基于程序门的量子计算机的主要范式。在量子机学习中，对量子电路的门进行了参数化，并且参数是根据数据和电路输出的测量来通过经典优化来调整的。参数化的量子电路（PQC）可以有效地解决组合优化问题，实施概率生成模型并进行推理（分类和回归）。该专着为具有概率和线性代数背景的工程师的观众提供了量子机学习的独立介绍。它首先描述了描述量子操作和测量所必需的必要背景，概念和工具。然后，它涵盖了参数化的量子电路，变异量子本质层以及无监督和监督的量子机学习公式。

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or N -way array. Decompositions of higher-order tensors (i.e., N -way arrays with N ≥ 3) have applications in psychometrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.

我们提出了一个算法框架，用于近距离矩阵上的量子启发的经典算法，概括了Tang的突破性量子启发算法开始的一系列结果，用于推荐系统[STOC'19]。由量子线性代数算法和gily \'en，su，low和wiebe [stoc'19]的量子奇异值转换（SVT）框架[SVT）的动机[STOC'19]，我们开发了SVT的经典算法合适的量子启发的采样假设。我们的结果提供了令人信服的证据，表明在相应的QRAM数据结构输入模型中，量子SVT不会产生指数量子加速。由于量子SVT框架基本上概括了量子线性代数的所有已知技术，因此我们的结果与先前工作的采样引理相结合，足以概括所有有关取消量子机器学习算法的最新结果。特别是，我们的经典SVT框架恢复并经常改善推荐系统，主成分分析，监督聚类，支持向量机器，低秩回归和半决赛程序解决方案的取消结果。我们还为汉密尔顿低级模拟和判别分析提供了其他取消化结果。我们的改进来自识别量子启发的输入模型的关键功能，该模型是所有先前量子启发的结果的核心：$ \ ell^2 $ -Norm采样可以及时近似于其尺寸近似矩阵产品。我们将所有主要结果减少到这一事实，使我们的简洁，独立和直观。

我们在限制下研究了一阶优化算法，即使用每个维度的$ r $ bits预算进行量化下降方向，其中$ r \ in（0，\ infty）$。我们提出了具有收敛速率的计算有效优化算法，与信息理论性能匹配：（i）：（i）具有访问精确梯度甲骨文的平稳且强烈的符合目标，以及（ii）一般凸面和非平滑目标访问嘈杂的亚级别甲骨文。这些算法的关键是一种多项式复杂源编码方案，它在量化它之前将矢量嵌入随机子空间中。这些嵌入使得具有很高的概率，它们沿着转换空间的任何规范方向的投影很小。结果，量化这些嵌入，然后对原始空间进行逆变换产生一种源编码方法，具有最佳的覆盖效率，同时仅利用每个维度的$ r $ bits。我们的算法保证了位预算$ r $的任意值的最佳性，其中包括次线性预算制度（$ r <1 $），以及高预算制度（$ r \ geq 1 $），虽然需要$ o \ left（n^2 \右）$乘法，其中$ n $是尺寸。我们还提出了使用Hadamard子空间对这种编码方案的有效放松扩展以显着提高梯度稀疏方案的性能。数值模拟验证我们的理论主张。我们的实现可在https://github.com/rajarshisaha95/distoptconstrocncomm上获得。

与经典线性模型不同，非线性生成模型在统计学习的文献中被稀疏地解决。这项工作旨在引起对这些模型及其保密潜力的关注。为此，我们调用了复制方法，以在反相反的问题中得出渐近归一化的横熵，其生成模型由具有通用协方差函数的高斯随机场描述。我们的推导进一步证明了贝叶斯估计量的渐近统计解耦，并为给定的非线性模型指定了解耦设置。复制解决方案描述了严格的非线性模型建立了全有或全无的相变：存在一个关键负载，最佳贝叶斯推断从完美的学习变为不相关的学习。基于这一发现，我们设计了一种新的安全编码方案，该方案可实现窃听通道的保密能力。这个有趣的结果意味着，严格的非线性生成模型是完美的，没有任何安全编码。我们通过分析说明性模型的完全安全和可靠的推论来证明后一种陈述是合理的。

Tensor decomposition serves as a powerful primitive in statistics and machine learning. In this paper, we focus on using power iteration to decompose an overcomplete random tensor. Past work studying the properties of tensor power iteration either requires a non-trivial data-independent initialization, or is restricted to the undercomplete regime. Moreover, several papers implicitly suggest that logarithmically many iterations (in terms of the input dimension) are sufficient for the power method to recover one of the tensor components. In this paper, we analyze the dynamics of tensor power iteration from random initialization in the overcomplete regime. Surprisingly, we show that polynomially many steps are necessary for convergence of tensor power iteration to any of the true component, which refutes the previous conjecture. On the other hand, our numerical experiments suggest that tensor power iteration successfully recovers tensor components for a broad range of parameters, despite that it takes at least polynomially many steps to converge. To further complement our empirical evidence, we prove that a popular objective function for tensor decomposition is strictly increasing along the power iteration path. Our proof is based on the Gaussian conditioning technique, which has been applied to analyze the approximate message passing (AMP) algorithm. The major ingredient of our argument is a conditioning lemma that allows us to generalize AMP-type analysis to non-proportional limit and polynomially many iterations of the power method.

我们使用张量奇异值分解（T-SVD）代数框架提出了一种新的快速流算法，用于抵抗缺失的低管级张量的缺失条目。我们展示T-SVD是三阶张量的研究型块术语分解的专业化，我们在该模型下呈现了一种算法，可以跟踪从不完全流2-D数据的可自由子模块。所提出的算法使用来自子空间的基层歧管的增量梯度下降的原理，以解决线性复杂度和时间样本的恒定存储器的张量完成问题。我们为我们的算法提供了局部预期的线性收敛结果。我们的经验结果在精确态度上具有竞争力，但在计算时间内比实际应用上的最先进的张量完成算法更快，以在有限的采样下恢复时间化疗和MRI数据。

Suppose we are given an $n$-dimensional order-3 symmetric tensor $T \in (\mathbb{R}^n)^{\otimes 3}$ that is the sum of $r$ random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when $r \lesssim n^2$ but polynomial-time algorithms are only known in the regime $r \ll n^{3/2}$. Similar "statistical-computational gaps" occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a "planted versus null" testing problem. We consider a model for random order-3 tensor decomposition where one component is slightly larger in norm than the rest (to break symmetry), and the components are drawn uniformly from the hypercube. We resolve the computational complexity in the LDP model: $O(\log n)$-degree polynomial functions of the tensor entries can accurately estimate the largest component when $r \ll n^{3/2}$ but fail to do so when $r \gg n^{3/2}$. This provides rigorous evidence suggesting that the best known algorithms for tensor decomposition cannot be improved, at least by known approaches. A natural extension of the result holds for tensors of any fixed order $k \ge 3$, in which case the LDP threshold is $r \sim n^{k/2}$.

恢复来自简单测量的稀疏向量的支持是一个广泛研究的问题，考虑在压缩传感，1位压缩感测和更通用的单一索引模型下。我们考虑这个问题的概括：线性回归的混合物，以及线性分类器的混合物，其中目标是仅使用少量可能嘈杂的线性和1位测量来恢复多个稀疏载体的支持。关键挑战是，来自不同载体的测量是随机混合的。最近也接受了这两个问题。在线性分类器的混合物中，观察结果对应于查询的超平面侧随机未知向量，而在线性回归的混合物中，我们观察在查询的超平面上的随机未知向量的投影。从混合物中回收未知载体的主要步骤是首先识别所有单个组分载体的支持。在这项工作中，我们研究了足以在这两种模型中恢复混合物中所有组件向量的支持的测量数量。我们提供使用$ k，\ log n $和准多项式在$ \ ell $中使用多项式多项式的算法，以恢复在每个人的高概率中恢复所有$ \ ell $未知向量的支持组件是$ k $ -parse $ n $ -dimensional向量。

本文在对数损耗保真度下调查了多终端源编码问题，这不一定导致添加性失真度量。该问题是通过信息瓶颈方法的扩展到多源场景的激励，其中多个编码器必须构建其来源的协同速率限制描述，以便最大化关于其他未观察的（隐藏的）源的信息。更确切地说，我们研究所谓的基本信息 - 理论极限：（i）双向协同信息瓶颈（TW-CIB）和（ii）协同分布式信息瓶颈（CDIB）问题。 TW-CIB问题由两个遥远的编码器分开观察边缘（依赖）组件$ X_1 $和$ X_2 $，并且可以通过有关隐藏变量的信息提取信息的目的进行有限信息的多个交换机（Y_1，Y_2）$ ，它可以任意依赖于$（X_1，X_2）$。另一方面，在CDIB中，有两个合作的编码器，分别观察$ x_1 $和$ x_2 $和第三个节点，它可以侦听两个编码器之间的交换，以便获取有关隐藏变量$ y $的信息。根据标准化（每个样本）多字母互信息度量（对数损耗保真度）来测量的相关性（图 - 优点），并且通过限制描述的复杂性来产生一个有趣的权衡，从而测量编码器和解码器之间的交换所需的费率。内部和外界与这些问题的复杂性相关区域的衍生自特征从哪个感兴趣的案例的特征在于。我们所产生的理论复杂性相关区域最终针对二进制对称和高斯统计模型进行评估。