Inverting Deep Generative models, One layer at a time

Introduction

Modern deep generative models are demonstrating excellent performance as signal priors, frequently outperforming the previous state of the art for various inverse problems including denoising, inpainting, reconstruction from Gaussian projections and phase retrieval (see e.g. and references therein). Consequently, there is substantial work on improving compressed sensing with generative adversarial network (GANs) . Similar ideas have been recently applied also for sparse PCA with a generative prior .

since several recent works leverage inversion as a key step in solving more general inverse problems, see e.g. . Specifically, Shah et al. provide theoretical guarantees on obtaining the optimal solution for (2) with projected gradient descent, provided one could solve (1) exactly. This work provides a provable algorithm to perform this projection step under some assumptions.

Our Contributions: For the realizable case we show that for a single layer solving (1) is equivalent to solving a linear program. For networks more than one layer, however, we show it is NP-hard to simply determine whether exact recovery exists. For a two-layer network we show that the pre-image in the latent space can be a non-convex set.

For realizable inputs and arbitrary depth we show that inversion is possible in polynomial time if the network layers have sufficient expansion and the weights are randomly selected. A similar result was established very recently for gradient descent . We instead propose inversion by layer-wise Gaussian elimination. Our result holds even if each layer is expanding by a constant factor while requires a logarithmic multiplicative expansion in each layer.

For noisy inputs and arbitrary depth we propose two algorithms that rely on iteratively solving linear programs to reconstruct each layer. We establish provable error bounds on the reconstruction error when the weights are random and have constant expansion. We also show empirically that our method matches and sometimes outperforms gradient descent for inversion, especially when the latent dimension becomes larger.

Setup

We use bold lower-case symbols for vectors, e.g. ${\boldsymbol{x}}$, and $x_{i}$ for its coordinates. We use upper-case symbols for denote matrices, e.g. $W$, where ${\boldsymbol{w}}_{i}$ is its $i$-th row vector. For a indexed set $I$, $W_{I,:}$ represents the submatrix of $W$ consisting of each $i$-th row of $W$ for any $i\in I$.

The central challenge is to determine the signs for the intermediate variables of the hidden layers. We refer to these sign patterns as "ReLU configurations" throughout the paper, indicating which neurons are ‘on’ and which are ‘off’.

Invertibility for ReLU Realizable Networks

In this section we study the realizable case, i.e., when we are given an observation vector ${\boldsymbol{x}}$ for which there exists ${\boldsymbol{z}}^{*}$ such that ${\boldsymbol{x}}=G({\boldsymbol{z}}^{*})$. In particular, we show that the problem is NP-hard for ReLU activations in general, but could be solved in polynomial time with some mild assumptions with high probability. We present our theoretical findings first and all proofs of the paper are presented later in the Appendix.

We start with the simplest one-layer case to find if $\min_{{\boldsymbol{z}}}\|{\boldsymbol{x}}-G({\boldsymbol{z}})\|_{p}=0,$ for any $p$-norm. Since the problem is non-convex, further assumptions of $W$ are required for gradient descent to work. When the problem is realizable, however, to find feasible ${\boldsymbol{z}}$ such that ${\boldsymbol{x}}=\phi({\boldsymbol{z}})\equiv\text{ReLU}(W{\boldsymbol{z}}+{\boldsymbol{b}})$, one could invert the function by solving a linear programming:

Its solution set is convex and forms a polytope, but possibly includes uncountable feasible points. Therefore, it becomes unclear how to continue the process of layer-wise inversion unless further assumptions are made. To demonstrate the challenges to generalize the result to deeper nets, we show that the solution set becomes non-convex, and to determine whether there exists any solution is NP-complete.

2 Challenges to Invert a Two or More Layered ReLU Network

As a warm-up, we first present the NP-hardness to recover a binary latent code for a two layer network, and then generalize it to the real-valued case.

We defer the proof to the Appendix, which is constructive and shows the 3SAT problem is reducible to the above two-layer binary code recovery problem. Meanwhile, when the ReLU configuration for each layer is given, the recovery problem becomes to solve a simple linear system. Therefore the problem lies in NP, and together we have NP-completeness. With similar procedure, we could also construct a 4-layer network with real input and prove the following statement:

