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

K近邻(KNN)方法是一类非参数统计方法。与其他方法相比，KNN方法有几个优点。特别是，KNN方法可以自动适应任何连续的底层函数，而不依赖于任何特定的模型。此外，KNN方法使用简单，不需要太多的参数调整。此外，KNN方法也取得了很好的实证结果。由于这些优点，KNN方法被广泛应用于各种统计问题，包括函数估计和机器学习问题。然而，对用于这些应用的KNN方法的理论性质的理解是不完整的。因此，迫切需要研究KNN方法的理论性质。通过解决这些研究确定的估计误差的主要来源，可以设计具有更好性能的改进的KNN方法。在本项目中，研究者研究：1)KNN方法在函数估计和机器学习问题中的理论性质；以及2)针对这些应用设计具有更好性能的改进的KNN算法。尽管已有许多研究，但仍有几个理论问题需要进一步研究。具体地说：1)用于函数估计、分类和回归等的KNN方法的理论收敛速度仍然没有完全确定；2)对于许多有实际意义的应用，这种类型的方法在什么条件下是最优的还不清楚；3)现有的KNN方法的大多数分析依赖于独立和同分布的训练数据，而在某些应用中(例如涉及马尔可夫链的应用)，可用的数据是依赖的；4)尽管用于监督学习的KNN方法的应用和分析很多，但用于强化学习等的KNN方法的应用和分析是有限的。为了应对这些挑战，该项目将重点放在两个相互关联的推进上。第一个重点是研究KNN方法在信息论泛函估计中的应用，包括熵、互信息、Kullback-Leibler散度、有向信息等。第二个重点是设计和分析基于KNN的机器学习算法，包括监督学习、非凸优化和强化学习。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.