  In the era of deep learning, understanding over-fitting phenomenon becomes
increasingly important. It is observed that carefully designed deep neural
networks achieve small testing error even when the training error is close to
zero. One possible explanation is that for many modern machine learning
algorithms, over-fitting can greatly reduce the estimation bias, while not
increasing the estimation variance too much. To illustrate the above idea, we
prove that the proposed interpolated nearest neighbor algorithm achieves the
minimax optimal rate in both regression and classification regimes, and observe
that they are empirically better than the traditional $k$ nearest neighbor
method in some cases.
