Research map / Learning theory and algorithms / Kernels and regression theory

Generalization Bounds for Rank-sparse Neural Networks

NeurIPS 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Empirical generalization measures · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves generalization bounds for linear, fully connected, and convolutional networks that exploit approximate low rank of weight matrices via Schatten p quasi-norms, using a parametric interpolation covering-number argument.

Problem

Generalization bounds for neural networks that do not capture the implicit low-rank (bottleneck rank) structure of trained weight matrices, with existing norm-based bounds being exponential in depth and parameter-counting bounds ignoring rank.

Approach

Interpolates between norm-based and parameter-counting regimes by bounding L-infinity/L2 covering numbers of each layer in terms of Schatten p quasi-norms (parametric interpolation: split weights into a low-rank part via a singular value threshold and a small-Frobenius remainder), giving sample complexity tied to weight rank and holding simultaneously over all p_l.

Key results

• For linear networks, as p goes to 0 the bound gives sample complexity roughly [C+d] rank(A) (up to polylog factors), removing the L^3 factor of prior norm-based bounds in the linear case.
• For fully connected networks with p_l=0, the sample complexity is O~(L^3 + L sum_l [w_l+w_{l-1}] rank(A_l)), versus parameter counting O~(W^2 L^2) for fixed width.
• The fixed-width sample complexity becomes O~(W L^2 r) rather than O~(W^2 L^2) under the low-rank assumption.

Surprising findings

• The bounds do not reduce exactly to the norm-based result at p=2 because of a residual parametric dependence on input dimension d, so they are not uniformly better than either regime.

Limitations

• Bounds are vacuous for large-scale networks without aggressive bound optimization.
• Requires weight matrices (not activations) to be approximately low rank, which may not hold for smaller architectures or layers.
• Explicit dependence on input dimension d remains, and the bounds are uniform convergence results with a slow 1/sqrt(N) rate.

Experimental setup

Datasets: MNIST CIFAR-10

Benchmarks: MNIST CIFAR-10

Metrics: generalization bound value (sample complexity)

Baselines: peeling-based Rademacher bounds covering number bound of Golowich et al. PAC-Bayes bound of Neyshabur et al. parameter counting bounds Gaussian complexity bound of Galanti et al.

Builds on: parametric interpolation (matrix completion) loss function augmentation norm-based covering number bounds bottleneck rank / neural rank collapse

Closest papers by meaning

• Koopman-based generalization bound: New aspect for full-rank weights (ICLR 2024 · similarity 0.91)
• Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.89)
• Generalization Bounds and Model Complexity for Kolmogorov–Arnold Networks (ICLR 2025 · similarity 0.89)
• Generalization Analysis of Deep Non-linear Matrix Completion (ICML 2024 · similarity 0.89)
• Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.88)
• Low Rank Gradients and Where to Find Them (NeurIPS 2025 · similarity 0.88)