A Max-Min Approach to the Worst-Case Class Separation Problem

Abstract

In this paper, we propose a novel discriminative feature learning method based on a minorization-maximization framework for min-max (MM4MM) to address the long-standing “worst-case class separation (WCCS)” problem, which, in our design, refers to maximizing the minimum pairwise Chernoff distance between all class pairs in the low-dimensional subspace. The proposed algorithm relies on the relaxation of a semi-orthogonality constraint, which is proven to be tight at every iteration of the algorithm. To solve the worst-case class separation problem, we first introduce the vanilla version of the proposed algorithm, which requires solving a semi-definite program (SDP) at each iteration. We further simplify it to solving a quadratic program by formulating the dual of the surrogate maximization problem. We also then present reformulations of the worst-case class separation problem that enforce sparsity of the dimension-reducing matrix. The proposed algorithms are computationally efficient and are guaranteed to converge to optimal solutions. An important feature of these algorithms is that they do not require any hyperparameter tuning (except for the sparsity case, where a penalty parameter controlling sparsity must be chosen by the user). Experiments on several machine learning datasets demonstrate the effectiveness of the MM4MM approach.