Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins

2020/10/01 by Frei, Spencer, Cao, Yuan, Gu, Quanquan
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2010.00539

Abstract

We analyze the properties of gradient descent on convex surrogates for the zero-one loss for the agnostic learning of linear halfspaces. If OPT is the best classification error achieved by a halfspace, by appealing to the notion of soft margins we are able to show that gradient descent finds halfspaces with classification error O(OPT^1/2) + ε in poly(d,1/ε) time and sample complexity for a broad class of distributions that includes log-concave isotropic distributions as a subclass. Along the way we answer a question recently posed by Ji et al. (2020) on how the tail behavior of a loss function can affect sample complexity and runtime guarantees for gradient descent.

Related

• The complexity of learning halfspaces using generalized linear methods
• Learning Kernel-Based Halfspaces with the Zero-One Loss
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
• Agnostic Learnability of Halfspaces via Logistic Loss