2019/03/13 by Kur, Gil, Dagan, Yuval, Rakhlin, Alexander · 1 citation
#62G07 62G08 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1903.05315
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 ≥ 4 the maximum likelihood estimators of both problems achieve an optimal risk of Θd(n-2/(d+1)) (up to a logarithmic factor) in terms of squared Hellinger distance and L2 squared distance, respectively. Previously, the optimality of both these estimators was known only for d≤ 3. We also prove that the ε-entropy numbers of the two aforementioned families are equal up to logarithmic factors. We complement these results by proving a sharp bound Θ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 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⋅ n-2/(d+1) to c⋅ n-2/(d+1) (when d≥ 2).