精选理由
这篇论文为分类任务中的采样提供了理论最优界，做机器学习理论或大规模分类算法的研究者可以直接参考其采样策略，避免不必要的计算开销。
该论文证明了对于一大类Lipschitz连续分类损失函数（包括逻辑损失、sigmoid损失、hinge损失和ReLU损失），在多种正则化项下可实现(1±ε)相对误差的最优采样界。对于L2/k正则化，采样复杂度为k²/ε²；对于L1/k正则化，为k/ε²；对于L2²/k正则化，若损失函数满足有界导数性质，则复杂度为线性k，否则为k²/ε²。研究还表明，若g(0)=0，则无法实现无维度采样界。所有上界均有匹配的下界（至多对数因子）。该工作通过更精细的高阶矩和经验过程分析，改进了近期Alishahi和Phillips的k³/ε²灵敏度采样界，且仅需简单均匀或（平方）范数采样。
AI 翻译 · 中文
该论文证明了对于一大类Lipschitz连续分类损失函数（包括逻辑损失、sigmoid损失、hinge损失和ReLU损失），在多种正则化项下可实现(1±ε)相对误差的最优采样界。对于L2/k正则化，采样复杂度为k²/ε²；对于L1/k正则化，为k/ε²；对于L2²/k正则化，若损失函数满足有界导数性质，则复杂度为线性k，否则为k²/ε²。研究还表明，若g(0)=0，则无法实现无维度采样界。所有上界均有匹配的下界（至多对数因子）。该工作通过更精细的高阶矩和经验过程分析，改进了近期Alishahi和Phillips的k³/ε²灵敏度采样界，且仅需简单均匀或（平方）范数采样。
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 …