$k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a
fundamental machine learning problem. While near-linear time approximation
algorithms were known in the classical setting for a dataset with cardinality
$n$, it remains open to find sublinear-time quantum algorithms. We give quantum
algorithms that find coresets for $k$-clustering in $\mathbb{R}^d$ with
$\tilde{O}(\sqrt{nk}d^{3/2})$ query complexity. Our coreset reduces the input
size from $n$ to $\mathrm{poly}(k\epsilon^{-1}d)$, so that existing
$\alpha$-approximation algorithms for clustering can run on top of it and yield
$(1 + \epsilon)\alpha$-approximation. This eventually yields a quadratic
speedup for various $k$-clustering approximation algorithms. We complement our
algorithm with a nearly matching lower bound, that any quantum algorithm must
make $\Omega(\sqrt{nk})$ queries in order to achieve even $O(1)$-approximation
for $k$-clustering.

该研究在量子计算的框架下，提出了一种在时空复杂度上具有优势的 k - 聚类问题的量子算法，并在算法的基础上得到了一个核心集。

针对聚类问题的近优量子核心集构建算法

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

We consider the $k$-clustering problem with $\ell_p$-norm cost, which
includes $k$-median, $k$-means and $k$-center, under an individual notion of
fairness proposed by Jung et al. [2020]: given a set of points $P$ of size $n$,
a set of $k$ centers induces a fair clustering if every point in $P$ has a
center among its $n/k$ closest neighbors. Mahabadi and Vakilian [2020]
presented a $(p^{O(p)},7)$-bicriteria approximation for fair clustering with
$\ell_p$-norm cost: every point finds a center within distance at most $7$
times its distance to its $(n/k)$-th closest neighbor and the $\ell_p$-norm
cost of the solution is at most $p^{O(p)}$ times the cost of an optimal fair
solution.
In this work, for any $\varepsilon>0$, we present an improved $(16^p
+\varepsilon,3)$-bicriteria for this problem. Moreover, for $p=1$ ($k$-median)
and $p=\infty$ ($k$-center), we present improved cost-approximation factors
$7.081+\varepsilon$ and $3+\varepsilon$ respectively. To achieve our
guarantees, we extend the framework of [Charikar et al., 2002, Swamy, 2016] and
devise a $16^p$-approximation algorithm for the facility location with
$\ell_p$-norm cost under matroid constraint which might be of an independent
interest.
Besides, our approach suggests a reduction from our individually fair
clustering to a clustering with a group fairness requirement proposed by
Kleindessner et al. [2019], which is essentially the median matroid problem
[Krishnaswamy et al., 2011].

此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

个体公平聚类的改进近似算法

Improved Approximation Algorithms for Individually Fair Clustering

Coreset, which is a summary of the original dataset in the form of a small
weighted set in the same sample space, provides a promising approach to enable
machine learning over distributed data. Although viewed as a proxy of the
original dataset, each coreset is only designed to approximate the cost
function of a specific machine learning problem, and thus different coresets
are often required to solve different machine learning problems, increasing the
communication overhead. We resolve this dilemma by developing robust coreset
construction algorithms that can support a variety of machine learning
problems. Motivated by empirical evidence that suitably-weighted k-clustering
centers provide a robust coreset, we harden the observation by establishing
theoretical conditions under which the coreset provides a guaranteed
approximation for a broad range of machine learning problems, and developing
both centralized and distributed algorithms to generate coresets satisfying the
conditions. The robustness of the proposed algorithms is verified through
extensive experiments on diverse datasets with respect to both supervised and
unsupervised learning problems.

该文章提出了一种稳健的 coreset 构建算法，在中心化和分布式框架下生成符合一定理论条件的 coreset，以支持各类机器学习问题的高效求解。实验证明该算法具有较强的健壮性。