Minimizing the Maximal Loss: How and Why?
This addresses the challenge of improving generalization in ML by focusing on worst-case training errors, which is incremental as it builds on existing methods like AdaBoost and SVM.
The paper tackles the problem of minimizing the maximal loss instead of the average loss in machine learning, showing that better training accuracy can improve generalization performance in some situations, and proposes robust versions to handle outliers.
A commonly used learning rule is to approximately minimize the \emph{average} loss over the training set. Other learning algorithms, such as AdaBoost and hard-SVM, aim at minimizing the \emph{maximal} loss over the training set. The average loss is more popular, particularly in deep learning, due to three main reasons. First, it can be conveniently minimized using online algorithms, that process few examples at each iteration. Second, it is often argued that there is no sense to minimize the loss on the training set too much, as it will not be reflected in the generalization loss. Last, the maximal loss is not robust to outliers. In this paper we describe and analyze an algorithm that can convert any online algorithm to a minimizer of the maximal loss. We prove that in some situations better accuracy on the training set is crucial to obtain good performance on unseen examples. Last, we propose robust versions of the approach that can handle outliers.