The Generalization Error of Dictionary Learning with Moreau Envelopes

Abstract

This is a theoretical study on the sample complexity of dictionary learning with a general type of reconstruction loss. The goal is to estimate a m d matrix D of unit-norm columns when the only available information is a set of training samples. Points x in R^m are subsequently approximated by the linear combination Da after solving the problem _a R^d (x - Da) + g(a); function g:R^d [0,+) is either an indicator function or a sparsity promoting regularizer. Here is considered the case where (x) = _z R^m ||x-z||_2^2 + h(||z||_2) and h is an even and univariate function on the real line. Connections are drawn between and the Moreau envelope of h. A new sample complexity result concerning the k-sparse dictionary problem removes the spurious condition on the coherence of D appearing in previous works. Finally, comments are made on the approximation error of certain families of losses. The derived generalization bounds are of order O( n /n) and valid without any further restrictions on the set of dictionaries with unit-norm columns.

Tasks

Reproductions