Principled Algorithms for Optimizing Generalized Metrics in Binary Classification

We thank the reviewer for their strong support of our work. Below please find responses to specific questions.

1. Questions: The authors propose to leverage Rademacher bounds, which can be approximated via classical learning process such as ERM. I am curious on the inherent difficulty in the metric optimization step (i.e., finding $\lambda^\*$) in this paper. For example, is metric optimization at least as difficult as supervised learning multiple times with alternative losses that are independent of the metric learning process? Anyway, the answer to this question may not let me increase my evaluation to this paper, since it cannot be increased anymore.

Response: This is a natural question. The reviewer is asking about the difficulty of directly optimizing a general metric defined as the ratio of the expectations of two loss functions, both linear in ${\mathsf h}$, where ${\mathsf h}(x) = \text{sign}(h(x))$.

While the metric is quasi-concave in ${\mathsf h}$, its optimization with respect to $h$ is NP-hard (even with a constant denominator), even for a linear hypothesis set. In contrast, each surrogate loss optimization problem we consider (framed as supervised learning) can be solved in polynomial time over a convex hypothesis set, as the surrogate loss functions we adopt are convex.

Moreover, directly optimizing the empirical ratio of the numerator and denominator may not yield a provably good approximation of the metric, since their expectation does not align with the ratio of expectations.

We will include this discussion in the final version. If our interpretation of the reviewer’s question is incorrect, please clarify, and we will be happy to address it.

Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.

1. Weaknesses: The experiments were limited to the classic image classification task. Algorithms were not applied to scenarios such as significant class imbalance, which is a fundamental motivation for this paper as stated in Section 1.

Response: Thank you for the valuable suggestion. Following previous work, we used standard image classification datasets for our empirical evaluation to demonstrate the effectiveness of our methods compared to prior baselines. However, we agree that evaluating our algorithms on more imbalanced datasets would be beneficial, and we plan to include such experiments and comparisons in the final version.

2. Questions: I am curious about how the runtime of the proposed method compares to other baselines.

Response: The per-epoch computational cost of our method is comparable to that of Algorithm 2 in Koyejo et al. (2014). Both methods involve a single hyperparameter, and for a fixed value of this parameter, the computational cost is similar to training a standard binary classifier using a standard surrogate loss. We will include a more in-depth discussion of this topic in the relevant section of the paper.

Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.

1. Method: Thank you for the insightful comments. The quantities $\hat{\mathcal{E}} _{\ell^{\lambda}}$ and $\hat{h}$ are approximated using data sampled from the same distribution, but they can be obtained from different samples. In practice, as done in Koyejo et al. (2014), we can split the training data into two parts: $\hat{\lambda}$ is obtained from one part, and then used to train the hypothesis $\hat{h} _{\hat{\lambda}}$ on the other.

Theorems 5.4 and 5.5 remain valid as long as the data are sampled independently from the same distribution. Regarding your observation: in the case of an overparameterized model, it is true that $\mathcal{E} _{\ell^{\lambda}}(\hat{h} _{\lambda}) \leq 2\epsilon_m$ still holds by the standard generalization bound (Mohri et al., 2018), but the value of $\epsilon_m$ may be larger due to the high complexity of the model. As you correctly noted, $\epsilon_m$ becomes small only when the sample size is sufficiently large relative to the complexity of the hypothesis set. This limitation applies broadly to most generalization bounds for complex neural networks.

The current analysis of overparameterized settings typically requires alternative tools, particularly those that account for the optimization algorithm (e.g., SGD) and its dynamics. Such analyses often apply only to more restricted model families.

We will elaborate on these points and revise the presentation of Algorithms 2 and 3 for improved clarity in the final version.

2. Experiments: Thank you for the valuable suggestions. As indicated on line 435 (left), we used the METRO Algorithm 3 in our experiments. We will follow the reviewer’s recommendation to add more details about the datasets and include additional experimental results using alternative models in the final version. We also plan to incorporate experiments on more imbalanced datasets, as suggested by Reviewer wfsZ.

3. Relation To Broader Scientific Literature: First, we should emphasize that the guarantees for these methods differ fundamentally. Our METRO algorithms for optimizing general metrics are backed by strong theoretical guarantees that apply to arbitrary hypothesis sets and include finite-sample bounds. In contrast, prior methods (Koyejo et al., 2014) provide only Bayes-consistency guarantees, which hold solely for the class of all measurable functions and offer no convergence bound. Moreover, their approach lacks convergence rate guarantees for parameter tuning, unlike our finite-sample bounds.

Beyond these theoretical advantages, a key limitation of prior methods is their dependence on the structure of the Bayes-optimal solution. Since the Bayes-optimal predictor for a given metric often differs from binary classification only by an offset, their approach first trains a binary classifier and then selects an optimal threshold or offset. However, this strategy fails when the best predictor within a restricted hypothesis set does not align with the Bayes-optimal form (see Figure 1). Consequently, irrespective of parameter estimation or tuning, their approach does not succeed in general, as our example illustrates.

In contrast, our approach and algorithms provide convergence rate guarantees for arbitrary hypothesis sets and do not rely on the specific form of the Bayes-optimal solution, ensuring robust and theoretically grounded optimization.

4. Essential References Not Discussed: We thank the reviewer for pointing out these relevant references on optimizing the F-score. They are indeed closely related to our work, and we will be sure to include and discuss them in the final version.