any higher sparsity level, this is not an essential restriction in this direction.
Statement
any higher sparsity level, this is not an essential restriction in this direction. In all results, we assume that all networks have the commonly used ReLU activation function given by ReLU(x) = max(0, x) and use specific properties of it. Specifically, we show that no ReLU -neural network with only one hidden layer can recover all 1-sparse vectors in the setup of interest, regardless of the size of the network. We also show that there exist relu-networks with two hidden layers that can perform approximate recovery with an arbitrary precision. Moreover, we show that the previously developed tools can be applied to show that exact reconstruction of s-sparse vectors is possible with ⌈log2 s + 2⌉ layers. However, in this case of exact recovery, it is unknown whether the shown number of layers is optimal. 2. Main Results The main results of this work are the following two theorems. Theorem 2.1 states that a ReLU network with one hidden layer cannot recover all s-sparse vectors from any m ≪ n linear measurements, not even approximately and for 1-sparse vectors. In strong contrast, Theorem 2.2 states that for a ReLU network with two hidden layers, recovery of all s-sparse vectors is possible to an arbitrary precision ǫ > 0 under weak assumptions on the matrix A. Theorem 2.1 (Impossibility result for one hidden layer). Let A \in Rm\timesn , m \leq n, and f : Rm \to Rn be a function described by a (possibly biased) neural network with one hidden layer, ReLU activation function, and arbitrary width. Then, r kx − f (Ax)k2 m sup \geq 1− . x\inΣ1 \{0} kxk2 n Note that in the case of underdetermined recovery problems, arguably the case of particular interest, m ≪ n such that the lower bound for the relative error is close to 1. Theorem 2.2 (Arbitrary precision recovery with two hidden layers). Let s \geq 1 and A \in Rm\timesn be a matrix for which Ax 6= 0 for all 2s-sparse x \in Rn . Let ǫ \in (0, 1). There exists a function f : Rm \to Rn , represented by an unbiased ReLU network with two hidden layers such that for all s-s
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.