在本文中，我们提出了一个自然的单个偏好（IP）稳定性的概念，该概念要求每个数据点平均更接近其自身集群中的点，而不是其他群集中的点。我们的概念可以从几个角度的动机，包括游戏理论和算法公平。我们研究了与我们提出的概念有关的几个问题。我们首先表明，确定给定数据集通常允许进行IP稳定的聚类通常是NP-HARD。结果，我们探索了在某些受限度量空间中查找IP稳定聚类的有效算法的设计。我们提出了一种poly Time算法，以在实际线路上找到满足精确IP稳定性的聚类，并有效地算法来找到针对树度量的IP稳定2聚类。我们还考虑放松稳定性约束，即，与其他任何集群相比，每个数据点都不应太远。在这种情况下，我们提供具有不同保证的多时间算法。我们在实际数据集上评估了一些算法和几种标准聚类方法。

我们重新审视了Chierichetti等人首先引入的公平聚类问题，该问题要求每个受保护的属性在每个集群中具有近似平等的表示。即，余额财产。现有的公平聚类解决方案要么是不可扩展的，要么无法在聚类目标和公平之间实现最佳权衡。在本文中，我们提出了一种新的公平概念，我们称之为$ tau $ $ $ - fair公平，严格概括了余额财产，并实现了良好的效率与公平折衷。此外，我们表明，简单的基于贪婪的圆形算法有效地实现了这一权衡。在更一般的多价受保护属性的设置下，我们严格地分析了算法的理论特性。我们的实验结果表明，所提出的解决方案的表现优于所有最新算法，即使对于大量簇，也可以很好地工作。

本文展示了如何适应$ k $ -MEANS问题的几种简单和经典的基于采样的算法，以使用离群值设置。最近，Bhaskara等人。 （Neurips 2019）展示了如何将古典$ K $ -MEANS ++算法适应与异常值的设置。但是，他们的算法需要输出$ o（\ log（k）\ cdot z）$ outiers，其中$ z $是true Outliers的数量，以匹配$ o（\ log k）$ - 近似值的$ k的近似保证$ -Means ++。在本文中，我们以他们的想法为基础，并展示了如何适应几个顺序和分布式的$ k $ - 均值算法，但使用离群值来设置，但具有更强的理论保证：我们的算法输出$（1+ \ VAREPSILON）z $ OUTLIERS Z $ OUTLIERS在实现$ o（1 / \ varepsilon）$ - 近似目标函数的同时。在顺序世界中，我们通过改编Lattanzi和Sohler的最新算法来实现这一目标（ICML 2019）。在分布式设置中，我们适应了Guha等人的简单算法。 （IEEE Trans。知道和数据工程2003）以及Bahmani等人的流行$ K $ -Means $ \ | $。 （PVLDB 2012）。我们技术的理论应用是一种具有运行时间$ \ tilde {o}（nk^2/z）$的算法，假设$ k \ ll z \ ll n $。这与Omacle模型中此问题的$ \ Omega（NK^2/z）$的匹配下限相互补。

分层聚类研究将数据集的递归分区设置为连续较小尺寸的簇，并且是数据分析中的基本问题。在这项工作中，我们研究了Dasgupta引入的分层聚类的成本函数，并呈现了两个多项式时间近似算法：我们的第一个结果是高度电导率图的$ O（1）$ - 近似算法。我们简单的建筑绕过了在文献中已知的稀疏切割的复杂递归常规。我们的第二个和主要结果是一个US（1）$ - 用于展示群集明确结构的宽族图形的近似算法。该结果推出了以前的最先进的，该现有技术仅适用于从随机模型产生的图表。通过对合成和现实世界数据集的实证分析，我们所呈现的算法的实证分析表明了我们的工作的重要性，以其具有明确定义的集群结构的先前所提出的图表算法。

