Toward Minimal-dimensional Convex Calibrated Surrogate Losses for Classification with Rejection

Classification with rejection (CwR) generalizes the standard classification task by providing an extra option of rejection with a cost $c$ smaller than misclassification costs, and the design of its convex calibrated surrogate loss is our central topic. While typical surrogate losses for $K$-class classification operates on $K$-dimensional scoring functions, it has been proved that this dimensionality can be reduced to $\lceil\log_2K\rceil$ for CwR with $c\in(0,0.5]$, rendering more efficient computation. This logarithmic dependency is commonly conjectured to be the lowest possible among any convex calibrated surrogate losses for CwR. Through the lens of property elicitation, we explore even lower-dimensional structures for CwR, by constructing a $2$-dimensional convex calibrated surrogate loss under $c\in(0,0.5)$. This loss dimension is provably optimal among all convex calibrated surrogate losses. The boundary cost $c=0.5$ is more nuanced---we construct a $4$-dimensional convex calibrated loss, improving over the $\lceil\log_2 K\rceil$-dimension when $K>16$. Notably, this breaks the optimal logarithmic dimensionality attainable by the *embedding framework* [Finocchiaro et al., 2024], a widely used loss design principle for polyhedral losses, negatively resolving their conjecture on the dimension optimality.