Minimax Rates for Conditional Density Estimation via Empirical Entropy

Abstract

We consider the task of estimating a conditional density using i.i.d. samples from a joint distribution, which is a fundamental problem with applications in both classification and uncertainty quantification for regression. For joint density estimation, minimax rates have been characterized for general density classes in terms of uniform (metric) entropy, a well-studied notion of statistical capacity. When applying these results to conditional density estimation, the use of uniform entropy -- which is infinite when the covariate space is unbounded and suffers from the curse of dimensionality -- can lead to suboptimal rates. Consequently, minimax rates for conditional density estimation cannot be characterized using these classical results. We resolve this problem for well-specified models, obtaining matching (within logarithmic factors) upper and lower bounds on the minimax Kullback--Leibler risk in terms of the empirical Hellinger entropy for the conditional density class. The use of empirical entropy allows us to appeal to concentration arguments based on local Rademacher complexity, which -- in contrast to uniform entropy -- leads to matching rates for large, potentially nonparametric classes and captures the correct dependence on the complexity of the covariate space. Our results require only that the conditional densities are bounded above, and do not require that they are bounded below or otherwise satisfy any tail conditions.

arXiv comment59 pages, 1 figure. Minor edits to match published version

References in corpus (20)

• Local Rademacher complexities
• Empirical entropy, minimax regret and minimax risk
• Conditional density estimation in a regression setting
• Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes
• Kullback-Leibler aggregation and misspecified generalized linear models
• Fast Nonparametric Conditional Density Estimation
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Logistic Regression: The Importance of Being Improper
• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Safe-Bayesian Generalized Linear Regression
• Conditional Density Estimation by Penalized Likelihood Model Selection and Applications
• Lower bounds and aggregation in density estimation
• Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts
• A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity
• Sequential prediction under log-loss with side information
• Robust estimation of a regression function in exponential families
• Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance
• Towards Empirical Process Theory for Vector-Valued Functions: Metric Entropy of Smooth Function Classes