Fast Newton Nearest Neighbors Boosting For Image Classification
Wafa Bel Haj Ali, Richard Nock, Frank Nielsen, Michel Barlaud

Recent works display that large scale image classification problems rule out computationally demanding methods. On such problems, simple approaches like k-NN are affordable contenders, with still room space for statistical improvements under the algorithmic constraints. A recent work showed how to leverage k-NN to yield a formal boosting algorithm. This method, however, has numerical issues that make it not suited for large scale problems.
We propose here an Adaptive Newton-Raphson scheme to leverage k-NN, N3 , which does not suffer these issues. We show that it is a boosting algorithm, with several key algorithmic and statistical properties. In particular, it may be sufficient to boost a subsample to reach desired bounds for the loss at hand in the boosting framework. Experiments are provided on the SUN, and Caltech databases. They confirm that boosting a subsample sometimes containing few examples only is sufficient to reach the convergence regime of N3 . Under such conditions, N3 challenges the accuracy of contenders with lower computational cost and lower memory