ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction

Kwan Ho Ryan Chan; Yaodong Yu; Chong You; Haozhi Qi; John Wright; Yi Ma

Source-linked AI summary

ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction

Kwan Ho Ryan Chan, Yaodong Yu, Chong You, Haozhi Qi, John Wright, Yi Ma

arXiv:2105.10446v3May 21, 2021cs.LGcs.CVcs.ITstat.ML

TL;DR

The paper addresses the lack of rigorous principles for understanding and designing deep networks by deriving ReduNet from a compression-based discriminative representation objective. It uses rate reduction to construct network components forward through optimization, and reports interpretable, effective networks whose convolutional form supports invariant representations. The framework also identifies sparsity–invariance constraints and scope limitations for complicated real-data geometries.

Problem
Deep-network architectures and training practices often rely on heuristics, while the roles of their components and the structures of learned representations lack direct theoretical justification.
Method
The paper defines rate reduction as an information-theoretic objective for discriminative representations and derives ReduNet architectures, operators, and parameters layer-by-layer through forward optimization.
Results
ReduNet simulations and experiments verify that forward-constructed networks can be invariant to transformed instances and that computation scales with classes, channels, and sample dimension or size.
Takeaways & Limitations
The framework provides a white-box alternative in which network components have optimization, statistical, and geometric interpretations and can be further refined by back propagation.
Takeaways & Limitations
The basic ReduNet is expected to work best when classes have relatively benign nonlinear structures close to linear subspaces or Gaussian distributions; more complex real data may require additional strategies.

Abstract

from arXiv · show

