# What is the connection between adversarial learning in machine learning and program synthesis?

In particular, I'm considering the similarities in Generative Adversarial Networks and Combinatorial Sketching for Finite Programs.

In the first paper, our concern is with learning generator distribution $p_g$ over data $x$ which we represent using input noise $p_z(z)$ and map to $X$ using $G(z; \theta_g)$ as well as with learning an adversarial discriminator $D(x; \theta_d)$ which will output the probability that $x$ came from our data rather than $p_g$. We train $D$ so that it can identify which distribution its input comes from, and we train $G$ to minimize $log(1 - D(G(z)))$, in other words we train $G$ to fool $D$, and we train $D$ to "bust" $G$. This is all wrapped up in the goal $min_G max_D V(D, G)$, where $V$ is a value function.

In the second paper, we have what we call a sketch, which is a program $Sk(x; \theta_s)$, where $\theta_s$ is not known by the programmer, as well as a spec $Sp(x)$, which is a specification of the program we want the sketch to emulate. Our goal is to find $\theta_s$ such that $\forall x, Sk(x, \theta_s) = Sp(x)$. The approach taken in the paper to solving this problem is to face two SAT solvers against each other, each tasked essentially with defeating one another. The algorithm is really quite simple if you consider the $\Sigma_2^P$ question which we're answering: $\exists \theta_s \forall x, Sk(x, \theta_s) = Sp(x)$. We keep a running set $I$ of inputs which we want our next $\theta_s$ candidate to work for: we ask our generative SAT solver $G$ if $\exists \theta_s, \wedge_{x \in I} Sk(x, \theta_s) = Sp(x)$. If we get a candidate $\theta_s$, we then ask our discriminative SAT solver $D$ if $\exists x, Sk(x, \theta_s) \neq Sp(x)$. If we don't get a candidate it means our sketch can't fit our spec and we exit screaming. If $D$ finds some $x$, we add $x$ to $I$ and repeat the process. Otherwise we're finished, as we have $\theta_s$ such that $\forall x \in x, Sk(x, \theta_s) = Sp(x)$, which is exactly what we wanted.

For obvious reasons I feel these methods are related and it also turns out you can frame them both as resolving the following for some lattice $L$ and value function $V$, where $L = \mathbb{R}$ in the former and $L = \{false, true\}$ in the latter:

$\wedge_{x \in L}\vee_{y \in L}V(x, y)$

Surely someone has seen a connection like this before, I'd love to hear the thoughts of others. I had said when I first learned the sketching method in a class that I felt that it could have applications to machine learning and I was essentially shut down as just being ridiculous because of how distinct the domains traditionally are, but I really feel the above makes at the very least a nice analogy and at the most displays that the algorithms considered are closely related in ways that we just don't understand. One way of looking at it I think is that they are both playing similar games in $\Sigma_2^P$.

• you can probably phrase both as a zero sum game – Sasho Nikolov Mar 29 '17 at 21:39

As far as your lattice formulation, optimization over $\mathbb{R}$ is pretty different from optimization over the boolean lattice $\{\top,\bot\}^n$ -- the algorithms look quite different (e.g., gradient descent vs SAT solvers). It's not clear how you'd apply methods for continuous optimization (like gradient descent) to combinatorial optimization problems (like SAT), or how you'd apply methods for discrete combinatorial problems (like SAT solvers) to continuous optimization.
• I certainly believe that, though I'm currently reading up on $(E)Th(\mathbb{R})$ so I'll understand to what extent that's theoretically true soon. My other idea was to use the approach given in the sketching paper for machine learning tasks by iteratively adding new examples to the models cost function, prioritizes by how badly the model currently is doing on them. A more developed approach is taken in the talk given here: simons.berkeley.edu/talks/rob-fergus-2017-3-28. This talk was actually what spurred me to take this line of thought I'd had and pursue it again today. – Samuel Schlesinger Mar 29 '17 at 20:52