Let $W$ be random matrix and $b$ be vector. Let $x$ be secret vector; let $(y(x))_j = \max(W_j^Tx+b,0)$. Find $x' \in B(x;r)$ s.t $y(x')=y(x)$ whp

21 Views Asked by At

Let $1 \le n \le p$ be large positive integers. $W$ be a random $n \times p$ matrix with entries drawn iid from $\mathcal N(0,1/p)$ and let $b$ be an $n$-dimensional random vector with coordinates drawn iid from $\mathcal N(0,\sigma^2)$ for some $\sigma^2$. We can also consider the scenario when $b \in \mathbb R^n_{>0}$ is fixed (i.e not random). Now, fix a vector $x \in \mathbb R^p$ and consider the $n$-dimensional vector $y(x)$ with coordinates given by $(y(x))_j := \max(\langle W_j,x\rangle + b_j,0)$, for all $j \in [n]$. Finally, let $\epsilon > 0$.

Question. Is it possible to find a vector $x' \in \mathbb R^p$ with $\|x'-x\| \le \epsilon$, such that $y(x')=y(x)$ high probability (over the choice of $W$ and $b$) ?