Learning kernel-based halfspaces with the 0-1 loss. (English) Zbl 1234.68172

Shalev-Shwartz, Shai; Shamir, Ohad; Sridharan, Karthik

SIAM J. Comput. 40, No. 6, 1623-1646 (2011).

Summary: We describe and analyze a new algorithm for agnostically learning kernel-based halfspaces with respect to the 0-1 loss function. Unlike most of the previous formulations, which rely on surrogate convex loss functions (e.g., hinge-loss in support vector machines (SVMs) and log-loss in logistic regression), we provide finite time/sample guarantees with respect to the more natural 0-1 loss function. The proposed algorithm can learn kernel-based halfspaces in worst-case time \(\text{poly}(\exp(L\log(L/\epsilon)))\), for any distribution, where \(L\) is a Lipschitz constant

•  Encyclopedia of Mathematics
•  Encyclopedia of Mathematics
•  nLab
•  Wikipedia
•  Wikipedia
•  Wolfram MathWorld

(which can be thought of as the reciprocal of the margin), and the learned classifier is worse than the optimal halfspace by at most \(\epsilon\). We also prove a hardness result, showing that under a certain cryptographic assumption, no algorithm can learn kernel-based halfspaces in time polynomial in \(L\).

MSC:

68Q32	Computational learning theory
68T05	Learning and adaptive systems in artificial intelligence
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

learning halfspaces; kernel methods; learning theory