Groups
0-1 loss directly measures classification error but is discontinuous and non-convex, making optimization computationally hard.
PAC learning formalizes when a learner can probably (with probability at least 1−δ) and approximately (error at most ε) succeed using a polynomial number of samples.