<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-03-29T20:39:17.490Z
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.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-29T20:45:23.590Z
@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.
D.W.
CC BY-SA 3.0
2017-03-29T20:52:01.147Z
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: https://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
CC BY-SA 3.0
2017-03-30T06:35:16.413Z
Here's a related concept: http://web.cs.ucla.edu/~guyvdb/papers/ChoiIJCAI15.pdf
Samuel Schlesinger
CC BY-SA 3.0
2017-03-29T20:33:20.423Z
2017-03-29T20:33:20.423Z
D.W.
<p>In particular, I'm considering the similarities in <a href="https://arxiv.org/abs/1406.2661" rel="nofollow noreferrer">Generative Adversarial Networks</a> and <a href="https://people.csail.mit.edu/asolar/papers/asplos06-final.pdf" rel="nofollow noreferrer">Combinatorial Sketching for Finite Programs</a>. </p>

<p>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.</p>

<p>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.</p>

<p>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:</p>

<p>$\wedge_{x \in L}\vee_{y \in L}V(x, y)$</p>

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

CC BY-SA 3.0
2017-03-29T21:39:41.297Z
you can probably phrase both as a zero sum game
Sasho Nikolov
<cc.complexity-theory><ds.algorithms><machine-learning><adversarial-learning>
What is the connection between adversarial learning in machine learning and program synthesis?
Samuel Schlesinger
# What is the connection between adversarial learning in machine learning and program synthesis?

(Asked by: username_0 on 2017-03-29)

In particular, I'm considering the similarities in [Generative Adversarial Networks](https://arxiv.org/abs/1406.2661) and [Combinatorial Sketching for Finite Programs](https://people.csail.mit.edu/asolar/papers/asplos06-final.pdf).

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

**Tags:** cc.complexity-theory, ds.algorithms, machine-learning, adversarial-learning

> **Comments:**
> **username_1**: you can probably phrase both as a zero sum game  

---

## 1 answers

### Answer by username_2 on 2017-03-29. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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.  
> **username_0**: 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: https://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.  
> **username_0**: Here's a related concept: http://web.cs.ucla.edu/~guyvdb/papers/ChoiIJCAI15.pdf  

---