The conclusion holds naturally for generative models with deeper architecture.

Meanwhile, although the preimage for a single layer is a polytope thus convex, it doesn’t continue to hold for more than one layers, see Example 1. Fortunately, we present next that some moderate conditions guarantee a polynomial time solution with high probability.

3 Inverting Expansive Random Network in Polynomial Time

In the previous section, we indicate that the per layer inversion can be achieved through linear programming (4). With Assumption 1 we will be able to prove that the solution is unique with high probability, and thus Theorem 3 holds for ReLU networks with arbitrary depth.

Inverting LeakyReLU Network: On the other hand, inversion of LeakyReLU layers are significantly easier for the realizable case. Unlike ReLU, LeakyReLU is a bijective map, i.e., each observation corresponds to a unique preimage:

Invertibility for Noisy ReLU Networks

Again we start with a single layer, i.e. we observe ${\boldsymbol{x}}=\phi({\boldsymbol{z}}^{*})+{\boldsymbol{e}}=\text{ReLU}(W{\boldsymbol{z}}^{*})+{\boldsymbol{e}}$. Depending on the distribution over the measurement noise ${\boldsymbol{e}}$, different norm in the objective $\|G({\boldsymbol{z}})-{\boldsymbol{x}}\|$ should be used, with corresponding error bound analysis. We first look at the case where the entries of ${\boldsymbol{e}}$ are uniformly bounded and the approximation of $\operatorname*{arg\,min}_{{\boldsymbol{z}}}\|\phi({\boldsymbol{z}})-{\boldsymbol{x}}\|_{\infty}$.

Note that for an error $\|{\boldsymbol{e}}\|_{\infty}\leq\epsilon$, the true prior ${\boldsymbol{z}}^{*}$ that produces the observation ${\boldsymbol{x}}=\phi({\boldsymbol{z}}^{*})+{\boldsymbol{e}}$ falls into the following constraints:

which is also equivalent to the set \{{\boldsymbol{z}}\big{|}\|\phi({\boldsymbol{z}})-{\boldsymbol{x}}\|_{\infty}\leq\epsilon\}. Therefore a natural way to approximate the prior is to use linear programming to solve the above constraints.

If $\epsilon$ is known, inversion is straightforward from constraints (6). However, suppose we don’t want to use a loose guess, we could start from a small estimation and gradually increase the tolerance until feasibility is achieved. A layer-wise inversion is formally presented in Algorithm 1For practical use, we introduce a factor $\alpha$ to gradually increase the error estimation. In our theorem, it assumed we expicitly set $\epsilon$ to invert the $i$-th layer as the error estimation $\|{\boldsymbol{e}}\|_{0}(1/c_{2})^{d-i}$..

A key assumption that possibly conveys the error bound from the output to the solution is the following assumption:

with high probability $1-\exp(-\Omega(k))$ for any ${\boldsymbol{x}}$, and $c_{\infty}$ is a constant. Recall that $W_{I,:}$ is the sub-rows of $W$ confined to $I$.

With this assumption, we are able to show the following theorem that bounds the recovery error.

We argue that the assumptions required could be satisfied by random weight matrices sampled from i.i.d Gaussian distribution, and present the following corollary.

For LeakyReLU, we could do at least as good as ReLU, since we could simply view all negative coordinates as inactive coordinates of ReLU, and each observation will produce a loose bound. On the other hand, if there are significant number of negative entries, we could also change the linear programming constraints of Algorithm 1 as follows:

with high probability $1-\exp(-\Omega(k))$ for any ${\boldsymbol{x}}$.

There is a significant volume of prior work on the RIP-1 condition. For instance, studies in showed that a (scaled) random sparse binary matrix with $m=O(s\log(k/s)/\epsilon^{2})$ rows is $(s,1+\epsilon)$-RIP-1 with high probability. In our case $s=k$ and $\epsilon$ could be arbitrarily large, therefore again we only require the expansion factor to be constant. Similar results with different weight matrices are also shown in .

