Learning to Reject Meets Long-tail Learning

We thank the reviewer for their encouraging comments and questions.

What is the candidate value of $\mu$? The authors say that they propose to do a grid search over $\mu$, but what's the search space? If the search space is very large, the speed of the algorithm may be slow.

The reviewer is correct that we apply a grid search to choose $\mu$. However, the search space we use is very small, as detailed below:

• First, using the re-parametrization trick described in Appendix C.1, for $K$ groups, we only need to search over $K-1$ multiplier parameters. For our experiments, we consider settings with two groups (head and tail), requiring us to tune only one multiplier parameter.

• Second, even for this single parameter, we find sufficient to use a small search space. In fact, as noted in Appendix D.3, we pick the multiplier from the small range {1, 6, 11}.

• Third, recall that ours is a post-hoc approach that constructs a simple rejection rule from a pre-trained base model. When varying the multiplier parameter, we are merely changing the rejection rule in Equation 15 without re-training the base model. Therefore carrying out a search over multipliers can be implemented efficiently when $K$ is small.

If I understand correctly, the solution of the optimization problem in equation (9) seems to be heuristic. Is not optimized, but selected from a predefined set? I am afraid that such solutions may not lead to an optimal solution. Will the authors provide some theoretical or empirical analysis of this problem and prove that the solution can be close to optimal?

To confirm that it suffices to use a small search space for the multipliers, we repeated the CIFAR-100 experiments by picking the multiplier from a fine-grained grid {0.25, 0.5, 0.75, …, 11}. We additionally replaced our heuristic procedure in Section 4.2 with a grid search over group prior $\alpha$, choosing the head-to-tail ratio from the range {0, 0.004, 0.008, …, 0.996, 1.0}. We pick the parameter combination that yields the lowest balanced error on a held-out validation set

