Recovery and Generalization in Over-Realized Dictionary Learning
arXiv:2006.06179
Abstract
In over two decades of research, the field of dictionary learning has gathered a large collection of successful applications, and theoretical guarantees for model recovery are known only whenever optimization is carried out in the same model class as that of the underlying dictionary. This work characterizes the surprising phenomenon that dictionary recovery can be facilitated by searching over the space of larger over-realized models. This observation is general and independent of the specific dictionary learning algorithm used. We thoroughly demonstrate this observation in practice and provide an analysis of this phenomenon by tying recovery measures to generalization bounds. In particular, we show that model recovery can be upper-bounded by the empirical risk, a model-dependent quantity and the generalization gap, reflecting our empirical findings. We further show that an efficient and provably correct distillation approach can be employed to recover the correct atoms from the over-realized model. As a result, our meta-algorithm provides dictionary estimates with consistently better recovery of the ground-truth model.
References in corpus (11)
- Reconciling modern machine learning practice and the bias-variance trade-off
- The generalization error of random features regression: Precise asymptotics and double descent curve
- When Are Nonconvex Problems Not Scary?
- Simple, Efficient, and Neural Algorithms for Sparse Coding
- Rethinking Bias-Variance Trade-off for Generalization of Neural Networks
- On the Identifiability of Overcomplete Dictionaries via the Minimisation Principle Underlying K-SVD
- More Algorithms for Provable Dictionary Learning
- Minimax Lower Bounds on Dictionary Learning for Tensor Data
- Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates
- Provable benefits of representation learning
- Empirical Study of the Benefits of Overparameterization in Learning Latent Variable Models