Introduction

In the past decade, deep learning has exhibited remarkable empirical success across a wide range of engineering and scientific applications (LeCun et al., 2015), such as computer vision (He et al., 2016;Simonyan & Zisserman, 2014), natural language processing (Sutskever et al., 2014;Vaswani et al., 2017), and health care (Esteva et al., 2019), to name a few. As argued by Bengio et al. (2013); Ma et al. (2022), one major factor contributing to the success of deep learning is the ability of deep networks to perform powerful nonlinear feature learning by converting the data distribution to a compact and structured representation. This representation greatly facilitates various downstream tasks, including classification (Dosovitskiy et al., 2020), segmentation (Kirillov et al., 2023), and generation (Saharia et al., 2022).

Based on the theory of data compression and optimal coding (Ma et al., 2007), Chan et al. (2022); Yu et al. (2020) proposed a principled and unified framework for deep learning to learn a compact and structured representation. Specifically, they proposed to maximize the difference between the coding rate of all features and the sum of coding rates of features in each class, which is referred to as maximal coding rate reduction (MCRfoot_1 ). This problem is presented in Problem (4) and visualized in Figure 1(a). Here, the coding rate measures the "compactness" of the features, which is interpreted as the volume of a particular set spanned by the learned features: a lower coding rate implies a more compact feature setfoot_0 . Consequently, the MCR 2 objective aims to maximize the volume of the set of all features while minimizing the volumes of the sets of features from each class. Motivated by the structural similarities between deep networks and unrolled optimization schemes for sparse coding (Gregor & LeCun, 2010;Monga et al., 2021), Chan et al. (2022) constructed a new deep network based on an iterative gradient descent scheme to maximize the MCR 2 objective. 2 Notably, each component of this deep network has precise optimization and geometric interpretations. Moreover, it has achieved strong empirical performance on various vision and language tasks (Chu et al., 2023;Yu et al., 2023a).

Although the MCR 2 -based approach to deep learning is conceptually "white-box" and has achieved remarkable empirical performance, its theoretical foundations have been relatively under-explored. In fact, the effective feature learning mechanism and "white-box" network architecture design based on MCR 2 are direct consequences of these foundations, and understanding them will pave the way to improv- ing model interpretability and training efficiency of deep networks. Nevertheless, a comprehensive theoretical understanding of the MCR 2 problem remains lacking. In this work, we take a step towards filling this gap by studying its optimization properties. Notably, analyzing these properties, including local optimality and global landscape, of the MCR 2 objective is extremely challenging. To be precise, its objective function (see Problem ( 4)) is highly non-concavefoot_7 and complicated, as it involves quadratic functions and the difference between log-determinant functions. To the best of our knowledge, characterizing the local optimality and global optimization landscape of the MCR 2 problem remains an open question.

Our Contributions

In this work, we study the optimization foundations of the MCR 2 -based approach to deep learning. Towards this goal, we characterize the local and global optimality of the regularized MCR 2 problem and analyze its global optimization landscape (see Problem ( 5)). Our contributions can be highlighted as follows.

Characterizing the local and global optimality. For the regularized MCR 2 problem, we derive the closed-form expressions for its local and global optima for the first time.

Our characterization shows that each local maximizer of the regularized MCR 2 problem is within-class compressible and between-class discriminative in the sense that features from the same class belong to a low-dimensional subspace, while features from different classes belong to different orthogonal subspaces. Besides these favorable properties, each global maximizer corresponds to a maximally diverse representation, which attains the highest possible dimension in the space.

Studying the global optimization landscape. Next, we show that the regularized MCR 2 function possesses a benign global optimization landscape, despite its complicated structures. More precisely, each critical point is either a local maximizer or strict saddle point of the regularized MCR 2 problem; see Figure 1(b). Consequently, any gradient-based optimization, such as (stochastic) gradient descent, with random initialization can escape saddle points and at least converge to a local maximizer efficiently.

Finally, we conduct extensive numerical experiments on synthetic data sets to validate our theoretical results. Moreover, we use the regularized MCR 2 objective to train deep networks on real data sets. These experimental results constitute an application of the rigorously derived MCR 2 theory to more realistic and complex deep learning problems.

Our results not only establish optimization foundations for the MCR 2 problem but also yield some important implications for the MCR 2 -based approach to deep learning. Namely, our theoretical characterizations of local and global optimality offer a compelling explanation for the empirical observations that both deep networks constructed via gradient descent applied to the MCR 2 objective and overparameterized deep networks trained by optimizing the MCR 2 objective learn low-dimensional, discriminative, and diverse representations. These results align with the motivations of Chan et al. (2022); Yu et al. (2020) for employing the MCR 2 principle for deep learning, and elucidate the outstanding performance of MCR 2 -based neural networks across a wide range of vision and language tasks (Chu et al., 2023;Yu et al., 2024). Moreover, our results underscore the potential of MCR 2 -based approaches to serve as a cornerstone for future advancements in deep learning, offering a principled approach to pursuing structured and compact representations in practical applications.

Related Work

