On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
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)})$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
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…
regressionOne Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers
We propose the first general and practical framework to design certifiable algorithms for robust geometric perception in the presence of a large amount of outliers. We investigate the use of a truncated least squares (TL…
AllPose EstimationAn LiGME Regularizer of Designated Isolated Minimizers -- An Application to Discrete-Valued Signal Estimation
For a regularized least squares estimation of discrete-valued signals, we propose a Linearly involved Generalized Moreau Enhanced (LiGME) regularizer, as a nonconvex regularizer, of designated isolated minimizers. The pr…
Loss minimization and parameter estimation with heavy tails
This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the tech…
parameter estimationregressionGlobal Convergence of Iteratively Reweighted Least Squares for Robust Subspace Recovery
Robust subspace estimation is fundamental to many machine learning and data analysis tasks. Iteratively Reweighted Least Squares (IRLS) is an elegant and empirically effective approach to this problem, yet its theoretica…