This work attempts to provide a plausible theoretical framework that aims to interpret modern deep (convolutional) networks from the principles of data compression and discriminative representation. We argue that for high-dimensional multi-class data, the optimal linear discriminative representation maximizes the coding rate difference between the whole dataset and the average of all the subsets. We show that the basic iterative gradient ascent scheme for optimizing the rate reduction objective naturally leads to a multi-layer deep network, named ReduNet, which shares common characteristics of modern deep networks. The deep layered architectures, linear and nonlinear operators, and even parameters of the network are all explicitly constructed layer-by-layer via forward propagation, although they are amenable to fine-tuning via back propagation. All components of so-obtained "white-box" network have precise optimization, statistical, and geometric interpretation. Moreover, all linear operators of the so-derived network naturally become multi-channel convolutions when we enforce classification to be rigorously shift-invariant. The derivation in the invariant setting suggests a trade-off between sparsity and invariance, and also indicates that such a deep convolution network is significantly more efficient to construct and learn in the spectral domain. Our preliminary simulations and experiments clearly verify the effectiveness of both the rate reduction objective and the associated ReduNet. All code and data are available at \url{https://github.com/Ma-Lab-Berkeley}.

1. Introduction and Overview

The paper develops a theoretical framework that derives interpretable deep networks from learning discriminative representations through rate reduction. Its ReduNet construction explains network depth, width, operators, parameters, and convolutional structure through optimization, while experiments support the framework’s effectiveness.

Motivation: Deep-network practice lacks rigorous principles for choosing architectures, components, and training procedures, leaving many designs dependent on heuristics and trial and error.The paper identifies this gap as a central motivation for deriving network structure from a learning objective.
Principled objective: The framework shifts analysis from deep networks themselves to the intrinsic structures of data and derives a low-dimensional linear discriminative representation as the target.This reframing connects representation learning with a principled compression-based objective.
Principled objective: Rate reduction measures the coding-rate difference between all features and class-specific features, promoting within-class compression alongside between-class discrimination.The objective is intended to preserve diverse discriminative representations rather than collapsing each class to minimal features.
Constructive network: A projected gradient-ascent scheme for maximizing rate reduction naturally becomes a multilayer ReduNet, with one network layer corresponding to an optimization iteration.The framework assigns network width a statistical role and depth a computational role in representing and linearizing data structure.
Constructive network: ReduNet architectures, operators, and parameters are constructed layer-by-layer by forward propagation, yielding a white-box network that can also be fine-tuned by back propagation.The resulting components have stated optimization, statistical, and geometric interpretations rather than being selected solely empirically.
Invariant convolution: For shift- or translation-invariant representations, the derived linear operators become multi-channel convolutions, with the framework linking invariant classification to sparsity and spectral-domain construction.The paper presents this convolutional derivation as a consequence of enforcing rigorous invariance.

2. The Principle of Maximal Coding Rate Reduction

The paper defines compactness through rate distortion and proposes maximal coding rate reduction as an objective for linear discriminative representations. The resulting principle favors representations that contract within classes while separating classes into diverse, structured subspaces.

Measure of Compactness for Linear Representations: Rate distortion measures the minimum bits needed to encode a representation at a prescribed precision, providing an information-theoretic measure of compactness.For finite samples, coding length can be estimated by packing precision-sized balls into the subspace spanned by the data.
Measure of Compactness for Linear Representations: The rate-reduction function uses a finite-sample coding-rate construction for mixtures of low-dimensional subspaces and class-membership partitions.The partition is represented by diagonal membership matrices lying in a simplex, and the conditional coding rate is concave in the partition.
Principle of Maximal Coding Rate Reduction: A good linear discriminative representation maximizes the coding-rate difference between the whole dataset and the average coding rate of its class-specific subsets.This objective is called the principle of maximal coding rate reduction, or MCR2.
Properties of the Rate Reduction Function: Under sufficient ambient dimension, the learned class subspaces are orthogonal, while sufficiently high coding precision favors maximally diverse representations.The theory also favors embeddings into multiple independent subspaces with features distributed isotropically within each subspace.
Properties of the Rate Reduction Function: The framework requires an upper bound on each class dimension, and estimating intrinsic submanifold dimensions can be challenging even for noisy linear subspaces.The paper notes that dimensions can nevertheless be selected empirically through ablation experiments.
Principle of Maximal Coding Rate Reduction: MCR2 reconciles compactness and discriminativeness by compressing features within each class while expanding the joint representation across classes.This implements the rule that similarity contracts and dissimilarity contrasts.

3. Deep Networks from Maximizing Rate Reduction

Maximizing rate reduction through projected gradient ascent naturally yields ReduNet, a white-box deep network whose layers, operators, and parameters are explicitly derived from the objective. Its class-wise compression and between-class expansion have optimization and geometric interpretations, while shift-invariance turns its linear operators into multi-channel convolutions.

Motivation: ResNet can optimize the MCR2 objective, but its architecture and operators remain unjustified as a black-box choice.The open questions concern the need for depth, layer roles, width, convolutions, and nonlinear operators.
Gradient ascent: Projected gradient ascent incrementally adjusts features to improve rate reduction, starting from the input data.The iterates deform features while remaining on the unit sphere.
Gradient structure: Each gradient step combines Eℓ, which expands all features, with class-dependent Cj ℓ operators that compress features toward their class subspaces.Eℓ increases overall coding rate by acting on variance directions, whereas Cj ℓ reduces within-class coding rate by compressing residuals.
Feature-map construction: Because the training gradient depends on class membership, ReduNet constructs an increment transform over the entire feature domain to emulate the gradient flow.The resulting network can be viewed as a neural ODE whose flow is determined by the rate-reduction objective rather than a generic structure.
Network interpretation: Iterating the derived transform produces a deep network in which each layer corresponds to one gradient-ascent step for rate reduction.The basic scheme may converge slowly, sometimes requiring hundreds of layers, motivating accelerated-gradient alternatives.
Invariant architecture: Under shift-invariance, ReduNet’s linear operators naturally become multi-channel convolutions.The architecture also contains adjacent-layer skip connections, as expected from unfolding an iterative optimization scheme.
White-box construction: ReduNet parameters are explicitly constructed layer by layer by forward propagation, and its learned features can be classified with a nearest-subspace classifier.The framework gives the network’s layers, operators, and parameters precise optimization, statistical, and geometric interpretations.

4. Deep Convolution Networks from Invariant Rate Reduction

Invariant ReduNet assigns transformed samples to shared class subspaces, which makes classification invariant while encoding transformation-specific information within each subspace. Under circular shifts or translations, the resulting operators become data-derived multi-channel convolutions, with sparsity and spectral computation shaping the design.

Invariant representation: Assigning all transformed versions of a sample to one class and one subspace makes classifiers on those subspaces invariant to the transformation.The features retain equivariant information inside each subspace, while the subspaces themselves remain invariant.
Convolutional construction: For circular shifts, circulant data families make ReduNet operators and features circulant, so the network becomes convolutional without explicitly choosing convolutions.The corresponding matrix operations can be implemented using circular convolution.
Sparsity and separability: Sparsifying convolutions help resolve the conflict between invariant subspace modeling and class separability when linear lifting alone maps different classes into the same subspace.Soft thresholding or ReLU can produce sufficiently separable sparse features for subsequent ReduNet layers.
Architecture and efficiency: Using the discrete Fourier transform reduces the convolutional inverse computations from O(n^3C^3) to O(nC^3).The reduction follows from decomposing the frequency-domain operator into n blocks of size C × C.
Convolutional construction: For 2D translations, the derived linear operators act as multi-channel 2D circular convolutions on image features.The same invariant construction extends the convolutional interpretation from 1D shifts to image translations.
Architecture and efficiency: Invariant ReduNet derives multi-channel convolution forms, roles, channel counts, and parameters from the rate-reduction framework rather than selecting them heuristically.The construction generally produces cross-channel mixing rather than depth-wise separable convolutions.

5. Experimental Verification

Experiments evaluate MCR2 and ReduNet on supervised, invariant, noisy-label, and self-supervised settings. The reported results show richer class representations, robustness to corrupted labels, invariant subspaces, and useful label-free representations, while performance depends on output dimension and batch size.

MCR2 representation: MCR2 training expands the whole representation while compressing each class representation, producing diverse higher-dimensional features compared with cross-entropy.The experiments also use principal components to select diverse images from the same class.
Experimental caveat: MCR2 performance depends on selecting output dimension and batch size jointly, with sufficiently large batches needed for a given output dimension.Additional studies of these settings are reported in the appendix.
Robustness: MCR2 is significantly more robust than cross-entropy under corrupted labels, especially at higher corruption ratios.The paper attributes this comparison to MCR2 preserving intrinsic data structures and relying less on class labels.
Self-supervised learning: MCR2 can learn useful representations without labels and achieve better performance than other highly engineered methods on clustering tasks.These results are reported for the self-supervised learning setting.
Invariant ReduNet: Rotation-invariant ReduNet maps training samples and their rotated versions from ten classes into ten nearly orthogonal subspaces.The learned subspaces are reported to be invariant to shifts in polar angle.
Network construction: The experiments compare forward-constructed ReduNet with backpropagation fine-tuning and randomly initialized networks using the same backbone architecture.The supplied passage specifies the construction and training settings but does not state the comparative outcome.

6. Conclusions and Discussions

The paper presents ReduNet as a white-box framework deriving deep-network structures from rate reduction, with interpretable operators and forward construction. It also identifies invariance-related trade-offs, extensions, and scope boundaries.

White box versus black box: ReduNet derives deep convolutional networks from low-dimensional linear discriminative representation and intrinsic rate reduction.Its architecture and operators are constructed from a compression-based objective rather than designed purely empirically.
White box versus black box: The resulting operators and parameters are data-derived and have geometric and statistical interpretations, including a data auto-regression view of layerwise linear operators.Forward construction provides a basic mechanism for learning representations useful for later classification tasks.
Forward versus backward optimization and refinement: Forward-constructed ReduNet can initialize networks without relying entirely on random initialization and back propagation, while remaining amenable to fine-tuning.The paper reports that preliminary experiments show descent classification performance for the forward-constructed network.
Modeling invariance and equivariance: Under rigorous shift-invariance constraints, ReduNet’s linear operators become multi-channel convolutions, with construction and learning naturally benefiting from the spectral domain.The derivation connects equivariance and invariance through mappings of transformed instances into common subspaces.
Invariance and sparsity: The framework exposes a sparsity–invariance trade-off: separating classes under arbitrary shifts and superpositions requires sparse class representations.The paper states that this trade-off warrants further study of width and depth needed for performance guarantees.
Further improvements and extensions: The basic ReduNet is expected to work best when classes are close to linear subspaces or Gaussian distributions, whereas real data may have more complex geometry or multimodality.The authors suggest more sophisticated compression-control strategies may be needed for better representations on such data.
Further improvements and extensions: The framework can be extended toward unsupervised settings by optimizing the rate reduction objective over both representations and class membership.This follows the complementary problem of learning membership with the representation fixed.
Further improvements and extensions: The paper mainly considers data embedded as submanifolds in real or complex vector spaces, leaving non-Euclidean and dynamically structured data as open extensions.Examples include graphs, meshes, reinforcement learning, and optimal control.

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

For a fixed class partition, maximal coding rate reduction favors representations that separate classes while retaining diversity within each class, under rank and small-ϵ conditions.

Main result: Maximal coding rate reduction produces representations that are maximally discriminative between classes and diverse within classes.The result assumes the sum of class ranks is small relative to ambient dimension and ϵ is small.
Assumptions: The theorem assumes a fixed encoding of the partition, with diagonal membership matrices whose entries assign samples to classes.The partition matrices sum to the identity.
Assumptions: The theorem applies for arbitrary positive ϵ and n under the stated class-rank and ambient-dimension conditions.These parameters appear in the theorem’s setup before the structural conclusions.
Optimal representation: Between-class discriminability is characterized by pairwise orthogonality of the optimal class-specific representations.For distinct classes, the corresponding representation matrices have zero cross-product.
Optimal representation: Within-class diversity requires each optimal class representation to attain its specified rank, with singular-value conditions given in the theorem.The theorem states the rank condition explicitly and continues with singular-value characterization.

A.5 Proof of Main Results

The proof establishes the structure of maximal rate-reduction representations through constrained optimization, orthogonality arguments, singular-value analysis, and efficient convolutional construction under shift invariance.

Optimization structure: The proof analyzes a constrained optimization problem using KKT conditions and properties of a twice-differentiable objective.The argument first establishes positivity and then restricts the form of optimal solutions.
Optimization structure: Every optimal solution has strictly positive entries, ruling out solutions with zero coordinates under the stated derivative assumptions.The contradiction uses first-order conditions and the equality constraint.
Optimization structure: Strict unimodality of the derivative limits an optimal solution to at most two distinct values.The proof rules out three ordered values by comparing derivative monotonicity on either side of its maximizer.
Optimization structure: For the nonconstant case, the optimizer has r−1 entries equal to xH and one entry equal to xL, with xH>xL>0.The proof derives this multiplicity pattern from second-order necessary conditions and the constraint.
Class separation: The optimal class representations are pairwise orthogonal because any nonorthogonal pair could be replaced by a feasible configuration with larger rate reduction.The contradiction compares the candidate rate reduction with the assumed optimum.
Within-class structure: The within-class optimization depends only on singular values, leading to a two-level singular-value structure for the optimal representation.The proof reduces the matrix problem to scalar optimization and derives the corresponding σH and σL pattern.
Shift-invariant construction: Under rigorous shift invariance, the derived linear operators are naturally multi-channel convolutions rather than imposed convolutional parameterizations.Their construction is efficiently implemented in the spectral domain using fast Fourier transforms.

D.2 Implementation Details

The implementation uses standard image datasets, supervised and self-supervised augmentations, and simulated data designed to test the MCR2 objective under structured and unstructured conditions.

Training setting: The supervised models use ResNet-18 with four residual blocks of widths 64, 128, 256, and 512.Training runs for 500 epochs with stage-wise learning-rate decay every 200 epochs.
Augmentation: Supervised augmentation applies random cropping and random horizontal flipping.The supplied implementation details specify these transformations for the supervised setting.
Datasets: Experiments use CIFAR10, CIFAR100, and STL10 from the default PyTorch datasets.These datasets support the reported supervised and self-supervised settings.
Augmentation: Self-supervised CIFAR augmentations include resized cropping, horizontal flipping, color jitter, grayscale conversion, and tensor conversion.The listed probabilities and crop size are given in the augmentation pseudocode.
Augmentation: STL10 self-supervised augmentation additionally uses Gaussian blur and 96-pixel resized crops.Its pseudocode also includes horizontal flipping, color jitter, grayscale conversion, and tensor conversion.
MCR2 evaluation: Table 4 evaluates R, Rc, and ΔR with output dimensions 512, 256, and 128 on batches of 1,000 samples across 10 randomly assigned classes.It compares random Gaussian data with data sampled from orthogonal or nonorthogonal class subspaces.
Baseline: The CE baseline uses ResNet-18 on CIFAR10 with SGD, learning rate 0.1, momentum 0.9, weight decay 5e-4, and 400 training epochs.The learning rate decays every 150 epochs by a factor of 10.

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

MCR2 learns representations that are more diverse, higher-dimensional, and more class-discriminative than cross-entropy representations, while principal images summarize varied within-class modes.

MCR2 representations are much more diverse than cross-entropy representations, with roughly a dozen dimensions per class and nearly 120 overall dimensions versus slightly over 10 for entropy training.The MCR2 output dimension is 128.
MCR2 features from different classes are almost orthogonal, indicating stronger separation among learned class representations.
Within each class, images associated with the same singular-vector component share shapes, textures, patterns, and styles, while different components capture distinct modes.
For each CIFAR10 class, the ten singular-vector-selected principal images are more diverse and representative than randomly selected images, providing a dataset summary.

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

The supervised experiments examine MCR2 across architectures, hyperparameters, classification components, and corrupted-label settings, finding broad robustness across these evaluations.

Larger mini-batch sizes improve MCR2 performance across the evaluated supervised configurations and architectures.The experiments include ResNet, VGG, and ResNext architectures.
Nearest-subspace classification works across a wide range of component counts r_j.
Changing the precision parameter to ϵ2 = 0.75 or 1.0 can produce slightly improved performance over the reported main-body results.
On corrupted-label classification, MCR2 achieves significantly better performance than OLE and LargeMargin using the same network, and outperforms ITLM without noise-ratio-dependent hyperparameters.

D.5 Learning from Gaussian noise corrupted data.

With Gaussian noise added to input images, MCR2 classification slightly trails cross-entropy overall, but the two methods perform comparably at small noise levels.

The experiment evaluates Gaussian noise with standard deviations σ ∈ {0.04, 0.06, 0.08, 0.09, 0.1}.
MCR2 classification slightly lags cross-entropy under Gaussian input corruption, while their performances are comparable when the noise level is small.The comparison uses the same ResNet-18 architecture.

D.6.1 Self-supervised Learning of Invariant Features

MCR2-CTRL learns invariant features by treating augmentations of each sample as a self-supervised class and controlling expansion–compression dynamics. It improves clustering over direct rate-reduction optimization, although self-supervised representations remain suboptimal relative to supervised ones.

Self-supervised Learning of Invariant Features: MCR2-CTRL labels augmented views of each sample as one class and trains the feature mapping using the supervised MCR2 procedure.The method uses NMI, ACC, and ARI for clustering evaluation.
Self-supervised Learning of Invariant Features: Directly optimizing ΔR achieves 0.570 clustering accuracy on CIFAR10, the second-best result among the compared methods.
Self-supervised Learning of Invariant Features: Without class labels, direct ΔR optimization expands the overall coding rate quickly and saturates the MCR2 loss at a local maximum.
Self-supervised Learning of Invariant Features: Controlling expansion and compression changes the dynamics so features compress first and then gradually expand.With γ1 = γ2 = k, this behavior corresponds to the controlled MCR2-CTRL process.
Self-supervised Learning of Invariant Features: Self-supervised representations remain far from optimal compared with supervised representations initialized using correct class information, leaving better optimization strategies open.
Self-supervised Learning of Invariant Features: MCR2-CTRL achieves better clustering performance than MCR2 on CIFAR10, as measured by NMI, ACC, and ARI.

D.6.2 Clustering Metrics and More Results

This section defines clustering metrics and reports additional self-supervised experiments, alongside implementation and visualization context for ReduNet. It also notes that the ReduNet experiments use minimally adequate rather than performance-optimized hyperparameter choices.

Clustering Metrics: NMI, ACC, and ARI are introduced as clustering evaluation metrics for comparing predicted and ground-truth partitions.NMI measures partition agreement; ACC uses one-to-one cluster-to-label mappings; ARI is defined from cluster intersections.
More Results: Additional MCR2-CTRL experiments on STL10 find that varying hyperparameters has only a small effect on performance.The authors suggest that further gains may require improved control of optimization dynamics or strategies.
Implementation Scope: The ReduNet experiments use a simple design without particular optimization of channels, kernel sizes, normalization, or learning rate for performance or scalability.These choices are described as convenient and minimally adequate for verifying the concept.
Additional Experiments: ReduNet’s additional experiments include rotated and cyclically translated MNIST visualizations, with further results on invariant learning and Gaussian mixtures.The visualizations are presented in Figures 21 and 22, while the invariant and Gaussian-mixture experiments are reported in later subsections.

E.2 Additional Experiments on Learning Rotational Invariance on MNIST

The rotational-invariance experiments on MNIST examine how channel count affects ReduNet. Increasing the number of channels improves invariance training accuracy, while heatmaps and loss curves provide complementary diagnostics.

Effect of Channel Size: Increasing the channel size from 5 to 20 increases rotational-invariance training accuracy on MNIST.The experiment uses the same parameters as Figure 16(b), whose channel size is 20.
Effect of Channel Size: Cosine-similarity heatmaps visualize shifted learned features for different channel sizes in the rotational-invariance task.Figure 23 reports these heatmaps for the RI-MNIST dataset.
Losses: Training and test losses are reported for the rotationally invariant ReduNet on RI-MNIST.These curves are shown in Figure 24.

E.3 Additional Experiments on Learning 2D Translation Invariance on MNIST

The translation-invariance experiments on MNIST vary channel count in a 2D ReduNet. Larger channel sizes improve both invariance training and test accuracy, with feature-similarity heatmaps and loss curves supplying additional views.

Effect of Channel Size: Increasing the channel size from 5 to 75 increases both translation-invariance training accuracy and test accuracy on MNIST.The experiment uses the same parameters as Figure 16(f), whose channel size is 75.
Effect of Channel Size: Cosine-similarity heatmaps visualize shifted learned features for different channel sizes in the translation-invariance task.Figure 25 reports these heatmaps for the TI-MNIST dataset.
Losses: Training and test losses are reported for the translation-invariant ReduNet on TI-MNIST.These curves are shown in Figure 26.

E.4 Additional Experiments on Learning Mixture of Gaussians in S1 and S2

Additional Gaussian-mixture experiments examine ReduNet on S1 and S2 and on S1 with more than two classes. The results show orthogonal-subspace mappings and continued promotion of between-class discriminativeness, with a correlated-cluster merging behavior in one case.

S1 and S2: ReduNet maps data points from different Gaussian-mixture classes to orthogonal subspaces in additional S1 and S2 experiments.This behavior is reported for the experiments summarized in Figure 27.
More Than Two Classes: For more than two classes on S1, MCR2 still promotes between-class discriminativeness even though Theorem 1 no longer applies.The experiments use η = 0.5, ϵ = 0.1, and iterations L = 2,500 or L = 4,000 in the two Figure 28 cases.
More Than Two Classes: In one more-than-two-class case, ReduNet merges two linearly correlated clusters, consistent with rate reduction grouping data as linear subspaces.The stated behavior is interpreted through the objective’s linear-subspace grouping tendency.

E.5 Additional Experimental Results of ReduNet and Scattering Transform

Additional experiments compare ReduNet constructions using scattering transforms with random filters and examine translation-equivariant representations. Scattering-based lifting outperforms random filters, while translated test images retrieve training representations with matching translations.

Objective comparison: 48.65 versus 46.14: ResNet-18 trained with MCR2 reaches a higher rate reduction than a 4000-layer ReduNet constructed iteratively on CIFAR10.Both models use all 50,000 CIFAR10 training samples, but the ReduNet uses scattering features followed by random projection.
Scattering versus random filters: Scattering-transform lifting outperforms random-filter lifting across all evaluated MNIST configurations.The comparisons vary scattering scales and angles while matching resulting feature dimensions and evaluate all 10,000 MNIST test samples.
Equivariance: The equivariance experiment applies 16 random 7 × 7 Gaussian kernels to one-channel MNIST inputs before constructing a 30-layer ReduNet.The setup uses 500 training samples, precision ϵ2 = 0.1, step size η = 0.5, and λ = 500.
Equivariance: Translation-invariant ReduNet retrieves training samples with matching translations among the top-9 cosine-similarity neighbors for shifted MNIST test images.Each image is augmented by shifts of 7 pixels in the canonical directions, producing nine versions per original image.