Graph-based Discriminators: Sample Complexity and Expressiveness

Roi Livni, Yishay Mansour

Introduction

At the heart of generative modeling—most notably in Generative Adversarial Networks (GANs)—lies a fundamental question: Are these two distributions identical? Traditionally, this question is answered by training a discriminator to evaluate individual samples in isolation, deciding whether each looks "real" or "fake."

However, evaluating samples one by one makes it difficult to detect relational properties between generated outputs. A classic example is mode collapse, a common GAN failure mode where the generator produces the exact same output repeatedly. Standard discriminators struggle to detect this because they cannot easily compare generated samples against one another. To address this limitation, this paper introduces a rigorous mathematical foundation for graph-based discriminators—functions that evaluate $k$-tuples of samples simultaneously to find relational patterns.

The Framework: $k$-ary Discriminators and Graph VC Dimension

The authors extend the classical framework of statistical learning theory by shifting from standard 1-ary discriminators to $k$-ary discriminators.

  • Graph-based Distinguishers: Instead of a standard hypothesis function $f(x)$, the authors propose functions $g(x_1, \dots, x_k)$ that take a $k$-tuple of independent and identically distributed (i.i.d.) samples. Each function naturally defines a hyper-edge in a graph. A simple "collision test" to detect mode collapse, for instance, operates where $k=2$.
  • Graph VC Dimension ($gVC$): To understand the sample complexity of these $k$-ary discriminators, the authors introduce a new combinatorial measure. While the standard VC dimension counts how many individual points a hypothesis class can "shatter," $gVC$ is defined inductively based on projections. It essentially measures the complexity of the function class when all but one coordinate in the $k$-tuple are fixed.
  • Integral Probability Metric (IPM): The distance between distributions is analyzed by comparing the expected value of a graph function on $k$ samples from distribution $A$ versus $k$ samples from distribution $B$.

Theoretical Insights: Expressiveness and Learnability

A major contribution of this work is proving the strict hierarchy of expressiveness in graph-based discriminators. The authors demonstrate that $k+1$-ary discriminators are strictly more expressive than $k$-ary discriminators. Strikingly, a single graph-based test ($k=2$) can successfully distinguish between two distributions that any standard discriminator ($k=1$) with a finite VC dimension would find identical.

Furthermore, the paper highlights a fascinating distinction between "learnability" and "discriminability." A class of functions might be considered unlearnable in the traditional Probably Approximately Correct (PAC) framework (having an infinite standard VC dimension) but still be perfectly discriminable (having a finite graph VC dimension). This occurs because discrimination only requires uniform convergence over product distributions (independent samples)—a significantly weaker and easier requirement than converging over every possible joint distribution.

Ultimately, these insights provide a strong theoretical justification for recent empirical trends in GAN research, such as the use of "mini-batch discrimination" to prevent mode collapse.

Sample Complexity Bounds

Using the newly defined Graph VC Dimension, the authors establish rigorous bounds on the number of samples required to distinguish distributions:

  • Upper Bound: For a hypothesis class with a graph VC dimension of $\rho$, the number of samples needed to distinguish distributions is bounded by $O\left(\frac{\rho k^2}{\epsilon^2} \log \frac{1}{\delta}\right)$.
  • Lower Bound: Conversely, the authors prove that at least $\Omega\left(\frac{\sqrt{\rho}}{2^{7k^3}\epsilon^2}\right)$ samples are necessary. This establishes a fundamental mathematical limit on the efficiency of these $k$-ary discriminators.

Limitations and Future Directions

While this theoretical framework robustly expands our understanding of discriminative power, several open challenges remain:

  1. The Complexity Gap: There is a lingering mathematical gap between the upper bound ($O(\rho)$) and the lower bound ($\Omega(\sqrt{\rho})$) for sample complexity. Closing this gap is a primary target for future theoretical work.
  2. Online Learning: The current framework focuses on the batch setting. The authors suggest extending this work to the "online" setting—modeling sequential games between generators and discriminators—by developing a graph-based version of the Littlestone dimension.
  3. Practical Implementation: The paper relies on mathematical distributions over finite and infinite sets to prove its theorems. Translating these theoretical $k$-ary architectures into specific, optimal neural network layers for real-world GAN training remains an exciting frontier for applied machine learning researchers.

Summary updated

Abstract

A basic question in learning theory is to identify if two distributions are identical when we have access only to examples sampled from the distributions. This basic task is considered, for example, in the context of Generative Adversarial Networks (GANs), where a discriminator is trained to distinguish between a real-life distribution and a synthetic distribution. Classically, we use a hypothesis class $H$ and claim that the two distributions are distinct if for some $h\in H$ the expected value on the two distributions is (significantly) different. Our starting point is the following fundamental problem: "is having the hypothesis dependent on more than a single random example beneficial". To address this challenge we define $k$-ary based discriminators, which have a family of Boolean $k$-ary functions $\G$. Each function $g\in \G$ naturally defines a hyper-graph, indicating whether a given hyper-edge exists. A function $g\in \G$ distinguishes between two distributions, if the expected value of $g$, on a $k$-tuple of i.i.d examples, on the two distributions is (significantly) different. We study the expressiveness of families of $k$-ary functions, compared to the classical hypothesis class $H$, which is $k=1$. We show a separation in expressiveness of $k+1$-ary versus $k$-ary functions. This demonstrate the great benefit of having $k\geq 2$ as distinguishers. For $k\geq 2$ we introduce a notion similar to the VC-dimension, and show that it controls the sample complexity. We proceed and provide upper and lower bounds as a function of our extended notion of VC-dimension.
BibTeX
@inproceedings{livni2019graph,
  author = {Roi Livni and Yishay Mansour},
  title = {{Graph-based Discriminators: Sample Complexity and Expressiveness}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=uLRu_w9_FFp},
}
Figure