Distributionally Robust Universal Classification

Abstract

The Universal Classification (UC) problem seeks an optimal classifier from a universal policy space that includes all the measurable functions to minimize the zero-one loss. However, conventional empirical risk minimization often leads to overfitting and poor out-of-sample performance. To address this limitation, we study the Distributionally Robust Universal Classification (DRUC) problem with the Wasserstein ambiguity set centered at the empirical distribution. Unfortunately, the policy space of the DRUC formulation is infinite-dimensional, posing a significant computational challenge. To overcome this curse of dimensionality, we develop an in-sample DRUC counterpart, whose reformulation requires the number of decision variables independent of the covariate dimension and proportional to the sample size, while preserving its distributional robustness properties. We prove that, asymptotically, both the DRUC and the in-sample DRUC optimal values converge to the optimal UC value, and under mild conditions, we provide finite-sample performance guarantees. Furthermore, we derive a mixed-integer linear programming (MILP) reformulation to obtain the optimal in-sample DRUC policy and propose an efficient 2-approximation algorithm. Our numerical experiments demonstrate the reliability of the approximation algorithm, the ability to mitigate overfitting issues, and the superior out-of-sample performance of the proposed method.