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

Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2406-2424, 2020.

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\geq 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)})$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-kur20a, title = {On Suboptimality of Least Squares with Application to Estimation of Convex Bodies}, author = {Kur, Gil and Rakhlin, Alexander and Guntuboyina, Adityanand}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {2406--2424}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/kur20a/kur20a.pdf}, url = {https://proceedings.mlr.press/v125/kur20a.html}, 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\geq 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)})$.} }
Endnote
%0 Conference Paper %T On Suboptimality of Least Squares with Application to Estimation of Convex Bodies %A Gil Kur %A Alexander Rakhlin %A Adityanand Guntuboyina %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-kur20a %I PMLR %P 2406--2424 %U https://proceedings.mlr.press/v125/kur20a.html %V 125 %X 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{\Theta}_d(n^{-2/(d-1)})$ whereas the minimax rate is $\Theta_d(n^{-4/(d+3)})$.
APA
Kur, G., Rakhlin, A. & Guntuboyina, A.. (2020). On Suboptimality of Least Squares with Application to Estimation of Convex Bodies. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:2406-2424 Available from https://proceedings.mlr.press/v125/kur20a.html.

Related Material