Abstract
Classical Kullback-Leibler or entropic distances are known to enjoy certain desirable statistical properties in the context of decision-making with noiseless data. However, in most practical situations the data available to a decision maker is subject to a certain amount of measurement noise. We hence study here data-driven prescription problems in which the data is corrupted by a known noise source. We derive efficient data-driven formulations in this noisy regime and indicate that they enjoy an entropic optimal transport interpretation. Finally, we show that these efficient robust formulations are tractable in several interesting settings by exploiting a classical representation result by Strassen.
Introduction
In the field of stochastic optimization, the primary objective is to identify a decision $z$ that minimizes an expected loss function $E_P[\ell(z, \xi)]$. In practice, however, the underlying probability distribution $P$ is rarely known. Instead, decision-makers must rely on empirical data samples.
Traditional approaches, such as Sample Average Approximation (SAA), are prone to the "Optimizer’s Curse," where the model overfits to the specific noise and idiosyncrasies of the training data. This leads to decisions that appear optimal in training but perform poorly in real-world applications. Distributionally Robust Optimization (DRO) was developed to mitigate this by optimizing against the worst-case distribution within a defined "ambiguity set." While Kullback-Leibler (KL) divergence has been established as an efficient way to construct these sets for noiseless data, most real-world data is corrupted by measurement errors, sensor limits, or quantization. This paper introduces a framework for DRO specifically tailored for these noisy environments.
Methodology: Bridging Theory and Noise
The proposed framework is built upon three mathematical pillars designed to maintain statistical efficiency while ensuring computational feasibility:
- Large Deviation Theory: The author utilizes the "rate function"—a measure of how rarely an empirical distribution deviates from the truth—to define the ambiguity set. Unlike the noiseless regime where KL divergence suffices, the noisy regime requires a more complex rate function to account for the corruption process.
- $\delta$-Smoothing: Raw rate functions for noisy data can be mathematically irregular, often becoming infinite in continuous noise scenarios. To resolve this, the author introduces a $\delta$-smoothed rate function, creating a family of nested ambiguity sets that remain mathematically well-behaved.
- Strassen Representation and Duality: To transform the robust optimization problem into a solvable format, the paper employs Strassen’s representation of the Lévy-Prokhorov metric. This allows the infinite-dimensional problem over probability measures to be reformulated into a finite convex dual problem, solvable via standard optimization software.
Noise Models and Identifiability
The research analyzes several synthetic noise models that mirror common engineering challenges:
- Additive and Gaussian Noise: Representing general measurement errors and standard bell-curve fluctuations.
- Clipping Noise: Addressing censored data where values exceeding a sensor's range are recorded at the boundary.
- Quantization Noise: Modeling digital rounding errors inherent in signal processing.
A critical insight of the paper is the role of identifiability. For the data-driven solution to be consistent—meaning it converges to the true optimum as more data is collected—the noise must not be "too destructive." Specifically, the noise distribution's characteristic function must not have roots, ensuring the noise does not completely erase the underlying signal.
The Connection to Optimal Transport
One of the paper's most significant contributions is revealing the link between noisy DRO and Unbalanced Optimal Transport. The rate function for noisy data can be decomposed into a sum of KL divergence and an entropic optimal transport term. This provides a clear physical intuition: the "distance" between distributions in the ambiguity set accounts for both the statistical likelihood of the data and the "cost" of the noise shifting those data points from their true values.
Key Results and Tractability
The author provides rigorous proofs for the framework's effectiveness:
- Feasibility and Efficiency (Theorem 2.9): The formulations satisfy a "disappointment" guarantee, ensuring the probability that actual costs exceed predicted costs decays exponentially as the sample size increases.
- Consistency (Theorem 2.15): Under mild conditions, such as bounded Lipschitz loss, the data-driven decision is shown to converge to the true optimal decision as the number of samples $N \to \infty$.
- Computational Tractability: By providing a concrete dual formulation, the paper demonstrates that these "noisy-robust" approaches are not just theoretical constructs but are practically usable for engineers facing real-world data corruption.
Limitations and Future Directions
While the framework is robust, it currently assumes the noise source is known. In many practical scenarios, the noise characteristics themselves may be uncertain. Future research is needed to extend these results to "noise-uncertain" regimes. Additionally, while the dual formulation is tractable, calculating the probability of noise falling into complex intersections of norm balls may become a bottleneck in high-dimensional spaces, suggesting a need for further computational optimization.
Summary updated