Optimization Online


Regularization via Mass Transportation

Soroosh Shafieezadeh-Abadeh (soroosh.shafiee***at***epfl.ch)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)
Peyman Mohajerin Esfahani (p.mohajerinesfahani***at***tudelft.nl)

Abstract: The goal of regression and classification methods in supervised learning is to minimize the empirical risk, that is, the expectation of some loss function quantifying the prediction error under the empirical distribution. When facing scarce training data, overfitting is typically mitigated by adding regularization terms to the objective that penalize hypothesis complexity. In this paper we introduce new regularization techniques using ideas from distributionally robust optimization, and we give new probabilistic interpretations to existing techniques. Specifically, we propose to minimize the worst-case expected loss, where the worst case is taken over the ball of all (continuous or discrete) distributions that have a bounded transportation distance from the (discrete) empirical distribution. By choosing the radius of this ball judiciously, we can guarantee that the worst-case expected loss provides an upper confidence bound on the loss on test data, thus offering new generalization bounds. We prove that the resulting regularized learning problems are tractable and can be tractably kernelized for many popular loss functions. We validate our theoretical out-of-sample guarantees through simulated and empirical experiments.

Keywords: Distributionally robust optimization, optimal transport, supervised learning

Category 1: Robust Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 10/26/2017
Entry Accepted: 10/26/2017
Entry Last Modified: 07/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society