我们提供了一个新的双标准$ \ tilde {o}（\ log ^ 2 k）$竞争算法，可解释$ k $ -means群集。最近解释了$ k $ -means最近由Dasgupta，Frost，Moshkovitz和Rashtchian（ICML 2020）引入。它由易于解释和理解（阈值）决策树或图表描述。可解释的$ k $ -means集群的成本等于其集群成本的总和;每个群集的成本等于从群集中点到该群集的中心的平方距离之和。我们的随机双标准算法构造了一个阈值决策树，将数据设置为$（1+ \ delta）k $群集（其中$ \ delta \ In（0,1）$是算法的参数）。此群集的成本是大多数$ \ tilde {o}（1 / \ delta \ cdot \ log ^ 2 k）$乘以最佳不受约束$ k $ -means群集的成本。我们表明这一界限几乎是最佳的。

K-MEDIAN和K-MEACE是聚类算法的两个最受欢迎的目标。尽管有密集的努力，但对这些目标的近似性很好地了解，特别是在$ \ ell_p $ -metrics中，仍然是一个重大的开放问题。在本文中，我们在$ \ ell_p $ -metrics中显着提高了文献中已知的近似因素的硬度。我们介绍了一个名为Johnson覆盖假说（JCH）的新假设，这大致断言设定系统上的良好的Max K-Coverage问题难以近似于1-1 / e，即使是成员图形设置系统是Johnson图的子图。然后，我们展示了Cohen-Addad和Karthik引入的嵌入技术的概括（Focs'19），JCH意味着K-MEDIAN和K-MERION在$ \ ell_p $ -metrics中的近似结果的近似值的硬度为近距离对于一般指标获得的人。特别地，假设JCH我们表明很难近似K-Meator目标：$ \ Bullet $离散情况：$ \ ell_1 $ 3.94 - $ \ ell_2中的1.73因素为1.73倍$$ - 这分别在UGC下获得了1.56和1.17的先前因子。 $ \ bullet $持续案例：$ \ ell_1 $ 2210 - $ \ ell_2 $的$ \ ell_1 $ 210。$ \ ell_2 $-metric;这在UGC下获得的$ \ ell_2 $的$ \ ell_2 $的先前因子提高了1.07。对于K-Median目标，我们还获得了类似的改进。此外，我们使用Dinure等人的工作证明了JCH的弱版本。 （Sicomp'05）在超图顶点封面上，恢复Cohen-Addad和Karthik（Focs'19 Focs'19）上面的所有结果（近）相同的不可识别因素，但现在在标准的NP $ \ NEQ $ P假设下（代替UGC）。

图形上的分层聚类是数据挖掘和机器学习中的一项基本任务，并在系统发育学，社交网络分析和信息检索等领域中进行了应用。具体而言，我们考虑了由于Dasgupta引起的层次聚类的最近普及的目标函数。以前（大约）最小化此目标函数的算法需要线性时间/空间复杂性。在许多应用程序中，底层图的大小可能很大，即使使用线性时间/空间算法，也可以在计算上具有挑战性。结果，人们对设计只能使用sublinear资源执行全局计算的算法有浓厚的兴趣。这项工作的重点是在三个经过良好的sublinear计算模型下研究大量图的层次聚类，分别侧重于时空，时间和通信，作为要优化的主要资源：（1）（动态）流模型。边缘作为流，（2）查询模型表示，其中使用邻居和度查询查询图形，（3）MPC模型，其中图边缘通过通信通道连接的几台机器进行了分区。我们在上面的所有三个模型中设计用于层次聚类的sublinear算法。我们算法结果的核心是图表中的剪切方面的视图，这使我们能够使用宽松的剪刀示意图进行分层聚类，同时仅引入目标函数中的较小失真。然后，我们的主要算法贡献是如何在查询模型和MPC模型中有效地构建所需形式的切割稀疏器。我们通过建立几乎匹配的下限来补充我们的算法结果，该界限排除了在每个模型中设计更好的算法的可能性。