We show below the balanced error on the test and validation samples, with lower being better (the numbers are slightly different from the paper because they are evaluated on different validation-test splits): \begin{aligned} &~~~~\text{Test} &\text{Validation} \\ \text{Chow's rule}~~~~ &~~~~ 0.512 \pm 0.004 &0.498 \pm 0.011 \\ \text{Plug-in [Balanced, heuristic]}~~~~ &~~~~ 0.291 \pm 0.008 &0.282 \pm 0.007\\ \text{Plug-in [Balanced, grid search]}~~~~ &~~~~ 0.284 \pm 0.007 &0.264 \pm 0.008 \end{aligned}

Although the grid search provides gains on the validation set, on the test set, our heuristic approach to picking the multipliers and group priors yields metrics that are only slightly worse than grid-search. Moreover, the differences are within standard errors.

In the experimental section, only two compared methods are used. I am not sure if more compared methods are needed to validate the effectiveness of the proposal.

To the best of our knowledge, there are no prior L2R methods that can handle general (non-decomposable) evaluation metrics. We therefore compare our approach against representative methods that minimize the standard classification error.

The reason we do not pick an exhaustive list of methods from the L2R literature is because most of these methods share the same optimal solution (Equation 2), which as discussed in Section 3 (Remark 1), is notably different from the optimal solution for the balanced or worst-group errors.

We believe the two baselines we compare against represent two broad categories of L2R approaches, namely post-hoc methods (represented by Chow’s rule), and loss-based methods (represented by by the CSS baseline of Mozannar & Sontag (2020)).

We thank the reviewer for the encouraging comments.

are there any popular metrics not covered?

We are currently able to minimize the balanced error and the worst-group error. Using techniques similar to Yang et al. (2020), our approach can be extended to handle metrics of the form $\psi\left(e_1(h, r), \ldots, e_K(h, r)\right)$ in Secton 5, provided $\psi$ is either convex or fractional-linear. Metrics which do not fall under this family cannot be directly handle by our framework.

This paper considers the learning setting where a classifer and a separate rejector function exist. There is also another framework learning solely one classifier and later uses its output distribution over labels to conduct abstention. Is it impossible for this approach to derive Baye optimal solutions, or it is simply not the scope of the paper?

Thanks for the question. If we understand, the reviewer is referring to settings where the rejector $r(x)$ is strongly coupled with the underlying classifier $h(x)$ or scorer $f(x)$, e.g., is given by the margin or softmax probability of the predicted label.

One can in fact strengthen Equation 2 to derive the optimal choice of $r$ given a fixed $h$. Our main results (e.g., Theorem 2) can similarly be strengthened, and cover the case where one does not jointly optimise over both $h$ and $r$. For a fixed classifier $h$, the optimal rejector in Theorem 2 will take the form:

r\^\*(x) = 1 \~\~\\iff\~\~ \frac{1}{\alpha^*_{[h(x)]}} \cdot \eta_{h(x)}(x) < \sum_{y' \in [L]} \left( \frac{1}{\alpha^*_{ [y'] }} - \mu^*_{ [y'] } \right) \cdot \eta_{y'}(x) - c

Of course, if one does not choose $r$ in an optimal manner, this could lead to a globally sub-optimal solution. We can nonetheless add a discussion of this point.

This is indeed an interesting question! The reviewer is correct that our results can be extended to handle joint optimization of the classifier and rejector.

One possible approach is to formulate the Lagrangian for the constrained optimization problem in Equation (9), and replace the indicators in the resulting Lagrangian objective with a surrogate loss function. We may consider the joint losses proposed recently by Mozannar & Sontag (2020) or Verma & Nalisnick (2022) as candidate surrogate losses. The resulting optimization would involve a maximization over the Lagrange multipliers and a minimization over the classifier-rejector parameters.

We will be happy to include a discussion on this in the paper and mention it as a part of our future work.

We thank the reviewer for the encouraging comments and questions.

Is it possible to say how much grid search over the space of lagrange multiplers is needed to find a good solution?

Using the re-parametrization trick described in Appendix C.1, for $K$ groups, we only need to search over $K-1$ multiplier parameters. For our experiments, we consider settings with two groups (head and tail), requiring us to tune only one multiplier parameter. In our experiments, we find it sufficient to pick this parameter from a small set {1, 6, 11}. We tried a grid search over a fine-grained range but found the gains to be small. Please feel free to also see response to Reviewer 91tX.

the proposed optimization scheme finds a fixed point of the alpha parameters for given values of lagrange multipliers. But is this fixed point unique, and if not, are they all equally good?

The proposed optimization scheme was mainly intended as a heuristic to pick the group prior for the plug-in estimator. To confirm its efficacy, we repeated the CIFAR-100 experiments replacing our heuristic optimization scheme for picking $\alpha$ with a fine-grained grid search. Specifically, we chose the head-to-tail ratio from the range {0, 0.004, 0.008, …, 0.996, 1.0} and the multiplier from the wider range {0.25, 0.5, ..., 11} to yield the minimum balanced error on a held-out validation set.

We show below the balanced error on the test and validation samples, with lower being better (the numbers are slightly different from the paper because they are evaluated on different validation-test splits): \begin{aligned} &~~~~\text{Test} &\text{Validation} \\ \text{Chow's rule}~~~~ &~~~~ 0.512 \pm 0.004 &0.498 \pm 0.011 \\ \text{Plug-in [Balanced, heuristic]}~~~~ &~~~~ 0.291 \pm 0.008 &0.282 \pm 0.007\\ \text{Plug-in [Balanced, grid search]}~~~~ &~~~~ 0.284 \pm 0.007 &0.264 \pm 0.008 \end{aligned}

Although the grid search provides gains on the validation set, on the test set, our heuristic approach yields metrics that are only slightly worse than grid-search. Moreover, the differences are within standard errors.

We thank the reviewer for the encouraging and detailed comments.

Some intuitive justification for the Bayes optimal forms would have been useful. For instance, I would love to know if there's an intuitive explanation for the 'discount' factor

Thanks for the suggestion. To build intuition for the Bayes optimal rejector, let’s consider a simpler risk with a fixed cost of $\beta_y$ for errors on class y:

$\min_{h, r}~ \sum_i \beta_i \cdot \mathbb{P} \left( y = i, h(x) \ne y, r(x) = 0 \right) + c \cdot \mathbb{P}\left( r( x ) = 1 \right)$

The Bayes-optimal rejector for this risk is of the form:

r\^\*(x) = 1 \~\~\\iff\~\~ \\max\_y \\beta\_y \\cdot \\eta_y(x) < \\sum\_i \\beta\_i \\cdot \\eta\_i(x) - c~~~~~~(i)

One may consider the term $\max_y \beta_y \cdot \eta_y(x)$ as a measure of classifier confidence, and the right-hand side as an instance dependent threshold. When $\beta_y = 1, \forall y$, Equation (i) is the same as Chow’s rule: \~\~r\^\*(x) = 1 \~\~\\iff\~\~ \\max\_y \\eta_y(x) < 1 - c.

Note that the rejector $r^*$ is unconstrained in what rejection rate it has on individual classes. Suppose we now additionally constraint the rejector to satisfy a particular rejection rate for each class:

\\min\_{h, \~r}\~ \sum_i \beta_i \cdot \mathbb{P} \left( y = i, h(x) \ne y, r(x) = 0 \right) + c \cdot \mathbb{P}\left( r( x ) = 1 \right)

\\text\{s.t.\}\~\~ \\mathbb\{P\}\\left( r( x ) = 1, y = i \\right) = B_i, \\forall i,

for budgets $B_1, \ldots, B_L$.

In this case, the optimal rejector (under additional distributional assumptions) takes the form: r\^\*(x) = 1 \~\~\\iff\~\~ \\max\_y \beta_y \cdot \eta_y(x) < \sum_i (\beta_i - \mu_i) \cdot \eta_i(x) - c~~~~~~(ii), where the discount factors $\mu_i$s ensure that the rejector satisfies the budget constraints. The optimal rejector again uses the term $\max_y \beta_y \cdot \eta_y(x)$ to measure confidence, but differs in how it thresholds the confidence measure. For example, in the case of binary labels, the rejector can be seen as applying a different constant threshold for each predicted class (see e.g. Corollary 3).

We will be happy to add this discussion to the paper.

I found it a bit of a leap to go from deterministic classifiers in Theorem 2 to stochastic classifiers in Theorem 5.

We would first like to clarify that the balanced error is a special case of the formulation in Equation 16 for $\psi(z_1, \ldots, z_K) = \frac{1}{K} \sum_k z_k$. In this case, $\psi$ happens to be a simple linear function, and the optimal solution is deterministic. When $\psi$ is a general non-linear function (e.g. the worst-group error), the optimal solution admits a stochastic form.

The technical details of how we arrive at a stochastic solution are provided in Appendix B. The key point is that in order to solve Equation 16, we formulate an equivalent optimization problem over the space of confusion matrices $\mathcal{C}$ (see Appendix B.1 and Equation 28). In turn, attaining the optimal confusion matrix requires the use of randomization over $(h, r)$ pairs.

When $\psi$ is linear, as is the case with the balanced error, the optimal solution is a boundary point in $\mathcal{C}$, and therefore a deterministic $(h, r)$ pair. When $\psi$ is non-linear, the optimal solution can be an interior point, and therefore require randomizing between two $(h, r)$ pairs.

We will be happy to provide more details when transitioning from deterministic to stochastic rejectors.

Also, it would be good to draw corollaries where for some simple forms of \psi functions, you indeed get deterministic classifiers and rejectors

Thanks for the suggestion. When $\psi(z_1, \ldots, z_K) = \sum_k \beta_k z_k$ is a linear function with coefficients $\beta_k \in \mathbb{R}$, the optimal solution is the deterministic pair $(h, r)$ given in Theorem 9 in the appendix. In this case, indeed $h^{(1)} = h^{(2)}$ and $r^{(1)} = r^{(2)}$. We will add a note on this in the paper.

Dear Area Chair,

We appreciate the reminder. We are working on the rebuttal and will definitely submit it before the deadline.

Thanks and regards,

Authors