2022-06-28-kur22a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
An Efficient Minimax Optimal Estimator 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 $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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	kur22a	0	An Efficient Minimax Optimal Estimator For Multivariate Convex Regression	1510	1546	1510-1546	1510	false	Kur, Gil and Putterman, Eli	given family Gil Kur given family Eli Putterman	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/kur22a/kur22a.pdf