A scaling law refers to the observation that the test performance of a model
improves as the number of training data increases. A fast scaling law implies
that one can solve machine learning problems by simply boosting the data and
the model sizes. Yet, in many cases, the benefit of adding more data can be
negligible. In this work, we study the rate of scaling laws of nearest neighbor
classifiers. We show that a scaling law can have two phases: in the first
phase, the generalization error depends polynomially on the data dimension and
decreases fast; whereas in the second phase, the error depends exponentially on
the data dimension and decreases slowly. Our analysis highlights the complexity
of the data distribution in determining the generalization error. When the data
distributes benignly, our result suggests that nearest neighbor classifier can
achieve a generalization error that depends polynomially, instead of
exponentially, on the data dimension.

通过研究最近邻分类器的缩放定律，我们发现缩放定律可以有两个阶段：在第一阶段中，泛化误差多项式依赖于数据维度并迅速减小；而在第二阶段中，误差指数级依赖于数据维度并减小较慢，这凸显了数据分布在决定泛化误差中的复杂性。当数据分布良好时，我们的研究表明最近邻分类器可以在数据维度上多项式依赖，而非指数依赖，从而实现泛化误差的降低。

最近邻分类器的两个尺度定律阶段

Two Phases of Scaling Laws for Nearest Neighbor Classifiers

We study the problem of computing the minimum adversarial perturbation of the
Nearest Neighbor (NN) classifiers. Previous attempts either conduct attacks on
continuous approximations of NN models or search for the perturbation by some
heuristic methods. In this paper, we propose the first algorithm that is able
to compute the minimum adversarial perturbation. The main idea is to formulate
the problem as a list of convex quadratic programming (QP) problems that can be
efficiently solved by the proposed algorithms for 1-NN models. Furthermore, we
show that dual solutions for these QP problems could give us a valid lower
bound of the adversarial perturbation that can be used for formal robustness
verification, giving us a nice view of attack/verification for NN models. For
$K$-NN models with larger $K$, we show that the same formulation can help us
efficiently compute the upper and lower bounds of the minimum adversarial
perturbation, which can be used for attack and verification.

本篇论文的研究内容为：计算最小对抗性扰动的问题。研究者们提出了第一个能够计算最小对抗性扰动的算法，将问题用凸二次规划问题的列表进行了表示，用于 1-NN 模型的算法能够有效地解决这个问题。对于更大的 $K$-NN 模型，我们表明同样的表示形式可以帮助我们有效地计算最小对抗性扰动的上限和下限，这可用于攻击和验证。