聚类是基于它们的相似性对组对象的重要探索性数据分析技术。广泛使用的$ k $ -MEANS聚类方法依赖于一些距离的概念将数据划分为较少数量的组。在欧几里得空间中，$ k $ -Means的基于质心和基于距离的公式相同。在现代机器学习应用中，数据通常是作为概率分布而出现的，并且可以使用最佳运输指标来处理测量值数据。由于瓦斯坦斯坦空间的非负亚历山德罗夫曲率，巴里中心遭受了规律性和非舒适性问题。 Wasserstein Barycenters的特殊行为可能使基于质心的配方无法代表集群内的数据点，而基于距离的$ K $ -MEANS方法及其半决赛计划（SDP）可以恢复真实的方法集群标签。在聚集高斯分布的特殊情况下，我们表明SDP放松的Wasserstein $ k $ - 金钱可以实现精确的恢复，因为这些集群按照$ 2 $ - WASSERSTEIN MERTRIC进行了良好的分离。我们的仿真和真实数据示例还表明，基于距离的$ K $ -Means可以比基于标准的基于质心的$ k $ -Means获得更好的分类性能，用于聚类概率分布和图像。

本文介绍了一种新的基于仿真的推理程序，以对访问I.I.D. \ samples的多维概率分布进行建模和样本，从而规避明确建模密度函数或设计Markov Chain Monte Carlo的通常方法。我们提出了一个称为可逆的Gromov-monge（RGM）距离的新概念的距离和同构的动机，并研究了RGM如何用于设计新的转换样本，以执行基于模拟的推断。我们的RGM采样器还可以估计两个异质度量度量空间之间的最佳对齐$（\ cx，\ mu，c _ {\ cx}）$和$（\ cy，\ cy，\ nu，c _ {\ cy}）$从经验数据集中，估计的地图大约将一个量度$ \ mu $推向另一个$ \ nu $，反之亦然。我们研究了RGM距离的分析特性，并在轻度条件下得出RGM等于经典的Gromov-Wasserstein距离。奇怪的是，与Brenier的两极分解结合了连接，我们表明RGM采样器以$ C _ {\ cx} $和$ C _ {\ cy} $的正确选择诱导了强度同构的偏见。研究了有关诱导采样器的收敛，表示和优化问题的统计率。还展示了展示RGM采样器有效性的合成和现实示例。

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

We introduce a sketch-and-solve approach to speed up the Peng-Wei semidefinite relaxation of k-means clustering. When the data is appropriately separated we identify the k-means optimal clustering. Otherwise, our approach provides a high-confidence lower bound on the optimal k-means value. This lower bound is data-driven; it does not make any assumption on the data nor how it is generated. We provide code and an extensive set of numerical experiments where we use this approach to certify approximate optimality of clustering solutions obtained by k-means++.

假设我们在$ \ mathbb {r} ^ d $和predictor x中的响应变量y在$ \ mathbb {r} ^ d $，以便为$ d \ geq 1 $。在置换或未解释的回归中，我们可以访问x和y上的单独无序数据，而不是在通常回归中的（x，y）-pabes上的数据。到目前为止，在文献中，案件$ d = 1 $已收到关注，请参阅例如近期的纸张和杂草[信息和推理，8,619--717]和Balabdaoui等人。 [J.马赫。学习。 res，22（172），1-60]。在本文中，我们考虑使用$ d \ geq 1 $的一般多变量设置。我们表明回归函数的周期性单调性的概念足以用于置换/未解释的回归模型中的识别和估计。我们在允许的回归设置中研究置换恢复，并在基于Kiefer-WolfoItz的基于代索的计算高效且易用算法[ANN。数学。统计部。，27,887--906]非参数最大似然估计和来自最佳运输理论的技术。我们在高斯噪声的相关均方方向误差误差上提供显式上限。与之前的案件的工作$ d = 1 $一样，置换/未解释的设置涉及潜在的解卷积问题的慢速（对数）收敛率。数值研究证实了我们的理论分析，并表明所提出的方法至少根据上述事先工作中的方法进行了比例，同时在计算复杂性方面取得了大量减少。