在使用提供明确定义的隐私保证的用户数据时，至关重要。在这项工作中，我们旨在与第三方私下操纵和分享整个稀疏数据集。实际上，差异隐私已成为隐私的黄金标准，但是，当涉及到稀疏数据集时，作为我们的主要结果之一，我们证明\ emph {any}与最初的私人机制有差异化的私人机制数据集注定要拥有非常薄弱的隐私保证。因此，我们需要选择其他隐私概念，例如$ k $ - 匿名性更好地在这种情况下保存实用程序。在这项工作中，我们介绍了$ k $ - 匿名的变体，我们称之为平滑$ k $ - 匿名和设计简单算法，可有效地提供平滑的$ k $ - 匿名性。我们进一步执行经验评估以支持我们的理论保证，并表明我们的算法改善了匿名数据下游机器学习任务的性能。

在设计聚类算法时，初始中心的选择对于学习簇的质量至关重要。在本文中，我们基于数据的构建，我们开发了一种新的初始化方案，称为$ k $ -Median问题（例如图形引起的离散空间），基于数据的构造。从树中，我们提出了一种新颖有效的搜索算法，用于良好的初始中心，随后可用于本地搜索算法。我们提出的HST初始化可以产生与另一种流行初始化方法$ K $ -Median ++的初始中心，具有可比的效率。 HST初始化也可以扩展到差异隐私（DP）的设置，以生成私人初始中心。我们表明，应用DP本地搜索后，我们的私有HST初始化会改善对近似错误的先前结果，并在小因素内接近下限。实验证明了理论的合理性，并证明了我们提出的方法的有效性。我们的方法也可以扩展到$ k $ -MEANS问题。

大多数-AT是确定联合正常形式（CNF）中输入$ N $的最低价公式的问题至少为2 ^ {n-1} $令人满意的作业。在对概率规划和推论复杂性的各种AI社区中，广泛研究了多数饱和问题。虽然大多数饱满为期40多年来，但自然变体的复杂性保持开放：大多数 - $ k $ SAT，其中输入CNF公式仅限于最多$ k $的子句宽度。我们证明，每辆$ k $，大多数 - $ k $ sat是在p的。事实上，对于任何正整数$ k $和ratic $ \ rho \ in（0,1）$ in（0,1）$与有界分比者，我们给出了算法这可以确定给定的$ k $ -cnf是否至少有$ \ rho \ cdot 2 ^ n $令人满意的分配，在确定性线性时间（而先前的最着名的算法在指数时间中运行）。我们的算法对计算复杂性和推理的复杂性具有有趣的积极影响，显着降低了相关问题的已知复杂性，例如E-Maj-$ K $ Sat和Maj-Maj- $ K $ Sat。在我们的方法中，通过提取在$ k $ -cnf的相应设置系统中发现的向日葵，可以通过提取向日葵来解决阈值计数问题的有效方法。我们还表明，大多数 - $ k $ sat的易腐烂性有些脆弱。对于密切相关的gtmajority-sat问题（我们询问给定公式是否超过2 ^ {n-1} $满足分配），这已知是pp-cleanting的，我们表明gtmajority-$ k $ sat在p for $ k \ le 3 $，但为$ k \ geq 4 $完成np-cleante。这些结果是违反直觉的，因为这些问题的“自然”分类将是PP完整性，因为GTMAJority的复杂性存在显着差异 - $ k $ SAT和MOSTION- $ K $ SAT为所有$ k \ ge 4 $。

为了捕获许多社区检测问题的固有几何特征，我们建议使用一个新的社区随机图模型，我们称之为\ emph {几何块模型}。几何模型建立在\ emph {随机几何图}（Gilbert，1961）上，这是空间网络的随机图的基本模型之一，就像在ERD \ H上建立的良好的随机块模型一样{o} s-r \'{en} yi随机图。它也是受到社区发现中最新的理论和实际进步启发的随机社区模型的自然扩展。为了分析几何模型，我们首先为\ emph {Random Annulus图}提供新的连接结果，这是随机几何图的概括。自引入以来，已经研究了几何图的连通性特性，并且由于相关的边缘形成而很难分析它们。然后，我们使用随机环形图的连接结果来提供必要的条件，以有效地为几何块模型恢复社区。我们表明，一种简单的三角计数算法来检测几何模型中的社区几乎是最佳的。为此，我们考虑了两个图密度方案。在图表的平均程度随着顶点的对数增长的状态中，我们表明我们的算法在理论上和实际上都表现出色。相比之下，三角计数算法对于对数学度方案中随机块模型远非最佳。我们还查看了图表的平均度与顶点$ n $的数量线性增长的状态，因此要存储一个需要$ \ theta（n^2）$内存的图表。我们表明，我们的算法需要在此制度中仅存储$ o（n \ log n）$边缘以恢复潜在社区。

