A Minimax Approach to Supervised Learning

By Farzan Farnia, David Tse. 2016

120 citations recorded by the source corpus.

Given a task of predicting $Y$ from $X$, a loss function $L$, and a set of probability distributions $\Gamma$ on $(X,Y)$, what is the optimal decision rule minimizing the worst-case expected loss over $\Gamma$? In this paper, we address this question by introducing a generalization of the principle of maximum entropy. Applying this principle to sets of distributions with marginal on $X$ constrained to be the empirical marginal from the data, we develop a general minimax approach for supervised learning problems. While for some loss functions such as squared-error and log loss, the minimax approach rederives well-knwon regression models, for the 0-1 loss it results in a new linear classifier which we call the maximum entropy machine. The maximum entropy machine minimizes the worst-case 0-1 loss over the structured set of distribution, and by our numerical experiments can outperform other well-known linear classifiers such as SVM. We also prove a bound on the generalization worst-case error in the minimax approach.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Agnostic Federated Learning (2019, methodology): “Our optimization solution also differs from the work of Farnia and Tse (2016) and Lee and Raginsky (2017) on local minimax results, where samples are drawn from a single source D , and where the generalization error is minimized over a set of locally ambiguous distributions ̂ D , where ̂ D is the…”
Regularization via Mass Transportation (2017, background): “Farnia and Tse [17] investigate distributionally robust learning models with moment ambiguity sets that restrict the marginal of the features to the empirical marginal.”
Minimax Statistical Learning and Domain Adaptation with Wasserstein Distances (2017, methodology): “, via moment constraints [3], f -divergence balls [4], and Wasserstein balls [5, 6, 7].”
Distributionally Robust Optimization: A Review (2019, background): “Farnia and Tse [103] form the ambiguity set of distributions by matching the marginal of covariates to the empirical marginal of covariates while keeping the cross-moments between the response variables and covariates close enough (with respect to some norm) to that of the joint empirical distributi”