Background.
Motivated by the observation that the popular AdaBoost algorithm (which works by minimizing the (convex) exponential potential function) can have empirically poor classification accuracy when run on noisy data [1]}, [2]}, [3]}, Long and Servedio [4]} studied the performance of classification algorithms which work by minimizing a convex potential function in settings where linearly separable data is contaminated with random classification noise (RCN). The main result of [4]} is a proof that for a certain simple learning problem corresponding to a “clean” data distribution \({\cal D}_1\)  that is linearly separable with a margin, for any “convex potential function” \(\phi \) , minimizing \(\phi \)  over all linear combinations of base features in the presence of random classification noise only yields a binary classifier with an error rate of 1/2 under the clean distribution \({\cal D}_1\) . (Here a “convex potential function” is a convex function \(\phi : \rightarrow \)  satisfying certain mild conditions which we detail in def:cpf.) This is in sharp contrast with the fact that,
in the noise-free setting of a data distribution that is linearly separable with a margin,
driving the potential to zero leads to a
perfectly accurate binary classifier.
