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 d5. We present the first computationally efficient minimax optimal (up to logarithmic factors) estimators for the tasks of L-Lipschitz and Γ-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