Optimal Transport in the Face of Noisy Data.

Bart P. G. Van Parys

Abstract: Optimal transport distances are popular and theoretically well understood in the context of data-driven prediction. A flurry of recent work has popularized these distances for data-driven decision-making as well although their merits in this context are far less well understood. This in contrast to the more classical entropic distances which are known to enjoy optimal statistical properties. This begs the question when, if ever, optimal transport distances enjoy similar statistical guarantees. Optimal transport methods are shown here to enjoy optimal statistical guarantees for decision problems faced with noisy data.

Introduction

In the realm of stochastic optimization, the goal is to make decisions that minimize expected loss under an unknown probability distribution. Typically, practitioners rely on empirical data samples to approximate this distribution. However, this approach often falls victim to the "Optimizer’s Curse": a phenomenon where a decision optimized for a specific set of samples performs poorly in real-world applications because the model has overfitted to the noise or idiosyncrasies of the training data.

To mitigate this, Distributionally Robust Optimization (DRO) has emerged as a powerful paradigm. DRO seeks a decision that performs well across an "ambiguity set"—a collection of distributions centered around the observed data. While classical results have established that Kullback-Leibler (KL) divergence provides the most statistically efficient ambiguity sets for noiseless data, real-world data is frequently corrupted by measurement errors, censoring, or quantization. This paper addresses a fundamental question: What is the statistically efficient way to make robust decisions when the available data is noisy?

The Challenge of Noisy Observations

Consider a scenario where we do not observe the true signal $\xi$, but rather a corrupted version $\xi' = \xi + \epsilon$, where $\epsilon$ represents noise. Standard DRO formulations designed for clean data often fail in these contexts because they do not account for the "blurring" effect of the noise.

The author demonstrates that the standard large deviation rate functions used to characterize uncertainty in clean data become highly irregular when applied to noisy observations. To resolve this, the paper introduces a framework of "smoothed" rate functions ($I^\delta$). These functions are based on the Lévy-Prokhorov metric, which metrizes weak convergence and provides a more stable foundation for decision-making under uncertainty than traditional entropic distances when noise is present.

Bridging Optimal Transport and Robustness

A key contribution of this work is the theoretical bridge between statistical efficiency and Optimal Transport (OT). The author proves that the most efficient robust formulations for noisy data are deeply connected to entropic and "unbalanced" optimal transport problems.

While these OT-based ambiguity sets are theoretically superior, they are often computationally daunting. The Lévy-Prokhorov metric typically involves an exponential number of constraints, making direct optimization intractable. To overcome this, the paper utilizes Strassen’s Representation Theorem. This classical result allows the author to transform the complex, infinite-dimensional ambiguity set into a finite-dimensional convex optimization problem, effectively making the "smoothed" formulation solvable.

Computational Tractability via Duality

The paper derives a dual representation of the DRO problem, which significantly reduces the computational burden. By shifting the focus to the dual space, the complexity of the optimization becomes proportional to the number of data points ($N$). This transformation allows the problem to be solved using standard convex optimization tools.

The resulting decision problems are reduced to the task of integrating the noise distribution over intersections of norm balls. While this still requires a computational oracle, it is a much more manageable task that can be addressed using stochastic oracle methods. This allows the framework to handle various noise models, including:

  • Additive Gaussian Noise: Standard measurement errors.
  • Clipping Noise: Sensor limitations where values are capped.
  • Quantization Noise: Rounding errors from digital discretization.

Key Results and Statistical Guarantees

The proposed framework provides several rigorous guarantees that justify the use of optimal transport in noisy environments:

  1. Efficiency Guarantee: The robust formulations introduced here dominate other regular predictors by achieving an optimal balance between out-of-sample disappointment and minimal bias.
  2. Consistency: The paper establishes the specific rates at which the robustness radius ($r_N$) and the smoothing parameter ($\delta_N$) must decay as the sample size $N$ increases. This ensures that as more data is collected, the robust decision converges to the true optimal decision.
  3. Adaptability: Unlike the noiseless case, where KL divergence is the unique optimal choice, noisy data requires a family of formulations. These are parameterized by the smoothing factor $\delta$, allowing decision-makers to tune the model's sensitivity to the specific noise profile of their data.

Conclusion and Future Directions

This research provides a rigorous theoretical foundation for using optimal transport distances in data-driven decision-making. By accounting for the noise structure of the data, the proposed smoothed DRO framework offers a statistically principled alternative to traditional entropic methods.

However, some challenges remain. The current framework assumes the noise distribution is known (e.g., a known Gaussian variance). Future research could explore "doubly robust" models that account for uncertainty in the noise distribution itself. Additionally, while the dual form is tractable, high-dimensional noise geometries may still pose challenges for the required integration oracles. Finally, the limits of decision-making in "information-destroying" scenarios—where noise levels are so high that the original signal is unidentifiable—remain an open area of study.

Summary updated

Abstract

Optimal transport distances are popular and theoretically well understood in the context of data-driven prediction. A flurry of recent work has popularized these distances for data-driven decision-making as well although their merits in this context are far less well understood. This in contrast to the more classical entropic distances which are known to enjoy optimal statistical properties. This begs the question when, if ever, optimal transport distances enjoy similar statistical guarantees. Optimal transport methods are shown here to enjoy optimal statistical guarantees for decision problems faced with noisy data.
BibTeX
@inproceedings{parys2024optimal,
  author = {Bart P. G. Van Parys},
  title = {{Optimal Transport in the Face of Noisy Data.}},
  booktitle = {Operations},
  year = {2024},
  doi = {10.1016/j.orl.2024.107089},
}
Figure