Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
This addresses a theoretical gap in nonparametric regression for statisticians and machine learning researchers, revealing fundamental limitations of LSEs in high-dimensional convex settings.
The paper shows that Least Squares Estimators (LSEs) are suboptimal for estimating d-dimensional convex functions in squared error loss when d ≥ 5, with LSE risk scaling as n^{-2/d} compared to the minimax risk of n^{-4/(d+4)} across various function classes and designs.
Under the usual nonparametric regression model with Gaussian errors, Least Squares Estimators (LSEs) over natural subclasses of convex functions are shown to be suboptimal for estimating a $d$-dimensional convex function in squared error loss when the dimension $d$ is 5 or larger. The specific function classes considered include: (i) bounded convex functions supported on a polytope (in random design), (ii) Lipschitz convex functions supported on any convex domain (in random design), (iii) convex functions supported on a polytope (in fixed design). For each of these classes, the risk of the LSE is proved to be of the order $n^{-2/d}$ (up to logarithmic factors) while the minimax risk is $n^{-4/(d+4)}$, when $d \ge 5$. In addition, the first rate of convergence results (worst case and adaptive) for the unrestricted convex LSE are established in fixed-design for polytopal domains for all $d \geq 1$. Some new metric entropy results for convex functions are also proved which are of independent interest.