# Dimensionality-Dependent Generalization Bounds for k-Dimensional Coding Schemes

arXiv: https://arxiv.org/abs/1601.00238 · HTML: https://mlsanity.com/paper/1601.00238/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2016.

## Built on by (most cited first, 3 of 3)

- [Reframing Neural Networks: Deep Structure in Overcomplete Representations](https://mlsanity.com/paper/2103.05804/) (2021)
- [Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming](https://mlsanity.com/paper/2401.00664/) (2024)
- [Late Fusion Multi-view Clustering via Global and Local Alignment Maximization](https://mlsanity.com/paper/2208.01198/) (2022)

## Abstract (arXiv)

The k-dimensional coding schemes refer to a collection of methods that attempt to represent data using a set of representative k-dimensional vectors, and include non-negative matrix factorization, dictionary learning, sparse coding, k-means clustering and vector quantization as special cases. Previous generalization bounds for the reconstruction error of the k-dimensional coding schemes are mainly dimensionality independent. A major advantage of these bounds is that they can be used to analyze the generalization error when data is mapped into an infinite- or high-dimensional feature space. However, many applications use finite-dimensional data features. Can we obtain dimensionality-dependent generalization bounds for k-dimensional coding schemes that are tighter than dimensionality-independent bounds when data is in a finite-dimensional feature space? The answer is positive. In this paper, we address this problem and derive a dimensionality-dependent generalization bound for k-dimensional coding schemes by bounding the covering number of the loss function class induced by the reconstruction error. The bound is of order Oleft(left(mkln(mkn)/nright)λnright), where m is the dimension of features, k is the number of the columns in the linear implementation of coding schemes, n is the size of sample, λn>0.5 when n is finite and λn=0.5 when n is infinite. We show that our bound can be tighter than previous results, because it avoids inducing the worst-case upper bound on k of the loss function and converges faster. The proposed generalization bound is also applied to some specific coding schemes to demonstrate that the dimensionality-dependent bound is an indispensable complement to these dimensionality-independent generalization bounds.