Research map / Learning theory and algorithms / Prediction and decision losses
Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Reformulates optimization of linear-fractional generalized metrics (F-beta, AM, Jaccard, weighted accuracy) as general cost-sensitive learning with H-consistent surrogates and a binary search/cross-validation over lambda, yielding the METRO algorithm.
Problem
Optimizing generalized metrics (F-beta, AM, Jaccard, weighted accuracy) in binary classification over restricted hypothesis sets, where existing threshold-based methods rely on Bayes-optimal structure and lack finite-sample guarantees.
Approach
Rewrites the ratio-of-linear-losses metric as a fixed-lambda cost-sensitive problem with label-dependent costs, uses margin-based cost-sensitive surrogates with H-consistency bounds, and searches lambda* via binary search or cross-validation.
Key results
- METRO achieves the best F1 on CIFAR-10 (0.9359 ± 0.0041) vs. ERM 0.9004 ± 0.0015 over five runs.
- On JAC for CIFAR-10, METRO reaches 0.6575 ± 0.0018 vs. 0.4689 for ERM and 0.6428 for the best prior baseline.
- METRO outperforms all four baselines across all three datasets and all reported metrics in the table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-10 | F1: 0.9185 $\pm$ 0.0029 -> 0.9359 $\pm$ 0.0041 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-100 | F1: 0.9343 $\pm$ 0.0111 -> 0.9405 $\pm$ 0.0103 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · SVHN | F1: 0.9682 $\pm$ 0.0021 -> 0.9713 $\pm$ 0.0029 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-10 | F0.5: 0.9507 $\pm$ 0.0036 -> 0.9585 $\pm$ 0.0023 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-100 | F0.5: 0.9515 $\pm$ 0.0105 -> 0.9759 $\pm$ 0.0115 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · SVHN | F0.5: 0.9746 $\pm$ 0.0011 -> 0.9807 $\pm$ 0.0015 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-10 | F1.5: 0.9312 $\pm$ 0.0044 -> 0.9459 $\pm$ 0.0030 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-100 | F1.5: 0.9345 $\pm$ 0.0118 -> 0.9449 $\pm$ 0.0115 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · SVHN | F1.5: 0.9702 $\pm$ 0.0023 -> 0.9771 $\pm$ 0.0018 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-10 | JAC: 0.6428 $\pm$ 0.0130 -> 0.6575 $\pm$ 0.0018 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · CIFAR-100 | JAC: 0.4924 $\pm$ 0.0152 -> 0.5017 $\pm$ 0.0046 | Helped |
| Use METRO instead of Algorithm in [cite] | Three-hidden-layer CNN · SVHN | JAC: 0.4934 $\pm$ 0.0019 -> 0.4965 $\pm$ 0.0024 | Helped |
Surprising findings
- The best linear hypothesis for F0.5 can differ substantially in orientation from the thresholded best-in-class SVM, showing threshold-based methods fail to find the best in-class predictor.
Limitations
- Experiments use standard image datasets with balanced-ish binary tasks rather than strongly imbalanced data, as acknowledged by the authors.
- Generalization bound constants may be loose; lambda is tuned by cross-validation in practice.
- Over-parameterized neural networks yield large epsilon_m, so the finite-sample guarantees become weak.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 SVHN
Benchmarks: CIFAR-10 CIFAR-100 SVHN
Metrics: F1 F0.5 F1.5 Jaccard similarity coefficient
Baselines: ERM Algorithm 1 (Narasimhan et al.) Algorithm 2 (Narasimhan et al.) theta-weighted logistic algorithm (F1 method)
Builds on: H-consistency bounds cost-sensitive learning Narasimhan et al. two-stage thresholding for generalized metrics
Closest papers by meaning
- Post-Processing Guarantees for Classification under Linear-Fractional Performance Metrics (NeurIPS 2026 · similarity 0.89)
- Optimal Binary Classification Beyond Accuracy (NeurIPS 2022 · similarity 0.89)
- A General Online Algorithm for Optimizing Complex Performance Metrics (ICML 2024 · similarity 0.87)
- Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data (ICML 2025 · similarity 0.86)
- Improved Balanced Classification with Theoretically Grounded Loss Functions (NeurIPS 2025 · similarity 0.85)
- To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.