  We present a novel data-driven strategy to choose the hyperparameter $k$ in
the $k$-NN regression estimator without using any hold-out data. We treat the
problem of choosing the hyperparameter as an iterative procedure (over $k$) and
propose using an easily implemented in practice strategy based on the idea of
early stopping and the minimum discrepancy principle. This model selection
strategy is proven to be minimax-optimal over some smoothness function classes,
for instance, the Lipschitz functions class on a bounded domain. The novel
method often improves statistical performance on artificial and real-world data
sets in comparison to other model selection strategies, such as the Hold-out
method, 5-fold cross-validation, and AIC criterion. The novelty of the strategy
comes from reducing the computational time of the model selection procedure
while preserving the statistical (minimax) optimality of the resulting
estimator. More precisely, given a sample of size $n$, if one should choose $k$
among $\left\{ 1, \ldots, n \right\}$, and $\left\{ f^1, \ldots, f^n \right\}$
are the estimators of the regression function, the minimum discrepancy
principle requires the calculation of a fraction of the estimators, while this
is not the case for the generalized cross-validation, Akaike's AIC criteria, or
Lepskii principle.
