A Max-Min Approach to the Worst-Case Class Separation Problem
Authors: Mohammad Mahdi Omati
Prabhu babu
Petre Stoica
Arash Amini
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (07/2025)
A Max-Min Approach to the Worst-Case Class Separation Problem
Mohammad Mahdi Omati Deportment of Electrical Engineering Sharif University of Technology, Tehran, Iran
mohammad cokemmood_omati@yyaooo..
Prabhu Babu
prabhubabu Geaare iitd ac. in
Centre for Applied Research in Electrovics (CARE) Indian Institute of Technology Delhi, New Delhi-110016, India
Petre Stoica
Psoit uu.se
Division of Systems and Control, Department of Information Technolog Uppsala University, Uppsala, Sweden, 75237
Arash Amini
aamini@sharif.cmm edu
Department of Electrical Engineering
Sharif University of Technology, Tehrun, Iran
Reviewed on OpenReview: https: // openreview. net/ net/ forum? id= EEmuBd tfZ
Abstract
In this paper, we propose a novel discriminative feature learning method based on a cnmoriiatiionmmximmaaali framework for min-max (MM4MM) to address the long-standing "worst-case class separation (WCCS)" problem, which, in our design, refers maximizing the minimum pairwise Chernoff distance between all class pairs in the low-dimensional sub- space. The proposed algorithm relies on the relaxation of 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 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--rddueing matrix. The proposed algorithms com- putationally efficient and guaranteed to converge optimal solutions. An important feature of these algorithms is that they do not require any hyperparameter tuning (except for the sparsity case, where à penalty parameler controlling sparsily must be chosen by the user). Experiments on several machine learning datasets demonstrate the effectiveness of the MM4MM approach.
1 Introduction
As data acquisition methods advance, modern datasets have become more complex and feature-rich, leading to potential issues such overfitting and reduced interpretability due to redundant or irrelevant features. These challenges are particularly relevant in classification tasks, where effective fcature representation is critical for optimal performance. Dimensionality reduction methods, including feature extraction Nie et al.
(2021b); Wang et al. (2024); Nie et al. (2023 2021a); Chang et al.) (2016); Nie et al. (2017): Li et al. (2018a) and feature selection Gui et (2017) Li et al. (2017); (hheikhpour et al. (2017): Hancer al. (2020
ett al. (2022): Shen al. (2021): Li al. (2018b): Luo et al. (2018). are widely used enhance classification accuracy by focusing the most relevant. aspects of the data.

---

Published in Transactions on Machine Learning Research (07/2025)
Among the various dimensionality reduction approaches, specific category of linear supervised methods, known as discriminant analysis (DA), has attracted considerable interest due to its focus on enhancing class separability. Multiple criteria have been proposed in the literature, each based on different definitions of
separability Fisher [9366); Rao (1948) : Bian & Tao 2011 :: Zhang & Young 20100 Yu et al.] (2011):
: Su et al.
(2015): Nie el al. (2021b); Wang et al. (2024). Linear Discriminant Analysis (LDA) is the most widely used
technique within supervised learning, originally introduced by byFhhhrrr (1366) for binary classification and later extended to multi-class applications Rao (1945). The well-known Fisher criterion in LDA aims to identify low-dimensional subspace that simultancously maximizes inter-class scatter while minimizing intra-class scatter. Thanks to this approach, LDA has found extensive applications. Nonetheless, traditional L.DA faces certain limitations, including the risks of over-reduction, issues with small sample size, assumptions of Gaussian-distributedd data Nie el al. (0000a). Nie et al. 2020bb, and sensitivity to outliers Nie el. al. (021b
Heteroscedastic LDA (HLDA) Loog & Duin 2004)) modifies traditional LDA to handle heteroscedastic cases by using the Chernoff criterion instcad of the Fisher criterion. In this approach, the Chernoff distance is applied to generalize the concept of inter-class scatter. A theoretical analysis of HL.DA is detailed in Peng jet al.) In this class of methods, based on the definition of inter-class scatter, the Fisher criterion maximizes the arithmetic mean of all pairwise distances. This approach causes the class pair with the largest distance to dominate the projection direction, leading to an overlap of closely spaced class pairs chirs-referree to as the "worst-case class separation" problem.
To tackle this issue, various max-min distance analysis (MMDA) methods have been introduced, based on the assumption of homoscedastic Gaussian distributions, as in Bian & Tao (2011;; ; Zhang & Yeung (2010); Yu et al. (2011). These methods aim to maximize the minimum inter-class separability within the latent subspace. However, in real-world scenarios, classes often do not conform to the homoscedastic Gaussian assumption, meaning that differences in class means alone do not fully capture the separation between classes. Besides, existing MMDA methods attempt to increase the distance between nearest class means within the latent subspace but overlook differences in class covariances.
In Su et al. (2015), the authors introduce the heteroscedastic max-min distance analysis (HMMDA) method for dimensionality reduction, designed to leverage discriminative information derived from differences in class covariances, known as whitened HMMDA (WHMMDA). To address intra-class scatter, WHMMDA applies preprocessing whilening step. In Wang et al. (2024) the authors propose another criterion called Max-Min Ratio Analysis (MMRA), which focuses on maximizing the minimum ratio value between inter- class and intra-class scatter to enhance the separability of overlapping pairwise classes, In both Su et al.] (2015) Wang et al. (2024), to solve their specified optimization problem, the authors relax the non-convex optimization problem into a semidefinite problem, which can be solved using convex programming tools. They also propose a synthesis method to improve the precision of the solution. However, the method has a limitation: the relaxation may not be tight across all problem dimensions, potentially yielding suboptimal solutions.
In this paper, we propose an itcrative algorithm for addressing the hetcroscodastic max-min distance analysis problem, employing the minorizaliion-maxiniaalll framework for min-max (MM4MM) Saini et al. (2024) to tackle the long-standing worst-case class separation (WCCS) problem. The algorithm is built upon the relaxation of a semi-orthogonalitt constraint, which proved to be tight at cach iteration. We first introduce basic version of the algorithm that requires solving semi-definite program (SDP) at each iteration. We simplify this to quadratic program by deriving the dual of the surrogate maximization problem. Additionally, we provide reformulations that incorporate sparsity of the dimension-reducing matrix. The proposed algorithms are computationally efficient and enjoy guaranteed convergence. A notable benefit of our approach is that it requires no hyperparameter tuning, except in the sparsity case where a user-defined penalty parameter is needed. Experimental results on various machine learning datasets confirm the superior performance of the proposed approach compared to competing methods.
The paper is organized follows: Section 2 presents the problem formulation for the worst-case class scparation design and the sparse penalized problem. Scction 3 details the proposed MM4MM approach. Section 4 provides numerical results, and Section 5 concludes the paper.
2

---

