  This paper tackles the problem of the worst-class error rate, instead of the
standard error rate averaged over all classes. For example, a three-class
classification task with class-wise error rates of 10\%, 10\%, and 40\% has a
worst-class error rate of 40\%, whereas the average is 20\% under the
class-balanced condition. The worst-class error is important in many
applications. For example, in a medical image classification task, it would not
be acceptable for the malignant tumor class to have a 40\% error rate, while
the benign and healthy classes have 10\% error rates.We propose a boosting
algorithm that guarantees an upper bound of the worst-class training error and
derive its generalization bound. Experimental results show that the algorithm
lowers worst-class test error rates while avoiding overfitting to the training
set.