Low-dimensional structures in deep representation learning. In the literature, it has long been believed that the role of deep networks is to learn certain (nonlinear) low-dimensional and informative representations of the data (Hinton & Salakhutdinov, 2006;Ma et al., 2022). For example, Papyan et al. (2020) showed that the features learned by cross-entropy (CE) loss exhibit a neural collapse phenomenon during the terminal phase of training, where the features from the same class are mapped to a vector while the features from different classes are maximally linearly separable. The MCR 2 -based approach to deep learning. The MCR 2 -based approach to deep learning for seeking structured and compact representations was first proposed by Yu et al. (2020). Notably, they provided a global optimality analysis of the MCR 2 problem (4) with additional rank constraints on the feature matrix of each class. Chan et al. (2022) designed a new multi-layer deep network architecture, named ReduNet, based on an iterative gradient descent scheme for maximizing the MCR 2 objective. To learn selfconsistent representations, Dai et al. (2022) extended this approach to the closed-loop transcription (CTRL) framework, which is formulated as a max-min game to optimize a modified MCR 2 objective. This game was shown to have global equilibria corresponding to compact and structured representations (Pai et al., 2022). Recently, Yu et al. (2023b) showed that a transformer-like architecture named CRATE, which obtains strong empirical performance (Chu et al., 2023;Yu et al., 2023a;2024), can be naturally derived through an iterative optimization scheme for maximizing the sparse rate reduction objective, which is an adaptation to sequence data of the MCR 2 objective studied in this work.

Notation. Given a matrix A ∈ R m×n , we use ∥A∥ to denote its spectral norm, ∥A∥ F to denote its Frobenius norm, and a ij its (i, j)-th element. Given a vector a ∈ R d , we use ∥a∥ to denote its ℓ 2 -norm, a i its i-th element, and diag(a) the diagonal matrix with a on its diagonal. Given a positive integer n, we denote by [n] the set {1, . . . , n}.

Given a set of integers {n

Problem Setup

In this section, we first review the basic concepts of MCR 2 for deep representation learning in Section 2.1, and then introduce our studied problem in Section 2.2.

An Overview of MCR 2

In deep representation learning, given data {x i } m i=1 ⊆ R n from multiple (say K) classes, the goal is to learn neuralnetwork representations of these samples that facilitate downstream tasks. Recent empirical studies have shown that good features can be learned for tasks such as classification or autoencoding by using heuristics to promote either the contraction of samples in the same class (Rifai et al., 2011) or the contrast of samples between different classes (He et al., 2020;Oord et al., 2018) during the training of neural networks. Notably, Chan et al. (2022); Yu et al. (2020) unified and formalized these practices and demonstrated that the MCR 2 objective is an effective objective to learn within-class compressible and between-class discriminative representations of the data.

The formulation of MCR 2 . In this work, we mainly consider an MCR 2 objective for supervised learning problems. Specifically, let For each k ∈ [K], let Z k ∈ R d×m k be the matrix whose columns are the features in the k-th class. Without loss of generality, we reorder the samples in a class-by-class manner, so that we can write the matrix of all features as

(1)

On one hand, to make features between different classes discriminative or contrastive, one can maximize the lossy coding rate of all features in Z, as argued in (Chan et al., 2022;Yu et al., 2020), as follows:

where ϵ > 0 is a prescribed quantization error. 4 On the other hand, to make features from the same class compressible or contractive, one can minimize the average lossy coding rate of features in the k-th class as follows:

Consequently, a good representation tends to maximize the difference between the coding rate for the whole and that for each class as follows:

This is referred to as the principle of maximal coding rate reduction in (Chan et al., 2022;Yu et al., 2020). It is worth mentioning that this principle can be extended to selfsupervised and even unsupervised learning settings, where we learn the label vectors {π k } K k=1 during training.

The Regularized MCR 2 Problem

Due to the Frobenius norm constraints, it is a tremendously difficult task to analyze Problem (4) from an optimizationtheoretic perspective, as all the analysis would occur on a product of spheres instead of on Euclidean space. Therefore, we consider the Lagrangian formulation of (4). This can be viewed as a tight relaxation or even an equivalent problem of (4) whose optimal solutions agree under specific settings of the regularization parameter; see Proposition 3.2. Specifically, the formulation we study, referred to henceforth as the regularized MCR 2 problem, is as follows:

where λ > 0 is the regularization parameter. Remark that our study on this problem applies meaningfully to at least two approaches to learning deep representations using the MCR 2 principle.

Applications of our formulation to deep representation learning via unrolled optimization. The first approach, as argued by Chan et al. (2022); Yu et al. (2023a), is to construct a new deep network architecture, i.e., ReduNet (Chan et al., 2022) or CRATE (Yu et al., 2023a), based on an iterative gradient descent scheme to optimize the MCR 2 -type objective. In this approach, each layer of the constructed network approximates a gradient descent step to optimize the MCR 2 -type objective given the input representation. The key takeaway is that these networks approximately implement gradient descent directly on the representations, so our analysis of the optimization properties of the MCR 2 -type objective translates to explanations of the corresponding properties of the learned representations and architectures of these deep networks. In particular, our argument that the optima and optimization landscape of (5) are favorable directly translates to a justification of the correctness of learned representations of the ReduNet and a validation of its architecture design. Moreover, this study enables principled improvement of deep network architectures constructed via unrolled optimization by leveraging more advanced optimization techniques better suited for problems with benign landscapes. This can improve model interpretability and efficiency.

Applications of our formulation to deep representation learning with standard neural networks. In the second approach, one parameterizes the feature mapping f Θ (•) via standard deep neural networks such as a multi-layer perceptron or ResNet (He et al., 2016), and treats the MCR 2 -type objective like other loss functions applied to outputs of a neural network, such as mean-squared error or cross-entropy loss. Studying Problem (5) from this perspective would require us to optimize over Θ instead of over Z. This new optimization problem would be extraordinarily difficult to analyze, because modern neural networks have nonlinear interactions across many layers, so the parameters Θ would affect the final representation Z in a complex way. Fortunately, since modern neural networks are often highly over-parameterized, they can interpolate or approximate any continuous function in the feature space (Lu et al., 2017), so we may omit these constraints by assuming the unconstrained feature model, where z i for all i ∈ [N ] are treated as free optimization variables (Mixon et al., 2020;Yaras et al., 2022;Zhu et al., 2021;Wang et al., 2022a). Consequently, studying the optimization properties of Problem (5) provides valuable insights into the structures of learned representations and the efficiency of training deep networks using MCR 2 -type objectives.

Difficulties of analyzing Problem (5). Although Problem (5) has no constraints, one can observe that Problem (5) is highly non-concave due to the quadratic form Z k Z T k and the difference of log-determinant functions. Notably, this problem shares similarities with low-rank matrix factorization problems. However, it employs the log-determinant function instead of the Frobenius norm, and the computation of the objective gradient involves matrix inverses. Therefore, from an optimization point of view, it is extremely challenging to analyze Problem (5).

Main Results

In this section, we first characterize the local and global optimal solutions of Problem (5) in Section 3.1, and then analyze the global landscape of the objective function in Section 3.2.

Characterization of Local and Global Optimality

Although Problem (5) is highly non-concave and involves matrix inverses in its gradient computation, we can still explicitly characterize its local and global optima as follows.

where (a)

We defer the proof to Section 4.1 and Appendix D.1. In this theorem, we explicitly characterize the local and global optima of Problem (5). Intuitively, this demonstrates that the features represented by each local maximizer of Problem ( 5) are low-dimensional and discriminative in the sense that (i) Within-class compressible: According to (7), at each local maximizer, the features from the same class belong to the same low-dimensional linear subspace. (ii) Between-class discriminative: It follows from ( 7) and U T k U l = 0 for all k ̸ = l that, at each local maximizer, the features from different classes belong to different subspaces that are orthogonal to each other. Moreover, the features represented by each global maximizer of Problem ( 5) are not only low-dimensional and discriminative but also diverse in the sense that (iii) Maximally Diverse Representation: According to K k=1 r k = min{m, d}, at each global maximizer, the total dimension of all features is maximized to match the highest dimension that it can achieve in the feature space.

Quality of local versus global optima. Our above discussion explains the merits of achieving both local and global optima. At each maximizer, the representations are within-class compressible and between-class discriminative (Theorem 3.1 (i)). Moreover, global maximizers further satisfy that the representations are all maximally diverse (Theorem 3.1 (ii) (a)). If all classes were balanced, i.e., m 1 = • • • = m K , then Theorem 3.1 (ii) (b) would not apply, and these properties would be all that Theorem 3.1 asserts. In this case, global optima would clearly be desired over local optima. However, in the unbalanced case, the situation is more complex, because Theorem 3.1 (ii) (b) would apply. It says that for global optima, the classes with the smallest numbers of samples would fill to the largest dimension possible, and the very largest classes could collapse to 0, an undesirable situation. A dramatic example of this is when m 1 > • • • > m K > d, for then any global optimum would have rank(Z K ) = d and Z 1 , . . . , Z K-1 all collapse to 0. Overall, in the unbalanced case, global optima may not always correspond to the best representations. In particular, local optima with more equitable rank distributions (like bigger classes span more dimensions) which are still maximally diverse (i.e., ranks of each class sum to the dimension d) could be preferred in applications. As demonstrated in Section 5.1, these kinds of potentially useful local optima are realized in experiments, even with unbalanced classes.

Relation between Problems (4) and (5). Based on the characterization of global optimality in Theorem 3.1, we show the following proposition that establishes the relationship between the constrained MCR 2 problem (4) and the regularized MCR 2 problem (5) in terms of their global solutions under an appropriate choice of the regularization parameter. The proof of this result can be found in Appendix D.2. Proposition 3.2. Suppose that the number of training samples in each class is the same, i.e., m 1 = • • • = m K , and the coding precision ϵ > 0 satisfies

The following statements hold: (i) If m < d and the regularization parameter in Problem (5) is set as

Problems (4) and (5) have the same global solution set.

(ii) If m ≥ d, d/K is an integer, and the regularization parameter in Problem (5) is set as

the global solution set of Problem (4) is a subset of that of Problem (5).

According to this proposition, if ϵ and λ are appropriately chosen for Problem (5), when m < d, Problems (4) and ( 5) are equivalent in terms of their global optimal solutions; when m ≤ d, Problem ( 5) is a tight Lagrangian relaxation of Problem (4) such that the global solution set of the former contains that of the latter.

Analysis of Global Optimization Landscape

While we have characterized the local and global optimal solutions in Theorem 3.1, it remains unknown whether these solutions can be computed efficiently using GD to solve Problem (5), as GD may get stuck at a saddle point. Fortunately, Sun et al. (2015); Lee et al. (2016) showed that if a function is twice continuously differentiable and satisfies strict saddle property, i.e., each critical point is either a local minimizer or a strict saddle pointfoot_9 , GD converges to its local minimizer almost surely with random initialization. We investigate the global optimization landscape of Problem ( 5) by characterizing all of its critical points as follows.

Theorem 3.3 (Benign optimization landscape). Suppose that the number of training samples in the k-th class is

Given a coding precision ϵ > 0, if the regularization parameter satisfies (6), it holds that any critical point Z of Problem (5) that is not a local maximizer is a strict saddle point.

We defer the proof to Section 4.2 and Appendix D.3. Here, we make some remarks on this theorem and also on the consequences of the results derived so far.

Differences from existing results on the MCR 2 problem. 4) with Frobenius norm constraints on each Z k in the UFM. However, their analysis requires an additional rank constraint on each Z k and only characterizes globally optimal representations. In contrast, our analysis eliminates the need for the rank constraint, and we characterize local and global optimality in Problem (5), as well as its optimization landscape. Interestingly, we demonstrate that the features represented by each local maximizer -not just global maximizers -are also compact and structured. Furthermore, we demonstrate that the regularized MCR 2 objective ( 5) is a strict saddle function. To the best of our knowledge, Theorems 3.1 and 3.3 constitute the first analysis of local optima and optimization landscapes for MCR 2 objectives. According to Daneshmand et al. (2018); Lee et al. (2016); Xu et al. (2018), Theorems 3.1 and 3.3 imply that low-dimensional and discriminative representations can be efficiently found by (stochastic) GD on Problem (5) from a random initialization.

Comparison to existing landscape analyses in nonconvex optimization. In recent years, there has been a growing body of literature exploring optimization landscapes of non-convex problems in machine learning and deep learning. These include low-rank matrix factorization (Ge et al., 2017;Sun et al., 2018;Chi et al., 2019;Zhang et al., 2020), community detection (Wang et al., 2021;2022b), dictionary learning (Sun et al., 2017;Qu et al., 2020;Zhai et al., 2020), and deep neural networks (Sun et al., 2020;Yaras et al., 2022;Zhou et al., 2022;Zhu et al., 2021;Jiang et al., 2024). The existing analyses in the literature cannot be applied to the MCR 2 problem due to its special structure, which involves the log-determinant of all features minus the sum of the log-determinant of features in each class. Our work contributes to the literature on optimization landscape analyses of non-convex problems by showing that the MCR 2 problem has a benign optimization landscape. Our approach may be of interest to analyses of the landscapes of other intricate loss functions in practical applications.

Proofs of Main Results

In this section, we sketch the proofs of our main theorems in Section 3. The complete proofs can be found in Sections B and C of the appendix. For ease of exposition, let

Analysis of Optimality Conditions

Our goal in this subsection is to characterize the local and global optima of Problem (5). Towards this goal, we first provide an upper bound on the objective function F in Problem (5). In particular, this upper bound is tight when the blocks {Z k } K k=1 are orthogonal to each other. This result is a direct consequence of (Chan et al., 2022, Lemma 10)

where the inequality becomes equality if and only if

Next, we study the following set of critical points, which are between-class discriminative (i.e., Z T k Z l = 0):

, and (iii) the singular values satisfy where

and

This proposition shows that each critical point that is between-class discriminative (i.e., Z T k Z l = 0) exhibits a specific structure: the singular values of Z k can only take on two possible values, σ k and σ k . We will leverage this structure and further show that Z is a strict saddle if there exists a Z k with a singular value σ k .

Analysis of Optimization Landscape

Our goal in this subsection is to show that the function F in Problem (5) has a benign optimization landscape. Towards this goal, we denote the set of critical point of F by

According to (13), we divide the critical point set X into two disjoint sets Z and Z c , i.e., X = Z ∪ Z c , where

Moreover, according to Proposition 4.2, we further divide Z into two disjoint sets Z 1 and Z 2 , i.e., Z = Z 1 ∪ Z 2 . Here,

where σ k,i (Z k ) denotes the i-th largest singular value of Z k . Our first step is to show that any point belonging to Z 1 is a local maximizer, while any point belonging to Z 2 is a strict saddle point.

Proposition 4.3. Consider the setting of Theorem 3.3. Suppose that Z ∈ Z. Then, the following statements hold:

Next, we proceed to the second step to show that any point belonging to Z c is a strict saddle point. It suffices to find

With the above preparations that characterize all the critical points, we can prove Theorem 3.1 and Theorem 3.3. We refer the reader to Appendix D for the detailed proof.

Experimental Results

In this section, we first conduct numerical experiments on synthetic data in Section 5.1 to validate our theoretical results, and then on real-world data sets using deep neural networks in Section 5.2 to further support our theory. All codes are implemented in Python mainly using NumPy and PyTorch. All of our experiments are executed on a computing server equipped with NVIDIA A40 GPUs. Due to space limitations, we defer some implementation details and additional experimental results to Appendix E.

Validation of Theory for Solving Problem (5)

In this subsection, we employ GD for solving Problem (5) with different parameter settings. We visualize the optimization dynamics and structures of the solutions returned by GD to verify and validate Theorems 3.1 and 3.3.

Verification of Theorem 3.1. In this experiment, we set the parameters in Problem (5) as follows: the dimension of features d = 100, the number of classes K = 4, the num- Verification of Theorem 3.3. In this experiment, we maintain the same setting as above, except that the number of samples in each class is equal. We first fix m = 200 and vary d ∈ {40, 80, 120}, and then fix d = 50 and vary d ∈ {100, 200, 400} to run GD. We plot the distances between function values of the iterates to the optimal value, which is computed according to (7) in Theorem 3.1, against the iteration numbers in Figure 3. We observe that GD with random initialization converges to an optimal solution at a linear rate. This indicates that the MCR 2 has a benign global landscape, which supports Theorem 3.3.

Training Deep Networks Using Regularized MCR 2

In this subsection, we conduct numerical experiments on the image datasets MNIST (LeCun et al., 1998) and CIFAR-10 (Krizhevsky et al., 2009) to provide evidence that our theory also applies to deep networks. More specifically, we employ a multi-layer perceptron network with ReLU activation as the feature mapping z = f Θ (x) with output dimension 32 for MNIST and 128 for CIFAR-10. Then, we train the network parameters Θ via Adam (Kingma & Ba, 2014) by optimizing Problem (5).

