论文标题
关于最小二乘的次要性，并应用于凸体的估计
On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
论文作者
论文摘要
我们开发了一种技术，用于建立针对大型功能的最小二乘（或经验风险最小化）的样品复杂性的下限。作为一个应用程序，我们解决了关于最小二乘最小值的开放问题，以估计尺寸噪声支持功能测量的凸面$ d \ geq 6 $。具体而言，我们确定最小二乘是mimimax sub-timal的，并且达到$ \tildeθ_d（n^{ - 2/（d-1）}）$的速率为$θ_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)})$.
