Robust Learning via Nested Distributionally Robust Optimization

Jinyi Huang, Jinlong Lei, Guodong ShiICML 2026 · OpenReview

Overview

In real-world machine learning applications, data is rarely pristine. It typically suffers from two distinct types of noise: geometric perturbations (e.g., a slightly rotated image or shifted sensor reading) and statistical contamination (e.g., mislabeled examples or extreme outliers).

Researchers have introduced Nested Distributionally Robust Optimization (Nested DRO), a novel optimization framework designed to handle both types of noise simultaneously. By decoupling "data cleaning" from "geometric robustness" through a bilevel optimization structure, Nested DRO allows models to ignore adversarial outliers without accidentally discarding rare but highly informative "high-leverage" data points.

The Problem: Geometric Conflation

Current Distributionally Robust Optimization (DRO) methods typically attempt to handle both geometric and statistical noise using a single mathematical constraint, such as Optimal Transport. The authors identify a critical flaw in this approach, termed geometric conflation.

Consider a perfectly valid data point that lies far from the dataset's average—a "high-leverage" point. A standard geometric DRO model might measure its spatial distance, incorrectly assume it is an outlier, and discard it. Conversely, a model focused solely on statistical distributions might be fooled by "hidden outliers" that reside in dense, normal-looking regions but carry incorrect labels. The core challenge is decoupling these phenomena: smoothing out geometric noise without "cleaning" away the most crucial, informative parts of the dataset.

The Nested DRO Framework

To resolve geometric conflation, the authors propose a bilevel (nested) optimization structure. Instead of applying a single robustness step, Nested DRO separates the process into two distinct layers:

  1. The Inner Layer (Pessimistic Robustification): This step uses Optimal Transport (OT) to address geometric uncertainty. It asks, "What is the worst-case local perturbation this data could suffer?" effectively smoothing the loss landscape.
  2. The Outer Layer (Optimistic Cleaning): This step uses $\phi$-divergence to handle statistical contamination. Unlike the inner layer, this step is "optimistic"—it searches for the cleanest version of the dataset within a statistical neighborhood. It identifies outliers based on loss consistency rather than spatial distance.

The Mathematical Insight: Variance as a Filter

The authors prove that under certain conditions (such as using $\chi^2$-divergence), this complex nested problem simplifies into a highly tractable "mean-variance" objective:

$$ \text{Expected Loss} - \sqrt{2\epsilon \cdot \text{Variance}} $$

In standard robust learning, a variance term is typically added to enforce conservatism. In Nested DRO, it is subtracted. This "cleaning gain" represents the model's ability to adaptively downweight high-loss outliers, providing a principled justification for filtering out samples that cause high volatility in the loss.

Empirical Validation

The paper evaluates Nested DRO across both synthetic and real-world benchmarks:

  • Synthetic Regression: The authors designed a task where valid data points are placed far from the center (high leverage), while adversarial outliers are placed near the center. Nested DRO consistently outperformed standard DRO and state-of-the-art baselines (like OR-WDRO and UOT-DRO). As data dimensionality increased, the performance gap widened, demonstrating Nested DRO's resistance to the curse of dimensionality.
  • Corrupted CIFAR-10: In a high-dimensional image classification task, the authors applied a "mixed corruption" regime: 10% of images featured hard rotations, 10% had label noise, and 20% suffered from both. Nested DRO achieved 78.78% accuracy. By comparison, standard Empirical Risk Minimization (ERM) reached only 75%, while other robust baselines performed worse than ERM because they aggressively discarded difficult but valid rotated images.

Limitations and Future Work

While Nested DRO offers a significant step forward, the authors note a few limitations:

  • Small Uncertainty Regime: The elegant "mean-variance" closed-form solution is strictly valid when the statistical uncertainty radius ($\epsilon$) is small. In highly noisy environments, this approximation may lose accuracy.
  • Hyperparameter Tuning: Although the authors suggest an "adaptive radius" strategy, the model still requires careful tuning of both the geometric radius ($\rho$) and the cleaning budget ($\epsilon$).

Future work may extend this nested structure to other types of divergence constraints or apply it to sequential decision-making tasks, such as Reinforcement Learning, where decoupling noise from valid edge-case observations is equally critical.

Summary updated

Abstract

Distributionally Robust Optimization (DRO) is widely used to improve model robustness, with existing methods addressing either geometric perturbations (e.g., input shifts) or statistical contamination (e.g., heavy-tailed noise and outliers) effectively. However, these uncertainty sources often co-exist, and coupling them through a single divergence or optimal transport constraint conflates geometric displacement with loss-based outlierness, frequently discarding informative high-leverage samples. We introduce nested DRO, a bilevel formulation that combines an outer optimistic $\phi$-divergence cleaning step with an inner pessimistic optimal-transport robustification step, thereby decoupling geometric smoothing from statistical cleaning. We prove that this structure naturally induces a geometry-invariant, loss-based reweighting mechanism that separates outlier suppression from transport-induced regularization. We derive a tractable strong dual for the resulting non-convex problem and show its equivalence to variance-regularized risk minimization, leading to a clear statistical interpretation of the induced weights. Empirical results on synthetic and real datasets demonstrate that nested DRO consistently outperforms geometry-coupled DRO baselines, particularly under heavy-tailed contamination where preserving high-leverage structure is crucial.
BibTeX
@inproceedings{huang2026robust,
  author = {Jinyi Huang and Jinlong Lei and Guodong Shi},
  title = {{Robust Learning via Nested Distributionally Robust Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=OD3FfNLGe5},
}

Loading related content...

Figure