Non-parametric binary regression in metric spaces with logarithmic loss

Source abstract

Abstract In Bernoulli discriminative models, log-likelihood is a natural — and, in a well-defined sense, universal — choice of risk score. In this general setting, we propose a non-parametric variant of binary regression, where the model is regularized to be a Lipschitz function taking a metric space to [0, 1]. Our choice of logarithmic loss corresponds to the log-likelihood risk score. This setting presents novel computational and statistical challenges. On the computational front, we derive an efficient optimization algorithm based on interior point methods (IPM); an attractive feature is that it is parameter-free (that is, does not require tuning an update step size). On the statistical front, the unbounded loss function presents a problem for classic generalization bounds, based on covering-number and Rademacher techniques. Additionally, an impossibility result we prove shows that the unboundedness presents an inherent obstruction to learnability. We get around this challenge via an adaptive truncation approach, and also derive a lower bound indicating that the truncation is, in some sense, necessary. To our knowledge, our approach provides the first rigorous computational and theoretical results in this area. Finally, we present encouraging empirical results.