# An Efficient Minimax Optimal Estimator For Multivariate Convex Regression

arXiv: https://arxiv.org/abs/2205.03368 · HTML: https://mlsanity.com/paper/2205.03368/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 74 references that are in the map.
- First posted on arXiv 6 May 2022.

## Builds on (most cited first, 20 of 20)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Robust subgaussian estimation of a mean vector in nearly linear time](https://mlsanity.com/paper/1906.03058/) (2019)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [A Computational Framework for Multivariate Convex Regression and its Variants](https://mlsanity.com/paper/1509.08165/) (2015)
- [Recent progress in log-concave density estimation](https://mlsanity.com/paper/1709.03154/) (2017)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression](https://mlsanity.com/paper/1903.05315/) (2019)
- [Fitting Tractable Convex Sets to Support Function Evaluations](https://mlsanity.com/paper/1903.04194/) (2019)
- [On Suboptimality of Least Squares with Application to Estimation of Convex Bodies](https://mlsanity.com/paper/2006.04046/) (2020)
- [A new computational framework for log-concave density estimation](https://mlsanity.com/paper/2105.11387/) (2021)
- [Efficient Robust Proper Learning of Log-concave Distributions](https://mlsanity.com/paper/1606.03077/) (2016)
- [Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities](https://mlsanity.com/paper/1802.10575/) (2018)
- [On the Minimal Error of Empirical Risk Minimization](https://mlsanity.com/paper/2102.12066/) (2021)
- [Adaptive Sampling for Convex Regression](https://mlsanity.com/paper/1808.04523/) (2018)
- [Spectrahedral Regression](https://mlsanity.com/paper/2110.14779/) (2021)
- [A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities](https://mlsanity.com/paper/1812.05524/) (2018)
- [Efficient algorithms for multivariate shape-constrained convex regression problems](https://mlsanity.com/paper/2002.11410/) (2020)

## Abstract (arXiv)

This work studies the computational aspects of multivariate convex regression in dimensions d ≥ 5. Our results include the first estimators that are minimax optimal (up to logarithmic factors) with polynomial runtime in the sample size for both L-Lipschitz convex regression, and Gamma-bounded convex regression under polytopal support. Our analysis combines techniques from empirical process theory, stochastic geometry, and potential theory, and leverages recent algorithmic advances in mean estimation for random vectors and in distribution-free linear regression. These results provide the first efficient, minimax-optimal procedures for non-Donsker classes for which their corresponding least-squares estimator is provably minimax-suboptimal.