09/07/2020

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

Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina

Keywords: Regression, Excess risk bounds and generalization error bounds, High-dimensional statistics, Loss functions

Abstract Paper Similar Papers

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

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at COLT 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 16:40 
 0
 0
 0
 0
 3:00 
 0
 0
 0
 0
 12:09 
 0
 0
 0
 0
 15:52 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 11:50 
 0
 0
 0
 0
 3:08 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 5:17 
 0
 0
 0
 0
 7:26 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 22:51 
 0
 0
 0
 0
 12:52 
 0
 0
 0
 0
 2:00 
 0
 0
 0
 0
 16:08 
 0
 0
 0
 0
 17:27 
 0
 0
 0
 0
 14:21 
 0
 0
 0
 0
 9:47 
 0
 0
 0
 0
 15:15 
 0
 0
 0
 0
 16:06 
 0
 0
 0
 0
 5:21 
 0
 0
 0
 0
 13:44 
 0
 0
 0
 0
 10:14 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 11:10 
 0
 0
 0
 0
 14:45 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 15:11 
 0
 0
 0
 0
 14:21 
 0
 0
 0
 0
 13:14 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 4:19 
 0
 0
 0
 0
 2:56 
 0
 0
 0
 0
 15:32 
 0
 0
 0
 0
 7:29 
 0
 0
 0
 0
 4:55 
 0
 0
 0
 0
 14:52 
 0
 0
 0
 0
 13:19