Sharp Theoretical Analysis for Nonparametric Testing under Random Projection

Meimei Liu, Zuofeng Shang, Guang Cheng

Research output: Contribution to journalConference articlepeer-review

5 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. As a byproduct, the lower bound of projection dimension for minimax optimal estimation derived in [40] is proven to be sharp. One technical contribution is to establish upper bounds for a range of tail sums of empirical kernel eigenvalues.

Original languageEnglish (US)
Pages (from-to)2175-2209
Number of pages35
JournalProceedings of Machine Learning Research
StatePublished - 2019
Externally publishedYes
Event32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States
Duration: Jun 25 2019Jun 28 2019

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


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


Dive into the research topics of 'Sharp Theoretical Analysis for Nonparametric Testing under Random Projection'. Together they form a unique fingerprint.

Cite this