3 Relaxation on the ReLU Configuration Estimation

Our previous methods critically depend on the correct estimation of the ReLU configurations. In both Algorithm 1 and 2, we require the ground truth of all intermediate layer outputs to have many coordinates with large magnitude so that they can be distinguished from noise. An incorrect estimate from an "off" configuration to an "on" condition will possibly cause primal infeasibility when solving the LP. Increasing $\epsilon$ ameliorates this problem but also increases the recovery error.

With this intuition, a natural workaround is to perform some relaxation to tolerate incorrectly estimated signs of the observations.

Here the ReLU configuration is no longer explicitly reflected in the constraints. Instead, we only include the upper bound for each inner product ${\boldsymbol{w}}_{i}^{\top}{\boldsymbol{z}}$, which is always valid whether the ReLU is on or off. The previous requirement for the lower bound ${\boldsymbol{w}}_{i}^{\top}{\boldsymbol{z}}\geq x_{i}-\epsilon$ is now relaxed and hidden in the objective part. When the value of $x_{i}$ is relatively large, the solver will produce a larger value of ${\boldsymbol{w}}_{i}^{\top}{\boldsymbol{z}}$ to achieve optimality. Since this value is also upper bounded by $x_{i}+\epsilon$, the optimal solution would be approaching to $x_{i}$ if possible. On the other hand, when the value of $x_{i}$ is close to 0, the objective dependence on ${\boldsymbol{w}}_{i}^{\top}{\boldsymbol{z}}$ is almost negligible.

Meanwhile, in the realizable case when $\exists{\boldsymbol{z}}^{*}$ such that $\text{ReLU}(W{\boldsymbol{z}}^{*})={\boldsymbol{x}}$, and $\epsilon=0$, it is easy to show that the solution set for (8) is exactly the preimage of $\text{ReLU}(W{\boldsymbol{z}})$. This also trivially holds for Algorithm 1 and 2.

Experiments

We validate our algorithms on synthetic data at various noise levels and verify Theorem 4 and 5 numerically. For our methods, we choose the scaling factor $\alpha=1.2$. With gradient descent, we use learning rate of $1$ and up to 1,000 iterations or until the gradient norm is no more than $10^{-9}$.

Model architecture: The architecture we choose in the simulation aligns with our theoretical findings. We choose a two layer network with constant expansion factor $5$: latent dimension $k=20$, hidden neurons of size $100$ and observation dimension $n=500$. The entries in the weight matrix are independently drawn from ${\mathcal{N}}(0,1/n_{i})$.

Recovery with Various Input Neurons: According to the theoretical result, one advantage of our proposals is the much smaller expansion requirement than gradient descent (constant vs $\log k$ factors). Therefore we conduct the experiments to verify this point. We follow the exact setting as ; we fix the hidden layer and output sizes as $250$ and $600$ and vary the input size $k$ to measure the empirical success rate of recovery influenced by the input size.

In Figure 2 we report the empirical success rate of recovery for our proposals and gradient descent. With exact setting as in , a run is considered successful when $\|{\boldsymbol{z}}^{*}-{\boldsymbol{z}}\|_{2}/\|{\boldsymbol{z}}^{*}\|_{2}\leq 10^{-3}$. We observe that when input width $k$ is small, both gradient descent and our methods grant $100\%$ success rate. However, as the input neurons grows, gradient descent drops to complete failure when $k\geq$60, while our algorithms continue to present 100% success rate until $k=109$. The performance of gradient descent is slightly worse than reported in since they have conducted $150$ number of measurements for each run while we only considered the measurement matrix as identity matrix.

2 Experiments on Generative Model for MNIST Dataset

To verify the practical contribution of our model, we conduct experiments on a real generative network with the MNIST dataset. We set a simple fully-connected architecture with latent dimension $k=20$, hidden neurons of size $n_{1}=60$ and output size $n=784$. The network has a single channel. We train the network using the original Generative Adversarial Network . We set $n_{1}$ to be small since the output usually only has around $70$ to $100$ non-zero pixels.

