A Minimax Approach to Supervised Learning
Given a task of predicting Y from X, a loss function L, and a set of probability distributions Γ on (X, Y ), what is the optimal decision rule minimizing the worstcase expected loss over Γ? In this paper, we address this question by introducing a generalization of the maximum entropy principle. Applying this principle to sets of distributions with marginal on X constrained to be the empirical marginal, we provide a minimax interpretation of the maximum likelihood problem over generalized linear models as well as some popular regularization schemes. For quadratic and logarithmic loss functions we revisit well-known linear and logistic regression models. Moreover, for the 0-1 loss we derive a classifier which we call the minimax SVM. The minimax SVM minimizes the worst-case expected 0-1 loss over the proposed Γ by solving a tractable optimization problem. We perform several numerical experiments to show the power of the minimax SVM in outperforming the SVM.
This paper develops a notion of maximum conditional entropy for arriving at robust Bayes decision rules, where the entropies are generalizations of the usual Shannon entropy, beyond the case of log loss. The formulation is similar to that of Grunwald and Dawid but goes farther (and becomes more relevant for standard learning problems) by allowing for input and label random variables and hence conditional distributions. The first main result shows that (under regularity conditions) the Bayes rule for the distribution that maximizes conditional entropy is also a robust Bayes decision rule (against a set of distributions $\Gamma$). The authors then show an interesting duality result that re-expresses the problem of maximizing conditional entropy as a certain regularized minimization problem that, for exponential families and log loss, corresponds to regularized maximum likelihood. They also connect the suggested procedure to an excess risk bound, showing that with high probability, using their procedure for an empirical distribution guarantees low excess risk versus the hypothesis one obtains when using their procedure (which is still regularized) with oracle access to the true distribution; this result apparently is only for log loss, as per the leadup to Theorem 3. Finally, they show important derivations of key quantities for the method in the case of logistic, 0-1, and quadratic loss, corresponding previously known learning methods or new ones (in the case of minimax SVM). Initial experiments are promising.
\documentclass{article}  \begin{document}    This work represents a very interesting and original generalization of the work of Gr\"unwald and Dawid to the case of learning with inputs $x$. The technical results appear to be correct and the experimental results (which I think are quite preliminary) suggest the minimax SVM might be a good idea. I think the idea of robust Bayes decision rules makes sense and the authors show how under squared loss a connection to the Huber loss emerges. My main comment is that the paper itself is a somewhat difficult read due to terseness at key places, which might limit the impact of the paper. So, the rest of my comments are just geared towards improving the clarity of the paper.  Technically, in every instance where the authors apply Danskin's theorem, it was not really clear what form of Danskin's theorem was being used, and therefore it was difficult to follow the derivation. For instance, the proof of Theorem 2 (in the appendix) is clear up until the end ``Furthermore, applying Danskin's theorem to (9) implies...''. You should provide a citation for the form of Danskin's theorem being used, or just reproduce the theorem in the appendix. Using the form that I found, I could not reproduce (12); I think this comes down to the authors skipping quite a few steps. Also, in equation (24) of the appendix, I could not see how Danskin's theorem give (24), but this might be clarified once you mention the form of Daskins's theorem being used.  I found it difficult to follow the argument from lines 187-194 of the main text, including Corollary 1. It would be useful to explain this better, especially given that you can fit another paragraph in the paper and still stay within 8 pages. In particular, why does the uniform conditional distribution appear in equation (18)? Perhaps you can explain the ``it can be seen that'' with a few sentences. I think the geometric understanding provided is one of the highlights of the paper, so it is unfortunate if the reader cannot fully grasp what you have in mind.   Minor comments:  In equation (10) in the appendix, you are missing a minus sign in front of $\mathbf{A}_i$ both in the middle expression and the rightmost expression. This minus sign does appear in the first line of equation (11), so the mistake apparently was just a typo.  On line 26 of the appendix, you say that ``problem (5) is convex''. But the objective is concave being the entropy (a minimum of a linear function) and indicator are both concave.    \end{document}