Efficient Minimax Optimal Estimators For Multivariate Convex Regression
We study the computational aspects of the task of multivariate convex
regression in dimension $d \geq 5$. We present the first computationally
efficient minimax optimal (up to logarithmic factors) estimators for the tasks
of (i) $L$-Lipschitz convex regression (ii) $\Gamma$-bounded convex regression
under polytopal support. The proof of the correctness of these estimators uses
a variety of tools from different disciplines, among them empirical process
theory, stochastic geometry, and potential theory. This work is the first to
show the existence of efficient minimax optimal estimators for non-Donsker
classes that their corresponding Least Squares Estimators are provably minimax
sub-optimal; a result of independent interest.