High Dimensional Classification

Consider the supervised learning problem, where the ratio of the number of labeled samples n to the number of features d tends to zero as d goes to infinity and the optimal Bayes error of the problem doesn’t scale with d. We study the asymptotic error probability of different classifiers. To simplify the analysis, we assume Gaussian class conditional densities. In the following paper, we have shown that for any classifier in the mentioned learning configuration, without any prior knowledge on the unknown density parameters, the performance can not be better than the random coin toss asymptotically, no matter how small the Bayes optimal risk is. Moreover, we have shown that as  a necessary condition to obtain non-trivial classifiers, the Haar measure of the feasible parameter space should be zero asymptotically :

  • M. H. Rohban, P. Ishwar, B. Orten, W. C. Karl, V. Saligrama, “An Impossibility Result for High Dimensional Supervised Learning,” IEEE Information Theory Workshop, 2013 (arXiv:1301.6915 [stat.ML]).