U-statistic Reduction with Accurate Risk Control

Ohio State University, The, Columbus OH

Investigators

Abstract

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.