这篇论文为分类任务中的采样提供了理论最优界，做机器学习理论或大规模分类算法的研究者可以直接参考其采样策略，避免不必要的计算开销。
该论文证明了对于一大类Lipschitz连续分类损失函数（包括逻辑损失、sigmoid损失、hinge损失和ReLU损失），在多种正则化项下可实现(1±ε)相对误差的最优采样界。对于L2/k正则化，采样复杂度为k²/ε²；对于L1/k正则化，为k/ε²；对于L2²/k正则化，若损失函数满足有界导数性质，则复杂度为线性k，否则为k²/ε²。研究还表明，若g(0)=0，则无法实现无维度采样界。所有上界均有匹配的下界（至多对数因子）。该工作通过更精细的高阶矩和经验过程分析，改进了近期Alishahi和Phillips的k³/ε²灵敏度采样界，且仅需简单均匀或（平方）范数采样。
Optimal Dimension-Free Sampling for Regularized Classification
We prove optimal sampling bounds achieving $(1\pm\varepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove $k^2/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_2/k$ regularization, and $k/\varepsilon^2$ upper and lower bounds for $\|\cdot\|_1/k$ regularization. For $\|\cdot\|_2^2/k$ regularization, the sampling complexity depends mainly on a bounded derivative property: if $|g'(x)|\leq g(x)$, and $g(0)>0$, and $g$ is monotonic or convex, then it admits linear in $k$ sampling complexity; otherwise the general bound is $k^2/\varepsilon^2$. However, if $g(0)=0$, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic $k^3/\varepsilon^2$ sensitivity sampling bounds of (Alishahi and Phillips, ICML'24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.