On Suboptimality of Least Squares with Application to Estimation of Convex Bodies

Abstract

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\ge 6$. Specifically, we establish that Least Squares is mimimax sub-optimal, and achieves a rate of ${\tilde{\Theta }}_d(n^{-2/(d-1)})$ whereas the minimax rate is ${\Theta }_d(n^{-4/(d+3)})$.

arXiv commentTo appaer in Conference on Learning Theory (COLT) 2020

References in corpus (6)

• A new perspective on least squares under convex constraint
• Empirical entropy, minimax regret and minimax risk
• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
• Fitting Tractable Convex Sets to Support Function Evaluations
• Estimation of convex supports from noisy measurements

Cited by in corpus (1)

• On the Minimal Error of Empirical Risk Minimization