Sliced Distribution Matching based on Cumulative Distribution Functions with Applications to Control

Alexandros E. Tzikas, Liam A. Kruse, Mansur Arief, Mykel J. Kochenderfer, Stephen BoydarXiv 2024 · DOI · arXiv

Abstract

Computing the similarity between two probability distributions is a recurring theme across control. We introduce a unified family of distances between the probability distributions of two random variables that is based on the discrepancy between the cumulative distribution functions of random linear one-dimensional projections of the random variables. Our proposed distance is interpretable, computationally simple, and admits a differentiable approximation. We establish asymptotic theoretical guarantees for sample-based estimators of the distance. We empirically study the use of the distance in a two-sample test and demonstrate its ability to distinguish different distributions. Finally, we show that the distance allows for simple gradient-based solutions in control by studying distribution steering and ergodic control.

Introduction

Quantifying the similarity between two probability distributions is a fundamental challenge in robotics and control. For instance, determining if a swarm of robots has reached a desired spatial configuration or ensuring a single robot's long-term trajectory covers a search area according to a priority map requires robust distribution metrics. Traditional metrics like the Kullback–Leibler (KL) divergence or the Wasserstein distance are theoretically powerful but often become computationally prohibitive in high-dimensional spaces. Furthermore, many existing metrics are not easily differentiable, which prevents the use of efficient gradient-descent algorithms for solving complex control problems. This paper introduces a new, computationally efficient family of distances that are theoretically sound, fast to compute, and "optimizer-friendly."

Methodology: Sliced CDF-based Distances

The authors leverage a "sliced" approach to overcome the curse of dimensionality. Instead of comparing high-dimensional distributions directly, they project them onto many random 1D lines. This is analogous to comparing two 3D objects by examining their 2D shadows from multiple angles.

Key technical components include:

  • CDF-based Discrepancy: In 1D, the authors compare distributions using their Cumulative Distribution Functions (CDFs). This allows for the application of well-known 1D metrics like Kolmogorov-Smirnov or 1-Wasserstein.
  • Projection Averaging: The final distance is defined as the expected value of these 1D discrepancies across all possible projection directions.
  • Differentiable Approximation: To make the distance usable for gradient-based optimization, the authors replace the non-differentiable "step" in the empirical CDF calculation with a smooth sigmoid function. This enables the calculation of stochastic gradients of the distance with respect to the samples' positions.
Conceptual overview: high-dimensional distributions are projected onto 1D lines where their CDFs are compared and averaged.

This framework unifies several existing sliced distances into a single family and is particularly sample-efficient, as the distance can be estimated directly from samples (e.g., robot positions) without reconstructing a continuous density function.

Empirical Evaluation and Control Applications

The paper evaluates the proposed method using synthetic benchmarks and simulated physical systems. A key test involves high-dimensional Gaussians for two-sample testing to determine if the metric can distinguish between distributions with different means or covariances in up to 50 dimensions.

The metric successfully distinguished between different distributions even in 50 dimensions, where the "null" (same distribution) and "alternative" (different distribution) cases remained clearly separable.

Two-sample test results in 50 dimensions showing clear separation between null and alternative hypotheses.

Beyond testing, the distance was applied to distribution steering and ergodic control using a unicycle dynamics model. The algorithm successfully steered a cloud of 3,000 samples from a simple starting point to match a complex, bimodal target distribution. In ergodic control tasks, the method generated a single 5,000-step trajectory for a unicycle robot that effectively covered a target density map, demonstrating its utility for autonomous exploration and surveillance.

Conclusion

The introduced family of sliced CDF-based distances provides a robust and differentiable tool for distribution matching in control. By enabling the use of off-the-shelf deep learning optimizers like AdamW for distribution-level tasks, this work opens new avenues for complex swarm coordination and autonomous coverage. Future work will explore active selection of projection directions and the incorporation of real-world constraints such as obstacles and communication limits.

Summary updated

Abstract

Computing the similarity between two probability distributions is a recurring theme across control. We introduce a unified family of distances between the probability distributions of two random variables that is based on the discrepancy between the cumulative distribution functions of random linear one-dimensional projections of the random variables. Our proposed distance is interpretable, computationally simple, and admits a differentiable approximation. We establish asymptotic theoretical guarantees for sample-based estimators of the distance. We empirically study the use of the distance in a two-sample test and demonstrate its ability to distinguish different distributions. Finally, we show that the distance allows for simple gradient-based solutions in control by studying distribution steering and ergodic control.
BibTeX
@misc{tzikas2024sliced,
  author = {Alexandros E. Tzikas and Liam A. Kruse and Mansur Arief and Mykel J. Kochenderfer and Stephen Boyd},
  title = {{Sliced Distribution Matching based on Cumulative Distribution Functions with Applications to Control}},
  year = {2024},
  eprint = {2412.06220},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.06220},
}
Figure