在聚类问题中，中央决策者通过顶点给出完整的公制图，并且必须提供最小化某些目标函数的顶点的聚类。在公平的聚类问题中，顶点以颜色（例如，组中的成员身份）赋予，并且有效群集的功能也可能包括该群集中的颜色的表示。在公平集群中的事先工作假设完全了解集团成员资格。在本文中，我们通过假设通过概率分配不完美了解集团成员资格的知识。我们在此具有近似率保证的更常规设置中呈现聚类算法。我们还解决了“公制成员资格”的问题，其中不同的群体的概念和距离。使用我们所提出的算法以及基线进行实验，以验证我们的方法，并且当组成员资格不确定时，验证我们的方法以及表面细微的问题。

我们在$ d $ dimensional Euclidean Space中研究私人$ k $ -Median和$ k $ -means聚集问题。通过利用树的嵌入，我们提供了一种有效且易于实现的算法，该算法在非私人方法的经验上具有竞争力。我们证明我们的方法计算一个最多$ o（d^{3/2} \ log n）\ cdot opt + o（k d^2 \ log^2 n / \ epsilon^2）$的解决方案，其中$ \ Epsilon $是隐私担保。 （使用标准尺寸缩小技术可以用$ o（\ log k）$替换尺寸项，$ d $。）尽管最坏的案例保证比最先进的私人聚类方法的状态更糟糕，但算法是我们建议是实用的，以接近线性的方式运行，$ \ tilde {o}（nkd）$，时间和比例为数千万分。我们还表明，我们的方法适合在大规模分布式计算环境中并行化。特别是我们表明，我们的私人算法可以在sublinear内存制度中的对数MPC弹奏数中实现。最后，我们通过经验评估来补充理论分析，证明了该算法与其他隐私聚类基线相比的效率和准确性。

Originally, tangles were invented as an abstract tool in mathematical graph theory to prove the famous graph minor theorem. In this paper, we showcase the practical potential of tangles in machine learning applications. Given a collection of cuts of any dataset, tangles aggregate these cuts to point in the direction of a dense structure. As a result, a cluster is softly characterized by a set of consistent pointers. This highly flexible approach can solve clustering problems in various setups, ranging from questionnaires over community detection in graphs to clustering points in metric spaces. The output of our proposed framework is hierarchical and induces the notion of a soft dendrogram, which can help explore the cluster structure of a dataset. The computational complexity of aggregating the cuts is linear in the number of data points. Thus the bottleneck of the tangle approach is to generate the cuts, for which simple and fast algorithms form a sufficient basis. In our paper we construct the algorithmic framework for clustering with tangles, prove theoretical guarantees in various settings, and provide extensive simulations and use cases. Python code is available on github.

基于中心的聚类（例如，$ k $ -means，$ k $ -Medians）和使用线性子空间的聚类是两种最受欢迎的技术，可以将真实数据分配到较小的群集中。但是，当数据由敏感人群组组成时，不同敏感组的每点的聚集成本显着不同，可能会导致与公平相关的危害（例如，服务质量不同）。社会公平聚类的目的是最大程度地降低所有组中每点聚类的最大成本。在这项工作中，我们提出了一个统一的框架，以解决社会公平的基于中心的聚类和线性子空间聚类，并为这些问题提供实用，高效的近似算法。我们进行了广泛的实验，以表明在多个基准数据集上，我们的算法要么紧密匹配或超越最先进的基线。

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

