Statistical Optimality of Interpolated Nearest Neighbor Algorithms
This work addresses the problem of understanding over-fitting in machine learning for researchers, providing a theoretical explanation and a new algorithm, though it is incremental as it builds on existing nearest neighbor methods.
The paper tackles the over-fitting phenomenon in deep learning by proposing an interpolated nearest neighbor algorithm, proving it achieves minimax optimal rates in regression and classification and showing it empirically outperforms traditional k-nearest neighbor methods in some cases.
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.