Generalization Bounds for Rank-sparse Neural Networks

AI summary

Authors: Antoine Ledent (Singapore Management University, School of Computing and Information Systems), Rodrigo Alves (Czech Technical University in Prague, Department of Applied Mathematics), Yunwen Lei (The University of Hong Kong, Department of Mathematics) arXiv: 2510.21945v3 [cs.LG], published 2025-10-24 (v3 dated 25 Nov 2025) | License: CC BY 4.0

Overview

Research area: Deep learning theory, specifically generalization bounds and the capacity of neural network function classes.

Technical level: Advanced. The paper relies on Schatten quasi-norms, covering numbers, Rademacher complexity, singular value decomposition and the parametric interpolation technique borrowed from matrix completion theory.

Scope: The paper derives high-probability generalization bounds for linear, fully connected and convolutional networks that exploit the approximate low-rank structure of trained weight matrices, interpolating between norm-based and parameter-counting complexity estimates.

What This Paper Is About

A large body of work has observed that neural networks trained with gradient-based methods develop a "bottleneck rank": for larger depths, activations and weight matrices become approximately low rank, converging to the minimum rank needed to represent the training data. The authors ask what this phenomenon implies for generalization, and prove bounds whose sample complexity depends on the Schatten p quasi-norms of the weight matrices rather than on their full parameter count. The goal is to show that when the weights really are rank-sparse, the capacity of the function class — and therefore the amount of data needed to generalize — is much smaller than a naive parameter-counting bound suggests.

Key Contributions

1. New generalization bounds for linear networks. The authors prove bounds for multi-class linear classification that incorporate the implicit low-rank effect of depth through the Schatten p quasi-norm of the weight matrix. As p approaches 0, the bound gives a sample complexity of O~([C + d] · rank(A)), which the authors describe as a new characterization of multi-class linear classification with low-rank dependencies between classes.

2. Generalization bounds for fully connected networks via Schatten quasi-norms. Theorem 3.2 gives a bound valid simultaneously over every sequence of Schatten indices p_ℓ in [0, 2], tuned after training to balance a norm-based factor against the low-rank term ‖A_ℓ − M_ℓ‖^p / ‖A_ℓ‖^p, where the M_ℓ are reference matrices chosen in advance.

3. Extension via loss function augmentation. Theorem 3.3 replaces the norm-based factor B ∏ρ_i‖A_i‖ with a quantity involving B_{ℓ−1,A}, the maximum norm of an activation at layer ℓ−1 over the training set, which the authors say often yields substantial numerical improvements.

4. A new application of the parametric interpolation proof technique. The authors state that to their knowledge this technique had previously only been used in matrix completion, a substantially different setting.

Main Findings

• Sample complexity scaling with rank, width and depth: For small p, the bounds exhibit a sample complexity of O~(W r L²), where W and L are the width and depth of the network and r is the rank of the weight matrices. As p increases, the bound behaves more like a norm-based bound instead.

• Recovery of a parametric complexity for low-rank weights: For a fixed-width W̄ network, the sample complexity is O~(W̄ L² r̄) rather than O~(W̄² L²), the latter being what a pure parameter-counting bound would give. Each weight matrix A_ℓ in R^{W̄×W̄} contributes O~(W̄ r̄) "parameters" instead of the full W̄².

• The p_ℓ = 0 case: Theorem 3.3 yields a sample complexity of O~(L³ + L Σ_ℓ [w_ℓ + w_{ℓ−1}] rank(A_ℓ)). The authors note the additive L³ term can be removed with a simpler argument dedicated to the p_ℓ = 0 situation (Theorem E.8).

• Linear-network bound removes a factor of L³. Under the simplifying assumptions L ≫ 1, Lipschitz constant and B in O(1), and ‖B_ℓ‖ = 1 for all ℓ, Theorem 3.1 scales as O~(Σ_ℓ ‖B_ℓ‖_Fr² [C + d] / L) in sample complexity, whereas the known result (1.2) from [3] scales as O~(L³ min(C, d) Σ_ℓ ‖B_ℓ‖_Fr² / L). Taking L → ∞, the authors' bound behaves more and more like a parameter-counting bound since Σ‖B_ℓ‖_Fr²/L → rank(A).

• Tradeoff in tuning p_ℓ. The bound does not exactly coincide with the norm-based result (1.3) at p = 2, because a parametric dependence on the input dimension persists through the term [C + d]^{2/(p+2)}. The authors describe this as an interpolation that maintains a slight bias toward parameter counting, but is not uniformly inferior to either regime.

• Illustrative one-layer example. For an idealized one-layer case with weights restricted to {1, −1}, the norm-based bound (1.3) gives O~(C d) sample complexity, matching parameter counting; Theorem 3.2 also yields O~(C d).