In this paper, we propose Wasserstein Isometric Mapping (Wassmap), a nonlinear dimensionality reduction technique that provides solutions to some drawbacks in existing global nonlinear dimensionality reduction algorithms in imaging applications. Wassmap represents images via probability measures in Wasserstein space, then uses pairwise Wasserstein distances between the associated measures to produce a low-dimensional, approximately isometric embedding. We show that the algorithm is able to exactly recover parameters of some image manifolds including those generated by translations or dilations of a fixed generating measure. Additionally, we show that a discrete version of the algorithm retrieves parameters from manifolds generated from discrete measures by providing a theoretical bridge to transfer recovery results from functional data to discrete data. Testing of the proposed algorithms on various image data manifolds show that Wassmap yields good embeddings compared with other global and local techniques.

比较概率分布是许多机器学习算法的关键。最大平均差异（MMD）和最佳运输距离（OT）是在过去几年吸引丰富的关注的概率措施之间的两类距离。本文建立了一些条件，可以通过MMD规范控制Wassersein距离。我们的作品受到压缩统计学习（CSL）理论的推动，资源有效的大规模学习的一般框架，其中训练数据总结在单个向量（称为草图）中，该训练数据捕获与所考虑的学习任务相关的信息。在CSL中的现有结果启发，我们介绍了H \“较旧的较低限制的等距属性（H \”较旧的LRIP）并表明这家属性具有有趣的保证对压缩统计学习。基于MMD与Wassersein距离之间的关系，我们通过引入和研究学习任务的Wassersein可读性的概念来提供压缩统计学习的保证，即概率分布之间的某些特定于特定的特定度量，可以由Wassersein界定距离。

Projection robust Wasserstein (PRW) distance, or Wasserstein projection pursuit (WPP), is a robust variant of the Wasserstein distance. Recent work suggests that this quantity is more robust than the standard Wasserstein distance, in particular when comparing probability measures in high-dimensions. However, it is ruled out for practical application because the optimization model is essentially non-convex and non-smooth which makes the computation intractable. Our contribution in this paper is to revisit the original motivation behind WPP/PRW, but take the hard route of showing that, despite its non-convexity and lack of nonsmoothness, and even despite some hardness results proved by~\citet{Niles-2019-Estimation} in a minimax sense, the original formulation for PRW/WPP \textit{can} be efficiently computed in practice using Riemannian optimization, yielding in relevant cases better behavior than its convex relaxation. More specifically, we provide three simple algorithms with solid theoretical guarantee on their complexity bound (one in the appendix), and demonstrate their effectiveness and efficiency by conducing extensive experiments on synthetic and real data. This paper provides a first step into a computational theory of the PRW distance and provides the links between optimal transport and Riemannian optimization.

本文考虑了Barycentric编码模型（BCM）下的测量估计问题，其中假定未知的度量属于有限的已知测量集的Wasserstein-2 Barycenters集合。估计该模型下的度量等同于估计未知的Barycentric坐标。我们为BCM下的测量估计提供了新颖的几何，统计和计算见解，由三个主要结果组成。我们的第一个主要结果利用了Wasserstein-2空间的Riemannian几何形状，以提供恢复Barycentric坐标的程序，作为假设对真实参考度量访问的二次优化问题的解决方案。基本的几何见解是，该二次问题的参数是由从给定度量到定义BCM的参考度量的最佳位移图之间的内部产物确定的。然后，我们的第二个主要结果建立了一种算法，用于求解BCM中坐标的算法，当时通过I.I.D进行经验观察到所有测量。样品。我们证明了该算法的精确收敛速率 - 取决于基本措施的平稳性及其维度 - 从而保证其统计一致性。最后，我们证明了BCM和相关估计程序在三个应用领域的实用性：（i）高斯措施的协方差估计； （ii）图像处理； （iii）自然语言处理。

