Calibrated Surrogate Maximization of Linear-fractional Utility in Binary Classification

• Non-decomposable metrics such as Fβ-measure and Jaccard index cannot use per-example loss decomposition, making standard M-estimation difficult.Source: §1 · p. 1
• Linear-fractional metrics generalize BER, Fβ-measure, Jaccard index, Gower-Legendre index, and weighted accuracy.Source: §1 · p. 1
• The paper proposes a calibrated surrogate utility that lower-bounds the target utility and identifies conditions under which surrogate maximization also maximizes the true utility.Source: §1 · p. 2
• The approach combines concave and quasi-concave optimization, provides an unbiased gradient-direction estimator, and establishes consistency through Z-estimation.Source: §1 · p. 2

• Binary classifiers are evaluated through TP, FN, FP, and TN, whose trade-offs determine the chosen performance metric.Source: §2 · p. 2
• A linear-fractional utility is defined over classifiers and encompasses metrics that express preferences over confusion-matrix entries.Source: §2 · p. 2
• The paper adopts population utility, defined as a linear-fractional transform of the population confusion matrix, to avoid estimating the class-posterior probability.Source: §2 · p. 2
• Traditional ERM minimizes a surrogate risk for accuracy, but the paper instead seeks to maximize the selected utility directly.Source: §2 · p. 3
• Direct optimization is difficult because the true utility contains the 0/1-loss, which is computationally intractable in the relevant formulation.Source: §2 · p. 3

3.1 Lower Bounding True Utility

• Surrogate class-conditional scores replace 0/1-loss terms with φ and are designed so that TP-related terms increase while FP-related terms decrease under optimization.Source: §3.1 · p. 3
• The surrogate utility Uφ is a lower bound of the true utility U whenever φ(t) ≥ ℓ(t), so maximizing Uφ targets a certified lower bound.Source: §3.1 · p. 3

3.2 Tractability of Surrogate Utility

• The empirical fractional objective is generally neither concave nor quasi-concave globally, but its numerator is concave and the fraction is quasi-concave over ¯F.Source: §3.2 · p. 4

3.3 Gradient Direction Estimator

• Although the empirical fractional utility is biased, its gradient is an unbiased estimate of the expected gradient direction, enabling normalized gradient ascent and BFGS updates.Source: §3.3 · pp. 4–5

3.2 Tractability of Surrogate Utility

• The hybrid algorithm first maximizes the concave numerator, then optimizes and maximizes the fractional surrogate within the quasi-concave region.Source: §3.2 · p. 4, Figure 2 · p. 5

Calibration framework

• U-calibration links surrogate maximization to true-utility maximization over all measurable functions.If Uφ is U-calibrated, the surrogate can be optimized instead of the true utility; approximation error is outside this analysis.Source: §4 · p. 5
• τ-discrepancy requires a convex loss whose gradient is steeper on the negative side near zero, controlling TP/FP surrogate steepness.The condition is sufficient for calibration, not established as necessary.Source: §4 · pp. 5–6

Scope

• The calibration analyses for Fβ and Jaccard are stated to extend to general linear-fractional utilities.The paper positions these two metrics as specific cases of the broader linear-fractional framework.Source: §4 · pp. 5–6

Fβ-measure

• For the Fβ-measure, differentiable-almost-everywhere, convex, non-increasing losses satisfying the theorem’s condition yield Fβ-calibration.The paper presents this as a calibrated surrogate utility for direct Fβ optimization, including τ-discrepant losses.Source: §4 · p. 6

Jaccard index

• For the Jaccard index, analogous loss conditions, including τ-discrepancy over a suitable range, yield Jaccard-calibration.The same class of τ-discrepant losses can be used for Jaccard optimization, with τ selected by cross-validation or fixed.Source: §4 · p. 6

Estimation setup

• The estimator uses a linear-in-input model and reduces surrogate-utility maximization to solving an estimating-equation system.The parameter space is compact, and the population and empirical derivative systems define the relevant roots.Source: §5 · p. 6

Uniform convergence

• Uniform convergence holds under boundedness and Lipschitz conditions on the derivative-related functions, with separate smoothness allowed across τ-discrepant loss domains.The lemma supplies the basis for the subsequent consistency result.Source: §5 · pp. 6–7

Consistency

