New answers tagged

-2

Machine learning is subject to the laws of computing complexity. The prime factorization problem is in the NP complexity class, possibly even NP-hard (not proven). That is why detecting primes is among the hardest problems in machine learning, and might not be possible at all with that approach. Quantum computers (QC) can do it in polynomial time, but ...


6

It is not hard to see that without additional stability assumptions one won't be able to get high probability bounds. For example consider predicting unbiased coin using majority label in the sample. With probability $~1/\sqrt{n}$ we get that majority of leave-one-out is exactly the opposite of the excluded point so LOO will give error of 1. Note that the ...


Top 50 recent answers are included