CIF: SMALL: kNN methods for functional estimation and machine learning

K Nearest Neighbor (kNN) methods are a class of nonparametric statistical methods. Compared with other methods, kNN methods have several advantages. In particular, kNN methods can automatically adapt to any continuous underlying functions without relying on any specific models.

In addition, kNN methods are simple to use and do not require too much parameter tuning. Furthermore, kNN methods have achieved excellent empirical results. Due to these advantages, kNN methods are widely used in a large variety of statistical problems, including functional-estimation and machine-learning problems.

However, the understanding of theoretical properties of kNN methods for these applications is incomplete. As the result, there is a pressing need to investigate the theoretical properties of kNN methods. By addressing the main sources of estimation errors identified by these investigations, one can design improved kNN methods that have better performance.

In this project, the investigator is investigating: 1) theoretical properties of kNN methods in functional estimation and machine learning problems; and 2) the design of improved kNN algorithms with better performance for these applications. Despite many existing studies, several theoretical problems still need further investigation. In particular: 1) The theoretical convergence rates of kNN methods for functional estimations, classification and regression, etc., are still not fully established; 2) For many applications of practical interests, it is not clear under what conditions this type of methods is optimal; 3) Most of the existing analysis of kNN methods rely on availability of independent and identically distributed training data, while in certain applications (such as those involving Markov chains) the available data are dependent; 4) While there are many applications and analysis of kNN methods for supervised learning, the applications and analysis of kNN methods for reinforcement learning etc. are limited.

To address these challenges, this project is focusing on two interconnected thrusts. In the first thrust, the project is investigating the application of kNN methods in the estimation of information-theoretic functionals, including entropy, mutual information, Kullback-Leibler divergence, directed information, etc. In the second thrust, the project is designing and analyzing kNN based algorithms for machine learning problems, including supervised learning, nonconvex optimization and reinforcement learning.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.