Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models

Fengqiao Luo, Sanjay Mehrotra*

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We study distributionally robust optimization (DRO) problems where the ambiguity set is defined using the Wasserstein metric and can account for a bounded support. We show that this class of DRO problems can be reformulated as decomposable semi-infinite programs. We use a cutting-surface method to solve the reformulated problem for the general nonlinear model, assuming that we have a separation oracle. As examples, we consider the problems arising from the machine learning models where variables couple with data in a bilinear form in the loss function. We present a branch-and-bound algorithm to solve the separation problem for this case using an iterative piece-wise linear approximation scheme. We use a distributionally robust generalization of the logistic regression model to test our algorithm. We also show that it is possible to approximate the logistic-loss function with significantly less linear pieces than those needed for a general loss function to achieve a given accuracy when generating a cutting surface. Numerical experiments on the distributionally robust logistic regression models show that the number of oracle calls are typically 20–50 to achieve 5-digit precision. The solution found by the model has better predicting power than classical logistic regression when the sample size is small.

Original languageEnglish (US)
Pages (from-to)20-35
Number of pages16
JournalEuropean Journal of Operational Research
Volume278
Issue number1
DOIs
StatePublished - Oct 1 2019

Fingerprint

Wasserstein Metric
Robust Optimization
Decomposition Algorithm
Loss Function
Regression Model
Logistic Regression Model
Logistics
Decomposition
Optimization Problem
Piecewise Linear Approximation
Robust Regression
Branch and Bound Algorithm
Bilinear form
Logistic Regression
Approximation Scheme
Decomposable
Digit
Nonlinear Model
Machine Learning
Sample Size

Keywords

  • Distributionally robust optimization
  • Logistic regression
  • Robustness and sensitivity analysis
  • Semi-infinite programming
  • Wasserstein metric

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this

@article{eeb3b5712713475c91e421dd2cc5e63e,
title = "Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models",
abstract = "We study distributionally robust optimization (DRO) problems where the ambiguity set is defined using the Wasserstein metric and can account for a bounded support. We show that this class of DRO problems can be reformulated as decomposable semi-infinite programs. We use a cutting-surface method to solve the reformulated problem for the general nonlinear model, assuming that we have a separation oracle. As examples, we consider the problems arising from the machine learning models where variables couple with data in a bilinear form in the loss function. We present a branch-and-bound algorithm to solve the separation problem for this case using an iterative piece-wise linear approximation scheme. We use a distributionally robust generalization of the logistic regression model to test our algorithm. We also show that it is possible to approximate the logistic-loss function with significantly less linear pieces than those needed for a general loss function to achieve a given accuracy when generating a cutting surface. Numerical experiments on the distributionally robust logistic regression models show that the number of oracle calls are typically 20–50 to achieve 5-digit precision. The solution found by the model has better predicting power than classical logistic regression when the sample size is small.",
keywords = "Distributionally robust optimization, Logistic regression, Robustness and sensitivity analysis, Semi-infinite programming, Wasserstein metric",
author = "Fengqiao Luo and Sanjay Mehrotra",
year = "2019",
month = "10",
day = "1",
doi = "10.1016/j.ejor.2019.03.008",
language = "English (US)",
volume = "278",
pages = "20--35",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

TY - JOUR

T1 - Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models

AU - Luo, Fengqiao

AU - Mehrotra, Sanjay

PY - 2019/10/1

Y1 - 2019/10/1

N2 - We study distributionally robust optimization (DRO) problems where the ambiguity set is defined using the Wasserstein metric and can account for a bounded support. We show that this class of DRO problems can be reformulated as decomposable semi-infinite programs. We use a cutting-surface method to solve the reformulated problem for the general nonlinear model, assuming that we have a separation oracle. As examples, we consider the problems arising from the machine learning models where variables couple with data in a bilinear form in the loss function. We present a branch-and-bound algorithm to solve the separation problem for this case using an iterative piece-wise linear approximation scheme. We use a distributionally robust generalization of the logistic regression model to test our algorithm. We also show that it is possible to approximate the logistic-loss function with significantly less linear pieces than those needed for a general loss function to achieve a given accuracy when generating a cutting surface. Numerical experiments on the distributionally robust logistic regression models show that the number of oracle calls are typically 20–50 to achieve 5-digit precision. The solution found by the model has better predicting power than classical logistic regression when the sample size is small.

AB - We study distributionally robust optimization (DRO) problems where the ambiguity set is defined using the Wasserstein metric and can account for a bounded support. We show that this class of DRO problems can be reformulated as decomposable semi-infinite programs. We use a cutting-surface method to solve the reformulated problem for the general nonlinear model, assuming that we have a separation oracle. As examples, we consider the problems arising from the machine learning models where variables couple with data in a bilinear form in the loss function. We present a branch-and-bound algorithm to solve the separation problem for this case using an iterative piece-wise linear approximation scheme. We use a distributionally robust generalization of the logistic regression model to test our algorithm. We also show that it is possible to approximate the logistic-loss function with significantly less linear pieces than those needed for a general loss function to achieve a given accuracy when generating a cutting surface. Numerical experiments on the distributionally robust logistic regression models show that the number of oracle calls are typically 20–50 to achieve 5-digit precision. The solution found by the model has better predicting power than classical logistic regression when the sample size is small.

KW - Distributionally robust optimization

KW - Logistic regression

KW - Robustness and sensitivity analysis

KW - Semi-infinite programming

KW - Wasserstein metric

UR - http://www.scopus.com/inward/record.url?scp=85063958018&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063958018&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2019.03.008

DO - 10.1016/j.ejor.2019.03.008

M3 - Article

AN - SCOPUS:85063958018

VL - 278

SP - 20

EP - 35

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -