Learning Diverse and Discriminative Representations via the Principle of Maximal Coding Rate Reduction

Yaodong Yu; Kwan Ho Ryan Chan; Chong You; Chaobing Song; Yi Ma

Source-linked AI summary

Learning Diverse and Discriminative Representations via the Principle of Maximal Coding Rate Reduction

Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, Yi Ma

arXiv:2006.08558v1Jun 15, 2020cs.LGcs.CVcs.ITstat.ML

TL;DR

The paper addresses how to learn intrinsic low-dimensional representations that discriminate classes in mixed high-dimensional data. It proposes MCR^2, which maximizes the coding-rate difference between the whole dataset and its classes, and reports theoretical guarantees, unified applicability across learning settings, and greater robustness to label noise than cross-entropy.

Problem
Learning representations that preserve intrinsic structures while discriminating classes remains difficult for mixed high-dimensional data, especially when existing objectives are task-dependent or heuristic.
Method
MCR^2 maximizes the coding-rate difference between the whole dataset and the sum of its individual classes to learn diverse, discriminative representations.
Results
The paper provides theoretical guarantees and reports that MCR^2 learns useful representations in supervised, self-supervised, and unsupervised settings while being more robust to corrupted labels than cross-entropy.
Takeaways & Limitations
MCR^2 offers a unified principle for learning discriminative low-dimensional representations across multiple learning settings.
Takeaways & Limitations
Self-supervised representations can remain far from optimal because jointly optimizing features and partitions may reach only local maxima, leaving better optimization strategies open.

Abstract

from arXiv · show

To learn intrinsic low-dimensional structures from high-dimensional data that most discriminate between classes, we propose the principle of Maximal Coding Rate Reduction ($\text{MCR}^2$), an information-theoretic measure that maximizes the coding rate difference between the whole dataset and the sum of each individual class. We clarify its relationships with most existing frameworks such as cross-entropy, information bottleneck, information gain, contractive and contrastive learning, and provide theoretical guarantees for learning diverse and discriminative features. The coding rate can be accurately computed from finite samples of degenerate subspace-like distributions and can learn intrinsic representations in supervised, self-supervised, and unsupervised settings in a unified manner. Empirically, the representations learned using this principle alone are significantly more robust to label corruptions in classification than those using cross-entropy, and can lead to state-of-the-art results in clustering mixed data from self-learned invariant features.

1 Context and Motivation

The paper frames representation learning as recovering intrinsic structures from mixed high-dimensional data while making classes discriminative. It motivates representations that are between-class discriminative, within-class compressible, and maximally diverse, while addressing limitations of label-dependent and heuristic objectives.

Learning from finite samples seeks a continuous map that captures intrinsic data structures and facilitates classification or clustering.
End-to-end supervised prediction can fit mislabeled data while leaving the intrinsic geometry and guarantees of intermediate features unclear.
Information bottleneck seeks minimal sufficient features by maximizing I(z, y) while minimizing I(x, z), whereas autoencoding and contractive methods rely on reconstruction, compactness, or Jacobian-based heuristics.
Heuristic representation objectives may miss multimodal subclass structures or fail to discriminate them, motivating a principled measure usable in supervised and unsupervised settings.
The manifold assumption models each class on a low-dimensional submanifold within a high-dimensional ambient space.
The target representation maps class submanifolds to linear subspaces with uncorrelated classes, compressible within-class features, and maximally large class-specific dimensions.

2 Technical Approach and Method

The method measures representation compactness through finite-sample coding rates and maximizes the difference between the whole representation and class-specific subsets. Its optimal solutions theoretically combine orthogonal class subspaces with diverse, high-dimensional features within each class.

Motivation: MCR^2 addresses whether discriminative and diverse representation properties can be jointly achieved by a principled compactness objective.The objective is intended to characterize intrinsic geometric or statistical properties without explicit dependence on class labels, supporting multiple learning settings.
Coding-rate measure: Rate distortion measures the minimum bits needed to encode a representation at prescribed precision, but exact computation is difficult for general degenerate distributions.The paper uses coding rate because entropy is not well-defined for the relevant continuous degenerate distributions.
Coding-rate measure: Finite samples from subspace-like distributions permit accurate estimates of coding rate for learned representations.The representation consists of finite samples z_i = f(x_i, θ), whose coding length can be estimated at precision ϵ.
Rate reduction objective: For mixed data, MCR^2 partitions Z into class or cluster subsets and maximizes ΔR = R(Z, ϵ) − Rc(Z, ϵ | Π).R measures the coding rate of the whole set, while Rc sums the rates of the subsets specified by the membership matrices Π.
Rate reduction objective: The objective expands the whole representation while compressing each class, preferring incoherent features across classes and correlated features within classes.Feature-scale normalization is required because ΔR is monotonic in representation scale; Frobenius normalization, unit-sphere normalization, or approximately isometric layers are proposed.
Theoretical properties: MCR^2 theoretically yields mutually orthogonal class subspaces, maximal class-subspace dimensions, and isotropically distributed features within each subspace.These properties hold under sufficient ambient dimension and adequately small coding precision, and differ from information bottleneck’s minimal-sufficient-statistics objective.
Theoretical properties: At optimum, MCR^2 prefers multiple independent subspaces with the highest feasible dimensions rather than one-dimensional class representations.The paper contrasts this diversity-promoting behavior with geometric losses that can favor one-dimensional representations.

3 Experiments with Instantiations of MCR2

Experiments apply MCR2 to supervised, self-supervised, and unsupervised representation learning, showing robust discriminative features and effective invariant-feature clustering. A controlled training dynamic, MCR2-CTRL, improves self-supervised clustering, though jointly optimized self-supervised representations remain local optima.

Supervised learning: MCR2 is optimized with fixed class-membership matrices and mini-batch stochastic gradient descent in supervised learning.The mapping f(·, θ) is trained by optimizing the MCR2 objective while labels determine the membership matrix.
Supervised learning: MCR2 learns higher-dimensional and more diverse features than cross-entropy, with expanding whole-data structure and compressed within-class structure.The rates indicate whole-set expansion alongside class-wise compression; singular-value comparisons report greater diversity than cross-entropy features.
Supervised learning: MCR2 representations are designed to rely less on corrupted labels, supporting robustness when training labels or grouping information are noisy.The corrupted-label experiment compares identical networks trained with cross-entropy and MCR2 across corruption levels.
Self-supervised learning: Self-supervised invariant features are learned by treating augmentations of each sample as a class and applying the supervised MCR2 procedure.Each sample’s augmentations are grouped together, and the resulting self-labeled data train the feature mapping.
Self-supervised learning: Directly optimizing ΔR reaches 0.570 clustering accuracy on CIFAR10, reported as the second-best result compared with previous methods.Without class labels, the overall coding rate expands quickly and the MCR2 loss saturates at a local maximum.
Experimental setup: The experiments use ResNet-18 across CIFAR10, CIFAR100, and STL10, with results summarized in classification and clustering tables.The paper emphasizes basic usage and fair comparison rather than extensive engineering.
Limitations: Self-supervised representations initialized without correct class partitions remain far from optimal and are at best local maxima when θ and Π are jointly optimized.The paper identifies better optimization strategies for unlabeled or partially labeled data as an open problem.

4 Conclusion and Future Work

The paper presents MCR2 as a principled objective for learning discriminative low-dimensional representations and connects it to broader learning frameworks. It establishes theoretical and empirical support while identifying open questions about robustness, clustering, and practical deployment.

MCR2 receives rigorous theoretical justification and empirical evidence as a principle for learning discriminative low-dimensional representations across learning settings.
Open questions include why MCR2 is robust to label noise, effective for clustering from self-learned features, and systematically useful for improving clustering or classification.
The framework may support principled deep-learning objectives and architectures by monitoring and optimizing rate reduction across network layers.
The principle is stated to apply beyond mixed subspaces to mixed distributions or structures, with maximal-rate-reduction configurations remaining theoretically interesting.

Appendices

The appendices develop properties and bounds for log det and coding-rate functions, then use them to bound coding-rate reduction. The bounds become tight under shared covariance or pairwise orthogonality conditions.

The appendix establishes strict concavity of log det on positive-definite matrices, with equality in the concavity inequality only when the matrices coincide.
The coding-rate analysis uses determinant identities and orthogonal invariance to relate a representation matrix to its class-specific components.
The coding-rate upper bound is tight when component distributions have the same covariance and their representation components are pairwise orthogonal.
Strict concavity supplies a lower bound whose equality condition requires the class-specific covariance terms to be identical.
Lemma A.5 bounds coding-rate reduction using individual class components, with equality characterized through the orthogonality condition developed in the preceding bounds.

A.4 Main Results: Properties of Maximal Coding Rate Reduction

The main theorem characterizes maximizers of coding-rate reduction: class representations occupy orthogonal subspaces, while each class uses a maximally diverse representation under the stated rank and small-ϵ conditions.

For a fixed class partition, MCR2 is maximized by representations that are maximally discriminative across classes and diverse within classes, when total class rank is small relative to ambient dimension and ϵ is small.
At an optimum, representations from different classes lie in pairwise orthogonal subspaces.
Within each class, the optimal representation has rank dj, expressing the theorem’s within-class diversity property.

A.5 Proof of Main Results

The proof constructs the theorem through scalar optimization and coding-rate comparisons. It shows orthogonality improves the objective and derives the optimal singular-value structure, while simulations verify that higher-dimensional orthogonal subspaces obtain larger MCR2 values.

Scalar optimization: The scalar optimization lemma shows that global optima have either equal coordinates or one lower coordinate alongside r−1 equal higher coordinates.
Scalar optimization: Under the lemma’s derivative assumptions, all optimal coordinates are positive and the unequal solution has xH > xL > 0.
Orthogonality: The proof replaces nonorthogonal class components with orthogonal ones and obtains a strictly larger coding-rate reduction, contradicting optimality.
Singular values: The singular-value analysis reduces each class optimization to scalar variables and yields an optimal pattern with repeated high singular values and one positive lower value.
Simulation: In simulations, orthogonal subspaces with higher dimension achieve higher MCR2 values, consistent with the theorem’s diversity-promoting prediction.

B.2 Implementation Details

The experiments use ResNet-based models on CIFAR10, CIFAR100, and STL10, with supervised and self-supervised augmentation and evaluation settings specified separately.

Supervised experiments use ResNet-18 with four residual blocks of widths [64, 128, 256, 512], RandomCrop, and RandomHorizontalFlip.
The experiments use CIFAR10, CIFAR100, and STL10 from the default PyTorch datasets.
Self-supervised CIFAR augmentations combine random resized cropping, horizontal flips, color jitter, grayscale conversion, and tensor conversion.
STL10 augmentation additionally uses 96-pixel crops and Gaussian blur, alongside flipping, color jitter, grayscale conversion, and tensor conversion.
Cross-entropy baselines use ResNet-18 with ten outputs, SGD, learning rate 0.1, momentum 0.9, weight decay 5e-4, and 400 training epochs.

B.3.1 PCA Results of MCR2 Training versus Cross-Entropy Training

MCR2 learns representations with substantially greater within-class diversity and near-orthogonality across classes than cross-entropy training, while its principal images capture varied class modes.

MCR2 representations have roughly a dozen dimensions per class and nearly 120 overall, whereas cross-entropy representations have slightly more than 10 overall dimensions.
MCR2 features from different classes are almost orthogonal, while features within the same class are more similar.
The visualizations select images by comparing learned features with top singular vectors, with rows ordered by descending associated singular values.
Within Bird and Ship, images grouped by singular vectors share shapes, textures, patterns, and styles, while different rows show significantly different characteristics.
For each CIFAR10 class, the ten images aligned with the top singular vectors are more diverse and representative than randomly selected images.

B.3.2 Experimental Results of MCR2 in the Supervised Learning Setting.

Supervised experiments evaluate MCR2 across architectures, hyperparameters, classifier components, and label-corruption precision settings, with nearest-subspace classification used for evaluation.

The mainline supervised model uses ResNet-18 with output dimension d = 128, precision ϵ2 = 0.5, and mini-batch size m = 1,000.
Across supervised experiments, larger batch sizes improve performance, and the study compares ResNet, VGG, and ResNext architectures.
Nearest-subspace classification uses rj = 30 by default and works across a wide range of component counts.
Precision ϵ2 is varied across label-corruption levels to further assess MCR2 classification with corrupted labels.

B.3.3 Experimental Results of MCR2 in the Self-supervised Learning Setting

Self-supervised experiments compare MCR2 with MCR2-CTRL through training dynamics and clustering metrics, finding better clustering performance for MCR2-CTRL.

MCR2-CTRL uses ResNet-18 with output dimension d = 128, precision ϵ2 = 0.5, mini-batch size k = 20, and 50 augmentations.
During training, MCR2 features first expand and then compress, whereas MCR2-CTRL’s overall rate first compresses and then expands while class-conditioned rate remains small.
MCR2-CTRL achieves better clustering performance than MCR2 across NMI, ACC, and ARI comparisons.

B.3.4 Clustering Metrics and More Results

This section defines clustering evaluation metrics and reports additional self-supervised MCR2-CTRL experiments on STL10. Hyperparameter choices had only a small effect on performance.

Clustering Metrics: Clustering performance is evaluated using accuracy (ACC), normalized mutual information (NMI), and adjusted Rand index (ARI).
Clustering Metrics: The NMI definition introduces cluster-partition quantities involving C = [c1, . . . , cm] and marginal sums ai and bj.
More Results: Additional MCR2-CTRL self-supervised experiments vary training hyperparameters on STL10, with results summarized in Table 8.
More Results: The choice of hyperparameters has only a small effect on performance with the MCR2-CTRL objective.The authors hypothesize that further improvement may require better control of optimization.