• Under identifiability and the stated uniform-convergence condition, the empirical maximizer is consistent for the population surrogate-utility maximizer.The result assumes the population estimating function has an identifiable zero.Source: §5 · p. 7
• Identifiability requires Vφ(fθ) to have a unique zero fθ∗, with inf{∥Vφ(fθ)∥ | ∥θ−θ∗∥≥ϵ} > ∥Vφ(fθ∗)∥ = 0 for all ϵ > 0, and is reasonable for the concave and quasi-concave programs.Theorem 12 follows from van der Vaart (2000, Theorem 5.9), uniform convergence in Lemma 11, and the identifiability assumption.Source: §5 · p. 7

Surrogate optimization

• Surrogate optimization methods use alternative objectives, but earlier surrogates lacked established calibration or were shown inconsistent.The proposed approach remains in this family while adding a calibration guarantee.Source: §6 · p. 7

Plug-in rule

• Plug-in rules are consistent but require accurate class-posterior estimation, making them less sample-efficient and making threshold estimation dependent on that estimate.Source: §6 · p. 7

Cost-sensitive risk minimization

• Cost-sensitive risk minimization is consistent but may require repeatedly training classifiers, increasing computational cost for complex hypothesis sets.Source: §6 · p. 7

Comparison

• The proposed methods provide calibration guarantees without estimating class-posterior probabilities or training classifiers many times.Source: §6 · p. 7

7 Experiments

• The experiments use a linear-in-input hypothesis model, SVM-based initialization, 300 gradient updates, validation-based learning-rate selection, and metric-specific surrogate-loss parameters.NGA and normalized BFGS are reported as U-GD and U-BFGS.Source: §7 · pp. 7–8

Convergence Comparison:

• U-BFGS converges much faster than U-GD in most cases, reaching convergence within up to 30 iterations.U-GD can update the solution faster per step, creating a convergence-speed versus per-step-update trade-off.Source: Convergence Comparison · p. 8, Figure 4 · p. 8

7 Experiments

• The proposed methods achieve better or at least comparable F1-measure and Jaccard-index performance against baselines in benchmark experiments.Table 3 reports 50 trials per method–dataset pair with standard errors and significance-tested outperforming methods.Source: Convergence Comparison · p. 8, Table 3 · p. 8

Convergence Comparison:

• U-GD and U-BFGS outperform competing methods especially at very small sample sizes.Experiments subsample datasets to sizes from 20 through 400.Source: Convergence Comparison · p. 8, Figure 5 · p. 8
• U-GD can outperform U-BFGS in some small-sample cases because BFGS Hessian approximation may fail to work well with extremely small samples.Source: Convergence Comparison · p. 8

8 Conclusion

• The paper states sufficient surrogate-calibration conditions for linear-fractional metrics and presents them as the first such calibration result to the authors’ knowledge.Surrogate maximization combines concave and quasi-concave programs and is validated through simulations.Source: §8 · p. 8

Supplementary Material for “Calibrated Surrogate Maximization of

• The supplied material identifies the topic as calibrated surrogate maximization of linear-fractional utility in binary classification.Source: Supplementary Material for “Calibrated… · p. 11

A Calibration Analysis and Deferred Proofs from Section 4

• The Bayes-optimal set B contains functions attaining the supremum of a linear-fractional utility, and it may contain multiple classifiers.Under the stated nonemptiness assumption, Proposition 14 characterizes B through the utility coefficients and conditional class probability.Source: A Calibration Analysis and Deferred… · p. 11

A.1 Proof of Theorem 9

• The F_beta surrogate is shown F_beta-calibrated by applying the general calibration proposition and ruling out non-Bayes-optimal stationary solutions by contradiction.The proof uses the surrogate’s stationary condition, convexity, and the tau-discrepancy assumption.Source: §A.1 · pp. 12, 13, 15

A.2 Proof of Theorem 10

• The Jaccard surrogate is Jaccard-calibrated through the same contradiction-based stationary-condition argument used for the F_beta measure.The proof uses convexity, the tau-discrepancy condition, surrogate domination, and monotonicity of x 1/(1+x) on [0,1].Source: §A.2 · pp. 15–17

A.3 Analysis of Accuracy-Calibration

• Accuracy calibration requires only a convex, almost-everywhere differentiable surrogate loss with phi'(0) < 0, so the tau-discrepancy condition is unnecessary.The analysis recovers the conditions of Theorem 6 in Bartlett et al. (2006), but remains sufficient rather than necessary and sufficient.Source: §A.3 · pp. 17–18

