Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes

Abstract

We consider optimal transport based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g. strong convexity even if the non-DRO problem was not strongly convex, a suitable scaling of the Lagrangian for the DRO constraint, etc. which are crucial for the design of efficient algorithms). As a consequence of these results, one can develop efficient optimization procedures which have the same sample and iteration complexity as a natural non-DRO benchmark algorithm such as stochastic gradient descent.

arXiv comment67 pages, 6 figures, 3 tables

References in corpus (12)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Generalizing to Unseen Domains via Adversarial Data Augmentation
• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
• Distributionally Robust Logistic Regression
• Regularization via Mass Transportation
• Parametric Local Metric Learning for Nearest Neighbor Classification
• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• Robust Hypothesis Testing Using Wasserstein Uncertainty Sets
• Decomposition Algorithm for Distributionally Robust Optimization using Wasserstein Metric
• Confidence Regions in Wasserstein Distributionally Robust Estimation

Cited by in corpus (17)

• Certifying Some Distributional Robustness with Principled Adversarial Training
• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Distributionally Robust Optimization: A Review
• Wasserstein Distributionally Robust Stochastic Control: A Data-Driven Approach
• Distributionally Robust Optimization and Generalization in Kernel Methods
• A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression
• Robustifying Conditional Portfolio Decisions via Optimal Transport
• Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine
• Distributionally Robust Parametric Maximum Likelihood Estimation
• Learning-based distributionally robust motion control with Gaussian processes
• Robust Graph Learning Under Wasserstein Uncertainty
• Frank-Wolfe Methods in Probability Space
• Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis
• Adversarially Robust Kernel Smoothing
• Human Imperceptible Attacks and Applications to Improve Fairness
• Robust Machine Learning via Privacy/Rate-Distortion Theory
• Minimax control of ambiguous linear stochastic systems using the Wasserstein metric