When Do Local Discriminators Work? On Subadditivity of Probability Divergences

Mucong Ding, Constantinos Daskalakis, Soheil Feizi

Abstract

Local discriminators have been employed in deep generative models, in image-to-image translation methods, and in analyzing time-series data to improve generation quality and training stability. However, these successes are often based on heuristics without theoretical guarantees. This paper provides the theoretical foundations for using local discriminators by leveraging conditional independence structures captured by Bayesian networks or Markov Random Fields (MRFs). Our results are based on subadditivity properties of probability divergences, establishing that the distance between high-dimensional distributions can be bounded by the sum of distances between their local marginals. We prove subadditivity for several popular divergences (JS, TV, Wasserstein, etc.) and demonstrate the benefits of our principled design on both synthetic and real-world datasets.

Introduction: The Curse of Dimensionality in GANs

Training Generative Adversarial Networks (GANs) in high-dimensional spaces is notoriously difficult. Standard "model-free" GANs typically employ a single, massive discriminator to distinguish between real and fake data across the entire feature space. This approach faces the "curse of dimensionality": statistical hypothesis testing in high dimensions requires a sample complexity that grows exponentially with the number of variables.

To combat this, practitioners often use local discriminators—applying them to specific image patches or time-series subsequences. While empirically successful, this has largely been a heuristic approach. It has remained unclear which features a local discriminator should focus on, or if minimizing local differences guarantees that the global, joint distribution is learned correctly. This research provides the missing theoretical link, proposing "model-based" GANs that exploit known data structures.

Theoretical Framework: Generalized Subadditivity

The core contribution of this work is the concept of generalized subadditivity of probability divergences. If a divergence (such as Kullback-Leibler or Wasserstein) is subadditive over a graph, the total distance between two joint distributions is upper-bounded by the sum of distances between their local marginals.

Conceptual comparison of Bayes-net GANs using local discriminators versus standard GANs with a single giant discriminator.

The authors prove that several popular divergences—including Jensen-Shannon (JS), Kullback-Leibler (KL), and Total Variation (TV)—satisfy subadditivity on Bayesian networks. They further extend these findings to Integral Probability Metrics (IPMs) and Wasserstein distances for both Bayes-nets and MRFs. This theoretical foundation allows for the design of GANs where simple, local discriminators are trained on the neighborhoods (parents/children or cliques) of a known independence graph, rather than relying on one giant global discriminator.

Key Insights: The "U-Shaped" Trade-off

A critical finding of this research is the existence of an optimal "localization width." If discriminators are too local (width too small), they fail to capture essential dependencies (e.g., physical laws like gravity in a trajectory). Conversely, if they are too global, they succumb to the curse of dimensionality, leading to high estimation errors.

The relationship between localization width and error metrics, illustrating the optimal trade-off between capturing dependencies and avoiding the curse of dimensionality.

By identifying the underlying conditional independence structure, one can determine the minimal sufficient neighborhood for local discriminators. This structural awareness allows model-based GANs to capture the actual causal and independence structure of the data more accurately than standard models, which often hallucinate non-existent dependencies.

Experimental Results

The approach was evaluated on several structured datasets, including synthetic ball-throwing trajectories and real-world Bayesian networks like EARTHQUAKE and CHILD.

  • Higher Quality Samples: On the EARTHQUAKE and CHILD datasets, Bayes-net GANs consistently outperformed standard GANs across metrics such as Energy Statistics and Detection AUC.
  • Causal Accuracy: The proposed method successfully recovered ground-truth causal graphs from generated samples, whereas standard GANs often produced dense, fully-connected structures that did not reflect the true data-generating process.
  • Efficiency: Model-based approaches reached lower error states significantly faster than global approaches due to the reduced complexity of the local discriminators.

Conclusion and Future Work

While this framework provides a principled way to design local discriminators, it currently requires the underlying independence graph to be known a priori. Future research directions include combining this framework with structure learning, allowing a model to simultaneously learn the independence graph and the generative distribution. Scaling these principles to high-resolution images by defining meaningful neighborhoods in latent feature spaces also remains a promising area for exploration.

Summary updated

Abstract

Local discriminators have been employed in deep generative models, in image-to-image translation methods, in analyzing time-series data, etc. The approach is to apply local discriminators to different patches of an image or subsequences of time-series data, resulting in improved generation quality, reduced discriminator size, and faster and more stable training dynamics. These empirical successes, however, are based on heuristics; it is not clear what subset of features each local discriminator should be applied to, and there are no theoretical guarantees about the effect of the discriminator localization on estimating the distance between the generated and target distributions. In this paper, we provide theoretical foundations to answer these questions for high-dimensional distributions with conditional independence structure captured by either a Bayesian network or a Markov Random Field (MRF). Our results are based on subadditivity properties of probability divergences, which establish upper bounds on the distance between two high-dimensional distributions by the sum of distances between their marginals over (local) neighborhoods of the graphical structure of the Bayes-net or the MRF. We prove that several popular probability divergences, including Jensen-Shannon, Total Variation, Wasserstein, Integral Probability Metrics (IPMs), and nearly all f-divergences, satisfy some notion of subadditivity under mild conditions. Thus, given an underlying feature dependency graph and using our theoretical results, one can use, in a principled way, a set of simple local discriminators, rather than a giant discriminator on the entire graph, providing significant statistical and computational benefits. Our experiments on synthetic as well as real-world datasets demonstrate the benefits of using our principled design of local discriminators in generative models.
BibTeX
@inproceedings{ding2021when,
  author = {Mucong Ding and Constantinos Daskalakis and Soheil Feizi},
  title = {{When Do Local Discriminators Work? On Subadditivity of Probability Divergences}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=aYrzxTHQkNc},
}
Figure