Fast, Relaxation‑ and Hyperparameter‑Free Pairwise Worst-Case Class Separation

In this paper, we investigate a novel discriminative dimensionality reduction method based on maximizing the minimum pairwise ratio of between-class to within-class scatter. This objective function enhances class separability by providing critical, adaptive control over the variance within each class pair. The resulting max-min fractional program is non-convex and challenging to solve. Our main contribution is F${}^3$-PWCRA (Fast, Free of relaxation, Free of hyperparameters for Pairwise Worst-Case Ratio Analysis), a provably convergent two-level algorithm: an outer generalized Dinkelbach-type loop transforms the fractional objective into subtractive subproblems, ensuring the global convergence of the outer algorithm. Then, we propose a bisection strategy as an alternative, which offers robust convergence and straightforward implementation. For the inner loop, we develop an efficient minorization-maximization (MM) algorithm that tackles the non-convex subproblem by iteratively solving a simple quadratic program (QP), which we derive from the dual of a convex surrogate. F${}^3$-PWCRA is computationally efficient, free from semidefinite relaxations and hyperparameter tuning, and extensive benchmarks show it consistently outperforms state-of-the-art methods in classification error.