Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression

Abstract

In this paper, we study two problems: (1) estimation of a $d$-dimensional log-concave distribution and (2) bounded multivariate convex regression with random design with an underlying log-concave density or a compactly supported distribution with a continuous density. First, we show that for all $d\ge 4$ the maximum likelihood estimators of both problems achieve an optimal risk of ${\Theta }_d(n^{-2/(d+1)})$ (up to a logarithmic factor) in terms of squared Hellinger distance and $L_2$ squared distance, respectively. Previously, the optimality of both these estimators was known only for $d\le 3$. We also prove that the $\epsilon$-entropy numbers of the two aforementioned families are equal up to logarithmic factors. We complement these results by proving a sharp bound ${\Theta }_d(n^{-2/(d+4)})$ on the minimax rate (up to logarithmic factors) with respect to the total variation distance. Finally, we prove that estimating a log-concave density - even a uniform distribution on a convex set - up to a fixed accuracy requires the number of samples \emph{at least} exponential in the dimension. We do that by improving the dimensional constant in the best known lower bound for the minimax rate from $2^{-d}\cdot n^{-2/(d+1)}$ to $c\cdot n^{-2/(d+1)}$ (when $d\ge 2$).

References in corpus (12)

• Maximum likelihood estimation of a log-concave density and its distribution function: Basic properties and uniform consistency
• Empirical entropy, minimax regret and minimax risk
• Learning mixtures of structured distributions over discrete domains
• Multivariate convex regression: global risk bounds and adaptation
• Learning convex bodies is hard
• Learning Multivariate Log-concave Distributions
• Monotone probability distributions over the Boolean cube can be learned with sublinear samples
• Testing Identity of Multidimensional Histograms
• Approximation of the Euclidean ball by polytopes with a restricted number of facets
• Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
• A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families

Cited by in corpus (9)

• Self-regularizing Property of Nonparametric Maximum Likelihood Estimator in Mixture Models
• Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
• Intrinsic and Dual Volume Deviations of Convex Bodies and Polytopes
• Minimax Rates for Conditional Density Estimation via Empirical Entropy
• Handling Hard Affine SDP Shape Constraints in RKHSs
• Exact Solutions in Log-Concave Maximum Likelihood Estimation
• On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
• Stratified incomplete local simplex tests for curvature of nonparametric multiple regression
• Least Squares Estimation of a Quasiconvex Regression Function