Dimensionality-dependent generalization bounds for k-dimensional coding schemes

DOI10.1162/NECO_A_00872zbMATH Open1474.68315arXiv1601.00238OpenAlexW2223051473WikidataQ39621250 ScholiaQ39621250MaRDI QIDQ5380581FDOQ5380581

Authors: Tongliang Liu, Dacheng Tao, Dong Xu 

Publication date: 5 June 2019

Published in: Neural Computation (Search for Journal in Brave)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• $K$-Dimensional Coding Schemes in Hilbert Spaces
• Generalization Bounds for K-Dimensional Coding Schemes in Hilbert Spaces
• Strong optimality of the normalized ML models as universal codes and information in data
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem

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)