An Efficient Minimax Optimal Estimator For Multivariate Convex Regression

Gil Kur, Eli Putterman
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:1510-1546, 2022.

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 this Paper

BibTeX
@InProceedings{pmlr-v178-kur22a, title = {An Efficient Minimax Optimal Estimator For Multivariate Convex Regression}, author = {Kur, Gil and Putterman, Eli}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {1510--1546}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/kur22a/kur22a.pdf}, url = {https://proceedings.mlr.press/v178/kur22a.html}, 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.} }
Endnote
%0 Conference Paper %T An Efficient Minimax Optimal Estimator For Multivariate Convex Regression %A Gil Kur %A Eli Putterman %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-kur22a %I PMLR %P 1510--1546 %U https://proceedings.mlr.press/v178/kur22a.html %V 178 %X 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.
APA
Kur, G. & Putterman, E.. (2022). An Efficient Minimax Optimal Estimator For Multivariate Convex Regression. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:1510-1546 Available from https://proceedings.mlr.press/v178/kur22a.html.

Related Material