We study the problem of alleviating the instability issue in the GAN training procedure via new architecture design. The discrepancy between the minimax and maximin objective values could serve as a proxy for the difficulties that the alternating gradient descent encounters in the optimization of GANs. In this work, we give new results on the benefits of multi-generator architecture of GANs. We show that the minimax gap shrinks to as the number of generators increases with rate O(1/ ). This improves over the best-known result of O(1/ 2 ). At the core of our techniques is a novel application of Shapley-Folkman lemma to the generic minimax problem, where in the literature the technique was only known to work when the objective function is restricted to the Lagrangian function of a constraint optimization problem. Our proposed Stackelberg GAN performs well experimentally in both synthetic and real-world datasets, improving Fréchet Inception Distance by 14.61% over the previous multi-generator GANs on the benchmark datasets.
A Stackelberg competition is a nonzero-sum game where 1) each player has their own objective, which do not sum up to a constant, and 2) there is an order at which the players interact. The proposed formulation only assumes that parameters of one player (data generator) partition in I tuples \gamma_i of parameters, where each tuple parameterizes a different data generator component (e.g., a separate neural network). Further, each of those components is assumed to contribute a term to the game's objective that only depends on the corresponding parameter tuple \gamma_i, and the other player's parameters \theta (e.g., weights of the discriminator). From a game theoretic perspective, this still yields a 2-player zero-sum game where the action space of the data generator is the product space of the I tuple spaces. Hence, I have doubts about the general finding that more data generating components decreases the duality gap.
The gap between the a maximin and minimax solution is determined by the shape of the objective \phi(\gamma,\theta) and is zero, for example, if \phi is (quasi) convex in \gamma=[\gamma_1, ..., \gamma_I], and (quasi) concave in \theta. The authors bound the violation of this property w.r.t. the data generator components' parameters \gamma_i, and argue that this degree of violation is the same for the whole data generator parametrized by \gamma=[\gamma_1, ..., \gamma_I] if the data generator components are from the same family of mappings (e.g., having the same network architecture). While this conclusion is true under worst cast assumption, e.g., the globally maximal possible gap, this would also imply that all data generator components find the same global best solution, that is, yield the same mapping, in which case the gap would be identical to just using one of those components.
Intuitively, the only reason to have multiple data generator components is to learn different mappings such that the joint data generator -- mixing the outputs of the different components -- is more expressiv than just a single mapping. If the different mappings only result from the inability of finding the global best solution, a worst case argument is not very insightful; in this case, one should study the duality gap in the neighborhood of the starting solutions. On the other hand, if we assume a different family of mappings for each component, the convexity violation of the joint data generator is higher than for each component; hence, the gap does not necessarily decrease with more components.
So why do multiple data generator components help in practice, and why does the proposed model outperform single-component GANs and the multi-branch GAN in the experiments? Solving a maximin/minimax problem for highly non-convex-concave functions is challenging; there is an infinity of saddle point solutions which yield different "performances". The multi-branch GAN can be seen as a model averaging approach giving more stable results, whereas the proposed GAN seems more of an ensemble approach to stabilize the result. Though, this is speculative and I would encourage the authors to study this in-depth; the reasoning in Remark 1 is not convincing to me.
UPDATE:
I read the revision and stick to my vote. In the discussion, I wasn't able to get my points across, e.g., that bounding the worst case duality gap is not enough to conclude that the observed duality gap does not grow for multiple local optimal GANs, where the duality gap is expected to be much smaller. A simple experiment could be to actually measure the duality gap (flip the order of the players and measure the difference of the objectives, when starting with the same initialization). If the authors were right, the maximum of those gap should stay constant when adding more data generators. To justify a Stackelberg setting, the authors may provide an example instantiation that cannot be cast into a standard zero-sum game with minimax solution. I can't see such an example but I'm happy to be proven wrong.