On the Sample Complexity of Predictive Sparse Coding

Details On the Sample Complexity of Predictive Sparse Coding On the Sample Complexity of Predictive Sparse Coding

2012-02-18

arxiv.org/abs/1202.4050v1

Computer Science

Learning

Scientific paper

Predictive sparse coding algorithms recently have demonstrated impressive performance on a variety of supervised tasks, but they lack a learning theoretic analysis. We establish the first generalization bounds for predictive sparse coding. In the overcomplete dictionary learning setting, where the dictionary size k exceeds the dimensionality d of the data, we present an estimation error bound that is roughly O(sqrt(dk/m) + sqrt(s)/({\mu}m)). In the infinite-dimensional setting, we show a dimension-free bound that is roughly O(k sqrt(s)/({\mu} m)). The quantity {\mu} is a measure of the incoherence of the dictionary and s is the sparsity level. Both bounds are data-dependent, explicitly taking into account certain incoherence properties of the learned dictionary and the sparsity level of the codes learned on actual data.

Affiliated with

Also associated with

No associations

Rating

On the Sample Complexity of Predictive Sparse Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Sample Complexity of Predictive Sparse Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Sample Complexity of Predictive Sparse Coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32988