Research map / Learning theory and algorithms / Prediction and decision losses

Universal generalization guarantees for Wasserstein distributionally robust models

ICLR 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Distributionally robust optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Establishes exact (dimension-free, 1/sqrt(n) radius) generalization guarantees for Wasserstein distributionally robust models with arbitrary continuous costs and nonsmooth parametric losses, plus excess-risk bounds and an extension to doubly entropy-regularized WDRO.

Problem

Generalization guarantees for Wasserstein distributionally robust optimization were previously only approximate, restricted to specific costs/losses (e.g., squared norm, smooth losses), or required radii scaling badly with dimension; exact guarantees for nonsmooth losses (e.g., deep nets with ReLU)

Approach

Proves exact generalization via a nonsmooth-analysis argument on the convex dual of WDRO: a dual lower bound lambda_low (from a limit of the maximal-radius function at zero, giving the critical radius) plus uniform concentration of Lipschitz functions, yielding exact bounds for rho scaling as 1/sqrt(n) without convexity, differentiability, or squared-cost restrictions; extended to doubly regulariz

Key results

• Exact generalization guarantee: for rho > alpha/sqrt(n) and n large enough, the empirical robust risk upper-bounds... actually lower-bounds the true risk E_P[f] for all f with high probability, under compact sample space and finite Dudley entropy.
• Excess risk bound: R-hat_rho(f) <= E_P[f] + Lip_F (rho + alpha/sqrt(n))^(1/p) for c = d^p with Lipschitz losses.
• Extension to doubly regularized WDRO gives an inexact guarantee where the regularized robust risk bounds E_Q[f] minus epsilon KL(pi^{P,Q} || pi_0), with lambda_low decaying as exp(-||F||_inf/epsilon).

Surprising findings

• Dual lower bound lambda_low exists despite nonsmoothness of the dual generator, obtained by passing to the limit of the maximal-radius function at zero.

Limitations

• Requires compact sample space and finite Dudley entropy of the loss class, excluding unbounded/heavy-tailed data without truncation.
• Constants (lambda_low, rho_crit, alpha, beta) are generally not explicit except for linear and logistic regression.
• Regularized case yields only an inexact guarantee and the lower dual bound lacks Lipschitzness as mu goes to zero.

Experimental setup

Metrics: generalization bound validity excess risk bound

Baselines: Gao, Chen and Kleywegt (2022) exact generalization results Blanchet et al. linear model results Azizian et al. regularized WDRO generalization

Builds on: Wasserstein distributionally robust optimization duality uniform concentration for Lipschitz function classes (Dudley entropy) Sinkhorn/entropic optimal transport regularized WDRO

Closest papers by meaning

• Exact Generalization Guarantees for (Regularized) Wasserstein Distributionally Robust Models (NeurIPS 2023 · similarity 0.96)
• Generalization Bounds for (Wasserstein) Robust Optimization (NeurIPS 2021 · similarity 0.92)
• Provable Robust Overfitting Mitigation in Wasserstein Distributionally Robust Optimization (ICLR 2025 · similarity 0.89)
• Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.87)
• Knowledge-Guided Wasserstein Distributionally Robust Optimization (ICML 2025 · similarity 0.87)
• Wasserstein Distributionally Robust Optimization through the Lens of Structural Causal Models and Individual Fairness (NeurIPS 2024 · similarity 0.86)