变性推理（VI）为基于传统的采样方法提供了一种吸引人的替代方法，用于实施贝叶斯推断，因为其概念性的简单性，统计准确性和计算可扩展性。然而，常见的变分近似方案（例如平均场（MF）近似）需要某些共轭结构以促进有效的计算，这可能会增加不必要的限制对可行的先验分布家族，并对变异近似族对差异进行进一步的限制。在这项工作中，我们开发了一个通用计算框架，用于实施MF-VI VIA WASSERSTEIN梯度流（WGF），这是概率度量空间上的梯度流。当专门针对贝叶斯潜在变量模型时，我们将分析基于时间消化的WGF交替最小化方案的算法收敛，用于实现MF近似。特别是，所提出的算法类似于EM算法的分布版本，包括更新潜在变量变异分布的E step以及在参数的变异分布上进行最陡峭下降的m step。我们的理论分析依赖于概率度量空间中的最佳运输理论和细分微积分。我们证明了时间限制的WGF的指数收敛性，以最大程度地减少普通大地测量学严格的凸度的通用物镜功能。我们还提供了通过使用时间限制的WGF的固定点方程从MF近似获得的变异分布的指数收缩的新证明。我们将方法和理论应用于两个经典的贝叶斯潜在变量模型，即高斯混合模型和回归模型的混合物。还进行了数值实验，以补充这两个模型下的理论发现。

我们使用运输公制（Delon和Desolneux 2020）中的单变量高斯混合物中的任意度量空间$ \ MATHCAL {X} $研究数据表示。我们得出了由称为\ emph {Probabilistic Transfersers}的小神经网络实现的特征图的保证。我们的保证是记忆类型：我们证明了深度约为$ n \ log（n）$的概率变压器和大约$ n^2 $ can bi-h \'{o} lder嵌入任何$ n $ - 点数据集从低度量失真的$ \ Mathcal {x} $，从而避免了维数的诅咒。我们进一步得出了概率的bi-lipschitz保证，可以兑换失真量和随机选择的点与该失真的随机选择点的可能性。如果$ \ MATHCAL {X} $的几何形状足够规律，那么我们可以为数据集中的所有点获得更强的Bi-Lipschitz保证。作为应用程序，我们从Riemannian歧管，指标和某些类型的数据集中获得了神经嵌入保证金组合图。

We study a multi-factor block model for variable clustering and connect it to the regularized subspace clustering by formulating a distributionally robust version of the nodewise regression. To solve the latter problem, we derive a convex relaxation, provide guidance on selecting the size of the robust region, and hence the regularization weighting parameter, based on the data, and propose an ADMM algorithm for implementation. We validate our method in an extensive simulation study. Finally, we propose and apply a variant of our method to stock return data, obtain interpretable clusters that facilitate portfolio selection and compare its out-of-sample performance with other clustering methods in an empirical study.

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

社区检测和正交组同步是科学和工程中各种重要应用的基本问题。在这项工作中，我们考虑了社区检测和正交组同步的联合问题，旨在恢复社区并同时执行同步。为此，我们提出了一种简单的算法，该算法由频谱分解步骤组成，然后是彼此枢转的QR分解（CPQR）。所提出的算法与数据点数线性有效且缩放。我们还利用最近开发的“休闲一淘汰”技术来建立近乎最佳保证，以确切地恢复集群成员资格，并稳定地恢复正交变换。数值实验证明了我们算法的效率和功效，并确认了我们的理论表征。

我们研究无限制的黎曼优化的免投影方法。特别是，我们提出了黎曼弗兰克 - 沃尔夫（RFW）方法。我们将RFW的非渐近收敛率分析为最佳（高音）凸起问题，以及非凸起目标的临界点。我们还提出了一种实用的设置，其中RFW可以获得线性收敛速度。作为一个具体的例子，我们将RFW专用于正定矩阵的歧管，并将其应用于两个任务：（i）计算矩阵几何平均值（riemannian质心）; （ii）计算Bures-Wasserstein重心。这两个任务都涉及大量凸间间隔约束，为此，我们表明RFW要求的Riemannian“线性”Oracle承认了闭合形式的解决方案;该结果可能是独立的兴趣。我们进一步专门从事RFW到特殊正交组，并表明这里也可以以封闭形式解决riemannian“线性”甲骨文。在这里，我们描述了数据矩阵同步的应用程序（促使问题）。我们补充了我们的理论结果，并对RFW对最先进的riemananian优化方法进行了实证比较，并观察到RFW竞争性地对计算黎曼心质的任务进行竞争性。