Experimental setting and results. In the experiments, we randomly sample a balanced subset with K classes and m samples from MNIST or CIFAR-10, where each class has the same number of samples. We set λ = 0.001 and = 0.5. For different subsets with corresponding values of (m, K), we run experiments and report the function value F obtained by training deep networks and the optimal value F * computed using the closed-form solution in Theorem 3.1 (Björck & Golub, 1973) between the class subspaces:

where the columns of U k ∈ R d×r k are the right singular vectors corresponding to the top r k singular values of Z k defined in ( 14) and r k is its rankfoot_10 for each k ∈ [K]. In particular, when s is smaller, the spaces spanned by each pair Z k and Z l for k ̸ = l are closer to being orthogonal to each other. Then, we record the value s in Table 1 in different settings. Moreover, we visualize the pairwise cosine similarities between learned features on MNIST and CIFAR-10 when (m, K) = (1500, 6) and (2500, 10) in Figure 4.

We observe from Table 1 that the function value returned by training deep networks is extremely close to the global optimal value of Problem (5) and from the value s and Figure 4 that the features from different classes are nearly orthogonal to each other. These observations, together with Theorems 3.1 and 3.3, indicate that Problem (5) retains its optimization properties even when Z is parameterized by a neural network. Our theoretical analysis of Problem (5) thus illustrates a qualitative picture of training deep networks with the regularized MCR 2 objective.

Conclusion

In this work, we provided a complete characterization of the global landscape of the MCR 2 objective, a highly nonconcave and nonlinear function used for representation learning. We characterized all critical points, including the local and global optima, of the MCR 2 objective, and showed that -surprisingly -it has a benign global optimization landscape. These characterizations provide rigorous justifications for why such an objective can be optimized well using simple algorithms such as gradient-based methods. In particular, we show that even local optima of the objective leads to geometrically meaningful representations. Our experimental results on synthetic and real-world datasets clearly support this new theoretical characterization. With the global landscape clearly revealed, our work paves the way for exploring better optimization strategies, hence better deep neural network architectures, for optimizing the MCR 2 objective more efficiently and effectively. For future work, it is natural to extend our analysis to Problem (4) with deep network parameterizations. It is also interesting to study the sparse MCR 2 objective, which has led to high-performance transformer-like architectures (Yu et al., 2023a;b).

Impact Statement

This paper advances the state of knowledge in machine learning theory, including non-convex optimization for representation learning. We do not anticipate any particular societal or ethical impacts of this paper, besides those usually associated with theoretically oriented machine learning papers.

Supplementary Material

The organization of the supplementary material is as follows: In Appendix A, we introduce preliminary setups and auxiliary results for studying the MCR 2 problem. Then, we prove the technical results concerning the global optimality of Problem (5) in Appendix B and the optimization landscape of Problem (5) in Appendix C, respectively. In Appendix D, we prove the main theorems in Theorem 3.1 and Theorem 3.3. Finally, we provide more experimental setups and results in Appendix E.

Besides the notions introduced earlier, we shall use BlkDiag(X 1 , . . . , X K ) to denote the block diagonal matrix whose diagonal blocks are X 1 , . . . , X K .

A. Preliminaries

In this section, we first introduce the first-order optimality condition and the concept of a strict saddle point for F (•) in Problem (5) in Section A.1, and finally present auxiliary results about matrix computations and properties of the logdeterminant function in Section A.2. Recall that

and α, α k are defined in (11). To simplify our development, we write R c (Z, π k ) in (3) as

Therefore, we can write F (Z) in Problem (5) into

A.1. Optimality Conditions and Strict Saddle Points

To begin, we compute the gradient and Hessian (in bilinear form along a direction D ∈ R d×m ) of R(•) in (2) as follows:

where X := I n + αZZ T and α is defined in (11). Note that we can compute the gradient and Hessian of R c (•) in (21) using the same approach. Based on the above setup, we define the first-order optimality condition of Problem (5) as follows.

Definition A.1. We say that Z ∈ R d×m is a critical point of Problem (5) if ∇F (Z) = 0, i.e.,

where α and α k are defined in (11).

According to Jin et al. (2017); Lee et al. (2019), we define the strict saddle point, i.e., a critical point that has a direction with strictly positive curvaturefoot_11 , of Problem (5) as follows: Definition A.2. Suppose that Z ∈ R d×m is a critical point of Problem (5). We say that Z is its strict saddle point if there exists a direction

where

Remark that for the MCR 2 problem, strict saddle points include classical saddle points with strictly positive curvature as well as local minimizers.

A.2. Auxiliary Results

We provide a matrix inversion lemma, which is also known as Sherman-Morrison-Woodbury formula.

Lemma A.3 (Matrix inversion lemma). For any Z ∈ R d×m , we have

We next present a commutative property for the log-determinant function and the upper bound for the coding rate function.

We refer the reader to (Chan et al., 2022, Lemma 8 & Lemma 10) for the detailed proofs. Here, let Z = U ΣV T be a singular value decompositon (SVD) of Z ∈ R d×m , where r = rank(Z) ≤ min{m, d}, U ∈ O d×r , Σ ∈ R r×r is a diagonal matrix, and V ∈ O m×r .

Lemma A.4 (Commutative property). For any Z ∈ R d×m and α > 0, we have

where the equality holds if and only if

