Dimensionality-dependent generalization bounds for k-dimensional coding schemes

DOI10.1162/NECO_A_00872MaRDI QIDQ5380581zbMATH OpenOpenAlexWikidataFDO

Authors Tongliang Liu, Dacheng Tao, Dong Xu

Publication date 5 June 2019

Published in Neural Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.00238

Mathematics Subject Classification ID

Computational aspects of data analysis and big data (68T09)

Abstract: 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 $mathcalOleft(left(mkln(mkn)/night{)}^{lambd{a}_n}ight)$, 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, $lambd{a}_n>0.5$ when $n$ is finite and $lambd{a}_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.

Recommendations

• Generalization Bounds for K-Dimensional Coding Schemes in Hilbert Spaces
• Learning finite-dimensional coding schemes with nonlinear reconstruction maps
• The sample complexity of dictionary learning
• Lower bounds for sparse coding
• Learning Bounds for Kernel Regression Using Effective Data Dimensionality

Cites work

• scientific article; zbMATH DE number 3469876 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 1391397 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• $K$-Dimensional Coding Schemes in Hilbert Spaces
• 10.1162/153244302760200713
• 10.1162/153244303321897690
• A Hebbian/Anti-Hebbian Neural Network for Linear Subspace Learning: A Derivation from Multidimensional Scaling of Streaming Data
• A central limit theorem for k-means clustering
• A local search approximation algorithm for \(k\)-means clustering
• Adaptive Relevance Matrices in Learning Vector Quantization
• Atomic Decomposition by Basis Pursuit
• Concentration inequalities. A nonasymptotic theory of independence
• Distance Learning in Discriminative Vector Quantization
• Fast rates for empirical vector quantization
• Improved Minimax Bounds on the Test and Training Distortion of Empirically Designed Vector Quantizers
• Improved sparse coding under the influence of perceptual attention
• Individual Convergence Rates in Empirical Vector Quantizer Design
• Learning the parts of objects by non-negative matrix factorization
• Manifold Regularized Discriminative Nonnegative Matrix Factorization With Fast Gradient Descent
• NeNMF: An Optimal Gradient Method for Nonnegative Matrix Factorization
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis
• On the Performance of Clustering in Hilbert Spaces
• On the mathematical foundations of learning
• On the training distortion of vector quantizers
• Probability Inequalities for Sums of Bounded Random Variables
• Probability inequalities for empirical processes and a law of the iterated logarithm
• Rates of convergence in the source coding theorem, in empirical quantizer design, and in universal lossy source coding
• Sample Complexity of Dictionary Learning and Other Matrix Factorizations
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• Sharper bounds for Gaussian and empirical processes
• Sparse coding on the spot: spontaneous retinal waves suffice for orientation selectivity
• The benefit of multitask representation learning
• The minimax distortion redundancy in empirical quantizer design
• The sample complexity of dictionary learning
• Unsupervised Spike Detection and Sorting with Wavelets and Superparamagnetic Clustering

Cited in

(5)

• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Generalization Bounds for K-Dimensional Coding Schemes in Hilbert Spaces
• Learning finite-dimensional coding schemes with nonlinear reconstruction maps
• $K$-Dimensional Coding Schemes in Hilbert Spaces
• Strong optimality of the normalized ML models as universal codes and information in data

Describes a project that uses

Uses Software

• PDCO
• NeNMF
• Graclus

This page was built for publication: Dimensionality-dependent generalization bounds for \(k\)-dimensional coding schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5380581)