  In this work, we study a new approach to optimizing the margin distribution
realized by binary classifiers. The classical approach to this problem is
simply maximization of the expected margin, while more recent proposals
consider simultaneous variance control and proxy objectives based on robust
location estimates, in the vein of keeping the margin distribution sharply
concentrated in a desirable region. While conceptually appealing, these new
approaches are often computationally unwieldy, and theoretical guarantees are
limited. Given this context, we propose an algorithm which searches the
hypothesis space in such a way that a pre-set "margin level" ends up being a
distribution-robust estimator of the margin location. This procedure is easily
implemented using gradient descent, and admits finite-sample bounds on the
excess risk under unbounded inputs. Empirical tests on real-world benchmark
data reinforce the basic principles highlighted by the theory, and are
suggestive of a promising new technique for classification.