A.4 Calibration Analysis of General Linear-fractional Metrics

• For general linear-fractional metrics, the surrogate utility U_phi is U-calibrated under convex, non-increasing, almost-everywhere differentiable loss and stated utility and tau-discrepancy conditions.The utility conditions exclude pathological cases, while the additional conditions force calibration.Source: §A.4 · pp. 18–19
• The surrogate utility U_phi is U-calibrated for general linear-fractional metrics under the stated coefficient and tau-discrepancy conditions.The proof analyzes the stationary condition, separates Bayes-optimal cases, and invokes Proposition 14.Source: §A.4 · pp. 20–21

A.5 Non-negativity of Optimal Surrogate Utilities

• The optimal surrogate utility is non-negative for both the F_beta and Jaccard cases, despite potentially negative numerators.For F_beta, the result follows from a supremum representation under a regularity condition (Steinwart, 2007, Lemma 2.5).Source: §A.5 · p. 21

B Proof of Quasi-concavity of the Surrogate Utility

• The surrogate utility is quasi-concave because its alpha-super-level set is convex for every alpha >= 0.Convexity follows from concavity of the relevant W_0,phi terms under convex phi and convexity of the W_1,phi contribution.Source: B Proof of Quasi-concavity of the… · p. 22

C Proof of Uniform Convergence

• The uniform-convergence proof analyzes non-smooth τ-discrepant surrogates because standard contraction arguments require Lipschitz continuity, while gradient convergence requires smoothness.The analysis instead uses decompositions of the surrogate and bounds involving Rademacher complexity, Lipschitz properties, symmetrization, and concentration.Source: C Proof of Uniform Convergence · pp. 23–25
• The proof establishes uniform bounds with high probability by combining bounded differences, symmetrization, Rademacher-complexity bounds, and contraction inequalities.The resulting complexity control includes a bound on the linear class scaling as c_X c_Θ/√n.Source: C Proof of Uniform Convergence · pp. 25, 27

D.1 Details of Datasets

• Experiments use UCI and LIBSVM datasets, with random 8:2 train-evaluation splits and feature values scaled between zero and one.The datasets are described in Table 4, and the implementation compares ERM, weighted ERM, and plug-in baselines with the proposed methods.Source: §D.1 · p. 28, Table 4 · p. 28, §D.2 · p. 28

D.3 Convergence Comparison

• U-BFGS generally converges faster than U-GD and usually achieves higher performance across the reported F1-measure and Jaccard-index comparisons.U-BFGS converges within 30 iterations in almost all cases, whereas U-GD often requires around 100 iterations or fails to converge within 300 iterations.Source: §D.3 · p. 29

D.4 Performance Comparison with Benchmark Data

• U-BFGS and Plug-in work well for both metrics; their F1-measure performance is competitive, while U-BFGS is better for the Jaccard index.The paper recommends trying both methods in practice.Source: §D.4 · p. 29, Table 5 · p. 29, Table 6 · p. 30
• ERM performs poorly because it optimizes accuracy rather than F1-measure or Jaccard index, while W-ERM and U-GD underperform Plug-in or U-BFGS in the reported setup.The authors attribute U-GD’s weaker benchmark results partly to insufficient iterations, since Tables 5 and 6 use 100 iterations.Source: §D.4 · p. 29, Table 5 · p. 29, Table 6 · p. 30

D.5 Sample Complexity

• For sample sizes around 20 to 40, U-GD or U-BFGS outperforms Plug-in in several datasets for both F1-measure and Jaccard index.Plug-in seldom works significantly better than gradient-based methods when sample sizes range from about 100 to 400.Source: §D.5 · p. 30, Figure 12 · p. 34, Figure 13 · p. 35

D.6 Performance Sensitivity on τ

• Increasing τ tends to improve performance for Fβ-measure on eight listed datasets and for Jaccard index on four listed datasets.Other dataset-metric combinations show extrema as τ varies, so the trend is not universal.Source: §D.6 · p. 30, Figure 14 · p. 36
• The theory cannot determine surrogate calibration when τ exceeds about 0.33 for Fβ-measure or approaches 1.0 for Jaccard index.These thresholds are sufficient-condition boundaries, and further analysis of the discrepancy parameter is left for future work.Source: §D.6 · p. 31, Figure 15 · p. 37