Published in Transactions on Machine Learning Research (07 (075)
2 Problem Formulation
In this section, we formulate the worst-case class separation problem: with and without sparsity penalty. Consider the dataset X = X2, ._]] E Rdx", where d represents the dimensionality of each data point, and n indicates the total number of data points, divided into C' classes. Let m,, Σ, and p4 represent the mean, covariance, and prior probability of class i, respectively, and let S denote the intra-class seatter, given by S.. = E If we define the whitening transformation as Wi = S E Rdxd, and apply it to the dataset X, the intra-class scatter matrix becomes an identity matrix, while the covariances of different classes remain different. As a result, relying solely on diffcrences in class means does not adcquately capture class separability. Assuming each class follows Gaussian distribution with distinct means and covariances, the Chernoff distance deij between classes i and j leverages discriminative information from covariance differences, enabling a more accurate description of class overlap:
Σij
dai = (m, - / (m, mn)) + ai (1 - acr)
log
(1)
1-ais"
Σ
Σ
where Osj = pe+p,' m = WT m, and Σ. = W W, represent the mean and variance of class i in the
P:
whitened space, and Σng ag E, + (1 - azy Σ
The doy can be expressed as the trace of a positive semi-definite matrix Scxj (sec, c.g.: Loog & Duin (2004)):
1/2 (m, my) (m, - my)² Σ 1/2 Sco = Eng
1/2
Oijy (1 aij) (log Eig - Oni log Es (1 - any) log E3 (2)
1
+
The aim of our WCCS problem is to learn a dimension-reducing matrix W E Rdxd', which projects the high-dimensional data X onto a d'-dimensional subspace, while maximizing the minimum pairwise Chernoff distance the latent subspace:
max min ISKJSC s.t.
(WTScc) W)
(3)
W Is,
where Sci, = (p:P;) Sci-
As extension of WCCS problem, we also consider the problem where sparsity is imposed on W. To achieve this, we formulate the following penalized problem:
Tr (W"S Scy W) Al W|h
max min W Isijso
(4)
s.t.
W'W=I,
where [W] 1 denotes the sum of the absolute values of the elements of W, and X is predefined penalty parameter that regulates the sparsity of W. The formulation in (4h is inspired by prior work on sparse PCA D' aspremont et al. (2004); Zou & Xue (0018): Zou et al. (2006); Babu & Stoica (2023). whore the & norm of W typically added as a penalty lerm the objective to induce sparsity and thereby highlight the most
significant elements of the estimated principal components.
In the next section, start by reviewing the key steps of the peperiaation-maximizzinn (MM) approach for solving maximization problems. We then explore how the MM approach can be adapted to address max-min problems, referred to as the MM4MM approach, which is the focus of this paper.
3
MM and MM4MM
3.1
MM framework
Consider the following constrained maximization problem:
max fxx,
(5)
xex
3

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where is the variable to be optimized, f(x) is the objective function, and X denotes the constraint set. An MM-based algorithm addresses this problem by first creating surrogate function g (x x') that serves as lower bound for the objective function f(x) at the current iteration point x². In the second step, the algorithm maximizes this surrogate function to determine the next itcrate:
x ++ arg max 9 (x x²). XEX
66)
The steps described above are iteratively applied until the algorithm converges to a stationary point of the problem in (7). For g (x x') to be considered surrogate function, it must satisfy the following conditions:
9 x S fxx) Vx ExEX
x
(7)
g (xt x²) f (x*).
(8)
To summarize, the main steps of the MM approach are as follows:
1) Initialize with a feasible point xº.
2) Construct a minorizing function g (x x²) for f(x) at x!.
3) Compute x++1 E arg max g (x x²).
xEX
4) If |((x*)-(((*1)) c, where e is predefined convergence threshold, terminate; otherwise, set [xx*)]
t = + and return to Step 2.
It is easy to demonstrate that each MM step results in a monotonic increase in the objective function at every iteration, i.e.,
(x 2 9 (x++1 xx') 2 g (x' xx) = f (x').
(9)
The first. inequality and the third equality follow from and while the second inequality arises from
3.2 MM4MM framework
Consider the following max-min optimization problem:
max x
f(x) &
min fo f((x) 1.2 K
(10)
A surrogate function for the above max-min problem is g (x x(), defined as follows: min gi (x x²), v=1,2..... _K
(x x')
(11)
where each gi (xl x²) is a tight lower bound on fxx at xt. The individual surrogates (x) satisfy the following conditions:
xx' x²) Si (x'),
(12)
g: (x x²) fx(x).
(13)
It can be readily demonstrated that the surrogate function g (x x'), as defined in meets the conditions specified in and
gs
x x²) S fx()
min
Ii (x x²) S min f((x) = (x x²) s f(x),
(14)
im 1.1.2...
im 1.2..... K
and
9 (x' xx)
min 9i (x" xx)) min fs (xx)= fx').
(15)
i=1,2..
i=1,2,".,
As in the general MM framework, it can shown here that the iterates {xt) increase the objective function f(x) monotonic manner and converge to a stationary point. For a comprehensive discussion on the MM approach including various methods for deriving surrogate functions across different applications-ree -efeer Sun al. (2017): Saini et al. (2024h.
4

---

Published in Transactions on Machine Learning Research (07 (025)
3.3 Solving the WCCS problem
In this section, we will derive the MM4MM algorithm for the problem in 33 For the sake of convenience, we restate this optimization problem as follows:
min
(W)
ISKiSO
(16)
s.1.
w'W
where fay(W) & Tr (WTSc W). Before procoeding with the solution to 16 lemma that will aid in developing the proposed algorithm.
present and prove
Lemma The non-come coneconver semi orthoorthognnality constraint W I in and the global mazimizer of the relared problem will satisfy the constraint in 16
16 can be relaxed to W o
Proof. See Appendix 6.1
Applying Lemma ! we reformulate the problem in 16 as the following relaxed problem:
max min ISiGSO
Tr (WTSSy W)
(17)
s.t. WL
L
W
The constraint in 17 is convex since it can be rephrased as linear matrix inequality
3 0.
W
L
However, the maximization problem in 177 remains non-couvex, as the objective function (for each j)) is a convex quadratic in W, and the inclusion of the min operator adds further complications. To tackle this, employ the MM4MM approach to solve (17). Following the MM4MM steps outlined in Subsection 3.2 each convex quadratic term in (17) can be bounded from below by its tangent hyperplane at W This yields MM surrogate for the objective in 17). Given W for any (i,j), we obtain:
(w) Tr (WT W) 2 Tr ((W")* SeN, W') 2Th ((W") Scu (w (W- (W-"))
= 2Tr ((w') SoN w) - ((W') SCo W!) & (W)
(18)
Then the surrogate problem given by:
max W
min
Py (W)
isisss
I
WT
(19)
s.t.
x O.
W W I
By utilizing the expression for 95 (W in
19 we obtain:
max
min
2TH (A7 W)
+ cij
W
isijse
I
WT
(20)
s.t.
> 0.
W
I
where
A, A (W')7 SSy.
(21)
Tr ((W')* So0 w¹)
(22)
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
The problem 20
is convex and can be transformed into semidefinite program (SDP):
max
W
S.L.
2T (A W) +a22a, 1si<jsc
(23)
I
W
0
La
W
which can be efficiently handled using, for example, CVX Grant & Boyd (0144). The maximizer W for 20p (or equivalently (23)) meets the constraint W W =I at every iteration of the algorithm, not solely at convergence. This notable property will be demonstrated in the following. During this process, we will also
develop a computationally simpler reformulation of (33
We start by noting that the inner minimization problem in 20 with respect to the discrete variables i, can be reformulated using auxiliary variables { 2 0} satisfying Eisiesoo Fij = 1, as shown below:
max min W (#i)
2Tr (A T W) +
Σ
Cij
Igijso
s.t.
2i 220 0,
Σ 24 =1
(24)
Isijis
I
W I
0
W
where A Eisijjc Zi A.g. The objective function in 24 is linear in W for a given z and linear in z when W is fixed. Additionally, the constraint sets for both W and z are compact and convex. Therefore, by applying the minimax theorem Sion (1988), we can interchange the max and min operators in 24 yielding the following equivalent problem:
min max (11) W
2TH (A W)
+
EigCij ISijSC
Σ
Σ
s.t.
24 2
Z4H =1
(25)
ISKiSO
L
W
0
W
L.
The inner maximization problem 25 can be directly solved in closed form. Focusing on the first term the objective of (24), we can apply the Von Neumann inequality Marshall (1979), yielding:
Tr (AT S (A(
(26)
where o (A) and (x(W) represent the non-zero singular values of A and W, respectively. Since o (W) S 1, it follows that
Tr (A" < Σ (A),
(27)
with the equality obtained for
W ="=Al- A(TA)=
(28)
Indeed,
Tr (A' = (AAAA) +) =Tr -T - & (A).
(29)

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm MM4MM for WCCS (SDP approach)
Input: Initial estimate W (Serg) for 1 < i < S C, and convergence threshold 10-5.
Set == O.
1: repeat
Compute (Agr Giy) from 21
22
Compute z² by solving 30
Obtain W from (31
Set t = f 1.
6: until
E
[W
Output: W
W convergence.
Notice that W fulfills the constraint in [6 ie., (W*)² W =. Therefore, asserted, the maximizer of
23
satisfies the constraint WTW I at each itcration. Substituting 28 into 25 leads to the following
problem:
min {=5))
2
(z)) +
ZifCif ISKCJS
Σ
(30)
s.t.
Zij
Fij =1
ISijIC
where emphasize that A depends
The first term in 30 equals twice the nuclear norm of A()),
represented as [z)(z)),,, which is convex function of A and thus = As a result, (30) is convex problem,
similar to j23 and can be reformulated as an SDP Recht et al. (2010). However, compared to 23 the
nunber of variables and constraints in (30 is smaller, offering a potential advantage.
After obtaining the minimizer z" by solving 30 the corresponding W (which the maximizer of 23 can be calculated as:
w(++1) A (z') (A" (z") (z')
(31)
and it will be used as the next iteration. The MM procedure iterates this process until convergence is achioved. The steps of the MM4MM for the WCCS problem are summarized in Algorithm [
The primary computational demand of the proposed algorithm stems from calculating (Aij] for S
S C, solving the SDP in (30 and updating W++1 as outlined in 331 The computation of {At) for 1 isiejs C' involves matrix-matrin multiplications, which can be performed in O D(FIC-1)d'd operations. Solving the SDP in (30) has computational cost of approximately O(d + d''d.5) operations, while the evaluation in 31 requires O + Odd))) operations. Therefore, the total computational complexity per iteration is ( + d'dd4...
In the following, we introduce an alternative method for solving load. To achieve this, we begin with the formulation presented
30
aimed at reducing the computational
30
min (
2x] +
Σ
ZifGi
1sicisc
(32)
s.t.
2g 00
Σ 2ij =1
ISijsE
Let us introduce an auxillary variable Φ 0) and reformulate
32
as follows:
min (
Tr Tr + Ii (A (z)
ISicis
(33)
s.t.
By 120 O.
Σ
Ey =1
The problems and 33
equivalent, shown below. By minimizing 33 with respect to & while keeping fixed, find that the minimizer Φ' (ATA) - Substituting this back into (33 results in

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 2 Alternating Minimization Approach for Solving (30
1: Input: Initial estimate z", coefficients {eij, Aijh, and convergence threshold c = 10-3
2: Set f=0
repeat
Compute T' (())))
5: Obtain + by solving equation (35
6:
Set t = =
7: until x x 225||
6
Output: z z' al convergence
the problem 32
The problem in 333 can be tackled using alternating minimization method: for given
z, denoted as z we obtain the minimizer &' as described above. With Φ = &' fixed, the minimizer z can be found by solving the following convex problem:
min {
Tr (A (AAA)))
ZtyCif ISisiSc
E
(34)
s.t.
Byg 2 O,
Σ
Zij =1
Igiesc
which be reformulated a quadratic program (QP):
min (
z²Qz=
Σ
CifCij
1sicss
(35)
s.l.
Zij 2 0,
Σ Zij =1
15KjSC
where
Q = = (')
(36)
(i (i- 1)(2 + i. Here,
with = [w] 02
vk), K C(C-1), and Us vec(A.) rec(Aig), where k:
2
denotes the Kronecker product. For the derivation of the relationship between Q and the matrices Ag, refer to Appendix 6.2 The quadratic program (QP) in (35 can be efficiently solved using standard solvers, with a computational complexity that includes updating of at cost of approximately O (C*) O (d3) operations. This is significantly lower than O ((d + d') d'))..) However, unlike the problem in (30), the QP in (35) must be solved multiple times for various Ø² matrices. Fortunately, this typically requires only few iterations (usually fewer than 10). The iterative steps for the alternating minimization algorithm used to find the solution z for (30 are outlined in Algorithm 2
3.4 Solving the WCCS problem under the sparsity penalty
In this subsection, present extension of the proposed method to solve problem 4
max min
( W||]
W Isigse
(37)
S.L.
Www =I
where À a specified parameter that governs the sparsity of W. In a manner similar semniorthogonality constraint:
17 we relax the
max
min Isisiso
fis(W) A||W||
L
WT
(38)
s.t.
b
0
W
I
8

---

Published in Transactions on Machine Learning Research (07/2025)
For fixed W W the quadratic functions (fo(W) can be minorized using their tangent hyperplanes, leading to the following surrogate problem:
max min W ISK3EC
(gg (W) X| W[
la
W
(39)
s.t.
0 0
W
La
where, as previously mentioned, 9zy (:)(W) = 2T (A + Cij- is obvious that 39 is convex (specifically
an SDP) and can be solved using CVX. Similar subsection 3.3 the optimal solution of (39) can be shown
satisfy the constraint WTW To demonstrate this, we reformulate the problem in 39 using auxiliary
variables and z as follows:
max min W (
Σ
24j9ts (W) + AATI
Igijjso
s.t.
Zij 2 0,
Σ 2ij =1
ISicjso
(40)
La
WT
0
W
La
S1
Vi
Minimizing 40 with respect to B and yields the objective in 39 thus 39 and (40p are equivalent. By applying the minimax theorem (as the objective and constraints of 40 meet the required conditions), the max and min operators can interchanged:
min max W
Σ Isijis
Z4j9is (W) + ATT (W)W)
8.6.
Zij 2 0,
Σ Zij =1 ISijsC
(41)
WT
0
W
Ia
[B]
S1
Vi,j
By substituting the expression 9i5 (W) TT (A7, W)
+ Cijz
41
can be reformulated
min max 2Tr
A
B
W
+
Σ
ZijCij
2
ISijJCC
Σ
s.t.
Bg 2 0,
2ij =1
Isicjsc
(42)
Is
WT
0
W
I
Blal
<
Vi.j
Similar 28 the maximizer W of can be obtained in closed form:
W = A + A B) ((A+ (27 B 2 2
> A
)
A
(43)
which moets the constraint WTW I. Therefore, in this case as well, the MM iterations meet the semi- orthogonality constraint. The pscudocode for the proposed approach with sparsity penalty is summarized
in Algorithm 3
9

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 3 MM4MM for WCCS with sparsity penalty
Input: Initial estimate W set of matrices (Sci)} for 1 C, penalty paramcter X, and convergence
threshold = 10-5.
Initialize: Set =
repeat
2: Compute {Ag, Ciy) from
21
22
3: Obtain W by solving 39
4: Set. 1= ( +1.
5: until [W -W"]
6
[W7]
Output: W W at convergence.
4 Numerical results
4.1 Datasets
We evaluate the performance of the MM4MM algorithm for solving WCCS problem, with and without sparsity penalty. The evaluation is conducted six real-world datasets from the UCI Machine Learning Repository and Kaggle. These datasets are briefly described below:
The Iris dataset consists of 150 instances, each represented by four features: sepal length, sepal width, petal length, and petal width. The label categorizes each instance into one of three classes: Tris-setosa, Iris-versicolor, or Iris-virginica, with 50 samples per class. The Wine dataset contains 177 instances, each described by 13 chemical attributes such as alcohol content, malie acid, and ash, with labels indicating the type of wine corresponding one of three cultivars. The Seeds dataset comprises 210 instances with seven features that describe the geometric properties of wheat kernels, including arca, perimeter, and compactness, and is divided into three classes representing different lypes of wheat: Kama, Rosa, and Canadian. The Prestige dataset includes 98 instances with features representing education level, income, percentage of women in the occupation, and prestige scores. Depending on the analysis, the labels can be used for classification or regression tasks. The Diamonds dataset contains 599 instances and four main features: carat weight,, depth, table size, and clarity. The labels represent the quality of the cut, categorized into four classes: Fair, Good, Ideal, and Premium. Finally, the Digit dataset Prabhu (2019) is a high-dimensional dataset of 1, 1,797 samples, each represented by 64-dimensional features corresponding to images of handwritten digits (0 through 9).
4.2 Methods
For the five nogiD datasets (Iris, Wine, Seeds, Prestige, Diamond), we performed five-fold cross-validation: each dataset was divided into five subsets, with four subsets used for training and one for testing per fold. Performance metrics were computed over the five test folds. For the high-dimensional Digit dataset, we followed Wang et al. (2024), performing 20 independent experimental runs where 50% of samples were randomly selected for training and the remainder for testing in each run. PCA preprocessing was applied to all datasets following Wang et al. (2024): Su et al. 2015). preserving 98% of the variance. Final results report average accuracy standard deviation (over five folds for non-Digit datasots; over 20 runs for Digit).
For comparison, we included several widely used discriminant analysis methods: LDA Fisher
(936];
Rao
(1948), HLDA Loog & Duin 2004), MMDA Bian & Tao (2011), WHMMDA Su et al. (0018
2015
and
MMRA Wang et al. (2024).
For all datasets, the original dimensionality d was reduced to various potential values from 1 to d 1, except for LDA, where the maximum dimensionality of the selected subspace was constrained to C - 1 to achieve its best performance and allow for a fair comparison across methods.
Classification in the reduced subspaces was performed using three classifiers: the nearest neighbor classifier (1-NN), the nearest mean classifier (NM), and the quadratic discriminant analysis (QDA). The quadratic
10

---

Published in Transactions on Machine Learning Research (07/2025)
Table 1: Classifier Results Across 6 Datasets
Dataset
Classifier
LDA
IILDA
MMDA
WIIMMDA
MMRA
MM4MM (QP)
MM4MM (Sparse)
1-NN
0.06667
0.0533
0.0667
0.08667
0.0533
0.0600
0.0585
Std: 0.0236)
0.0298)
(2, Std: (.0471)
(.0226)
(3. 0.0296)
(3. Std: 0.0194)
(3. Std: 0.0360)
Iris
NM
(,0533
0,0467
0,0286
0.0287
0.0031
0,0200
0.0200
0.0288)
[3, Std:: 0.0447)
13, Std: 0.0279)
33, Std: 0.0148)
13. 0.03333
(3. Std: 0.0183)
[3. Strl: D-183)
QDA
0,0467
0,0400
0,0833
0,0033
0,0400
0.0533
0.0267
0.0350)
[3, Strl: 0.02279)
13, Std: 0.0236)
13, 0.0236)
13, Std. 0.0270)
[3. Stdl 0.0236)
[3. Stdl: (.0279)
1-NN
0.0224
0,0170
0.0168
0.0279
0,0056
0.0225
0.0170
Sté: 0.0125)
(12, Std: 0.0155)
(3. Std: 0,0154)
(4. Sté: 0.0481)
12. Std: 0.0124)
(10, Sté: 0.0126)
(3. Std: 0.0255)
NM
0.0113
0.0113
0,1224
0.0171
0.12225
0.0168
0.D057
Stu: 0.0154)
Std: 0.D164)
(4, Std: 0.0126)
Stu:: 0.0256)
(12. Std: D:02386)
(10. Std: D:0164)
[12, Sul: 0.0128)
0.01133
0.0168
0.0113
0.0222
0.0057
0.0056
0.0056
QDA
0.0154)
(12, Sod: 0.0154)
(11, 0.0154)
0.0232)
18. Std: 0.0128)
(12, 0.0124)
[12, Std: 0.0124)
0.0571
0,0381
0.0087
0.368y
0.0524
0:0571
Scedls
1-NN
12. Std: 0.0213)
16, Stcl: 0.02388)
(3. Stdl 0.10119)
(5, Stdl 0.0391)
(6. Stel 0.07664)
[4. Stel: 0.00913
(4. Strl: D42213)
NM
0.0429
0.0333
0.0381
0.0031
0.3190
0.0333
0.0333
12. Std: 0.0199)
[6. Std: 0,0130)
(8. Std: 0,0271)
(6. Std: (101190)
(6. Std: 0.1121)
(a. Std: 0.0271)
(4. Std: 0.0319)
QDA
0.0381
0.0311
0.0051
0.00M
0.3420
0.0333
0.0236
Std: 0.0271)
Strl: 0101300)
15, Std: 0,0213)
Stdl 0.0213)
(6. Stul: 0.1099)
(3. Strl: 0.0213)
(4. Strl: D/0391)
f..776
0.0811
0,0911
0.1021
0.3412
0.0632
0,0400
I-NN
[2, Std: 0.02854)
[1. Std: 0.0575)
(4, Stu: 0.0406)
(4, Std: 0.0708)
(4, Stu: 0.1944)
(3. Stul: 0. 0.09412)
(4. Std: 0.05-8)
Prestige
f.05226
0.0916
0.0805
0,0811
0.3863
0.0842
0.0716
NM
(2, Std: 0.0484)
(4, Std: 0.0650)
(4. Std: 0.0567)
(4. Std: 0.0665)
(4. Std: 0.1916)
(4. Std: 0. 0.1212)
(3. Std: 0.0780)
QDA
0,0721
D.0S6
(10705
011811
0.3458
0.0721
0.0526
12. Stu: 0.0303)
(4. Sud: 0,05722)
(4, Std: 0.0444)
(4, Std: 0.0762)
(4, Std: 0.1833)
(4. Std:: 0.0596)
(3. Std: 0.0912)
L-NN
0,0484
0.0518
0,0484
0.1387
0.0485
0.1220
0.0467
22. Std: 0.0162)
[3. Std: 0.01388)
(2, Std: 0.0170) 70)
33. Std: 0.04633
(3. Stdl: 0.02933
[3. Strl: 0 0.0807)
(3. Stá: 0.01722)
Diarond
0,08335
0.0768
010832
0.1654
0.0789
0,1403
0.0752
NM
3. Std: 0.0406)
[3, Std: 0.01-48)
13, Std: 0.0194)
33, Std: 0.0489)
(3. Stdl: 0.04533
[3. Strl: 0. 0.0611)
(3. Str:: (.9266)
QDA
0,0318
0.0217
0.0351
0.1236
0.0300
0.0919
0.0217
(3. Std: 0,0217)
[3. Std: 0.0127)
(3, Std: (.0161)
(3. Std: (1.0519)
(3, Std: 0.01733)
(3. Std: 0. 0.0562)
(3. Std: 0.0112)
1-NN
(.0777
0,0181
0.0454
0.14335
0,0222
0.0299
0.0299
(G. Std: 0.0081)
[36, Sul: 0.0045)
(11, Std:: B.0063)
(16, Stul: (.0055)
(46, Stul: 0.0222)
(16, Std: 0.00-13)
[16, Sul: o 0.0043)
Digit
0,0730
0,0163
0.0484
0,0495
0.0571
0,0476
0.0476
(G. Std: 0.0070)
(11, Std: 0.0072)
(26, Std: D. 8.00-19)
(46,, Std: D.0058)
(46, Stu:: 0.0072)
(41, Std: 0.0073)
[41, Sul: 0 0.0073)
0.0656
0.0231
0.0275
0.0252
0.0553
0.0223
0,0223
QDA
(6. Std: 0.0070)
( 21, Stá: 0.0055)
(36, Std: 0.0089)
(31, Std: 0.0047)
(46, Std: 0.0093)
(26, Std: 0.0060)
(26, Std: 0.0060)
classifier utilized the following decision rule:
i = arg min
1(x - ((x)-m))' ",,""",'' m.) + +log| |
i=I,....c
x
where m; represents the mean vector of class i, and E; is the covariance matrix of class This ensured that the classifiers could capture both linear and non-linear separability, providing thorough evaluation of performance across the different dimensionality reduction methods. To refer to our approaches in the experimental results, name them MM4MM (QP) and MM4MM (Sparse). It is important to highlight that for MM4MM (Sparse), we performed a grid search over À E {0.001,, 0.1,, 1.0} and, for each value, computed the objective function according to the optimal solution formulation. We then selected the A that yielded the highest objective.
4.3 Results
Tables D presents the optimal average classification error rates along with their corresponding standard deviations and dimensionalities for the various dimensionality reduction methods across the five datasets. Tt is worth mentioning that because each method-inchudin ours and the at distinct target dimensionality, we follow the evaluation protocol from (Su et al. (2015) and report results at each method's respective optimal dimensionality. As result, while Section 3 previously outlined the computational complexity of our approach, making a direct runtime comparison would be unfair.
its peak accuracy
As we can see from Table I for the Iris dataset, the proposed approaches consistently outperform traditional methods for non-linear classifiers. The NM classifier, paired with either MM4MM (QP) or MM4MM (Sparse), achieves the lowest average error rates. Furthermore, in both the 1-NN and QDA classifiers, the best approach is found to be MM4MM (Sparse), demonstrating the strength of combining our advanced dimensionality reduction method with all the classifiers mentioned.
11

---

Published in Transactions on Machine Learning Research (07/)025)
On the Wine dataset, which features complex chemical attributes, MM4MM (Sparse) demonstrates signif- icant improvements in minimizing error rates, particularly with the NM and QDA classifiers, as well as MM4MM (QP) with the QDA classifier.
The results from the Seeds dataset reveal that, although the MMDA approach outperforms others for the 1- NN classifier, the MM4MM (Sparse) method achieves the lowest error rates for the NM and QDA classifiers, highlighting its superior classification performance. Additionally, for the NM classifier, both MM4MM (QP) and HLDA demonstrate competitive performance, comparable to the MM4MM methods. Furthermore, for the QDA classifier, MM4MM (QP) and WHMMDA show the second- performance.
For the Prestige dataset, which consists of socio-economic data, the proposed methods MM4MM (Sparse) as the best and MM4MM (QP) as the second best outperform traditional approaches in terms of classification error and standard deviations across all three classifiers. This result highlights the robustness of MM4MM (Sparse) in optimizing subspace transformations.
The Diamonds dataset, used for modeling regression scenarios, demonstrates that the QDA classifier com- bined with MM4MM (Sparse) achieves the lowest error rates, confirming the efficacy of this approach for handling datascts with complex feature inter-dependencies. In contrast, all competing methods (excopt HLDA with the QDA classifier) show higher error rates, highlighting their diminished effectiveness in non- linear data environments.
For the high-dimensionall Digit dataset, our proposed MM4MM (QP) method demonstrates superior effective- ness in 2 out of 3 classifiers. While HLDA achieves the lowest error rate under the 1-NN classifier, MM4MM (QP) outperforms all competing methods under both the NM and QDA classifiers. This consistent top-tier performance across multiple classifiers confirıs MM4MM (QP) a robust solution for high-dimensional data, yielding the lowest error rates in the majority of experimental settings. It is worth mentioning that the reason why MM4MM (Sparse) shows similar values to MM4MM (QP) is that its best performance is achicved at lambda = 0.001 for this datasct.
5 Conclusion
In this work, we introduced a new discriminative feature learning method built on minorization- maximization framework for min-max (MM4MM), aimed specifically at addressing the problem of "worst- case class separation (WCCS)" The algorithm was designed to operate using relaxed semi-orthogonality constraint, which was shown to be tight at every iteration.
Our approach began with a vanilla version that required solving semi-definite program (SDP) at each iteration. To simplify this, we also developed a method that reduced the problem to a quadratic program by constructing the dual the surrogate maximization problem. Additionally, we proposed a reformulation of the WCCS problem that includes sparsity penalty.
The proposed algorithms are computationally efficient and enjoy guaranteed convergence. A key advantage of the proposed approach is that it does not require any hyperparameter tuning, except for the sparsity-based version where users need to select penalty parameter for controlling sparsity. Experiments conducted on multiple machine learning datasets demonstrated the strong performance of the MM4MM approach.
References
Prabhu Babu and Petre Stoica. Fair principal component analysis (PCA): minorizattion-maxiizzziio algo- rithms for fair PCA, fair robust PCA and fair sparse PCA. arXiv preprint, arXiv:2305.05963, 2023.
Wei Bian and Dacheng Tao. Max-min distance analysis by using sequential SDP relaxation for dimension reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(5:00337 1050, 2011. doi: 11.1109/TPAMI2000
Xiaojun Chang, Feiping Nic, Sen Wang. Yi Yang, Xiaofang Zhou, and Chengqi Zhang. Compound rank- & projections for bilinear analysis. IEEE Transactions on Neural Networks and Learning Systems, 27()): 1502-1513, 2016. doi: 10.10
12

---

Published in Transactions on Machine Learning Research (07/2025)
Alexandre D' aspremont, Laurent Ghaoui, Michael Jordan, and Gert Lanckriet. A direct formulation for sparse PCA using semidefinite programming. In L.. Saul, Y. Weiss, and L. Bottou (eds.), Advances in Newral Information Processing Systems, volume 17. MIT Press, 2004. URL https://proceeddngg www.oiiinnnnnnuiis....... Papeee pdf
Ronald Fisher. The use of multiple measurements in Laxonomic problems. 179 179-188, 1936.
Annals of eugenics, T(2):
Michael Grant and Stephen Boyd. CVX: MATLAB software for disciplined convex programming, version 2.1, 2014.
Jie Gui, Zhenan Sun, Shuiwang Ji, Dacheng Tao, and Tieniu Tan. Feature selection based on structured sparsity: A comprehensive study. IEEE Transactions on Neural Networks and Learning Systems, 28(7): 1490-1507, 2017. doi: 10.1109/ 10.1109/TNNI.S. CANN....016.25311
Emrah Hancer, Bing Xue, and Mengjie Zhang. A survey on feature selection approaches for clustering. Artificial Intelligence Review, 53 5316):4519-4555, 2020. ISSN 1573-7462. doi: 10.1007/110442--11--986666 URL
Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P. Trevino, Jiliang Tang, and Huan Liu.
Feature selection: A data perspective. ACM Compul. Suro., 50(6), December 2017. ISSN 0360-0300. doi:
10.1145/3136625, URL httpp://doi..rrg 0rt../...00.0/111111////322222
Xiaoping Li, Yadi Wang, and Rubén Ruiz. A survey on sparse learning models for feature selection. IEEE Transactions on Cybernetics, 52(3):1642-1660) 2022. doi: 10.1109/TCYB. C.CYYB.020.29824444
Zhihui Li, Feiping Nie, Xiaojun Chang. Liqiang Nie, Huaxiang Zhang, and Yi Yang. Rank-constrained spectral clustering with flexible embedding. JEEE Transactions on Neural Networks and Learning Systems, 29(12):6073-600 6082, 2018a. doi: 10.1109/ 10.1109/TNNLS... TONNLS.0018.21111
Zhihui Li, Feiping Nie, Xiaojun Chang, Yi Yang, Chengqi Zhang, and Nicu Sebe. Dynamic affinity graph construction for spectral clustering using multiple features. IEEE Transactions on Neural Networks and Learning Systems, 29(12))6323 6332, 2018b. doi: N0.1109/TNNIS.2000 28122886667..
Marco Loog and Robert P. W. Duin. Linear dimensionality reduction via heteroscedasticc extension of LDA: The chernoff critcrion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(6): 732 222,739,680 2004. doi: 10.1109 TPAM9////....0......
Minnan Luo, Feiping Nie, Xiaojun Chang, Yi Yang, Alexander G. Hauptmann, and Qinghua Zheng. Adaptive unsupervised feature selection with structure regularization. IEEE Transactions on Neural Networks and Learning Systems, 29(4):944 956, 2018. doi: MAL109/TNNNS... 201.2....71.2250977..
AW Marshall. Inequalities: Theory of majorization and its applications, 1979.
Feiping Nie, Wei Zhu, and Xuelong Li. Unsupervised large graph embedding. In Proceedings of the Thirly- First AAAT Conference on Artificial Intelligence, AAAT17, pp. 2422 2422.. AAAT Press, 2017.
Feiping Nie, Zheng Wang, Rong Wang, and Xuelong Ti. Submanifold-preserviee discriminant analysis with an auto-optimized graph. IEEE Transactions on Cybernetics, 50(8):3682 3695, 2020a. doi: 10.1109/ TCCB.2009.2910772
Feiping Nie, Zheng Wang, Rong Wang, Zhen Wang, and Xuelong Li. Adaptive local linear discriminant analysis. ACM Trans. Knowl. Discov. Data 14(1), February 2020b. ISSN 1556-4681, doi: URL https://doi. 10 1145/3369870
Feiping Nic, Xia Dong, and Xuclong Li. Unsupervised and semisupervised projection with graph opti- mization. IEEE Transactions on Neural Networks and Learning Systems, 32(4))1547-1555, 2021a. doi: N0.1109//NNTTSS2200..2220
13

---

Published in Transactions on Machine Learning Research (07/2025)
Feiping Nie, Zheng Wang, Rong Wang, Zhen Wang, and Xuelong Li. Towards robust discriminative projec- tions learning via non-greedy f2,1-nrrm minmax. JEEE Transactions on Pallera Analysis and Machine Intelligence, 43(6):2086 2100, 2021b.
Feiping Nie, Xia Dong, Zhanxuan Hu, Rong Wang, and Xuelong Li. Discriminative projected clustering via unsupervisod Ida. IEEE Transactions Neural Networks and Learning Systems, 34(11):9466-94)) 9480, 2023. doi: 10.1109/ 32225.202...302211.
Jing Peng, Guna Seetharaman, Wei Fan, Stefan Robila, and Aparna Varde. Chernoff Dimensionality Reduction Where Fisher Meets PKT, pp. 271 282. doi: 10.
10.137717777171111199992 0117//1977161119888882224 URI. https:
//epubs. siam. wttp////aas///..o.o///o/ wwt.:/.117.1...1111 17111777...991111977111111
V. U. Prabhu. Kannada-MNISTT: A new handwritten digits dataset for the Kannada language, 2019.
C Radhakrishna Rao. The utilization of multiple measurements in problems of biological classification.
Journal of the Royal Statistical Society. Series B (Methodolonical), 10(2):159 203, 1948.
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via muclear norm minimization. SIAM review, 52(3):471-501, 2010.
Astha Saini, Petre Stoica, Prabhu Babu, Aakash Arora, et al. Min-max framework for majorization- mininization algorithms in signal processing applications: An overview. Foundalions and Trends0 in Signal Processing, 18(4):310-889, 2024.
Razieh Sheikhpour, Mehdi Agha Sarram, Sajjad Gharaghani, and Mohammad Ali Zare Chahooki. A survey on semi-supervised feature selection methods. Pattern Recognition, 64:141 158, 2017. ISSN 0031-3203. doi: https:///bb..cgg//00000///////p patco..................ooooooo 2016. 11.6.11103.... atticlee/pi/S00112201665553
URL
Heng Tao Shen, Yonghua Zhu, Wei Zheng, and Xiaofeng Zhu. quld-quadratic minimization for unsupervised feature selection on incomplete data. IEEE Transactions on Neural Networks and Learning Systems, 32
(7):3122 3135, 2021. doi: 1..1109/TNNLS TTT.TTNNNN..S..NNNN...ON 2020.3009632.
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):17 176, 1958.
Bing Su, Xiaoqing Ding, Changsong Liu, and Ying Wu. Heteroscedastic max-min distance analysis. In 2015 IEEE Conference on Compuler Vision and Pallern Recognition (CMnn) pp. 4539 4547, 2015. doi: 10.
Bing Su, Xiaoqing Ding, Changsong Liu, and Ying Wu. Heteroscedastic max min distance analysis for dimensionality reduction. IEEE Transactions on Image Processing, 27(8):4052-4088 2018. doi: 10.1109/ TIP.2018.2838 2836312.
Ying Sun, Prabhu Babu, and Daniel P. Palomar. Majorizationn-miiiizzzaii algorithms in signal processing, communications, and machine learning. IEEE Transactions on Signal Processing, 65(3):794488 116,,1166110 2017. doi: 10.1109/TSPP TT..009/TSPP.1..... 201.226129...
Zheng Wang, Feiping Nie, Canyu Zhang, Rong Wang, and Xuelong Li. Worst-case discriminative feature learning via max-min ratio analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(1):641-658, 2024. doi: T0000///PAM..223.....
Yaoliang Yu, Jiayan Jiang, and Liming Zhang. Distance metric lcarning by minimal distance maximization. Pallern Recognition, 44(3):639 649, 2011. ISSN 0031-3203. doi: htpp:///oi.orr///.000////oooooo 2010. 09.019. URL //tp:///wwwwwww www.ncedirect.cc..mm...... http://www..aacaooocccoocaaaaaaa
Yu Zhang and Dit- Yan Yeung. Worst-case linear discriminant analysis. In J. Lafferty. C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta (ods.), Advanees in Neural Information Processing Systems, vol- ume 23. Curran Associates, Inc., 2010. URL /ttp:::///prooeddinggg
14

---

Published in Transactions on Machine Learning Research (07/2025)
Hui Zou and Lingzhou Xue. A selective overview of sparse principal component analysis. Proceedings of the IEFE, (668))1311-1320) 2018. doi: 101109//PROC.228888888888
Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Compu-
tational and Graphical Statistics, 15(2):265-255 286, 2006. URL http://wwww...oorr////aaaa/aa///
Accessed 29 Oct. 2024.
15

---

Published in Transactions on Machine Learning Research (07 (07/2025)
6 Appendix
6.1 The proof of Lemma
Proof. Note that in
16 (for any i.j)
Tr (w" W) Tr (Sci, (or) Tr (Sca WQQ WQQ"w"),
which holds for any matrix Q such that QQ = I. Therefore, for any matrix W that meets the relaxed constraint, we can select Q such that Q"w" WQ = diagonal _ < I. Since W and WW share the same non-zero eigenvalues, follows that:
WW VAVT.
(44)
where contains the principal eigenvectors of WW and VTV Using 44
we have:
(w"Scy W) = Tr ((V' Scy V) V)
Σ VV'SC V) kk A&k S Σ SV'Scy V)
(45)
Hence, all functions in 16 take larger values when = I than when A 5 This indicates that the global maximizer of [6
constrained by w < will indeed satisfy the constraint in (16). Therefore, the relaxation W W does not alter the solution of (16), and the proof of Lemma completed.
6.2 Proof of 36
Proof. To find explicit form of Q let define A and En as A Aij, ãn zij where A: = (1-1)(201) -- i. As a result can be rewritten as Eb E where C(C-1), Calculating A T A gives: 2
K A
K
K
=
E
A
Σ
A
&
1=1
1=1
1=1
Multiplying both sides of the above equation by Φ from the right and taking the trace, we obtain:
Tr (A
zu Tr (A) A..")
(46)
k=
On the other hand, the quadratic form T Qz expands to:
K
K
i Qu.
(47)
By comparing 46 and 47
we obtain:
Qk Tr (AT (').
Using the veclorization operator, define 0x (.)) The trace properly gives:
Tr (AFA+ of (I Φ²) vi,
where I is the identity matrix and @ denotes the Kronecker product. We construct by stacking Ug columns:
S [r] 02 ux]
16

---

Published in Transactions on Machine Learning Research (07/2025)
Thus, we have:
Tr (r = -² (T Φ') Sz.
(48)
Equating 48 to z zz, we derive:
Q == ST &I D')S.
where S [1i U2 dK] and vs vec(Aig)
) with:
(i (i- (2 i)
k
+ i
and the proof is completed.
17


Reviews:
[{"review_id": "sXFX4OPSxL", "reviewer": "Reviewer_A2cH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. The relaxation of the semi-orthogonality constraint and its tightness proof provide a rigorous foundation, avoiding suboptimality caused by conventional relaxations.\n2. The dual problem formulation reduces computational complexity, making it suitable for high-dimensional data.\n3. Evaluations across several datasets (Iris, Wine, Seeds, etc.) and classifiers (1-NN, NM, QDA) consistently show lower error rates and higher stability for the proposed method compared to baselines.\n\n**Weaknesses:**\n\n1. The paper mentions that the sparsity version requires the user to specify $\\lambda$, but does not discuss the selection strategy of $\\lambda$. It is recommended to supplement the sensitivity analysis of the impact of $\\lambda$ on sparsity and performance, or provide an adaptive $\\lambda$ selection method.\n2. The lack of comparison with recent deep learning-based discriminant analysis methods (e.g., deep metric learning) may affect the comprehensiveness of the conclusion. It is recommended to increase the comparative experiments with deep methods. The scale of the experimental datasets is small (e.g., Iris has only 150 samples), and the scalability of the method needs to be verified on larger datasets (e.g., ImageNet subsets).\n3. The Gaussian distribution assumption may not hold for real-world datasets (e.g., text or graph data). It is recommended to discuss and analyze the applicability of the proposed method to non-Gaussian distribution datasets, or to verify its robustness through experiments.\n4. Theoretical convergence rate (e.g., linear or sublinear) is not provided. A quantitative analysis would enhance completeness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "For the problem of the long-standing worst-case class separation (WCCS), a novel feature learning method based on a minorization-maximization framework for min-max optimization (MM4MM) is proposed. The core objective is to enhance discriminative feature learning by maximizing the minimum pairwise Chernoff distance between all class pairs in a low-dimensional subspace. The experimental results on UCI and Kaggle datasets demonstrate superior classification accuracy and robustness compared to traditional methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the \"Weaknesses\" part.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rCzDHtyEvF", "reviewer": "Reviewer_gNA4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The method addresses the \"worst-case class separation (WCCS)\" problem. This clearly defines the problem being tackled and its significance.\n- The proposed algorithm utilizes the relaxation of a semi-orthogonality constraint. Based on Lemma 1, this relaxation does not alter the solution of the original problem. This is a strong theoretical result underpinning the algorithm.\n- The paper offers different algorithm versions, starting with a vanilla version involving an SDP and then simplifying it to a more computationally efficient quadratic program (QP). This addresses potential computational bottlenecks.\n- The authors also present reformulations that incorporate the sparsity of the dimension-reducing matrix. This adds flexibility and the potential for more interpretable results.\n\n### Weaknesses\n\n[Computational Complexity]\n- While the authors claim computational efficiency, the stated complexity of the SDP approach is $\\mathcal{O}((d + d^{\\prime})^{4.5})$, which could be a concern for very high-dimensional datasets. Although the QP approach is relaxed to $\\mathcal{O}(C^6)+\\mathcal{O}(d^3)$, $\\mathbf{Q}$ in (35) is a huge matrix in some situations and raises concerns regarding space complexity. Section 3.3 states that iterations are usually fewer than 10, but this has not been experimentally demonstrated. A more detailed analysis of the practical scalability and runtime compared to other methods, especially in high-dimensional scenarios, might be valuable. Moreover, comparing orders regarding time and space complexity is more persuasive.\n\n[Parameter Tuning]\n- While the basic algorithm is hyperparameter-free, the sparsity-based version requires users to select a penalty parameter ($\\lambda$). The paper mentions this but does not provide detailed guidance on choosing this parameter effectively. Further discussion or potential strategies for selecting $\\lambda$ could be beneficial. Discussing hyperparameter tuning in previous methods might also be useful to show that hyperparameter-free, as claimed by the authors, is a notable benefit.\n\n[Experimental Results]\n- While the overall performance is strong, the results in Table 1 show that MM4MM did not universally outperform all other methods across every dataset and classifier. For example, MMDA showed better results on the Seeds dataset with the 1-NN classifier. The authors could consider a more nuanced discussion of the conditions under which MM4MM excels and where other methods might still be competitive. In particular, I am concerned that the high performance may not be attributed to the proposed method but to the regularization term. Compared to MM4MM(QP) only, the performance of the proposed method is not necessarily significantly better.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel minorization-maximization framework for min-max (MM4MM) to address the \"worst-case class separation (WCCS)\" problem: maximizing minimum pairwise Chernoff distances between classes in a low-dimensional subspace.\n\nAccording to the authors, key contributions are as follows:\n\n- MM4MM algorithm for WCCS with proven semi-orthogonality constraints\n- Both the SDP-based vanilla version and the more efficient quadratic programming formulation\n- Sparse reformulations for interpretable feature representations\n- Computationally efficient with guaranteed convergence and minimal hyperparameter tuning\n- Experimental results show competitive or superior performance versus state-of-the-art methods across multiple datasets\n\nThe method combines theoretical soundness with practical effectiveness, offering advances in feature learning, efficiency, and usability through its novel optimization framework and sparse formulations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Based on TMLR's acceptance criteria, I have an overall favorable opinion of this paper. However, as noted in Weaknesses, there appears to be some gap between claims and evidence. In order to ensure acceptance, I would like to ask your views on these gaps, including appropriate revisions to the paper.\n\n\n[Minor Comments]\n\nPlease check again regarding references. For example,\n- \"Fisher Fisher\" in the second paragraph of Section 1;\n- The references in the sentence should be bracketed;\n- Hyperlinks to the corresponding references would be helpful.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "odqnuebyRC", "reviewer": "Reviewer_cPL4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**  \nAlthough I am not an expert in feature discriminant learning, I found the paper to be well-written. The related work is detailed, the various concepts are introduced progressively, and the different problem formulations are easy to understand. The minorization-maximization approach for coordinate-wise maximization-minimization tasks is conceptually simple and elegant. Notably, it provides a natural solution to WCSP and its variants.\n\n**Weaknesses**  \nGiven that the WCSP is nonconvex, it is crucial to establish its computational complexity. Is it NP-hard? Or does it fall within the class P due to the structure of the objective function and the semi-orthogonality of the constraints? \n\nIn relation to this, maximizing a constrained convex objective is generally NP-hard. Therefore, I am not entirely convinced that Problem (16) can be solved in polynomial time. This observation does not question the validity of Lemma 1; I am quite confident we can transition from (15) to (16), but I still remain doubtful that we can move from (16) to (21). So, additional comments regarding (16) and clear proof that it can be solved in polynomial time would clarify the validity of the entire framework.\n\nWhile I commend the authors' effort to reduce the complexity of (16), the resulting formulation (34) still requires cubic time to solve. Unfortunately, all datasets used in the experiments are low-dimensional. So, I suggest considering higher-dimensional datasets (e.g., gene expression data) to demonstrate that the MM4MM framework can scale effectively.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the worst-case class separation problem (WCSP) within the context of feature discriminant learning. The WCSP involves maximizing the minimum of a convex objective while adhering to a nonconvex semi-orthogonality constraint. The authors propose an algorithmic framework based on two main ideas. First, they suggest relaxing the semi-orthogonality constraint into a convex one, ensuring that the global maximizer of the relaxed problem still meets the original non-convex constraint. Second, they tackle the optimization of the objective function—which features a max-min operation—using a minorization-maximization approach.\n\nAlthough the resulting semi-definite optimization problem is convex, its computational complexity remains high. To address this, the authors provide an alternative quadratic formulation that can be efficiently solved with standard algorithms. Additionally, they explore a sparse version of the WCSP and present a relaxation that is also suitable for convex solving. Comparative experiments conducted on several datasets demonstrate the effectiveness of this framework.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Major Comments**  \nC1. Establish the computational complexity of Problem (2). Specifically, determine whether it is in P or NP-hard.  \nC2. Although Problem (16) involves the maximization of a convex objective under a convex constraint, demonstrate that it can be solved in polynomial time. (Of course, if the answer to C1 is “P,” then the answer to C2 is \"P\" as well.)  \nC3. Utilize higher-dimensional datasets to illustrate the scalability of the MM4MM approach.  \n\n**Minor Comments**  \nC4. In Section 2, the sentence “[...] we formulate the worst-case optimization problem” is unclear. It should be revised to read: “[...] we formulate the worst-case class separation problem (WCSP).”  \nC5. In Section 3.3, the statement “The maximization problem in (16) remains non-convex, as the objective function (for each (i,j)) is a convex quadratic in W, and the inclusion of the min operator adds further complications” is incorrect. The problem is actually convex because both the objective and constraints are convex. However, the main challenge arises because the objective is being “maximized”.", "broader_impact_concerns": "Not Applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)