Discrete minimax estimation with trees

2018/12/14 by Devroye, Luc, Reddad, Tommy
#60G07 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1812.06063

Abstract

We propose a simple recursive data-based partitioning scheme which produces piecewise-constant or piecewise-linear density estimates on intervals, and show how this scheme can determine the optimal L₁ minimax rate for some discrete nonparametric classes.

Related

• Minimax Trees in Linear Time with Applications
• Revisiting Le Cam's Equation: Exact Minimax Rates over Convex Density Classes
• Generalized van Trees inequality: Local minimax bounds for non-smooth functionals and irregular statistical models
• Minimax Optimal Algorithms with Fixed-k-Nearest Neighbors
• Minimax Trees in Linear Time