This is a relatively clean subproblem that we came upon a few months ago while thinking about gradient hacking. We're throwing it out to the world to see if anyone can make progress. 

Problem: Construct a gradient hacker (definition below), or prove that one cannot exist under the given conditions.

Setup: Let $x\in R^d$ be the network inputs, $\theta \in R^w$, be the network trainable parameters, $\hat{y}\in R$ be the network outputs, and $f(x,\theta )=\hat{y}$ be the network architecture. $f(x,\theta )$ must be a feedforward neural network that reads in its own weights as input. Weight sharing is allowed (vertical or horizontal), and some weight sharing is necessary in order to take all w weights as input.

Suppose that we train this network on a dataset $D=\{x^{\left(i\right)},y^{\left(i\right)}\}$, with MSE loss $L\left(\theta \right)=\frac{1}{n}{\sum }_i\left(f\right(x^{\left(i\right)},\theta )-y^{\left(i\right)}{)}^2$, assuming gradient flows: ${\theta }^{\prime }\left(t\right)=-{\nabla }_{\theta }L\left(\theta \right(t\left)\right)$. Given an initial point ${\theta }_0$, the training dynamics are therefore:

Definition: A tuple $(f,{\theta }_g,D)$ is a gradient hacker if the following conditions hold:

1. ${\theta }_g$ is not a global optimum: $\exists \theta$ such that $L\left(\theta \right)<L\left({\theta }_g\right)$
2. $\exists ϵ>0$ such that $\forall {\theta }_0:||{\theta }_0-{\theta }_g||<ϵ$:
   1. the network’s training converges to ${\theta }_g$, i.e., ${lim}_{t\to \infty }\theta \left(t\right)={\theta }_g$. 
   2. There is internal structure of $f(\cdot ,{\theta }_0)$ that computes the gradient; i.e., there is some subset of the activations whose mean over every datapoint in D is ${\nabla }_{{\theta }_0}L\left({\theta }_0\right)$. ^[1]

This captures my intuition that a gradient hacker knows where it wants to go (in this case "get to ${\theta }_g$"), and then it should decide what it outputs in order to make the gradient true.

Some more ambitious problems (if gradient hackers exist):

• Characterize the set of all gradient hackers. 
• Show that they all must satisfy some property. 
• Construct gradient hackers for arbitrarily large $n$, $d$, $w$, and neural net depth.
• Variations on the problem: a subset of the activations equals ${\nabla }_{{\theta }_0}L\left({\theta }_0\right)$ for every input, or the subset of activations correspond to the gradient on that input.

1. ^{^}

   This is a bit strict, but we didn't want to list different ways something could be isomorphic to the gradient.