Similar to the simulation part, we compared our methods with gradient descent . Under this setting, we choose the learning rate to be $10^{-3}$ and number of iterations up to 10,000 (or until gradient norm is below $10^{-9}$).

We also compare the distribution of relative recovery error with respect to different input noise levels, as ploted in Figure 1(c)(d). From the figures, we observe that for this real network, our proposals still successfully recover the ground truth with good accuracy most of the time, while gradient descent usually gets stuck in local minimum. This explains why it produces defective image reconstructions as shown in 3.

Finally, we presented some sensing results when we mask part of the observations using PGD with our inverting procedure. As shown in Figure 4, our algorithm always show reliable recovery while gradient descent sometimes fails to output reasonable result. More experiments are presented in the Appendix.

Conclusion

References

Appendix A Methodology Details

In this section we present the detailed steps for our proposed methods.

We formally present the relaxed version based on (8):

We also propose the relaxed LP for LeakyReLU activation, with key step as follows:

Similarly when $\epsilon=0$ and $\exists{\boldsymbol{z}}_{0},\text{LeakyReLU}(W{\boldsymbol{z}}_{0})={\boldsymbol{x}}$, the solution to (A.1) is exactly ${\boldsymbol{z}}_{0}$.

Appendix B Theoretical Analysis

Warm-up: NP-hardness to Invert a Binary Two-Layer Network: We show that 3SAT is reducible to the inversion problem. We first review the MAX-3SAT problem: Given a 3-CNF formula (i.e. a formula in conjunctive normal form where each clause is limited to at most three literals), determine its satisfiability.

Now we design a network $G({\boldsymbol{z}})=W_{2}\text{ReLU}(W_{1}{\boldsymbol{z}}+{\boldsymbol{b}}_{1})$ with binary input vectors that could be reduced from 3SAT problem.

Now we design a real-valued network that could be reduced from 3SAT problem. Firstly, the network consists of $k$ input nodes ${\boldsymbol{z}}:=\{z_{1},z_{2},\cdots z_{k}\}$. Next, the connecting 2 layers map each $z_{i}$ to $v_{i}=\min\{\max\{z_{i},-1\},1\},i\in[k]$. Now, the third connecting layer ${\boldsymbol{u}}:=\{u_{1},\cdots u_{m+2}\}$ consists of $m+2$ nodes, where the first $m$ nodes indicate each clause: $u_{i},i\leq m$ will be connected to $3$ nodes among $z_{i},i\in[n]$, where the weight is $-1$ for a positive literal, and $1$ for a negative literal. Let $u_{m+1}=\sum_{i=1}^{n}\max\{z_{i},0\}$, and $u_{m+1}=\sum_{i=1}^{n}-\min\{z_{i},0\}$. The bias term on this third layer is ${\boldsymbol{b}}$ such that the first $m$ values are $-2$ and the last two values are 0. Finally, the last layer ${\boldsymbol{x}}$ is of 2 nodes, first one is the summation of the first $m$ nodes of $u_{i}$, and the second one is $u_{m+1}+u_{m+2}.$

We will set the output to be ${\boldsymbol{x}}=[0,n]$. Notice the first two layers make sure each value of $u_{i}$ is in the range of $.$ When the output of $x_{2}=n$, it means all values of $u_{i}$ must be $\pm 1$. Therefore we go back to the previous setting with binary input vectors and $x_{1}=0$ simply means that all $m$ clauses are satisfied. Therefore a 4 layered ReLU network could be polynomially reduced from 3SAT problem. ∎

Proof of Non-convexity. The following example demonstrate this property is no longer true for a two-layer case:

For $W_{1}=[,]$, $W_{2}=$, and observation $x=1$, the solution set for

Example 1 is very straightforward to show the non-convexity of the preimage. Notice point ${\boldsymbol{x}}_{1}=(-1,1)$ and ${\boldsymbol{x}}_{2}=(1,3)$ are in the solution set, but their convex combination $x_{3}=\frac{x_{1}+x_{2}}{2}=(0,2)$ is not a solution point with $G(x_{3})=2$.