Finally, we show that the objective function of Problem ( 5) is invariant under the block diagonal orthogonal matrices.

Lemma A.6. For any

we have

This implies ∇F (ZO) = ∇F (Z). Finally, using (24), we have

where the equality holds if and only if Z T k Z l = 0 for all 1 ≤ k ̸ = l ≤ K. Substituting this into (5) directly yields (12).

B.2. Proof of Proposition 4.2

Proof of Proposition 4.2. Let Z ∈ Z be arbitrary, where Z is defined in (13). It follows from

This, together with ( 23), yields that ∇F (Z) = 0 is equivalent to

Obviously, Z k = 0 is a solution of the above equation for each k ∈ [K], which satisfies Z T k Z l = 0 for all l ̸ = k. Now, we consider Z k ̸ = 0, and thus

Σk 0 0 0

be a singular value decomposition (SVD) of

. Substituting this SVD into (33) yields for all k ∈ [K],

which is equivalent to

Using Σ k = BlkDiag( Σk , 0), we further obtain

Since Σk is a diagonal matrix with diagonal entries being positive, we have for all k ∈ [K],

This implies for each i ∈

Therefore, we obtain that σ 2 k,i > 0 for each i ∈ [r k ] is a positive root of the following quadratic equation with a variable x ∈ R:

where

According to (6), one can verify that for each k ∈ [K],

This yields that the above quadratic equation has positive roots as follows. For each i ∈ [r k ] and k ∈ [K], we have

Finally, using Z T k Z l = 0 and (34), we obtain

These, together with (34), yields ( 14).

Conversely, suppose that each block Z k of Z satisfies Z k = 0 or takes the form ( 14) for some

and σ k,i > 0 satisfying (15). We are devoted to showing Z ∈ Z. It is straightforward to verify that Z T k Z l = 0 for all 1 ≤ k ̸ = l ≤ K. This, together with Lemma 4.1, implies

where the last equality is due to ( 15), ( 16), ( 17), and (36). Then, we compute

where the second equality follows from ( 27). This, together with ( 23), yields

where the last equality follows from ( 14) and ( 39). Therefore, we have ∇F (Z) = 0 as desired. This, together with

Proof of Proposition 4.3. For each Z ∈ Z, it follows from Lemma 4.1 that

where f k is defined in (32). Suppose that there exists k ∈ [K] such that r k = 0, i.e., Z k = 0. According to ( 24) and (32), we compute for any

where the second equality follows from m k α k /m = α according to (11). This implies 0 is a local maximizer of f k (Z k ). Suppose to the contrary that r k > 0 for all k ∈ [K]. For each Z ∈ Z, using Lemma 4.1 with Z T k Z l = 0 for all k ̸ = l, (14), and (32), we have

where the second equality is due to (14) and Lemma A.4. For ease of exposition, let

Using ( 15), ( 36), (37), and (38), one can verify that h

. This yields that h k (σ k ) is a local minimizer and h(σ k ) is a local maximizer. This, together with (42) and the fact that 0 is a local maximizer of f k (Z k ), implies (i) and (ii).

C.2. Proof of Proposition 4.4

Proof of Proposition 4.4. Note that Z ∈ R d×m is a critical point that satisfies (25). Suppose that rank (Z) = r and rank (Z k ) = r k for all k ∈ [K]. Obviously, we have r k ≤ min{m k , d} for all k ∈ [K] and K k=1 r k ≤ r ≤ min{m, d}. Now, let ZZ T = QΛQ T be an eigenvalue decomposition of ZZ T ∈ S d + , where Q ∈ O d×r and Λ ∈ R r×r is a diagonal matrix with diagonal entries being positive eigenvalues of ZZ T . Suppose that ZZ T has p distinct positive eigenvalues, where 1 ≤ p ≤ r. Let λ 1 > • • • > λ p > 0 be its distinct eigenvalue values with the corresponding multiplicities being h 1 , . . . , h p ∈ N + , respectively. Obviously, we have p i=1 h i = r. Therefore, we write

where

According to Lemma A.6, we can see that Z is a critical point with curvature if and only if ZO is a critical point with the same curvature for each

. Substituting this into (25) in Definition A.1 gives

This is equivalent to

This yields that each column of Z k is an eigenvector of Z for each k ∈ [K]. This, together with the decomposition in ( 44), yields that we can permute the columns of Z k such that the columns belonging to the space spanned by Q i are rearranged together. Let s k,i ∈ N denote the number of columns of Z k that belong to the space spanned by

there exists an a column permutation matrix

where

This, together with (21) and Lemma A.5, yields

Moreover, let

Using this and (45), we have

This, together with (2), Lemma A.5, and

Characterize the structure of critical points. Now, for each k ∈

be a singular value decomposition (SVD) of

According to ( 5), ( 23), ( 45), and ( 46), we have for all k ∈ [K] and i ∈ [p],

Substituting the block forms of

k in (49) into the above equation and rearranging the terms, we obtain for all k ∈ [K] and i ∈ [p],

Using X = I + αZZ T and rearranging the terms, we have for all k ∈ [K] and i ∈ [p],

Since

0 for all i ̸ = j, and (50), we have for all k ∈ [K] and i ∈ [p],

Rearranging the terms in the above equation, we obtain for each k ∈ [K] and i ∈ [p],

Substituting this back to (52) yields for each k ∈ [K] and i ∈ [p],

This, together with ( 49) and ( 53), yields

It follows from this and (47) that

Since there exists k ̸ = l ∈ [K] such that Z T k Z l ̸ = 0, we can assume without loss of generality that

