Data subsampling is one of the most natural methods to approximate a
massively large data set by a small representative proxy. In particular,
sensitivity sampling received a lot of attention, which samples points
proportional to an individual importance measure called sensitivity. This
framework reduces in very general settings the size of data to roughly the VC
dimension $d$ times the total sensitivity $\mathfrak S$ while providing strong
$(1\pm\varepsilon)$ guarantees on the quality of approximation. The recent work
of Woodruff & Yasuda (2023c) improved substantially over the general $\tilde
O(\varepsilon^{-2}\mathfrak Sd)$ bound for the important problem of $\ell_p$
subspace embeddings to $\tilde O(\varepsilon^{-2}\mathfrak S^{2/p})$ for
$p\in[1,2]$. Their result was subsumed by an earlier $\tilde
O(\varepsilon^{-2}\mathfrak Sd^{1-p/2})$ bound which was implicitly given in
the work of Chen & Derezinski (2021). We show that their result is tight when
sampling according to plain $\ell_p$ sensitivities. We observe that by
augmenting the $\ell_p$ sensitivities by $\ell_2$ sensitivities, we obtain
better bounds improving over the aforementioned results to optimal linear
$\tilde O(\varepsilon^{-2}(\mathfrak S+d)) = \tilde O(\varepsilon^{-2}d)$
sampling complexity for all $p \in [1,2]$. In particular, this resolves an open
question of Woodruff & Yasuda (2023c) in the affirmative for $p \in [1,2]$ and
brings sensitivity subsampling into the regime that was previously only known
to be possible using Lewis weights (Cohen & Peng, 2015). As an application of
our main result, we also obtain an $\tilde O(\varepsilon^{-2}\mu d)$
sensitivity sampling bound for logistic regression, where $\mu$ is a natural
complexity measure for this problem. This improves over the previous $\tilde
O(\varepsilon^{-2}\mu^2 d)$ bound of Mai et al. (2021) which was based on Lewis
weights subsampling.

数据子采样是一种近似大规模数据集的自然方法，该论文提出了一种敏感性采样方法，并改进了子空间嵌入和逻辑回归中的采样复杂度。

通过 L2 增强实现 Lp 敏感性采样的最优界限

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$  augmentation

We study the data selection problem, whose aim is to select a small
representative subset of data that can be used to efficiently train a machine
learning model. We present a new data selection approach based on $k$-means
clustering and sensitivity sampling. Assuming access to an embedding
representation of the data with respect to which the model loss is H\"older
continuous, our approach provably allows selecting a set of ``typical'' $k +
1/\varepsilon^2$ elements whose average loss corresponds to the average loss of
the whole dataset, up to a multiplicative $(1\pm\varepsilon)$ factor and an
additive $\varepsilon \lambda \Phi_k$, where $\Phi_k$ represents the $k$-means
cost for the input embeddings and $\lambda$ is the H\"older constant.
We furthermore demonstrate the performance and scalability of our approach on
fine-tuning foundation models and show that it outperforms state-of-the-art
methods. We also show how it can be applied on linear regression, leading to a
new sampling strategy that surprisingly matches the performances of leverage
score sampling, while being conceptually simpler and more scalable.

我们研究数据选择问题，将利用 $k$-means 聚类和敏感性抽样方法，基于模型损失的嵌入表示，可选择一组典型样本，其平均损失与整个数据集的平均损失相对应，具有可证明的性质，并且在微调基础模型上表现优于最先进的方法，同时展示了它如何应用于线性回归，提供了一个更简单且可扩展性更强的抽样策略。

基于聚类敏感性采样的数据高效学习：基础模型与扩展

Data-Efficient Learning via Clustering-Based Sensitivity Sampling:  Foundation Models and Beyond

Coresets are one of the central methods to facilitate the analysis of large
data sets. We continue a recent line of research applying the theory of
coresets to logistic regression. First, we show a negative result, namely, that
no strongly sublinear sized coresets exist for logistic regression. To deal
with intractable worst-case instances we introduce a complexity measure
$\mu(X)$, which quantifies the hardness of compressing a data set for logistic
regression. $\mu(X)$ has an intuitive statistical interpretation that may be of
independent interest. For data sets with bounded $\mu(X)$-complexity, we show
that a novel sensitivity sampling scheme produces the first provably sublinear
$(1\pm\varepsilon)$-coreset. We illustrate the performance of our method by
comparing to uniform sampling as well as to state of the art methods in the
area. The experiments are conducted on real world benchmark data for logistic
regression.

使用核心集理论应用于 logistic 回归模型的研究，提出一个统计学上解释直观的复杂度度量方法，并发展了一个新的灵敏度采样方案来处理 logistic 回归中的大量数据，并在真实世界的 logistic 回归基准数据上比较了其性能。

逻辑回归的核心集

On Coresets for Logistic Regression

A coreset for a set of points is a small subset of weighted points that
approximately preserves important properties of the original set. Specifically,
if $P$ is a set of points, $Q$ is a set of queries, and $f:P\times
Q\to\mathbb{R}$ is a cost function, then a set $S\subseteq P$ with weights
$w:P\to[0,\infty)$ is an $\epsilon$-coreset for some parameter $\epsilon>0$ if
$\sum_{s\in S}w(s)f(s,q)$ is a $(1+\epsilon)$ multiplicative approximation to
$\sum_{p\in P}f(p,q)$ for all $q\in Q$. Coresets are used to solve fundamental
problems in machine learning under various big data models of computation. Many
of the suggested coresets in the recent decade used, or could have used a
general framework for constructing coresets whose size depends quadratically on
what is known as total sensitivity $t$.
In this paper we improve this bound from $O(t^2)$ to $O(t\log t)$. Thus our
results imply more space efficient solutions to a number of problems, including
projective clustering, $k$-line clustering, and subspace approximation.
Moreover, we generalize the notion of sensitivity sampling for sup-sampling
that supports non-multiplicative approximations, negative cost functions and
more. The main technical result is a generic reduction to the sample complexity
of learning a class of functions with bounded VC dimension. We show that
obtaining an $(\nu,\alpha)$-sample for this class of functions with appropriate
parameters $\nu$ and $\alpha$ suffices to achieve space efficient
$\epsilon$-coresets.
Our result implies more efficient coreset constructions for a number of
interesting problems in machine learning; we show applications to
$k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the
integer $(j,k)$-projective clustering problem.

本文提出一种改进的 coreset 构建方法，利用 sensitivity sampling 技术，并对 VC dimension 类的函数的采样复杂度进行分析，从而能够更加高效地解决包括聚类等在内的机器学习问题。