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
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:
- 10649054
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Mathematical Programming
- ISSN:
- 0025-5610
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We present here classes of integer programming problems that are solvable efficiently and with combinatorial flow algorithms. The problems are characterized by constraints that have either at most two variables per inequality that appear with opposite sign coefficients, or have in addition a third variable that appears only in one constraint. Such integer programs, referred to here as monotone IP2 or IP3, are shown to be solvable in polynomial time for polynomially bounded variables. This article demonstrates the vast applicability of IP2 and IP3 as models for integer programs in multiple scenarios. Since the problems are easily recognized, the knowledge of their structure enables one to determine easily that they are efficiently solvable. The variety of applications, that previously were not known to be solved as efficiently, underlies the importance of recognizing this structure and, if appropriate, formulating problems as monotone IP2 or IP3. Additionally, if there is flexibility in the modeling of an integer programming problem, the formulation choice as monotone IP2 or IP3 leads to efficient algorithms, whereas slightly different modeling choices would lead to NP‐hard problems.more » « less
-
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
