In multi-class classification using nearest neighbour, I believe that as the dimension of the space increases, we need exponentially more samples to keep the classification error under a certain threshold. Is there any theoretical support for this intuition? I am considering scenarios where the boundary is deterministic (not probabilistic) and the data points are uniformly distributed within a defined domain of real space.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.