1
$\begingroup$

After the model is trained, you just need to input random noise and the generator will output an image, does this mean GANs have constant running time ? I'm asking about both naïve GAN and variants of GAN

$\endgroup$
2
  • $\begingroup$ constant running time with respect to what? $\endgroup$
    – Alberto
    Nov 27, 2023 at 12:36
  • $\begingroup$ What do you mean? I just asked about the running time complexity of GAN, does the model have a constant running time or what? $\endgroup$
    – user78202
    Nov 27, 2023 at 14:38

1 Answer 1

1
$\begingroup$

The question is a bit ill defined... usually when we want some bound on the running time, we have to say with respect to what

For example:

  • sorting is O(nlogn) wrt the size of the input
  • Transformer is O(n^2 * d) wrt to the number of input words (or number of patches)
  • Diffusion models have O(1) complexity if we just consider the forward/backward diffusion

Now, as you can see, the problem is "hat are we considering for the measure"... sure if you encode GAN will Fully connected layers, you just have the n^2 for matrix multiplication... however, diffusion models have N step of diffusion to account for, but with the big-O notation taht N is canceled as it is just a constant

$\endgroup$
6
  • $\begingroup$ Is inference time different from running time, I read from the internet that GAN's inference time is faster than diffusion model ? $\endgroup$
    – user78202
    Nov 27, 2023 at 17:26
  • $\begingroup$ @David yes, but for the definition of computational complexity, you cannot see such difference, as they differ by a constant... GANs only need 1 forward pass, diffusion models usually in the order of tens of forward passes $\endgroup$
    – Alberto
    Nov 27, 2023 at 17:35
  • $\begingroup$ So both run at constant time ? Because you can define the number of steps in diffusion model $\endgroup$
    – user78202
    Nov 27, 2023 at 17:42
  • $\begingroup$ @David exactly, from a computational point of view, since it's constant, it's omitted from the analysis (though, in real life, you have definitely to consider it) $\endgroup$
    – Alberto
    Nov 27, 2023 at 20:54
  • $\begingroup$ I guess diffusion model is better than GAN in every aspect ? $\endgroup$
    – user78202
    Nov 30, 2023 at 20:33

You must log in to answer this question.