Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees
Distributionally robust optimization (DRO) has shown lot of promise in providing robustness in learning as well as sample based optimization problems. We endeavor to provide DRO solutions for a class of sum of fractionals, non-convex optimization which is used for decision making in prominent areas such as facility location and security games. In contrast to previous work, we find it more tractable to optimize the equivalent variance regularized form of DRO rather than the minimax form. We transform the variance regularized form to a mixed-integer second order cone program (MISOCP), which, while guaranteeing near global optimality, does not scale enough to solve problems with real world data-sets. We further propose two abstraction approaches based on clustering and stratified sampling to increase scalability, which we then use for real world data-sets. Importantly, we provide near global optimality guarantees for our approach and show experimentally that our solution quality is better than the locally optimal ones achieved by state-of-the-art gradient-based methods. We experimentally compare our different approaches and baselines, and reveal nuanced properties of a DRO solution.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingFormSimilar Papers 제목 키워드 기반
Adversarially Robust Kernel Smoothing
We propose a scalable robust learning algorithm combining kernel smoothing and robust optimization. Our method is motivated by the convex analysis perspective of distributionally robust optimization based on probability …
BIG-bench Machine LearningFormA Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning
We consider a distributionally robust formulation of stochastic optimization problems arising in statistical learning, where robustness is with respect to uncertainty in the underlying data distribution. Our formulation …
Stochastic OptimizationWasserstein Distributionally Robust Optimization: A Three-Player Game Framework
Wasserstein distributionally robust optimization (DRO) has recently received significant attention in machine learning due to its connection to generalization, robustness and regularization. Existing methods only conside…
Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks
The reliable deployment of neural networks in control systems requires rigorous robustness guarantees. In this paper, we obtain tight robustness certificates over convex attack sets for min-max representations of ReLU ne…
image-classificationImage ClassificationDistributionally Robust Optimization with Correlated Data from Vector Autoregressive Processes
We present a distributionally robust formulation of a stochastic optimization problem for non-i.i.d vector autoregressive data. We use the Wasserstein distance to define robustness in the space of distributions and we sh…
Stochastic Optimization