This, together with Z (i) T Z (j) = 0 for all i ̸ = j, implies that there exists i * ∈ [p] such that z 1,i1 , z 2,i2 are both columns of Z (i * ) . Without loss of generality, suppose that z 1,i1 and z 2,i2 are Since Z

, where

, the second equality follows from

k,1 , and (60). Summing up the above equality for all k ∈

where the second equality follows from the definition of β i in (53). Finally, we compute

where the inequality is due to ∥q 2 ∥ = ∥c 2 ∥ ̸ = 0 and

Given a matrix Z ∈ R d×m , let ZZ T = QΛQ T be an eigenvalue decomposition of ZZ T ∈ S d + , where Q ∈ O d×r and Λ ∈ R r×r is a diagonal matrix with diagonal entries being positive eigenvalues of ZZ T . Suppose that ZZ T has p distinct positive eigenvalues, where 1 ≤ p ≤ r. Let λ 1 > • • • > λ p > 0 be its distinct eigenvalue values with the corresponding multiplicities being h 1 , . . . , h p ∈ N + , respectively. Obviously, we have p i=1 h i = r. Therefore, we write 19), ( 20), (ii) in Proposition 4.3 and Proposition 4.4, if Z ∈ Z c ∪ Z 2 , then Z is a strict saddle point. This, together with X = Z c ∪ Z 1 ∪ Z 2 and the fact that Z is a local maximizer, implies that Z ∈ Z 1 . Using this, (20), and Proposition 4.2 yields that Z satisfying ( 7), (a), (b), and (c).

(ii) According to (i) in Theorem 3.1, suppose that the k-th block of a local maximizer Z admits the decomposition in ( 7) satisfying (a), (b), and (c) for all k ∈ [K]. This, together with (42) in the proof of Proposition 4.3, yields that

where σ k is defined in ( 16) for each k ∈ [K]. Then, we define a function g :

One can verify that for all n 1 ≥ n 2 , we have g(n 1 , x) ≤ g(n 2 , x) for each x. Therefore, we have for all m k ≤ m l ,

where the second inequality follows from σ 2 k is the maximizer of the function g(m k , x) = h k (x) according to (43). This, together with (61), yields that Z is a global maximizer if and only if K k=1 r k = min{m, d} and for all k ̸ = l satisfying m k < m l and r l > 0, we have r k = min{m k , d}.

D.2. Proof of Proposition 3.2

To prove Proposition 3.2, we first need to characterize the global optimal solution set of Problem (4).

where

Proof. According to Lemma A.5, we have

where the inequality becomes equality if and only if Z T k Z l = 0 for all k ̸ = l. To simplify our development, let r k := rank(Z k ) denote the rank of Z k ∈ R d×m k , where r k ≤ min{d, m k } for each k ∈ [K] and K k=1 r k ≤ min{d, m}, and

Moreover, let

Σk 0 0 0

be a singular value decomposition (SVD) of Z k , where

. Substituting this SVD into (64), together with ∥Z k ∥ 2 F = m k , yields that to maximize H(Z), it suffices to study for each k ∈

Lemma D.2. Suppose that m, K are integers such that m/K is a positive integer, r ≤ m/K is an integer, and α > 0 is a constant. Consider the following optimization problem

the optimal solution is

Proof. If r = 1, it is trivial to see that ( 69) is the optimal solution. Therefore, it suffices to study r ≥ 2. To simplify our development, let f (x) := -log(1 + αx) + log(1 + Kαx)/K and F (x) := r i=1 f (x i ). Then, one can verify that for all x ≥ 0,

Introducing dual variables λ associated with the constraint r i=1 x i = m/K and µ i associated with the constraint x i ≥ 0 for each i ∈ [r], we write the Lagrangian as follows

Then, we write the KKT system as follows:

Now, let S := {i ∈ [r] : x i > 0} denote the support set of a KKT point x ∈ R r and s := |S| denote the cardinality of the support set, where 1 ≤ s ≤ r. This, together with (72), implies that for each i ∈ S,

This is equivalent to the following quadratic equation:

We compute

Note that for all i ∈ S, we have x i > 0, and thus µ i = 0. This, together with K ≥ 2 and the first equation in (73), implies λ > 0. Consequently, the quadratic equation ( 74) has a positive root if and only if η ≥ 0 and ∆ ≥ 0. This implies

Then, the solution of Problem ( 74) is x i ∈ {x, x} for each i ∈ S, where

Now, we discuss the KKT points that could potentially be optimal solutions. Let x ∈ R r be a KKT point satisfying x i ∈ {x, x} for each i ∈ S, where s ∈ {1, 2, . . . , r}. In particular, when s = 1, we have x i = m/K for all i ∈ S. In the following, we consider s ∈ {2, . . . , r}.

Case 1. Suppose that x i = x j for all i, j ∈ S. This, together with i∈S x i = m/K and x i ∈ {x, x} for each i ∈ S, yields

Case 2. Suppose that there exists i ̸ = j ∈ S such that x i ̸ = x j . This, together with x i ∈ {x, x}, implies x > x. According to (70), we have f ′′ (x) = 0 at x = 1/(α √ K). Then, we obtain that f ′ (x) is strictly decreasing in [0, x] and strictly increasing in [x, ∞]. Then, one can further verify that x < x < x. This, together with (70), implies

For ease of exposition, let l(x) = |{i ∈ S : x i = x}| be the number of entries of x that equal to x. Then, we claim that any optimal solution x ⋆ satisfies l(x ⋆ ) ≤ 1. Now, we prove this claim by contradiction. Without loss of generality, we assume that x ⋆ i = x for all i = 1, . . . , r -l and x ⋆ i = x for all i = r -l + 1, . . . , r with l ≥ 2. This, together with (79) and l ≥ 2, yields