B.2 Proof of Exact Recovery for the Realizable Case

The proof of Theorem 4 highly depends on the exact inversion for a single layer:

With Assumption 2, we are able to show the following theorem that bounds the recovery error.

Given a noisy observation ${\boldsymbol{x}}=\phi({\boldsymbol{z}}^{*}):=\text{ReLU}(W{\boldsymbol{z}}^{*})+{\boldsymbol{e}}$. Let $\epsilon=\|{\boldsymbol{e}}\|_{\infty}.$ If $W$ satisfies Assumption 2 with the integer $m>k$, and the observation ${\boldsymbol{z}}^{*}$ has at least $m$ coordinates that is larger than $2\epsilon$, then Algorithm 1 outputs an ${\boldsymbol{z}}$ that satisfies $\|{\boldsymbol{z}}-{\boldsymbol{z}}^{*}\|_{\infty}\leq\frac{2\epsilon}{c_{\infty}}$ with high probability $1-\exp(-\Omega(k))$.

Denote $I=\{i|x_{i}>\epsilon\}$, and ${\boldsymbol{x}}^{*}=\text{ReLU}(W{\boldsymbol{z}}^{*})$ to be the true output. Notice it also satisfies $x^{*}_{i}>0,\forall i\in I$ from the error bound assumption. Since ${\boldsymbol{x}}^{*}$ has more than $m$ entries $\geq 2\epsilon$, the observation ${\boldsymbol{x}}$ satisfies $|I|\geq m$. Notice for a feasible vector ${\boldsymbol{z}}$ with constraints in (6), it satisfies that

since the error is bounded uniformly for each coordinate in ${\boldsymbol{x}}^{*}$. Meanwhile, notice the real ${\boldsymbol{z}}^{*}$ satisfies $\phi_{i}({\boldsymbol{z}}^{*})=x^{*}_{i},\forall i\in I$, we have $W_{I,:}{\boldsymbol{z}}^{*}={\boldsymbol{x}}^{*}_{I}$. With Assumption 2, $W_{I,:}$ satisfies $\|W_{I,:}{\boldsymbol{a}}\|_{\infty}\geq c_{\infty}\|{\boldsymbol{a}}\|_{\infty}$ for an arbitrary ${\boldsymbol{a}}$ whp. Therefore together with (10) and let ${\boldsymbol{a}}={\boldsymbol{z}}-{\boldsymbol{z}}^{*}$ and get:

Therefore $\|{\boldsymbol{z}}-{\boldsymbol{z}}^{*}\|_{\infty}\leq\frac{2\epsilon}{c_{\infty}}$ with probability $1-\exp(\Omega(k))$.

For a sub-Gaussian random matrix $A$ with height $N$ and width $n$, where $N>2n$. Its smallest singular value

satisfies $s_{n}(A)\geq c_{2}\sqrt{N}$ with high probability $1-\exp(\Omega(n))$, where $c_{2}$ is some absolute constant.

The original paper requires $N>(1+\Omega(\log^{-1}(n))n$ and we presented above with a relaxed condition that $N>2n$.

Here ${\boldsymbol{z}}^{*}_{i}$ is the ground truth of $i$-th intermediate vector. ${\boldsymbol{z}}_{i}$ is the one we observe and ${\boldsymbol{z}}_{i-1}$ is the solution Algorithm 2 produces.

Appendix C More Experimental Results

More Results on LP Relaxation. In Figure 5, we compare the performance with respect to different noise levels over all our proposals, including the results of Algorithm 3 that we omit in the main text. Although we do not see significant improvement of the LP relaxation method over our other proposals, we believe the relaxation over the strict ReLU configurations estimation is of good potential and should be more investigated in the future.

Time comparison. Firstly, we should declare that for the very well-conditioned random weighted networks, gradient descent converges with large stepsize and we don’t observe much supriority over GD in terms of the running time. In the table below we presented the running time for random net with different input dimensions ranging from 10 to 110.

More experiments on the Sensing Problem. Finally we add some more examples for some impainting problem on MNIST with non-identity forward operator $A$.