Minimax Lower Bounds for Cost Sensitive Classification
This work addresses the theoretical underpinnings of cost-sensitive classification, which is crucial for mission-critical applications, but it is incremental as it builds on existing lower bound results.
The paper tackles the problem of understanding the fundamental limits of cost-sensitive classification by extending minimax lower bounds from balanced binary classification, highlighting the impact of misclassification costs on problem hardness.
The cost-sensitive classification problem plays a crucial role in mission-critical machine learning applications, and differs with traditional classification by taking the misclassification costs into consideration. Although being studied extensively in the literature, the fundamental limits of this problem are still not well understood. We investigate the hardness of this problem by extending the standard minimax lower bound of balanced binary classification problem (due to \cite{massart2006risk}), and emphasize the impact of cost terms on the hardness.