• Comparison with the closest prior low-rank bound [64]. That bound contains an explicit exponential depth dependence through C₁^L, where C₁ is described as "rather large" (the authors note it accumulates factors of Talagrand's majorizing measure theorem and generic chaining, suggesting C₁ ≥ 11), and its product of spectral norms carries exponent 1, versus the tunable exponent 2p_ℓ/(p_ℓ + 2) in this work. The authors acknowledge [64] has far fewer polylogarithmic factors and a shorter proof.

• Empirical evaluation reported in the appendix. The authors state that the behavior of their bounds is evaluated experimentally on MNIST and CIFAR-10 for both DNNs and CNNs in Appendix D; the numerical results themselves are not reproduced in the main text provided.

Methodology in Plain English

The paper's strategy is to control the complexity of each layer using a quantity that smoothly interpolates between two well-known extremes.

1. Start from a known equivalence. Theorem 1.1 (attributed to [24]) states that minimizing weight decay over a product of factor matrices B_L B_{L−1} … B_1 is equivalent to minimizing the Schatten 2/L quasi-norm of the product matrix A. Since 2/L approaches 0 as depth grows, weight decay implicitly pushes the network toward low-rank solutions.

2. Split the singular values with a threshold. To bound the size of the function class, the authors decompose each weight matrix M into two parts: a top part keeping singular values above a threshold τ, and a remainder. The top part has small rank, bounded using Markov's inequality from the Schatten p constraint. The remainder is small in spectral norm. This is the parametric interpolation step.

3. Bound covering numbers for each part. The low-rank component is handled with parametric (rank-and-norm) counting, and the residual is handled with a norm-based argument. Proposition 3.4 gives an L^∞ covering number for one layer that scales roughly as [m + d][MB/ε]^{2p/(p+2)} log(mdN M/ε).

4. Chain the covers across layers. The per-layer covering bounds are combined layer by layer to control Rademacher complexity or covering numbers of the full network, producing the final generalization gap bounds.

5. Make p tunable. Because the final bounds hold simultaneously for every choice of the indices p_ℓ in [0, 2], a practitioner can pick the values that best fit the observed network after training — a small p favors the low-rank interpretation, a larger p favors the norm-based one.

6. Replace norm products with measured activations. In the loss-augmentation extension, the product of spectral norms up to layer ℓ is replaced by the empirically measured maximum activation norm at that layer, which the authors note is usually much smaller.

Why This Matters

Impact on research. Norm-based and parameter-counting bounds have long been criticized as vacuous or as ignoring the structure that training actually induces. This paper connects the empirical observation of low-rank ("bottleneck rank") representations, established across DNNs, CNNs and LLMs, to a concrete reduction in measured sample complexity: from O~(W̄²L²) down to O~(W̄ L² r̄) when weights are rank-r̄. It also imports the parametric interpolation technique into supervised deep learning for the first time, from a matrix completion setting with a different observation model (network outputs A x_i rather than matrix entries A_{i,j}).

Applications the underlying insight touches (drawn from the phenomena the paper discusses, not claims of deployed systems):

• Network compression and pruning. The lottery ticket hypothesis is cited as a phenomenon that small perturbation or sparse-update norm terms can partly explain; rank-sparse weight matrices are directly relevant to low-rank compression.
• Low-rank factorization of large models. The paper notes the low-rank phenomenon has been demonstrated experimentally in DNNs, CNNs and even LLMs, making rank-aware capacity estimates relevant to large-scale model design.
• Understanding deep linear networks. Weight decay on linear networks is exactly equivalent to a Schatten quasi-norm constraint, so the linear-network results apply directly to this analytically tractable class, which is used as a theoretical stand-in for deep nonlinear models.
• Multi-class and structured prediction. The linear results are framed as a multi-class linear classification analysis with low-rank dependencies between classes, with related extensions noted in the multi-label, structured-output and ranking literature.

Industry relevance. The results are theoretical and the authors do not report deployment. Their practical value lies in giving a principled reason why overparametrized models can still generalize, and why explicit or implicit low-rank structure (weight decay, gradient descent at large depth) should be expected to reduce the data requirements of a model. The appendices include an experimental evaluation on MNIST and CIFAR-10, which is the paper's closest link to practice.

Future Directions

• Improving input-dimension dependence. The authors note that the dependency on the input space dimension d in Theorem 3.1 may be improvable if the input data lies on a low-dimensional subspace, but state this would require significant modifications to the proofs and leave it to future work.

• Reconciling the p = 2 limit with norm-based bounds. The bound retains a parametric dependence on the input dimension through [C + d]^{2/(p+2)}, so it does not exactly recover the norm-based result (1.3) when p is set to 2. Closing this gap is an open question.

• Reducing polylogarithmic and additive overheads. The authors note their bounds carry more polylogarithmic factors than [64], and that the additive L³ term in the p_ℓ = 0 case requires a separate argument (Theorem E.8) to remove — suggesting room for tighter analyses.

• Broadening the application of parametric interpolation. Since this is, to the authors' knowledge, the first use of the technique outside matrix completion, the method may be adaptable to other learning settings beyond the linear, fully connected and convolutional cases covered here.

Target Audience

This paper is aimed at machine learning theorists and graduate researchers working on generalization bounds, neural network capacity, or the theory of implicit regularization and low-rank bias in gradient-based training. Readers interested in the connection between weight decay and Schatten quasi-norm regularization, or in how rank-based complexity compares with classical norm-based and VC-dimension-based bounds, will find the most value here. Practitioners working on model compression or low-rank architectures may find the high-level message useful, but the derivations themselves assume comfort with covering numbers, Rademacher complexity and matrix analysis.

Authors’ abstract

It has been recently observed in much of the literature that neural networks exhibit a bottleneck rank property: for larger depths, the activation and weights of neural networks trained with gradient-based methods tend to be of approximately low rank. In fact, the rank of the activations of each layer converges to a fixed value referred to as the ``bottleneck rank'', which is the minimum rank required to represent the training data. This perspective is in line with the observation that regularizing linear networks (without activations) with weight decay is equivalent to minimizing the Schatten $p$ quasi norm of the neural network. In this paper we investigate the implications of this phenomenon for generalization. More specifically, we prove generalization bounds for neural networks which exploit the approximate low rank structure of the weight matrices if present. The final results rely on the Schatten $p$ quasi norms of the weight matrices: for small $p$, the bounds exhibit a sample complexity $ \widetilde{O}(WrL^2)$ where $W$ and $L$ are the width and depth of the neural network respectively and where $r$ is the rank of the weight matrices. As $p$ increases, the bound behaves more like a norm-based bound instead.