04/08/2021

Agnostic Proper Learning of Halfspaces under Gaussian Marginals

Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

Keywords:

Abstract Paper Similar Papers

Abstract: We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose running time qualitatively matches that of the best known improper agnostic learner. Building on this result, we also obtain the first proper polynomial time approximation scheme (PTAS) for agnostically learning homogeneous halfspaces. Our techniques naturally extend to agnostically learning linear models with respect to other activation functions, yielding the first proper agnostic algorithm for ReLU regression.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at COLT 2021 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
 13:19 
 0
 0
 0
 0
 12:27 
 0
 0
 0
 0
 13:54 
 0
 0
 0
 0
 14:00 
 0
 0
 0
 0
 16:22 
 1
 1
 0
 0
 2:59 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 3:25 
 0
 1
 0
 0
 5:10 
 0
 0
 0
 0
 3:48 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 13:59 
 1
 0
 0
 0
 2:43 
 0
 0
 0
 0
 4:48 
 0
 0
 0
 0
 15:14 
 0
 0
 0
 0
 12:52 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 12:32 
 0
 0
 0
 0
 0:50 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 3:26 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 4:15 
 0
 0
 0
 0
 14:30 
 0
 0
 0
 0
 12:07 
 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 14:50 
 0
 0
 0
 0
 12:11 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 10:55 
 0
 0
 0
 0
 11:59 
 1
 1
 0
 0
 3:14 
 0
 0
 0
 0
 4:54 
 0
 1
 1
 1
 5:22 
 0
 0
 0
 0
 6:30 
 0
 0
 0
 0
 17:13 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 5:15