Recent results show that estimates defined by over-parametrized deep neural
networks learned by applying gradient descent to a regularized empirical $L_2$
risk are universally consistent and achieve good rates of convergence. In this
paper, we show that the regularization term is not necessary to obtain similar
results. In the case of a suitably chosen initialization of the network, a
suitable number of gradient descent steps, and a suitable step size we show
that an estimate without a regularization term is universally consistent for
bounded predictor variables. Additionally, we show that if the regression
function is H\"older smooth with H\"older exponent $1/2 \leq p \leq 1$, the
$L_2$ error converges to zero with a convergence rate of approximately
$n^{-1/(1+d)}$. Furthermore, in case of an interaction model, where the
regression function consists of a sum of H\"older smooth functions with $d^*$
components, a rate of convergence is derived which does not depend on the input
dimension $d$.

通过合适的初始化、梯度下降步数和步长选择，在深度神经网络中无需正则化项，可以达到普适的一致性和收敛速度，而且对于有界预测变量，$L_2$ 误差收敛速度约为 $n^{-1/(1+d)}$，对于交互模型，收敛速度与输入维度 $d$ 无关。

无正则项梯度下降学得的过参数化深度神经网络估计的 $L_2$ 误差分析

Analysis of the expected $L_2$ error of an over-parametrized deep neural  network estimate learned by gradient descent without regularization

The $k$ nearest neighbour learning rule (under the uniform distance tie
breaking) is universally consistent in every metric space $X$ that is
sigma-finite dimensional in the sense of Nagata. This was pointed out by
C\'erou and Guyader (2006) as a consequence of the main result by those
authors, combined with a theorem in real analysis sketched by D. Preiss (1971)
(and elaborated in detail by Assouad and Quentin de Gromard (2006)). We show
that it is possible to give a direct proof along the same lines as the original
theorem of Charles J. Stone (1977) about the universal consistency of the
$k$-NN classifier in the finite dimensional Euclidean space. The generalization
is non-trivial because of the distance ties being more prevalent in the
non-euclidean setting, and on the way we investigate the relevant geometric
properties of the metrics and the limitations of the Stone argument, by
constructing various examples.

证明了 $k$ 最近邻学习规则在每个 sigma-finite 维度空间中都是普遍一致的，同时调查了度量的相关几何性质以及 Stone 方法中的限制，通过构建各种例子来推广这一结论。

度量空间中 k-NN 规则的普适一致性和 Nagata 维度

Universal consistency of the $k$-NN rule in metric spaces and Nagata  dimension

The $k$-nearest neighbour ($k$-NN) classifier is one of the oldest and most
important supervised learning algorithms for classifying datasets.
Traditionally the Euclidean norm is used as the distance for the $k$-NN
classifier. In this thesis we investigate the use of alternative distances for
the $k$-NN classifier.
We start by introducing some background notions in statistical machine
learning. We define the $k$-NN classifier and discuss Stone's theorem and the
proof that $k$-NN is universally consistent on the normed space $R^d$. We then
prove that $k$-NN is universally consistent if we take a sequence of random
norms (that are independent of the sample and the query) from a family of norms
that satisfies a particular boundedness condition. We extend this result by
replacing norms with distances based on uniformly locally Lipschitz functions
that satisfy certain conditions. We discuss the limitations of Stone's lemma
and Stone's theorem, particularly with respect to quasinorms and adaptively
choosing a distance for $k$-NN based on the labelled sample. We show the
universal consistency of a two stage $k$-NN type classifier where we select the
distance adaptively based on a split labelled sample and the query. We conclude
by giving some examples of improvements of the accuracy of classifying various
datasets using the above techniques.

本论文研究使用替代距离的最近邻分类器（k-NN）算法，并探讨了基于一系列随机范数或基于一些特定的一致性条件的距离，并探究了对类别标签的自适应选择距离的两阶段 k-NN 分类器。

一类距离度量下基于 k - 近邻的数据集分类

k-Nearest Neighbour Classification of Datasets with a Family of  Distances

Nearest neighbor methods are a popular class of nonparametric estimators with
several desirable properties, such as adaptivity to different distance scales
in different regions of space. Prior work on convergence rates for nearest
neighbor classification has not fully reflected these subtle properties. We
analyze the behavior of these estimators in metric spaces and provide
finite-sample, distribution-dependent rates of convergence under minimal
assumptions. As a by-product, we are able to establish the universal
consistency of nearest neighbor in a broader range of data spaces than was
previously known. We illustrate our upper and lower bounds by introducing
smoothness classes that are customized for nearest neighbor classification.

本文提出了一种新的最近邻方法，它能够适应不同空间区域的不同距离尺度，并分析其在度量空间的行为，从而得出分布相关的有限样本收敛速率，并实现了广泛数据空间的最近邻的普遍一致性。