  In this paper, we theoretically justify an approach popular among
participants of the Higgs Boson Machine Learning Challenge to optimize
approximate median significance (AMS). The approach is based on the following
two-stage procedure. First, a real-valued function is learned by minimizing a
surrogate loss for binary classification, such as logistic loss, on the
training sample. Then, a threshold is tuned on a separate validation sample, by
direct optimization of AMS. We show that the regret of the resulting
(thresholded) classifier measured with respect to the squared AMS, is
upperbounded by the regret of the underlying real-valued function measured with
respect to the logistic loss. Hence, we prove that minimizing logistic
surrogate is a consistent method of optimizing AMS.
