On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
This addresses a theoretical open problem in statistical estimation for convex geometry, with implications for researchers in high-dimensional statistics and optimization, though it is incremental in the broader context of machine learning.
The paper tackles the problem of establishing lower bounds on the sample complexity of Least Squares for large function classes, and as an application, it shows that Least Squares is minimax sub-optimal for estimating convex sets from noisy support function measurements in dimensions d≥6, achieving a rate of Θ̃_d(n^{-2/(d-1)}) compared to the minimax rate of Θ_d(n^{-4/(d+3)}).
We develop a technique for establishing lower bounds on the sample complexity of Least Squares (or, Empirical Risk Minimization) for large classes of functions. As an application, we settle an open problem regarding optimality of Least Squares in estimating a convex set from noisy support function measurements in dimension $d\geq 6$. Specifically, we establish that Least Squares is mimimax sub-optimal, and achieves a rate of $\tildeΘ_d(n^{-2/(d-1)})$ whereas the minimax rate is $Θ_d(n^{-4/(d+3)})$.