An official website of the United States government
To train machine learning models that are robust to distribution shifts in the data, distributionally robust optimization (DRO) has been proven very effective. However, the existing approaches to learning a distributionally robust model either require solving complex optimization problems such as semidefinite programming or a first-order method whose convergence scales linearly with the number of data samples -- which hinders their scalability to large datasets. In this paper, we show how different variants of DRO are simply instances of a finite-sum composite optimization for which we provide scalable methods. We also provide empirical results that demonstrate the effectiveness of our proposed algorithm with respect to the prior art in order to learn robust models from very large datasets.
more »
« less
This content will become publicly available on November 24, 2026
On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
Abstract Distributionally Favorable Optimization (DFO) is a framework for decision-making under uncertainty, with applications spanning various fields, including reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge– the application of the inner infimum operator often fails to retain the convexity. In light of this challenge, we study the tractability and complexity of DFO. We establish sufficient and necessary conditions for determining when DFO problems are tractable (i.e., solvable in polynomial time) or intractable (i.e., not solvable in polynomial time). Despite the typical nonconvex nature of DFO problems, our results show that they are mixed-integer convex programming representable (MICP-R), thereby enabling solutions via standard optimization solvers. Finally, we numerically validate the efficacy of our MICP-R formulations.
more »
« less
- Award ID(s):
- 2246414
- PAR ID:
- 10649284
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Mathematical Programming
- ISSN:
- 0025-5610
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper explores the micro Energy-Water-Hydrogen (m-EWH) nexus, an engineering system designed to reduce carbon emissions in the power sector. The m-EWH nexus leverages renewable energy sources (RES) to produce hydrogen via electrolysis, which is then combined with carbon captured from fossil fuel power plants to mitigate emissions. To address the uncertainty challenges posed by RES, this paper proposes a real-time decision-making framework for the m-EWH nexus, which requires the rapid solution of large-scale mixed-integer convex programming (MICP) problems. To this end, we develop a machine learning-accelerated solution method for real-time optimization (MARO), comprising three key modules: (1) an active constraint and integer variable prediction module that rapidly solves MICP problems using historical optimization data; (2) an optimal strategy selection module based on feasibility ranking to ensure solution feasibility; and (3) a feature space extension and refinement module to improve solution accuracy by generating new features and refining existing ones. The effectiveness of the MARO method is validated through two case studies of the m-EWH nexus, demonstrating its capability to swiftly and accurately solve MICP problems for this complex system.more » « less
-
Summary Estimators based on Wasserstein distributionally robust optimization are obtained as solutions of min-max problems in which the statistician selects a parameter minimizing the worst-case loss among all probability models within a certain distance from the underlying empirical measure in a Wasserstein sense. While motivated by the need to identify optimal model parameters or decision choices that are robust to model misspecification, these distributionally robust estimators recover a wide range of regularized estimators, including square-root lasso and support vector machines, among others. This paper studies the asymptotic normality of these distributionally robust estimators as well as the properties of an optimal confidence region induced by the Wasserstein distributionally robust optimization formulation. In addition, key properties of min-max distributionally robust optimization problems are also studied; for example, we show that distributionally robust estimators regularize the loss based on its derivative, and we also derive general sufficient conditions which show the equivalence between the min-max distributionally robust optimization problem and the corresponding max-min formulation.more » « less
-
Distributionally robust optimization (DRO) has been shown to offer a principled way to regularize learning models. In this paper, we find that Tikhonov regularization is distributionally robust in an optimal transport sense (i.e. if an adversary chooses distributions in a suitable optimal transport neighborhood of the empirical measure), provided that suitable martingale constraints are also imposed. Further, we introduce a relaxation of the martingale constraints which not only provide a unified viewpoint to a class of existing robust methods but also lead to new regularization tools. To realize these novel tools, provably efficient computational algorithms are proposed. As a byproduct, the strong duality theorem proved in this paper can be potentially applied to other problems of independent interest.more » « less
-
Entropy-Regularized Wasserstein Distributionally Robust Optimization Uncertainty in data poses a central challenge in operations research. Distributionally robust optimization (DRO) offers a principled framework for addressing this challenge by producing solutions resilient to distributional variations. Among various DRO approaches, the Wasserstein DRO has received significant attention though its computational efficiency relies on stringent assumptions, and its worst case distributions are typically discrete. In “Sinkhorn Distributionally Robust Optimization,” Wang, Gao, and Xie leverage the Sinkhorn distance—an entropy-regularized variant of the Wasserstein distance—to more realistically model uncertainty, enhancing computational efficiency. The authors establish a strong duality reformulation and propose a first order stochastic mirror descent algorithm with provable complexity guarantees for general loss functions. Unlike Wasserstein DRO, Sinkhorn DRO yields continuous worst case distributions, offering a more flexible representation of practical uncertainties. Extensive experiments in the newsvendor problem, portfolio optimization, and adversarial classification demonstrate its superior performance in both out-of-sample performance and efficiency.more » « less
