An Efficient Minimax Optimal Estimator for Multivariate Convex Regression
Abstract
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 $L$-Lipschitz and $\Gamma$-bounded convex regression under polytopal support. This work is the first to show the existence of efficient minimax optimal estimators for non-Donsker classes whose corresponding Least Squares Estimators are provably minimax suboptimal. 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.
Cite
Text
Kur and Putterman. "An Efficient Minimax Optimal Estimator for Multivariate Convex Regression." Conference on Learning Theory, 2022.Markdown
[Kur and Putterman. "An Efficient Minimax Optimal Estimator for Multivariate Convex Regression." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/kur2022colt-efficient/)BibTeX
@inproceedings{kur2022colt-efficient,
title = {{An Efficient Minimax Optimal Estimator for Multivariate Convex Regression}},
author = {Kur, Gil and Putterman, Eli},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {1510-1546},
volume = {178},
url = {https://mlanthology.org/colt/2022/kur2022colt-efficient/}
}