Institutional Repository
Technical University of Crete
EN  |  EL



My Space

The generalization error of dictionary learning with moreau envelopes

Georgogiannis Alexandros

Full record

Year 2018
Type of Item Conference Full Paper
Bibliographic Citation A. Georgogiannis, "The generalization error of dictionary learning with moreau envelopes," in 35th International Conference on Machine Learning, 2018, pp. 2764-2787.
Appears in Collections


This is a theoretical study on the sample complexity of dictionary learning with general type of reconstruction losses. 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 mina∈Rd Φ(x - Da) + g(a) with function g being either an indicator function or a sparsity promoting regularizer. Here is considered the case where Φ(x) = inf z∈Rm ||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 regarding 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( p log n/n).