U-statistic Reduction with Accurate Risk Control

U-统计是一类在许多现代统计学习工具中发挥核心作用的统计学。然而，高昂的计算代价困扰着它们的实际应用。尽管自20世纪70年代以来，人们在U统计量的计算约简方面做了大量的研究工作，但对约化U统计量的统计推断中的准确风险控制这一重要问题的研究很少。此外，计算速度与风险控制准确性之间的权衡仍未确定。该项目将弥补这一重大差距，提供迫切需要的基础设施技术，使统计学家能够安全地扩大其基于U-统计的学习工具。该项目的成果将为广泛的研究领域和应用提供深远的好处，包括非参数统计、机器学习、社会学、计算机视觉和生物医学科学。该项目还将为研究生提供研究培训。该项目将研究经典的“无噪声”U-统计量和网络U-统计量，这是有噪声U-统计量的一个重要子集。这项研究将引入创新的理论分析技术，导致对计算-统计权衡的尖锐描述，并制定新的方法，其性能优于基于重采样和次采样的现有方法。该项目旨在建立一个对不同流行的U-统计量减少方案进行原则性分析的总体框架。为了便于实施和调整，研究结果将汇总为实用的循序渐进的指南。PI的团队还将为公众用户开发和传播用户友好的软件。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

U-statistics are a class of statistics that play central roles in many modern statistical learning tools. However, the heavy computational cost haunts their practical application. Despite considerable research efforts since the 1970s towards computational reduction for U-statistics, there exists little study on the important problem of accurate risk control in statistical inference for reduced U-statistics. Also, how computational speed trades off with risk control accuracy remains uncharacterized. This project will bridge this significant gap, providing the urgently needed infrastructual techniques that enable statisticians to securely scale up their U-statistic-based learning tools. The results of this project will provide profound benefits to a wide spectrum of research areas and applications, including nonparametric statistics, machine learning, sociology, computer vision and biomedical sciences. The project will also provide research training for graduate students.This project will study both classical "noiseless" U-statistics and network U-statistics, an important subset of noisy U-statistics. The research will introduce innovative theoretical analysis techniques that lead to a sharp characterization of computational-statistical trade-offs and formulate new methods outperforming existing ones based on resampling and subsampling. The project aims to establish a general framework for principled analysis of different popular U-statistic reduction schemes. The research findings will be summarized into practical, step-by-step guides for easy implementation and tuning. The PI's team will also develop and disseminate user-friendly software for public users.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.