Robust and Resource Efficient Identification of Two Hidden Layer Neural Networks

We address the structure identification and the uniform approximation of two fully nonlinear layer neural networks of the type f(x)=1T h(BT g(AT x)) on mathbb Rd from a small number of query samples. We approach the problem by sampling actively finite difference approximations to Hessians of the network. Gathering several approximate Hessians allows reliably to approximate the matrix subspace mathcal W spanned by symmetric tensors a1 otimes a1 ,dots,am0otimes am0 formed by weights of the first layer together with the entangled symmetric tensors v1 otimes v1 ,dots,vm1otimes vm1, formed by suitable combinations of the weights of the first and second layer as vℓ=A G0 bℓ/|A G0 bℓ|2, ℓ ∈ [m1], for a diagonal matrix G0 depending on the activation functions of the first layer. The identification of the 1-rank symmetric tensors within mathcal W is then performed by the solution of a robust nonlinear program. We provide guarantees of stable recovery under a posteriori verifiable conditions. We further address the correct attribution of approximate weights to the first or second layer. By using a suitably adapted gradient descent iteration, it is possible then to estimate, up to intrinsic symmetries, the shifts of the activations functions of the first layer and compute exactly the matrix G0. Our method of identification of the weights of the network is fully constructive, with quantifiable sample complexity, and therefore contributes to dwindle the black-box nature of the network training phase. We corroborate our theoretical results by extensive numerical experiments.