Classification with Margin Constraints: A Unification with Applications to Optimization

Abstract

This paper introduces Classification with Margin Constraints (CMC), a simple generalization of cost-sensitive classification that unifies several learning settings. In particular, we show that a CMC classifier can be used, out of the box, to solve regression, quantile estimation, and several anomaly detection formulations. On the one hand, our reductions to CMC are at the loss level: the optimization problem to solve under the equivalent CMC setting is exactly the same as the optimization problem under the original (e.g. regression) setting. On the other hand, due to the close relationship between CMC and standard binary classification, the ideas proposed for efficient optimization in binary classification naturally extend to CMC. As such, any improvement in CMC optimization immediately transfers to the domains reduced to CMC, without the need for new derivations or programs. To our knowledge, this unified view has been overlooked by the existing practice in the literature, where an optimization technique (such as SMO or PEGASOS) is first developed for binary classification and then extended to other problem domains on a case-by-case basis. We demonstrate the flexibility of CMC by reducing two recent anomaly detection and quantile learning methods to CMC.