Nonparametric Testing Under Randomized Sketching

Meimei Liu, Zuofeng Shang, Yun Yang, Guang Cheng

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


A common challenge in nonparametric inference is its high computational complexity when data volume is large. In this paper, we develop computationally efficient nonparametric testing by employing a random projection strategy. In the specific kernel ridge regression setup, a simple distance-based test statistic is proposed. Notably, we derive the minimum number of random projections that is sufficient for achieving testing optimality in terms of the minimax rate. An adaptive testing procedure is further established without prior knowledge of regularity. One technical contribution is to establish upper bounds for a range of tail sums of empirical kernel eigenvalues. Simulations and real data analysis are conducted to support our theory.

Original languageEnglish (US)
Pages (from-to)4280-4290
Number of pages11
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number8
StatePublished - Aug 1 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


  • Computational limit
  • kernel ridge regression
  • minimax optimality
  • nonparametric testing
  • random sketch


Dive into the research topics of 'Nonparametric Testing Under Randomized Sketching'. Together they form a unique fingerprint.

Cite this