我们介绍了$（p，q）$ - 公平集群问题。在这个问题中，我们给出了一组点数$ p $和不同重量函数的集合$ w $。我们想找到一个群集，最小化$ \ ell_q $ -norm的$ \ ell_p $-norm的$ \ ell_p $ -norms的$ p $从中心。这概括了各种聚类问题，包括社会博览会$ k $ -Median和$ k $ - emeans，并且与其他问题紧密相连，如Densest $ K $ -subgraph和Min $ K $ -Union。我们利用凸编程技术来估计$（p，q）$ - 为$ p $和$ q $的不同价值观达到公平的聚类问题。当$ p \ geq q $时，我们得到$ o（k ^ {（pq）/（2pq）}）$，它几乎匹配$ k ^ {\ omega（（pq）/（pq））} $低于基于Min $ K $ -Union和其他问题的猜想硬度的束缚。当$ q \ geq p $时，我们得到一个近似，它与界限$ p，q $的输入的大小无关，也与最近的$ o相匹配（（\ log n /（\ log \ log n）） ^ {1 / p}）$ - $（p，\ infty）$ - makarychev和vakilian（colt 2021）的公平聚类。

我们研究了清单可解放的平均估计问题，而对手可能会破坏大多数数据集。具体来说，我们在$ \ mathbb {r} ^ $和参数$ 0 <\ alpha <\ frac 1 2 $中给出了一个$ $ n $ points的$ t $ points。$ \ alpha $ -flaction的点$ t $是iid来自乖巧的分发$ \ Mathcal {D} $的样本，剩余的$（1- \ alpha）$ - 分数是任意的。目标是输出小型的vectors列表，其中至少一个接近$ \ mathcal {d} $的均值。我们开发新的算法，用于列出可解码的平均值估计，实现几乎最佳的统计保证，运行时间$ O（n ^ {1 + \ epsilon_0} d）$，适用于任何固定$ \ epsilon_0> 0 $。所有先前的此问题算法都有额外的多项式因素在$ \ frac 1 \ alpha $。我们与额外技术一起利用此结果，以获得用于聚类混合物的第一个近几个线性时间算法，用于分开的良好表现良好的分布，几乎匹配谱方法的统计保证。先前的聚类算法本身依赖于$ k $ -pca的应用程序，从而产生$ \ omega（n d k）$的运行时。这标志着近二十年来这个基本统计问题的第一次运行时间改进。我们的方法的起点是基于单次矩阵乘法权重激发电位减少的$ \ Alpha \至1 $制度中的新颖和更简单的近线性时间较强的估计算法。在Diakonikolas等人的迭代多滤波技术的背景下，我们迫切地利用了这种新的算法框架。 '18，'20，提供一种使用一维投影的同时群集和下群点的方法 - 因此，绕过先前算法所需的$ k $ -pca子程序。

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

Arthur和Vassilvitskii的著名$ K $ -MEANS ++算法[SODA 2007]是解决实践中$ K $ - 英镑问题的最流行方式。该算法非常简单：它以随机的方式均匀地对第一个中心进行采样，然后始终将每个$ K-1 $中心的中心取样与迄今为止最接近最接近中心的平方距离成比例。之后，运行了劳埃德的迭代算法。已知$ k $ -Means ++算法可以返回预期的$ \ theta（\ log K）$近似解决方案。在他们的开创性工作中，Arthur和Vassilvitskii [Soda 2007]询问了其以下\ emph {greedy}的保证：在每一步中，我们采样了$ \ ell $候选中心，而不是一个，然后选择最小化新的中心成本。这也是$ k $ -Means ++在例如中实现的方式。流行的Scikit-Learn库[Pedregosa等人； JMLR 2011]。我们为贪婪的$ k $ -Means ++提供几乎匹配的下限和上限：我们证明它是$ o（\ ell^3 \ log^3 k）$ - 近似算法。另一方面，我们证明了$ \ omega的下限（\ ell^3 \ log^3 k / \ log^2（\ ell \ log k））$。以前，只有$ \ omega（\ ell \ log k）$下限是已知的[bhattacharya，eube，r \“ ogllin，schmidt; esa 2020），并且没有已知的上限。