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$.

  • 1
    $\begingroup$ you can probably phrase both as a zero sum game $\endgroup$ Commented Mar 29, 2017 at 21:39

1 Answer 1


I don't think they're very similar, once you look under the hood at the techniques that are used. GANs are typically about continuous optimization; program sketches are discrete combinatorial problems.

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.

  • $\begingroup$ I mean if you used a theory of the reals in the solver and used gradient descent as a tool when it is required, I could imagine something useful could come out of it. To me it seems that we'll likely need to synthesize discrete and continuous programs in tandem if we ever want them to do the work of complex software designed by humans. I do agree that the techniques are quite different, but it seems that the questions which each problem reduces to are quite similar, and that is why I asked this question. $\endgroup$ Commented Mar 29, 2017 at 20:39
  • $\begingroup$ @SamuelSchlesinger, the theory of the reals is not ordinarily used (or useful) used) for training GAN's. Instead, typically one uses continuous optimization techniques such as gradient descent. You wouldn't want to try to express a neural network in the theory of the reals and then train it by applying a solver for the theory of the reals; that has been tried, and it scales very poorly. $\endgroup$
    – D.W.
    Commented Mar 29, 2017 at 20:45
  • $\begingroup$ 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. $\endgroup$ Commented Mar 29, 2017 at 20:52
  • $\begingroup$ Here's a related concept: web.cs.ucla.edu/~guyvdb/papers/ChoiIJCAI15.pdf $\endgroup$ Commented Mar 30, 2017 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.