Generalization error bounds for iterative recovery algorithms unfolded as neural networks

Information and Inference A Journal of the IMA, vol. 12, pp. 2267–2299

Abstract

Abstract Motivated by the learned iterative soft thresholding algorithm (LISTA), we introduce a general class of neural networks suitable for sparse reconstruction from few linear measurements. By allowing a wide range of degrees of weight-sharing between the flayers, we enable a unified analysis for very different neural network types, ranging from recurrent ones to networks more similar to standard feedforward neural networks. Based on training samples, via empirical risk minimization, we aim at learning the optimal network parameters and thereby the optimal network that reconstructs signals from their low-dimensional linear measurements. We derive generalization bounds by analyzing the Rademacher complexity of hypothesis classes consisting of such deep networks, that also take into account the thresholding parameters. We obtain estimates of the sample complexity that essentially depend only linearly on the number of parameters and on the depth. We apply our main result to obtain specific generalization bounds for several practical examples, including different algorithms for (implicit) dictionary learning, and convolutional neural networks.

Authors 3

1. Ekkehard Schnoor corresponding Aachen Chair for Mathematics of Information Processing

   RWTH Aachen University

   Affiliation as printed

   Chair for Mathematics of Information Processing , RWTH Aachen University , Germany

2. Arash Behboodi Aachen Institute for Theoretical Information Technology

   RWTH Aachen University

   Affiliation as printed

   Institute for Theoretical Information Technology , RWTH Aachen University , Germany

3. Holger Rauhut Aachen Chair for Mathematics of Information Processing

   RWTH Aachen University

   Affiliation as printed

   Chair for Mathematics of Information Processing , RWTH Aachen University , Germany