Using the second-order necessary condition for constraint optimization problems (see, e.g., (Nocedal & Wright, 1999, Theorem 12.5)) and

Then, we take

which contradicts (80). Therefore, x ⋆ cannot be an optimal solution. Then, we prove the claim. In this case, we can write the KKT point that could be an optimal solution as follows: There exists i ∈ S such that

Now, we compute the function values for the above two cases, i.e., ( 78) and ( 82), and compare them to determine which one is the optimal solution. To simplify our analysis, let h(x) := f (x)/x. For (78) in Case 1, we compute

For (82) in Case 2, we compute

where the inequality is because x ≤ m/ ((s -1)K) and f (x) is strictly dereasing in [0, ∞). For all x ∈ [m/(sK), m/ ((s -1)K)], we compute

where the first inequality follows from log(1 + αx) -log(1 + Kαx)/K ≥ log(1 + α) -log(1 + αK)/K due to x ≥ m/(sK) ≥ 1, the second inequality uses log(1 + α) -log(1 + αK)/K = (K -1) log(1 + α)/K + log ((1 + α)/(1 + αK)) /K ≥ ((K -1) log(1 + α) -log K) /K, and the last inequality is because of x ≥ m/(sK).

According to (68), we have

Using the mean-value theorem, there exists x ∈ (m/(sK), m/ ((s -1)K)) such that

where the inequality follows from (85). Now, we are devoted to bounding f (x). According to ( 75) and ( 76), we have

This, together with the fact that f (x) is decreasing in (0, ∞), yields

where the last inequality uses η 76). This, together with ( 83), (84), and (87), yields

where the last inequality follows from (68). This implies that the optimal solution takes the form of (78) for some s ∈ [r].

Consequently, the function value of (78) for each s ∈

This, together with Lemma D.3, implies that when the optimal solution takes the form of ( 78) with s = r, Problem (67) achieves its global minimum. Then, we complete the proof.

Lemma D.3. Consider the setting in Lemma D.2 and the following function

where s ∈ [1, r] and α satisfies (68).

Proof. For ease of exposition, let β := mα and x := 1/s ∈ [1/r, 1]. According to (68), we have

This implies β ≥ r √ K. Then, we study According to the results in Figures 5(a), 5(b), 6, and 7 of Experiments 1 and 2, we observe that when the number of samples is larger than its dimension, i.e., m ≥ d, the learned features via the MCR 2 principle are within-class compressible and between-class discriminative in both balanced and unbalanced data sets. Moreover, the dimension of the space spanned by these features is maximized such that K k=1 r k = min{m, d}. This directly supports Theorem 3.1. By comparing the function value returned by GD and that computed by the closed-form in Theorem 3.1, we found that GD with random initialization will always converge to a global maximizer of Problem (5) when the data is balanced, while it will always converge to a local maximizer of Problem (5) when data is unbalanced. This directly supports Theorem 3.3.

According to the results in Figures 5(c) and 8 of Experiment 3, we observe that when the number of samples is smaller than its dimension, i.e., m ≤ d, the learned features via the MCR 2 principle are orthogonal to each other and the dimension of each subspace is equal to the number of samples, i. In the experiments on MNIST, we employ a 4-layer multilayer perception (MLP) network with ReLU activation as the feature mapping with the intermediate dimension 2048 and output dimension 32. In particular, each layer of MLP networks consists of a linear layer and layer norm layer followed by ReLU activation in the implementation. We train the network parameters via Adam by optimizing the MCR 2 function. For the Adam settings, we use a momentum of 0.9, a full-batch size, and a dynamically adaptive learning rate initialized with 5 × 10 -3 , modulated by a CosineAnnealing learning rate scheduler (Loshchilov & Hutter, 2016). We terminate the algorithm when it reaches 3000 epochs. More experimental results on MNIST. Besides the numerical results in Table 1, we also plot the heatmap of the cosine similarity between pairwise columns of the features in Z obtained by training deep networks in Figure 9. We observe that the features from different classes are nearly orthogonal to each other, while those from the same classes are highly correlated. This supports our results in Theorem 3.1.

Network architecture and training setups for CIFAR-10. In the experiments on CIFAR10, we employ a 2-layer multilayer perceptron (MLP) network with ReLU activation as the feature mapping with the intermediate dimension 4096 and output dimension 128. In particular, each layer of MLP networks consists of a linear layer and layer norm layer followed by ReLU activation in the implementation. We train the network parameters via Adam by optimizing the MCR 2 function. For the Adam settings, we use a momentum of 0.9, a full-batch size, and a dynamically adaptive learning rate initialized with 5 × 10 -3 , modulated by a CosineAnnealing learning rate scheduler (Loshchilov & Hutter, 2016). We terminate the algorithm when it reaches 4000 epochs.

More experimental results on CIFAR-10. Besides the numerical results in Table 1, we also plot the heatmap of the cosine similarity between pairwise columns of the features in Z obtained by training deep networks in Figure 9. We observe that the features from different classes are nearly orthogonal to each other, while those from the same classes are highly correlated. This supports our results in Theorem 3.1. 5) on m samples split equally among K classes of MNIST and CIFAR-10. In the figure, the darker pixels represent higher cosine similarity between features. In particular, when the (i, j)-th pixel is close to 0 (very light blue), the features i and j are approximately orthogonal.