信息技术的进步导致了非常大的数据集，通常保存在不同的存储中心。必须适于现有的统计方法来克服所产生的计算障碍，同时保持统计有效性和效率。分裂和征服方法已应用于许多领域，包括分位式流程，回归分析，主偶数和指数家庭。我们研究了有限高斯混合的分布式学习的分裂和征服方法。我们建议减少策略并开发一种有效的MM算法。新估计器显示在某些一般条件下保持一致并保留根 - N一致性。基于模拟和现实世界数据的实验表明，如果后者是可行的，所提出的分离和征管方法具有基于完整数据集的全球估计的统计性能。如果模型假设与真实数据不匹配，甚至可以略高于全局估算器。它还具有比某些现有方法更好的统计和计算性能。

本文考虑了一个规范聚类问题，其中一个人从两个椭圆分布的平衡混合物中获取未标记的样本，并旨在估计标签的分类器。许多流行的方法包括PCA和K-Meanse需要混合物的各个组分在稍微球形，并且在拉伸时表现不佳。为了克服这个问题，我们提出了一个非凸面的程序寻求仿射变换，将数据转换为一维点云集中在$ -1 $和1美元之后，之后群集变得容易。我们的理论贡献是两倍：（1）我们表明，当样品大小超过维度的一些恒定倍数时，非凸损耗功能表现出理想的几何特性，以及（2）我们利用这一点，以证明这是一个有效的第一 - 订单算法在没有良好的初始化的情况下实现了近最佳统计精度。我们还提出了一般的方法，用于聚类，具有灵活的特征变换和损失目标。

我们研究了基于分布强大的机会约束的对抗性分类模型。我们表明，在Wasserstein模糊性下，该模型旨在最大限度地减少距离分类距离的条件值 - 风险，并且我们探讨了前面提出的对抗性分类模型和最大限度的分类机的链接。我们还提供了用于线性分类的分布鲁棒模型的重构，并且表明它相当于最小化正则化斜坡损失目标。数值实验表明，尽管这种配方的非凸起，但是标准的下降方法似乎会聚到全球最小值器。灵感来自这种观察，我们表明，对于某一类分布，正则化斜坡损失最小化问题的唯一静止点是全球最小化器。

混合模型的学习可以看作是聚类问题。实际上，给定根据分布混合物独立生成的数据样本，我们经常希望根据样品的{\ IT正确靶向群集}，根据它们从哪个组件分布中生成的样品。对于聚类问题，从业人员通常选择使用简单的$ k $ -MEANS算法。 $ k $ -Means试图找到一个{\ it最佳聚类}，该{\ it clustering}将每个点与其群集中心之间的平方距离最小化。在本文中，我们考虑通过优化方形距离获得的解决方案（群集）的基本（即信息理论）极限。特别是，假设数据样本是从球形高斯分布的混合物中生成的，我们为任何最佳聚类和正确的目标聚类提供了足够的条件。我们还将结果概括为对数符号分布。此外，我们表明，在混合模型上相似甚至较弱的条件下，具有降低尺寸的样品的任何最佳聚类也接近正确的目标群集。这些结果为$ k $ -Means（有或没有降低尺寸降低）的信息提供了直觉，作为学习混合模型的算法。

现代高维方法经常采用“休稀稀物”的原则，而在监督多元学习统计学中可能面临着大量非零系数的“密集”问题。本文提出了一种新的聚类减少秩（CRL）框架，其施加了两个联合矩阵规范化，以自动分组构建预测因素的特征。 CRL比低级别建模更具可解释，并放松变量选择中的严格稀疏假设。在本文中，提出了新的信息 - 理论限制，揭示了寻求集群的内在成本，以及多元学习中的维度的祝福。此外，开发了一种有效的优化算法，其执行子空间学习和具有保证融合的聚类。所获得的定点估计器虽然不一定是全局最佳的，但在某些规则条件下享有超出标准似然设置的所需的统计准确性。此外，提出了一种新的信息标准，以及其无垢形式，用于集群和秩选择，并且具有严格的理论支持，而不假设无限的样本大小。广泛的模拟和实数据实验证明了所提出的方法的统计准确性和可解释性。