Hypothetically, can we perfectly classify new instances given infinite support from validation and training? KNN Hypothetically speaking, Given infinite amounts of training data and validation data, can we achieve perfect classification (score of 1) given ML algorithms such as KNN?
Thank you.
 A: Short answer : no.
In real life data sets, the data your work with is usually not separable. No matter the shape of the boundary you chose, some points will not have the expected behavior.
If you make more assumptions, then yes, you may achieve a perfect score. Say:


*

*you have a data set and two classes $A$ and $B$ such that $d(A,B) > \epsilon $ for some positive $\epsilon$. (1)

*the training sample you observe is uniformly sampled from $A$ an $B$ (otherwise @gented counter example applies)
Given a new point $x$, you want to decide whether it belongs to $A$ or $B$. Now, calling $a_n$ the sequence of points in $A$ and $b_n$ the sequence of points in $B$ start looking for an $n$ such that $d(x, a_n) < \epsilon / 2 $ or $d(x, b_n) < \epsilon / 2 $. Such an $n$ exists (as long as $x$ belongs to one of the classes) otherwise you could prove the existence of a hole in the datasets, contradicting the second hypothesis. Once $n$ found, you know that $x\in A$ if $d(x, a_n) < \epsilon / 2 $.
This is more or less a 1-nearest neighbor search, with a stopping criterion ensuring that we do not need to evaluate the distances between a new point and "all" the points.
(1) the distance between the two sets being defined as the (limit of the) smallest distance between two points from $A$ and $B$
A: It depends mainly on the featuers you are using. Imagine, for instance, that you are trying to determine the sex of every human being on Earth knowing only his/her date of birth. Good luck training your model on infinite data!
However, if the classes are perfectly separated by the features incorporated in the model, you can find 100$ accuracy even on finite samples
