When Does Synthetic Data Augmentation Improve Score-Based Imbalanced Classification?

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

When Does Synthetic Data Augmentation Improve Score-Based Imbalanced Classification?

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

When Does Synthetic Data Augmentation Improve Score-Based Imbalanced Classification? arXiv:2606.26053v1 [stat.ML] 24 Jun 2026

Zhengchi Ma∗, Pengfei Lyu†, and Anru R. Zhang‡

Abstract Synthetic data augmentation is widely used to mitigate class imbalance, but its theoretical effects on score-based classification remain poorly understood. This paper develops a framework for characterizing when synthetic minority augmentation can improve threshold-integrated and threshold-optimized metrics, including AUROC, AUPRC, best-threshold balanced accuracy, and best-threshold F1 score. We separate the effect of augmentation into two components: a change in effective class weighting and a discrepancy between the synthetic and true minority distributions. Under wellspecified score models, the raw estimator already targets the likelihood-ratio ordering, which is population-optimal for the metrics considered. Consequently, augmentation cannot provide a fundamental population-level improvement beyond possible finitesample variance reduction, and may introduce additional bias through synthetic distributional error. We further establish minimax lower bounds showing that the raw estimator already achieves the optimal metric-regret rate in the well-specified regime. Under misspecification, however, augmentation can play a qualitatively different role: by changing the effective class balance, it can alter the restricted-class projection and correct ranking errors induced by the raw imbalanced objective. We provide explicit improvement bounds quantifying the roles of approximation error, finite-sample estimation error, and synthetic distributional error. Simulation studies corroborate the theory, demonstrating limited gains under well-specification and nontrivial but nonmonotone improvements under misspecification.

Introduction

Imbalanced Classification and Synthetic Augmentation. A widespread challenge in modern statistics is imbalanced classification, in which the target classes are observed at markedly different frequencies. In such settings, standard empirical risk minimization with unweighted losses can be inadequate because the majority class may dominate the objective, often at the expense of minority-class performance. The consequences are especially severe ∗

Department of Electrical & Computer Engineering, Duke University Department of Biostatistics & Bioinformatics, Duke University ‡ Department of Biostatistics & Bioinformatics and Department of Computer Science, Duke University †

when the minority class represents rare but high-impact events, such as clinical outcomes in medical data analysis (Salmi et al., 2024; Siddavatam and Shinde, 2025), financial risks (Chen et al., 2024b; Breskuvienė and Dzemyda, 2024), rare ecological phenomena (Zbinden et al., 2024), or active compounds in drug discovery (Almeida et al., 2024). These examples underscore the need for statistically principled approaches to class imbalance, particularly methods that move beyond treating data augmentation as a purely heuristic remedy (Chen et al., 2024a). Synthetic data augmentation has emerged as a practical strategy for mitigating class imbalance. Rather than relying solely on the limited number of observed minority-class examples, augmentation methods generate additional samples to increase the representation of rare classes in the training data. Classical approaches include bootstrap-type resampling and interpolation-based methods such as SMOTE and its refinements (Efron and Tibshirani, 1994; Chawla et al., 2002; He et al., 2008; Han et al., 2005; Bunkhumpornpat et al., 2009, 2012). More recent approaches use conditional generation, Mixup, VAEs, normalizing flows, GANs, diffusion or score-based models, and attention-based language models to produce synthetic examples (Zhang et al., 2017; Tian and Shen, 2025; Kingma and Welling, 2013; Papamakarios et al., 2021; Goodfellow et al., 2014; Ho et al., 2020; Nakada et al., 2024). These methods range from simple resampling heuristics to flexible distributional modeling, making synthetic augmentation an important component of modern imbalanced learning. Despite its widespread use, the effect of synthetic augmentation remains unsettled. Some empirical studies report that oversampling or synthetic augmentation can improve classification performance, while others find little or no AUROC improvement, degraded calibration, or performance comparable to simpler reweighting or threshold-adjustment strategies (Blagus and Lusa, 2013; Van den Goorbergh et al., 2022; Piccininni et al., 2024; Yang et al., 2024). Recent theoretical and methodological work has begun to clarify when synthetic samples can be useful, emphasizing generator mismatch, local class geometry, synthetic sample size, bias correction, and inference validity (Nakada et al., 2024; Xia and Klusowski, 2026; Ma and Zhang, 2026; Shen et al., 2026; Lyu et al., 2025; Ahmad et al., 2025; Keret and Shojaie, 2025; Räisä et al., 2025; Xu, 2026). Taken together, these findings suggest that synthetic augmentation is not merely a computational device for enlarging training sets; it raises fundamental questions about bias, uncertainty, distributional mismatch, and the metrics used to evaluate predictive performance. Score-Based Classification. This paper studies synthetic augmentation through the lens of score-based classification, where a learned score orders observations by their evidence for the minority class and hard decisions are obtained by thresholding this score. The scorebased view is especially useful in imbalanced classification because it is more informative than hard-label prediction. A score preserves the relative strength of evidence across samples and supports threshold selection, uncertainty assessment (Sadinle et al., 2019), ranking (Clémençon et al., 2008), and trade-off analysis between false positives and false negatives (Cook and Ramadas, 2020). Performance can therefore be studied both through rankingbased or threshold-integrated criteria such as AUROC and AUPRC, and through thresholdoptimized decision criteria such as best-threshold balanced accuracy and best-threshold F1 2

score. We focus on these four metrics because they evaluate the classification outcome without fixing a single operating threshold in advance. Empirical evidence on whether synthetic augmentation improves these metrics is mixed. Several studies in clinical prediction and high-dimensional classification report that random resampling or SMOTE-type augmentation provides little or no AUROC improvement (Piccininni et al., 2024; Van den Goorbergh et al., 2022; Zheng et al., 2025; Nguyen et al., 2019). Other applications find that synthetic augmentation can improve AUROC or AUPRC in downstream prediction tasks (Kim et al., 2024; Kannan et al., 2025; Li et al., 2023; Chen et al., 2026). These apparently contradictory findings raise two basic theoretical questions: When can synthetic data improve threshold-integrated metrics such as AUROC and AUPRC, and when should no improvement be expected? and When is threshold tuning of the raw score sufficient, and when can synthetic augmentation improve the learned score beyond what threshold tuning alone can achieve? These questions are distinct because threshold tuning and augmentation act at different stages of the learning pipeline. Threshold tuning changes only the final decision rule for a fixed score; it cannot change the ordering induced by that score. Synthetic augmentation, by contrast, changes the training objective and can therefore alter the fitted score itself. The central distinction developed in this paper is between well-specified settings, where augmentation cannot change the oracle score-ranking target, and misspecified settings, where changing the effective class balance can alter the restricted-class projection and correct ranking errors induced by the raw imbalanced objective.

1.1

Our Contributions

This paper develops a theoretical framework for understanding when synthetic minorityclass augmentation can and cannot improve score-based imbalanced classification. A flowchart summarizing the main results is shown in Figure 1. Our main contributions are as follows. First, we formulate synthetic data augmentation through population and empirical risk objectives that separate two effects of augmentation: the change in effective class weighting and the distributional discrepancy between the synthetic minority distribution and the true minority distribution. This formulation allows us to study augmentation for score-based criteria, including AUROC, AUPRC, best-threshold balanced accuracy, and best-threshold F1 score. Second, we show that under well-specified score models, synthetic augmentation does not change the population-optimal ranking target. In this regime, both the raw and ideal augmented objectives target the same likelihood-ratio ordering. Augmentation may reduce finite-sample variance by increasing the effective sample size, but it also introduces synthetic distributional error when Psyn ̸= P1 . We establish finite-sample metric-regret bounds for raw and augmented estimators and prove minimax lower bounds showing that, for AUROC and 3

Figure 1: Flowchart of the main results. best-threshold balanced accuracy, the raw estimator already achieves the optimal rate up to dimension-dependent factors. Third, we identify a qualitatively different phenomenon under model misspecification. When the model class is too restrictive, augmentation is not guaranteed to help, because generating more data cannot remove intrinsic approximation error. In contrast, when the model class can approximate a better-balanced oracle score but the raw imbalanced objective selects a misaligned ordering, high-quality synthetic augmentation can improve the learned score itself. In this setting, augmentation can improve AUROC, AUPRC, and best-threshold performance beyond what can be achieved by threshold tuning the raw score alone. Fourth, we provide explicit improvement guarantees under misspecification. These bounds quantify how the gain from augmentation is reduced by three terms: approximation error under the chosen effective class weight, finite-sample estimation error, and synthetic distributional error. The results show that synthetic augmentation yields a provable advantage when it corrects a ranking mismatch induced by the raw imbalanced objective and when the synthetic distribution is sufficiently accurate. Finally, we complement the theoretical analysis with simulation studies illustrating the regimes identified by the theory. The simulations show limited potential for fundamental gains in the well-specified regime, and nontrivial but nonmonotone improvements under misspecification when high-quality synthetic samples correct objective-induced ranking errors. Organization. The rest of this paper is organized as follows. Section 2 introduces the notation and problem formulation for synthetic minority augmentation and establishes the oracle optimality of the likelihood-ratio benchmark. Section 3 studies synthetic augmentation under well-specified models, deriving metric-regret bounds and minimax lower bounds. 4

Section 4 turns to misspecified models and characterizes when synthetic augmentation can, and cannot, improve score ordering beyond threshold tuning. Section 5 presents simulation studies illustrating the theoretical findings. Finally, Section 6 concludes with implications and limitations.

Notation and Problem Formulation

Notation. We write P(·) for the probability of an event and EP [·] for expectation under a distribution P , omitting the subscript when no ambiguity arises. For vectors, ∥ · ∥ denotes the Euclidean norm. Gradients and Hessians with respect to θ are denoted by ∇ and ∇2 , respectively. For symmetric matrices A and B, we write A ⪰ B if A − B is positive semidefinite. The 1-Wasserstein distance between probability measures P and Q is denoted by W1 (P, Q) and is defined by Z W1 (P, Q) = inf d(x, y) dγ(x, y), γ∈Π(P,Q)

where Π(P, Q) is the set of all couplings of P and Q. Throughout, c and C denote positive constants whose values may change from line to line. We use p for the feature dimension and d for the parameter dimension. Score-Based Binary Classification Model. We consider a binary classification problem with features X ∈ X ⊆ Rp and label Y ∈ {0, 1}, where Y = 1 denotes the minority class and Y = 0 denotes the majority class. The class priors are π0 = P(Y = 0),

π1 = P(Y = 1).

Let P0 and P1 denote the class-conditional feature distributions: X | Y = i ∼ Pi ,

i = 0, 1.

The observed training set consists of n0 majority samples drawn from P0 and n1 minority samples drawn from P1 . To study synthetic minority augmentation, we also consider ñ synthetic minority samples drawn from a synthetic distribution Psyn . A score is a real-valued function s : X → R assigning each feature vector x a numerical value, with larger values indicating stronger evidence for the minority class. When the score is parameterized by θ ∈ Θ ⊆ Rd , we write it as sθ . Given training data, the learned score is denoted by ŝ in general, or by sθ̂ in the parameterized setting. A hard classifier can be obtained by thresholding the learned score: ŷτ (x) = 1{ŝ(x) ≥ τ }. We do not assume that there is a unique population score that ŝ estimates pointwise. For the evaluation metrics considered in this paper, the relevant population object is the ordering 5

induced by the score. The posterior probability is one canonical scoring function, but it is only one representative of an equivalence class: any strictly increasing transformation of the likelihood ratio, when it exists, induces the same ranking and the same threshold family. Thus, throughout the paper, a score refers to a real-valued function used to rank observations; it need not be calibrated as a probability or constrained to lie in a prespecified interval. In many imbalanced classification problems, the primary object of interest is the ranking induced by the score rather than prediction at a single threshold. We therefore evaluate scores using population metrics that aggregate performance over thresholds or optimize over thresholds. Population Evaluation Metrics. All performance metrics in this paper are evaluated with respect to the original population distribution with class priors (π0 , π1 ), unless explicitly subscripted by a data-generating parameter in minimax statements. Synthetic samples are used only to modify the training objective and do not change the population distribution used for evaluation. For a score function s, we write AUC(s) for the population area under the ROC curve and AUPRC(s) for the population area under the precision–recall curve. For independent samples X1 ∼ P1 and X0 ∼ P0 , the AUROC of s is 1 AUC(s) = EX1 ∼P1 1{s(X1 ) > s(X0 )} + 1{s(X1 ) = s(X0 )} . 2 X0 ∼P0 Thus, AUROC is the probability that a randomly selected minority-class sample receives a higher score than a randomly selected majority-class sample, with ties counted as one half. For a threshold τ ∈ R, define recall and false-positive rate by Recs (τ ) = P1 (s(X) ≥ τ ),

FPRs (τ ) = P0 (s(X) ≥ τ ).

The corresponding precision is Precs (τ ) =

π1 Recs (τ ) , π1 Recs (τ ) + π0 FPRs (τ )

whenever the denominator is positive. The AUPRC of s is the area under the precision– recall curve traced out as τ varies, with respect to the original class priors (π0 , π1 ). When the relevant score distributions are continuous, we may equivalently parameterize the precision– recall curve by recall using a quantile threshold tr (s) satisfying P1 (s(X) ≥ tr (s)) = r. Then the precision at recall level r and the AUPRC are Prec∗s (r) =

π1 r , π1 r + π0 P0 (s(X) ≥ tr (s))

Z 1 AUPRC(s) =

Prec∗s (r) dr.

We also consider two threshold-dependent metrics, optimized over the threshold. Balanced accuracy and F1 score at threshold τ are BA(s, τ ) =

1 {P1 (s(X) ≥ τ ) + P0 (s(X) < τ )} , 2 6

and

2π1 Recs (τ ) . π1 {1 + Recs (τ )} + π0 FPRs (τ ) For any measurable set B, the set version of the two scores can be defined as F1 (s, τ ) =

BA(B) =

1 (P1 (B) + P0 (B c )) , 2

F1 (B) =

2π1 P1 (B) . π1 (1 + P1 (B)) + π0 P0 (B)

We use their best-threshold versions for score evaluation: BA∗ (s) := sup BA(s, τ ),

F∗1 (s) := sup F1 (s, τ ).

τ ∈R

Likelihood-Ratio Benchmark. The likelihood ratio provides a population-level benchmark for score-based classification. When emphasizing the data-generating parameter, we write the class-conditional distributions P0 and P1 as P0,η∗ and P1,η∗ . Suppose the data are generated from a distribution indexed by η ∗ and that P0,η∗ and P1,η∗ admit densities p0,η∗ and p1,η∗ . The ordinary likelihood ratio is Lη∗ (x) :=

p1,η∗ (x) , p0,η∗ (x)

where we assume P1,η∗ ≪ P0,η∗ . We also define the normalized likelihood-ratio score Λη∗ (x) :=

p1,η∗ (x) Lη∗ (x) = . p0,η∗ (x) + p1,η∗ (x) 1 + Lη∗ (x)

Since t 7→ t/(1 + t) is strictly increasing on [0, ∞), Lη∗ and Λη∗ induce the same ranking and the same threshold family up to a monotone reparameterization of the threshold. Therefore, for ranking-based metrics and best-threshold metrics, either score may be used as the oracle benchmark. The normalized likelihood-ratio score Λη∗ should be distinguished from the posterior probability. By Bayes’ rule, ηη∗ (x) = P(Y = 1 | X = x) =

π1 Lη∗ (x) π1 p1,η∗ (x) = . π0 p0,η∗ (x) + π1 p1,η∗ (x) π0 + π1 Lη∗ (x)

Thus ηη∗ , Λη∗ , and Lη∗ all induce the same ranking and the same threshold family up to monotone reparameterization. When no confusion arises, we write L := Lη∗ ,

Λ := Λη∗ .

The Neyman–Pearson lemma states that, for testing between two simple hypotheses, the most powerful test at a fixed type-I error level is obtained by thresholding the likelihood ratio. In the present classification setting, this means that the likelihood-ratio ordering is the population-optimal ordering of samples by their relative evidence for the two classes. A learned score function ŝ can therefore be viewed as an attempt to approximate this oracle ordering from the training sample. We use the following lemma to formalize the optimality of the likelihood-ratio benchmark for the four metrics considered in this paper. 7

Lemma 1 (Likelihood-Ratio Score Achieves Optimal Population Metrics). For X0 ∼ P0 and X1 ∼ P1 , let s : X → R be any measurable score such that Λη∗ (X0 ), Λη∗ (X1 ), s(X0 ), and s(X1 ) have continuous distributions. Then AUC(s) ≤ AUC(Λη∗ ) = sup AUC(s′ ), s′ ∈Sc

AUPRC(s) ≤ AUPRC(Λη∗ ) = sup AUPRC(s′ ), s′ ∈Sc

∗

BA (s) ≤ BA (Λη∗ ) =

sup

BA(B),

B⊆X measurable

F∗1 (s) ≤ F∗1 (Λη∗ ) =

sup

F1 (B),

B⊆X measurable

where Sc = {measurable s : s(X0 ), s(X1 ) have continuous distributions}. Lemma 1 shows that the likelihood-ratio ordering is the population-optimal benchmark for the evaluation criteria used in this paper. For AUROC and AUPRC, optimality follows from the fact that likelihood-ratio thresholds are optimal at each fixed false-positive or recall level. For best-threshold balanced accuracy and F1 score, the optimal decision regions are also induced by thresholding the likelihood ratio, although the maximizing threshold depends on the metric. Thus, throughout the paper, we use Λη∗ as the oracle score and study metric regrets that quantify the gap between a learned score and this oracle benchmark. Learning Objectives with Synthetic Minority Augmentation. We now define the population and empirical objectives used to learn the score function. The purpose of this formulation is to separate three objects: the risk induced by the original imbalanced sample, the risk induced by augmenting the minority class with synthetic samples, and an auxiliary ideal augmented risk that uses the post-augmentation class weight but keeps the minority distribution equal to the true distribution P1 . Let ℓ(s; x, y) denote the loss incurred by score s on an example (x, y). Here ℓ(s; x, y) is shorthand for a loss that depends on s through s(x), for example ℓ(s(x), y). If the score is parameterized by θ, we write ℓ(θ; x, y) := ℓ(sθ (x), y). The raw population risk corresponding to training on the original imbalanced data is Rraw (s) :=

n1 n0 EP0 ℓ(s; X, 0) + EP ℓ(s; X, 1). n0 + n1 n0 + n 1 1

When the empirical class proportions reflect the population priors, these weights converge to (π0 , π1 ). When synthetic minority samples are added, the effective class proportions in the training objective change. The augmented population risk is Raug (s) :=

n0 n1 ñ EP0 ℓ(s; X, 0) + EP1 ℓ(s; X, 1) + EP ℓ(s; X, 1). n0 + n1 + ñ n0 + n1 + ñ n0 + n1 + ñ syn 8

Let s∗raw and s∗aug denote minimizers of Rraw and Raug , respectively. If the score model is ∗ ∗ parameterized, we denote the corresponding population minimizers by θraw and θaug . The corresponding empirical objectives are constructed from the observed samples. Let (0) 0 (1) 1 ñ {xi }ni=1 be the majority samples, {xi }ni=1 the real minority samples, and {x̃i }i=1 the synthetic minority samples. The raw empirical risk is n0 n1 X X 1 1 (0) (1) ℓ(s; xi , 0) + ℓ(s; xi , 1). R̂raw (s) := n0 + n1 i=1 n0 + n1 i=1

The augmented empirical risk is ) (n n1 ñ 0 X X X 1 (1) (0) ℓ(s; xi , 1) + ℓ(s; x̃i , 1) . ℓ(s; xi , 0) + R̂aug (s) := n0 + n1 + ñ i=1 i=1 i=1 We denote the corresponding empirical risk minimizers by ŝraw and ŝaug . If the score model is parameterized, we denote the corresponding empirical minimizers by θ̂raw and θ̂aug . It is useful to introduce a unified notation for class-weighted risks. For any effective minority weight α ∈ (0, 1), define Rα (s) := (1 − α)EP0 ℓ(s; X, 0) + αEP1 ℓ(s; X, 1). In particular, n1 n1 + ñ , αaug := . n0 + n 1 n0 + n1 + ñ Then Rraw = Rαraw , while Rαaug represents the idealized objective that would arise if the additional minority samples were drawn from the true minority distribution P1 . Let s∗αaug denote a minimizer of Rαaug . Comparing Rαaug with Rraw isolates the effect of changing class weights, while comparing Raug with Rαaug isolates the distributional discrepancy caused by using Psyn instead of P1 . Unless otherwise stated, we assume that all minimizers are well defined and that the loss function and model class satisfy the regularity conditions needed for empirical risk minimization and the population-level comparisons developed below. Because synthetic data generators are often trained on the original data, the resulting synthetic samples may depend on real samples. For theoretical simplicity, we assume independence between the real and synthetic samples. In practice, this can be enforced by sample splitting: one subset of the original data is used to train the generator, and a disjoint subset is used to train the classifier (Tian and Shen, 2025). Throughout the paper, we assume that such preprocessing has been applied when necessary. For a probability-like score u ∈ [0, 1], we say that the loss ℓ(u, y) is strictly proper if, for every η ∈ [0, 1], the conditional risk αraw :=

ηℓ(u, 1) + (1 − η)ℓ(u, 0) is uniquely minimized at u = η. Equivalently, among all scores interpreted as class probabilities, the Bayes action is the true conditional probability η. 9

Class-Weighted Bayes Scores. Assume that P1 ≪ P0 so that L = dP1 /dP0 is well defined. If the loss ℓ is strictly proper, then the unconstrained minimizer of Rα over measurable scores s : X → [0, 1] is αL(x) = gα (Λ(x)), ηα (x) = (1 − α) + αL(x) where gα (t) =

αt . (1 − α)(1 − t) + αt

The map gα is strictly increasing on [0, 1], and g1/2 (t) = t. Thus, changing the class weight changes the calibration of the Bayes score but not its ranking. For a restricted score class S, we write s∗α ∈ arg min Rα (s) s∈S

for the corresponding restricted population minimizer.

Synthetic Augmentation under Well-Specified Models

In this section, we analyze synthetic minority augmentation under well-specified score models. We begin with the perfectly specified maximum likelihood setting, where the training loss coincides with the negative log-likelihood of the data-generating model. This case illustrates a basic principle: when the raw population objective already recovers a score with the likelihood-ratio ordering, synthetic augmentation does not change the populationoptimal ranking target. It can only affect finite-sample estimation, and may be harmful when Psyn ̸= P1 . We then abstract this principle into a general well-specification condition, requiring only that the learned score be close to a strictly increasing transformation of the likelihood ratio. Under this condition, we show that score-level closeness controls both threshold-independent and best-threshold metrics. We then specialize the general results to parametric empirical risk minimization and derive finite-sample bounds for both raw and augmented training. Finally, we prove minimax lower bounds showing that, in the well-specified regime, raw-data estimation already achieves the optimal metric-regret rate.

3.1

Perfect Specification: The MLE Benchmark

We first consider the ideal case in which the population score model is perfectly specified. In this setting, the functional form of the population score is correctly specified up to an unknown data-generating parameter η ∗ . That is, the relevant oracle score belongs to a parametric score family {sη : η ∈ Θ}. The training loss is chosen to match this model, so empirical risk minimization with the raw data is equivalent to maximum likelihood estimation. 10

Examples include correctly specified generalized linear score models. For instance, in logistic regression, sη (x) = (1 + exp(−η ⊤ x))−1 , and perfect specification means that P(Y = 1 | X = x) = sη∗ (x) for some η ∗ ∈ Θ. Similarly, in a probit model, sη (x) = Φ(η ⊤ x), where Φ is the standard normal distribution function. In these examples, the negative log-likelihood is the matching loss, and the population minimizer recovers sη∗ , which induces the oracle likelihood-ratio ordering. In the perfectly specified MLE setting, the loss ℓ(η; x, y) is the negative log-likelihood associated with the score model. Thus the raw empirical minimizer is the MLE, and the learned score is parametrized by the MLE estimator: n +n

η̂raw ∈ arg min η∈Θ

0 1 X 1 ℓ(η; Xi , Yi ), n0 + n1 i=1

ŝraw (x) = sη̂raw (x).

At the population level, correct specification and identifiability imply that the raw risk is minimized at the true parameter: η ∗ ∈ arg min Rraw (η). η∈Θ

Consequently, the raw population objective targets a score that is a strictly increasing transformation of the oracle likelihood-ratio score Λη∗ . Therefore, in the perfectly specified MLE setting, synthetic minority augmentation cannot improve the population-optimal ranking target. It can only affect the finite-sample estimator, and may be harmful when Psyn ̸= P1 . To connect this observation with class reweighting and ideal minority augmentation, consider the unified class-weighted risk Rα (η) = (1 − α)EP0 ℓMLE (η; X, 0) + αEP1 ℓMLE (η; X, 1),

α ∈ (0, 1).

Let ηα∗ be a minimizer of Rα . For correctly specified likelihood models in which changing class weights only changes the effective class prior, the weighted population minimizer changes the calibration of the score but not the likelihood-ratio ordering. Hence there exists a strictly increasing function gα such that sηα∗ (x) = gα (Λη∗ (x)). Thus raw training, class reweighting, and ideal minority augmentation preserve the same population ranking target. The MLE case is a canonical example of a broader well-specified regime. The essential property is not maximum likelihood estimation itself, but likelihood-ratio alignment: the learned score should be close to a strictly increasing transformation of the likelihood ratio. In the next subsections, we formulate this property directly and study its implications. 11

3.2

General Well-Specification and Metric Convergence

We use the following assumption to formalize the notion that a learned score is wellspecified for the population metrics considered in this paper. Assumption 1 (Well-Specified Score). There exists a strictly increasing function g such that ∥ŝn − g ◦ Λη∗ ∥L∞ (P0 +P1 ) = OP (rn ), where rn → 0. Equivalently, with probability tending to one, for both X ∼ P0,η∗ and P1,η∗ , |ŝn (X) − g(Λη∗ (X))| ≲ rn . Assumption 1 says that the learned score need not estimate a unique population score pointwise. Instead, it only needs to approximate some strictly increasing transformation of the likelihood-ratio score. This is the relevant notion of well-specification for the thresholdindependent and best-threshold metrics studied here, because these metrics depend on the ordering and threshold sets induced by the score rather than on its numerical calibration. Theorem 1 (AUROC and AUPRC Regrets). Suppose Assumption 1 holds. Let X0 ∼ P0 and X1 ∼ P1 be independent. Assume that g(Λη∗ (X0 )), g(Λη∗ (X1 )), ŝn (X0 ), and ŝn (X1 ) have continuous distributions and that there exist constants C, t0 > 0 such that, for all t ∈ [0, t0 ], P (|g(Λη∗ (X1 )) − g(Λη∗ (X0 ))| ≤ t) ≤ Ct. Then r AUC(Λη∗ ) − AUC(ŝn ) = OP (rn ),

AUPRC(Λη∗ ) − AUPRC(ŝn ) = OP

π0 rn π1

Theorem 1 shows that, under well-specification, both AUC(ŝn ) and AUPRC(ŝn ) converge to the corresponding metrics induced by the likelihood-ratio benchmark. The convergence rate for AUPRC is slower than that for AUROC, reflecting the fact that AUPRC depends on the full precision–recall curve and on the class priors. The factor π0 /π1 highlights the greater sensitivity of AUPRC in severely imbalanced settings. Theorem 2 (Best-Threshold BA and F1 Regrets). Suppose Assumption 1 holds. Assume that there exist constants C, t0 > 0 such that, for every threshold τ , every r ∈ [0, t0 ], and each y ∈ {0, 1}, Py (|g(Λη∗ (X)) − τ | ≤ r) ≤ Cr. Then ∗

∗

F∗1 (Λη∗ ) − F∗1 (ŝn ) = OP

BA (Λη∗ ) − BA (ŝn ) = OP (rn ),

rn π1

Theorem 2 shows that best-threshold decision performance also converges to that of the likelihood-ratio benchmark. Although BA(s, τ ) and F1 (s, τ ) depend on a fixed threshold, optimizing over τ removes dependence on a particular threshold choice and evaluates the best decision rule induced by the score. The additional factor 1/π1 in the F1 bound reflects the stronger sensitivity of precision-based metrics to class imbalance. 12

3.3

Specification in Parametric Empirical Risk Minimization Models

We now specialize the preceding score-level theory to parametric empirical risk minimization. In this framework, the score is induced by a parameter θ ∈ Θ, and different training procedures correspond to minimizing class-weighted population or empirical risks. The resulting bounds separate two effects of synthetic augmentation: the potential variance reduction from increasing the effective sample size, and the bias introduced when Psyn differs from the true minority distribution P1 . Recall from Section 2 that, for any effective minority weight α ∈ (0, 1), the unconstrained minimizer of Rα is ηα = gα ◦ Λ. Let αraw =

1 n1 < , n0 + n 1 2

αaug =

n1 + ñ . n0 + n1 + ñ

Assumption 2 (Population Well-Specification). For every α ∈ (0, 1), there exists a strictly increasing function gα such that sθα∗ (x) = gα (Λη∗ (x)),

where θα∗ ∈ arg min Rα (θ). θ∈Θ

Assumption 2 states that, for each class-weighted population objective, the corresponding population minimizer induces a score that is a strictly increasing transformation of the likelihood-ratio benchmark. Therefore, changing class weights may change the scale or calibration of the score, but it does not change the oracle ranking implied by Λη∗ . When an empirical estimator is close to its corresponding population minimizer, this population-level well-specification transfers to Assumption 1, with rn determined by the parameter estimation error. Assumption 3 (Regularity Conditions for Parametric ERM). The following conditions hold. (a) No ties and anti-concentration. The relevant score distributions have no ties. Moreover, there exist constants C, t0 > 0 such that, for all t ∈ [0, t0 ], P (|sθ (X1 ) − sθ (X0 )| ≤ t) ≤ Ct for the relevant parameters θ. (b) Score Lipschitzness. There exists Ls > 0 such that, for all θ, θ′ ∈ Θ, |sθ (x) − sθ′ (x)| ≤ Ls ∥θ − θ′ ∥. (c) Local curvature. The relevant population risks are locally strongly convex at their minimizers: for some λ > 0, ∗ ∇2 Rraw (θraw ) ⪰ λI,

∗ ∇2 Raug (θaug ) ⪰ λI.

(d) Gradient concentration. The coordinatewise gradients of the loss at the relevant population minimizers are uniformly bounded by B > 0. (e) Synthetic distribution error. The synthetic minority distribution satisfies W1 (Psyn , P1 ) ≤ ϵsyn . ∗ Moreover, x 7→ ∇ℓ(θaug ; x, 1) is Lg -Lipschitz.

(f ) Ideal augmented-risk curvature. The ideal augmented risk Rαaug satisfies the quadratic growth condition Rαaug (θ) − Rαaug (θα∗ aug ) ≥ Lα ∥θ − θα∗ aug ∥2 ∗ in a local neighborhood of θα∗ aug containing θaug . In addition, the following local strongconvexity inequality holds in the same neighborhood:

Rαaug (θα∗ aug ) ≥ Rαaug (θ) + ∇Rαaug (θ)T (θα∗ aug − θ) +

2 µ ∗ θαaug − θ . 2

(g) Local Hessian regularity and convexity. The parameter space Θ is convex, and ∗ ∗ ∈ int(Θ). For every (x, y), the map θ 7→ ℓ(θ; x, y) is convex and twice contin, θaug θraw uously differentiable. There exist constants r, LH , BH > 0 such that ∗ ∗ {θ : ∥θ − θraw ∥ ≤ r} ∪ {θ : ∥θ − θaug ∥ ≤ r} ⊆ int Θ,

LH r ≤

λ . 4

∗ ∗ ∗ ∗ }, , θaug ∈ {θraw Moreover, for all θ satisfying ∥θ − θpop ∥ ≤ r, where θpop ∗ ∗ ∇2 ℓ(θ; x, y) − ∇2 ℓ(θpop ; x, y) op ≤ LH ∥θ − θpop ∥,

for Pj -almost every x when y = j ∈ {0, 1}, and for Psyn -almost every x when y = 1. In addition, for i ∈ {0, 1} and X ∼ Pi , ∗ ∗ ∇2 ℓ(θpop ; X, i) − EPi ∇2 ℓ(θpop ; X, i) op ≤ BH almost surely. Furthermore, for X ∼ Psyn , ∗ ∗ ∇2 ℓ(θaug ; X, 1) − EPsyn ∇2 ℓ(θaug ; X, 1) op ≤ BH almost surely. These regularity assumptions translate parameter estimation error into metric-regret bounds. The anti-concentration conditions ensure that small score perturbations do not change too many rankings or threshold decisions. Score Lipschitzness converts parameter error into score error. Curvature and bounded gradients yield concentration of empirical risk minimizers around their population counterparts. Finally, the Wasserstein bound and gradient Lipschitzness quantify the bias introduced by replacing true minority samples with synthetic samples. 14

Theorem 3 (AUROC Regret in Well-Specified ERM). Under Assumptions 2 and 3, for sufficiently large sample sizes n0 , n1 and for a constant c > 0, each of the following bounds holds with probability at least 1 − δ: s CLs c B 2 d log(6d/δ) , AUC(Λη∗ ) − AUC(sθ̂raw ) ≤ λ n0 + n 1 and CLs c AUC(Λη∗ ) − AUC(sθ̂aug ) ≤ λ

B 2 d log(8d/δ) + CLg Ls n0 + n1 + ñ

2 ñ ϵsyn . µLα n0 + n1 + ñ

Theorem 4 (AUPRC Regret in Well-Specified ERM). Under Assumptions 2 and 3, for sufficiently large sample sizes, and assuming that sθ (X1 ) with X1 ∼ P1 has a continuous CDF, for a constant c > 0, each of the following bounds holds with probability at least 1 − δ: r 1/4 CLs c π0 B 2 d log(6d/δ) AUPRC(Λη∗ ) − AUPRC(sθ̂raw ) ≤ , (1) λ π1 n0 + n 1 and 1/4 CLs c π0 B 2 d log(8d/δ) AUPRC(Λη∗ ) − AUPRC(sθ̂aug ) ≤ λ π1 n0 + n1 + ñ " 2 #1/4 r L2g π0 ñ + 2 2CLs ϵsyn . π1 2µLα n0 + n1 + ñ r

(2)

Theorems 3 and 4 show that, in the well-specified ERM setting, both raw and augmented estimators approach the likelihood-ratio benchmark for AUROC and AUPRC. For the raw estimator, the error is driven by the usual finite-sample estimation term based on the original sample size n0 + n1 . For the augmented estimator, the variance term can improve because the effective sample size becomes n0 + n1 + ñ, but an additional bias term appears due to the discrepancy between Psyn and P1 , measured by ϵsyn . Thus, in the well-specified setting, synthetic data augmentation does not yield a fundamental improvement over raw training unless the reduction in empirical error offsets the synthetic distributional error. Similarly, we obtain best-threshold bounds for balanced accuracy and F1 score. Theorem 5 (Best-Threshold BA Regret in Well-Specified ERM). Under Assumptions 2 and 3 and for sufficiently large sample sizes, assume further that there exist constants C, t0 > 0 such that, for every relevant parameter θ, threshold τ , r ∈ [0, t0 ], and y ∈ {0, 1}, Py (|sθ (X) − τ | ≤ r) ≤ Cr.

(3)

Then, for a constant c > 0, each of the following bounds holds with probability at least 1 − δ: s CLs c B 2 d log(6d/δ) , (4) BA∗ (Λη∗ ) − BA∗ (sθ̂raw ) ≤ λ n0 + n 1 15

and BA∗ (Λη∗ ) − BA∗ (sθ̂aug ) ≤

CLs c λ

B 2 d log(8d/δ) CLs Lg ñ +√ ϵsyn . n0 + n1 + ñ 2µLα n0 + n1 + ñ

(5)

Theorem 6 (F1 Regret in Well-Specified ERM). Under the conditions of Theorem 5 and for sufficiently large sample sizes, for a constant c > 0, each of the following bounds holds with probability at least 1 − δ: s CLs c B 2 d log(6d/δ) , (6) F∗1 (Λη∗ ) − F∗1 (sθ̂raw ) ≤ π1 λ n0 + n 1 and CLs c F∗1 (Λη∗ ) − F∗1 (sθ̂aug ) ≤ π1 λ

4CLs Lg B 2 d log(8d/δ) ñ + √ ϵsyn . n0 + n1 + ñ π1 2µLα n0 + n1 + ñ

(7)

Theorems 5 and 6 show that the same variance–bias tradeoff persists for best-threshold decision metrics. Threshold tuning extracts the best decision-level performance available from the learned score, but it cannot remove the synthetic distributional error introduced by inaccurate augmentation. The additional factor 1/π1 in the F1 bound again reflects its sensitivity to class imbalance. The synthetic distributional error ϵsyn should be interpreted as the statistical price of learning the synthetic generator from the available minority data. Since the generator is typically trained using only the n1 minority-class observations, the discrepancy W1 (Psyn , P1 ) is limited by the accuracy with which the minority distribution can be estimated. In nonparametric settings, this error may suffer from the curse of dimensionality, whereas stronger structural assumptions may yield parametric or near-parametric rates. Therefore, in the well-specified regime, adding synthetic data does not necessarily improve metric-regret performance: it may reduce finite-sample variance, but it also introduces a bias term that can dominate when the synthetic distribution is inaccurate. The correctly specified MLE benchmark discussed in Section 3.1 is a special case of the preceding ERM theory, obtained by taking the loss to be the negative log-likelihood. Corollary 1 (Correctly Specified MLE). Suppose Assumption 3 and Equation (3) hold with ℓ equal to the negative log-likelihood of a correctly specified and identifiable parametric likelihood model with a continuous CDF for sθ (X1 ), where X1 ∼ P1 . Suppose the parametric model class is sufficiently rich so that the data-generating score for any class priors (π̃0 , π̃1 ) is attainable; that is, π̃1 p1,η∗ (x) x 7→ π̃1 p1,η∗ (x) + π̃0 p0,η∗ (x) belongs to the model class. Then, for every α ∈ (0, 1), the corresponding population MLE score sηα∗ is a strictly increasing transformation of the likelihood-ratio score Λη∗ . Furthermore, the raw MLE and the synthetic augmented MLE satisfy the metric-regret bounds in Theorems 3, 4, 5, and 6. 16

In particular, the corollary shows that the raw MLE achieves the likelihood-ratio benchmark at the usual parametric rate, whereas the augmented MLE has the same variance–bias tradeoff as in the ERM bounds. Remark 1 (Asymptotic versus Limited-Data Regimes). The upper bounds of Theorems 3–6 should be interpreted differently in the asymptotic and non-asymptotic regimes. Asymptotically, with n = n0 + n1 → ∞ at fixed model complexity, the raw estimator attains the parametric rate OP (n−1/2 ), whereas the augmented estimator attains only OP (n−1/2 + ϵsyn ). −1/p In nonparametric settings, ϵsyn ≍ OP (n1 ), where p is the feature dimension, which is normally slower than n−1/2 . Therefore, augmentation cannot improve the asymptotic rate unless ϵsyn = oP (n−1/2 ), and may even be harmful. This point is most relevant for low-complexity models, where the raw estimator reaches its large-sample behavior at moderate n. The limited-data regime common in modern applications is different. With highly flexible models such as deep networks, the effective complexity can be large relative to n, so the nonasymptotic bounds are the informative ones. Writing r r Complexity(S) Complexity(S) , erroraug ≈ C + Cϵsyn , errorraw ≈ C n n + ñ where Complexity(S) is any suitable capacity measure such as parameter dimension, VC dimension, or Rademacher complexity, the raw estimation term is large when complexity is large relative to n, and adding ñ synthetic samples can reduce it substantially. Since the resulting bias ϵsyn depends on the feature-space complexity of the generator, not the full classifier complexity, erroraug ≪ errorraw is possible. Thus, even under well-specification, augmentation can improve finite-sample performance. This is achieved not by changing the population target, but by reducing estimation error enough to offset the synthetic bias.

3.4

Minimax Lower Bounds for Metric Regret

We complement the preceding upper bounds with minimax lower bounds for metric regret. The goal is to show that the convergence rates above are not merely artifacts of the analysis, but are unavoidable in a broad class of well-specified models. We consider a local parametric family around a fixed parameter value and construct nearby distributions whose likelihood-ratio scores induce different rankings or decision regions. As a result, no estimator can uniformly achieve a faster rate than the minimax lower bound. Here d denotes the parameter dimension, so local alternatives are constructed along directions u ∈ Sd−1 in parameter space. Assumption 4 (Regularity and Separation Conditions for AUROC). The following conditions hold. (a) There exist η0 ∈ Θ and r0 > 0 such that B2 (η0 , r0 ) ⊆ Θ. (b) For each y ∈ {0, 1}, Py,η has density py,η with respect to a common dominating measure ν, and py,η is continuously differentiable in η on B2 (η0 , r0 ) for every x. Also, P1,η ≪ P0,η 17

for all η ∈ B2 (η0 , r0 ). Define Sy (x; η) = ∇η log py,η (x). Assume there exist constants Iy < ∞ and Blr < ∞ such that sup

Ey,η ∥Sy (X; η)∥22 ≤ Iy ,

η∈B2 (η0 ,r0 )

and for all η, η ′ ∈ B2 (η0 , r0 ), all t ∈ [0, 1], and ηt = η ′ + t(η − η ′ ), py,ηt (x)/py,η′ (x) ≤ Blr for almost every x. Let Imax := max{I0 , I1 }. (c) Define the pairwise likelihood-ratio contrast ∆η (x, z) :=

Λη (x) Λη (z) − . 1 − Λη (x) 1 − Λη (z)

Let Qη := P0,η ⊗ P0,η and Q0 := Qη0 . Assume that there exists cQ > 0 such that, for all η ∈ B2 (η0 , r0 ), Qη ≥ cQ Q0 as measures. For h > 0 and u, u′ ∈ Sd−1 , define ηh,u := η0 + hu,

ηh,u′ := η0 + hu′ ,

and define the rank-disagreement set o n ′ Rh (u, u ) := (x, z) : ∆ηh,u (x, z)∆ηh,u′ (x, z) < 0 . Assume there exist constants α ∈ (0, 1), crk > 0, and h0 > 0 such that, for every h ∈ (0, h0 ] and every u, u′ ∈ Sd−1 satisfying ∥u − u′ ∥2 ≥ α, Z o n min |∆ηh,u (x, z)|, |∆ηh,u′ (x, z)| dQ0 (x, z) ≥ crk h. Rh (u,u′ )

Assumption 4 imposes the regularity and separation conditions needed to prove a minimax lower bound for AUROC. The first two conditions ensure that the model contains a local neighborhood around η0 and that the class-conditional distributions vary smoothly with the parameter. The last condition requires that, for two sufficiently separated local directions, the corresponding likelihood-ratio scores disagree on a non-negligible set of pairs. Thus, although the distributions are close in statistical distance, their oracle rankings differ by order h. Theorem 7 (AUROC Minimax Lower Bound). Under Assumption 4, there exists a constant cd such that, for any d ≥ cd , there exists a constant c > 0 such that, for all sufficiently large sample sizes, r d 1 inf sup Eη {AUCη (Λη ) − AUCη (b s)} ≥ c ≳√ . sb η∈Θ n n Theorem 7 shows that the n−1/2 -type rate for AUROC regret is minimax optimal, up to dimension-dependent factors. Combined with the upper bounds above, this result shows that the raw estimator already attains the optimal rate in the well-specified regime. If the synthetic distributional error is of smaller order than the minimax rate, the augmented estimator can also attain the minimax rate. 18

Assumption 5 (Regularity and Separation Conditions for Balanced Accuracy). Assume Assumption 4(a)–(b). In addition, assume the following local balanced-accuracy oracle boundary disagreement condition. For h > 0 and u, u′ ∈ Sd−1 , define ηh,u′ := η0 + hu′ ,

ηh,u := η0 + hu, and define Dh+ (u, u′ ) := Bηh,u ∩ Bηch,u′ = and Dh− (u, u′ ) := Bηch,u ∩ Bηh,u′ =

1 1 x : Ληh,u (x) ≥ , Ληh,u′ (x) < 2 2

1 1 x : Ληh,u (x) < , Ληh,u′ (x) ≥ 2 2

Assume there exist constants α ∈ (0, 1), cBA > 0, and h0 > 0 such that, for every h ∈ (0, h0 ] and every u, u′ ∈ Sd−1 satisfying ∥u − u′ ∥2 ≥ α, both directed lower bounds hold: ( ) Z Ληh,u′ (x) Ληh,u (x) min −1 , − 1 dP0,η0 (x) ≥ cBA h, + 1 − Ληh,u (x) 1 − Ληh,u′ (x) Dh (u,u′ ) and

(

Z min − Dh (u,u′ )

Ληh,u′ (x) Ληh,u (x) −1 , −1 1 − Ληh,u (x) 1 − Ληh,u′ (x)

) dP0,η0 (x) ≥ cBA h.

Assumption 5 is the analogue of Assumption 4 for best-threshold balanced accuracy. Instead of pairwise ranking disagreements, it focuses on disagreements near the balancedaccuracy oracle boundary {Λη (x) = 1/2}. The sets Dh+ (u, u′ ) and Dh− (u, u′ ) contain points whose balanced-accuracy oracle classifications differ under two nearby parameters. The lower bounds require these disagreement regions to have non-negligible weighted mass of order h. Theorem 8 (Balanced Accuracy Minimax Lower Bound). Under Assumption 5, there exists a constant cd such that, for any d ≥ cd , there exists a constant c > 0 such that, for all sufficiently large sample sizes, r ∗ d 1 ≳√ . inf sup Eη BAη (Λη ) − BA∗η (b s) ≥ c sb η∈Θ n n Theorem 8 shows that best-threshold balanced accuracy also has an unavoidable n−1/2 type minimax lower bound, up to dimension-dependent factors. The intuition is similar to the AUROC case, but the difficulty now comes from uncertainty around the balanced-accuracy oracle boundary rather than pairwise ranking.

Synthetic Augmentation under Misspecified Models

The previous section shows that, under well-specification, synthetic minority augmentation does not change the oracle population ranking target. Its possible benefit is finite-sample variance reduction, offset by any bias from Psyn ̸= P1 . We now turn to the more delicate and practically important case of model misspecification. In this regime, the learned score is not simply a noisy estimate of a likelihood-ratio-aligned oracle; rather, it is the projection of a class-weighted population objective onto a restricted model class. Changing the effective class balance through augmentation can then alter not only the calibration of the fitted score but also its induced ordering within the restricted class. At the unrestricted population level, all class-weighted Bayes scores ηα = gα ◦ Λ share the same likelihood-ratio ranking. Thus, changing α does not change the Bayes ordering itself. Under misspecification, however, the restricted minimizer s∗α ∈ arg mins∈S Rα (s) need not preserve this ordering, and different values of α can lead to very different approximation errors in S. We refer to this phenomenon as an objective-induced ranking mismatch: the raw imbalanced objective may select a restricted score whose ordering is misaligned with the oracle likelihood-ratio ordering. When this mismatch is correctable by moving to a larger effective minority weight, augmentation can improve AUROC, AUPRC, and best-threshold performance by moving the training objective toward an effective prior whose Bayes score is better approximated by the model class. Recall from Section 2 that, for any effective minority weight α ∈ (0, 1), the unconstrained minimizer of Rα is ηα (x) = gα (Λ(x)),

gα (t) =

αt . (1 − α)(1 − t) + αt

Thus, the central issue in this section is not a change in the Bayes ordering, but misspecification: the difficulty of approximating ηα within S can depend strongly on α. When α ≪ 1, the transformation gα becomes sharply nonlinear. Indeed, gα′ (t) =

α(1 − α) , {(1 − α)(1 − t) + αt}2

gα′ (1) =

1−α , α

gα′′ (1) =

2(1 − α)(1 − 2α) . α2

Thus, for α ≪ 1, the map compresses moderate values of Λ(x) toward zero while developing a sharp transition near t = 1. Hence, even when Λ is well approximated by S, the composition gα ◦ Λ = ηα need not be. The next two examples make this phenomenon concrete. Example 1 (Lipschitz Transformation Class). Let K ∈ (1/2, 1), and define HK = {h : [0, 1] → [0, 1] : |h(t) − h(t′ )| ≤ K|t − t′ |,

∀ t, t′ ∈ [0, 1]} .

Consider the restricted score class of likelihood-ratio scores after a Lipschitz transformation: SK = {x 7→ h(Λ(x)) : h ∈ HK } .

Since K < 1, the identity map t 7→ t is not contained in HK , and hence any non-constant balanced target Λ is not exactly represented in SK . We can show that, whenever the imbalance is severe enough that α < 1 − 1/(2K), inf sup |h(t) − gα (t)| > inf sup |h(t) − t|.

h∈HK t∈[0,1]

Moreover, let µ be a probability measure on X . Suppose there exists a constant r0 > 0 such that Λ(X), with X ∼ µ, admits a density q satisfying q(t) ≥ q > 0 on [1 − r0 , 1]. Whenever 450(1 − K)2 1 , < α ≤ min r0 , q 15K we have inf Eµ (h(Λ(X)) − Λ(X))2 < inf Eµ (h(Λ(X)) − gα (Λ(X)))2 .

h∈HK

Thus, under severe imbalance, the balanced likelihood-ratio score can be easier to approximate than the corresponding imbalanced Bayes score. Example 2 (Norm-Constrained Shallow ReLU Network). Let X = (X1 , . . . , Xp ) ∈ [0, 1]p . Assume that the normalized likelihood-ratio score has the generalized additive form p

1X λj (xj ), Λ(x) = p j=1 where each λj : [0, 1] → [0, 1] is twice continuously differentiable and satisfies λj (1) = 1 for j = 1, . . . , p. Assume further that there exist constants B1 , B2 < ∞, 0 < r0 < 1, and λ− > 0 such that, for every j = 1, . . . , p, ∥λ′j ∥L∞ ([0,1]) ≤ B1 ,

∥λ′′j ∥L∞ ([0,1]) ≤ B2 ,

and λ′j (t) ≥ λ− ,

t ∈ [1 − r0 , 1].

Let σ(u) = u+ = max{u, 0} be the ReLU activation function. For an integer m ≥ p and a network-norm budget A > 0, define the shallow ReLU class ( ) m m X X (p) Nm,A = x 7→ β0 + β ⊤ x + aℓ σ(wℓ⊤ x − tℓ ) : ∥β∥2 + |aℓ | ∥wℓ ∥2 ≤ A . ℓ=1

ℓ=1

Here m is the number of hidden ReLU units, and A is a standard path-norm or variationnorm budget. Assume the norm regularization is not too restrictive and the number of hidden ReLU units is not too small relative to the feature dimension: ( r ) B1 B2 A ≥ √ + B2 , m ≥ p max 1, . p 2 21

Also assume the imbalance is severe: 2λ− 1 B2 0 < αraw < min λ− r0 , √ − . A p 4 8(⌊m/p⌋ + 1)2 Then inf ∥s − η1/2 ∥L∞ ([0,1]p ) < inf ∥s − ηαraw ∥L∞ ([0,1]p ) . (p)

(p)

s∈Nm,A

Thus, for sufficiently severe imbalance, the balanced target is strictly easier to approximate within the same fixed-width, norm-constrained shallow ReLU class. The detailed proofs of Examples 1 and 2 can be found in Section S2 of the supplementary materials. The examples show that the target induced by the training prior can be substantially harder or easier to approximate within a misspecified class. To quantify this approximation effect, define the α-specific approximation error ϵα = inf {Rα (s) − Rα (ηα )} . s∈S

Both terms use the same α because ηα is the unconstrained minimizer of the same objective Rα . Thus, ϵα is the misspecification error of S for the objective induced by training with effective prior α. In particular, ϵbal := ϵ1/2 = inf R1/2 (s) − R1/2 (Λ) , ϵraw := ϵαraw , s∈S

where η1/2 = Λ. The quantity ϵbal corresponds to balanced augmentation, ñ = n0 − n1 . Adding ñ synthetic minority samples sets the effective minority weight to α(ñ) =

n1 + ñ . n0 + n1 + ñ

Equivalently, targeting α ≥ αraw requires ñ =

α n0 − n 1 1−α

synthetic samples. The best achievable approximation error over augmentation levels is ϵ∗ =

inf α∈(αraw ,1)

ϵα .

When the infimum is attained, let α∗ be a minimizer, with corresponding augmentation size ñ∗ =

α∗ n0 − n 1 . 1 − α∗

In practice, α∗ , or equivalently ñ∗ , can be selected by data-driven methods such as K-fold cross-validation (Ma and Zhang, 2026). 22

This perspective separates two regimes. If ϵraw is small, the raw objective is already effectively well-specified for ranking. If instead ϵraw ≫ ϵbal ≥ ϵ∗ , the raw objective forces S to approximate the sharply transformed ηαraw , whereas augmentation toward α∗ targets a smoother or otherwise better-approximated ηα . Augmentation then improves discrimination not by changing the Bayes ranking, which is prior-invariant, but by reducing the objectiveinduced ranking mismatch and letting the restricted minimizer track that common ranking more faithfully. We continue to consider a score class S, where each score s ∈ S is parameterized as sθ with θ ∈ Θ. We impose the following assumptions. Assumption 6. The following conditions hold. • The score takes values in [0, 1]. There exists a constant u0 ∈ [0, 1] such that ℓ(u0 , 0) = min ℓ(u, 0), u∈[0,1]

and there exists m0 > 0 such that, for all u ∈ [0, 1], ℓ(u, 0) − ℓ(u0 , 0) ≥ m0 (u − u0 )2 . Assume the constant score s0 (x) ≡ u0 belongs to S. • There exists BLR < ∞ such that Lη∗ (x) ≤ BLR

P0 -almost surely.

Moreover, there exists Bs < ∞ such that, for every non-constant score s ∈ S, the distribution function F0,s (t) = P0 (s(X) ≤ t) is continuous and Bs -Lipschitz: |F0,s (t) − F0,s (t′ )| ≤ Bs |t − t′ |

for all t, t′ ∈ R.

• The minority-risk range is finite: D1 := sup |EP1 ℓ(s(X), 1) − EP1 ℓ(t(X), 1)| < ∞. s,t∈S

• The loss is strictly proper and satisfies the quadratic calibration condition Cη (u) − Cη (η) ≥ mℓ (u − η)2 , where Cη (u) = ηℓ(u, 1) + (1 − η)ℓ(u, 0).

• The pairwise margin condition holds: P (|Λ(X1 ) − Λ(X0 )| ≤ t) ≤ Cpair t for all sufficiently small t > 0, where X1 ∼ P1 and X0 ∼ P0 are independent. Under these assumptions, we obtain the following improvement guarantees. Theorem 9 (Empirical AUROC and AUPRC Improvement under Misspecification). Under Assumptions 6 and 3(a)–(g), for any AUROC level A ∈ (1/2, AUC(Λη∗ )), whenever the data imbalance is severe enough that αraw D1 < m0 1 − αraw

A − 21 √ Bs (1 + BLR )

2 ,

there exists a constant C > 0 such that, with probability at least 1 − δ, ∗ 1/3 ϵ AUC(sθ̂aug )−AUC(sθ̂raw ) ≥ AUC(Λη∗ ) − A − C mℓ s r CLs c B 2 d log(14d/δ) 1 ∗ ∗ n1 − CLg Ls α − (1 − α ) ϵsyn . − λ n0 + n 1 2µLα n0 Similarly, for any AUPRC level A ∈ (π1 , AUPRC(Λη∗ )), whenever the data imbalance is severe enough that 4  αraw A − π1  , D1 < m0  q √ π0 1 − αraw 2 B B (1 + B ) π1

there exists a constant C > 0 such that, with probability at least 1 − δ, 1/2 ∗ 1/6 π0 ϵ AUPRC(sθ̂aug ) − AUPRC(sθ̂raw ) ≥ AUPRC(Λη∗ ) − A − C π1 mℓ r 2 1/4 CLs c π0 B d log(14d/δ) − λ π1 n0 + n 1 " 2 #1/4 r 2 L π0 n1 g − CLs α∗ − (1 − α∗ ) ϵsyn . π1 µLα n0 Theorem 10 (Empirical Best-Threshold BA and F1 Improvement under Misspecification). Suppose Assumption 6 holds, except that the pairwise margin condition is replaced by the best-threshold anti-concentration condition: there exist constants C, t0 > 0 such that, for every relevant parameter θ, every threshold τ ∈ R, every r ∈ [0, t0 ], and each y ∈ {0, 1}, Py (|sθ (X) − τ | ≤ r) ≤ Cr. 24

Also suppose Assumption 3(b)–(g) holds. Then for any balanced-accuracy level 1 ∗ A∈ , BA (Λη∗ ) , 2 whenever the data imbalance is sufficiently severe that αraw D1 < m0 1 − αraw

A − 21 p √ Bs (1 + BLR )

!4 ,

there exist constants C, c > 0 such that, with probability at least 1 − δ, r 1 − α∗ + α∗ BLR ϵ∗ ∗ ∗ ∗ BA (sθbaug ) − BA (sθbraw ) ≥ BA (Λη∗ ) − A − 2α∗ (1 − α∗ )3/2 mℓ s CLs c B 2 d log(14d/δ) CLs Lg ∗ ∗ n1 − −√ α − (1 − α ) ϵsyn . λ n0 + n1 n0 2µLα Similarly, let bπ := 2π1 /(1 + π1 ). For any best-threshold F1 level A ∈ (bπ , F∗1 (Λη∗ )) , whenever the data imbalance is sufficiently severe that αraw D1 < m0 1 − αraw

A − bπ p √ 4 Bs (1 + BLR )

!4 ,

there exist constants C, c > 0 such that, with probability at least 1 − δ, r ∗ ∗ 2 ϵ∗ 2(1 − α + α B ) LR F∗1 (sθbaug ) − F∗1 (sθbraw ) ≥ F∗1 (Λη∗ ) − A − α∗ (1 − α∗ )3/2 mℓ s 4CLs Lg CLs c B 2 d log(14d/δ) ∗ ∗ n1 − √ − α − (1 − α ) ϵsyn . π1 λ n0 + n1 n0 π1 2µLα Theorems 9 and 10 show that synthetic augmentation can yield genuine improvements in ranking and threshold-based performance under model misspecification. The intuition is as follows. Fix a target performance level A. When the imbalance is sufficiently severe, the raw objective becomes strongly majority-favoring, so its population minimizer cannot pay enough majority-class risk cost to produce a score with high discrimination. Consequently, the raw population score has AUROC, AUPRC, balanced accuracy, or F1 score bounded by A. Augmentation instead moves the effective prior from αraw to a larger α, changing the restricted target from the sharply transformed ηαraw to a smoother or otherwise betterapproximated ηα . When α is chosen so that ϵα is small, optimally ϵα = ϵ∗ , the augmented estimator stays close to a score preserving the likelihood-ratio ordering. The improvement lower bounds reflect exactly this tradeoff: the oracle performance gap is reduced only by the 25

approximation error, finite-sample estimation error, and synthetic distributional error. As the sample size grows and the synthetic distribution becomes accurate, the latter two vanish; if the approximation term is also small enough, the bound remains positive, guaranteeing improvement over the raw imbalanced estimator. Remark 2 (Model Expressiveness Explains Mixed AUROC Gains from Synthetic Augmentation). The literature reviewed in the introduction reports both positive and negative findings on whether synthetic augmentation improves AUROC. For example, Van den Goorbergh et al. (2022) found no AUROC improvement for logistic regression. This is consistent with the regime in which the score model is too restrictive to represent an improved ranking: logistic regression has limited flexibility in complex problems, so both ϵraw and ϵ∗ can be large, and the improvement lower bound need not be positive. By contrast, studies reporting gains typically use more expressive models such as neural networks or boosting, matching the regime in which the model class is rich enough to exploit the rebalanced objective while augmentation corrects the ranking errors induced by the raw prior. Our theory thus explains these mixed findings: AUROC gains from synthetic augmentation depend not only on the quality of the generated data, but also on whether the model class can exploit the information introduced by augmentation.

Simulation Studies

We conduct simulation studies that illustrate the theoretical findings of Sections 3 and 4. The simulations are organized into three regimes: a well-specified setting in which the fitted score family matches the data-generating mechanism exactly (Section 3.1), a restrictedmodel setting in which logistic regression is fitted to data-generating distributions with varying degrees of compatibility with a linear score, and a flexible-model setting in which a multilayer perceptron (MLP) is fitted to two of those same distributions. In each study, all reported metrics are evaluated on an independent test set of ntest observations drawn from the original population distribution (P0 , P1 ), and synthetic samples never enter the test set and are used only to modify the training objective. For a training set with n0 majority and n1 minority observations, we define the synthetic proportion nsyn ∈ [0, 1], q = n0 − n 1 the fraction of the majority-minority size gap closed by adding nsyn synthetic minority samples to training. The grid of q values is study-specific and is stated within each subsection, rather than fixed across all three studies. All results are averaged over 100 independent replications. Unless noted otherwise, the lines represent the across-replication mean, and shaded bands show the mean ± one standard error. We compare raw training (no augmentation) with up to three augmentation strategies: an oracle benchmark that draws additional minority samples from the true P1 serving as an ideal reference for distribution-matched augmentation, bootstrap resampling of the observed minority training data, and SMOTE (Chawla et al., 2002) which creates synthetic samples by linear interpolation between neighboring minority observations. 26

Threshold tuning protocol. When validation-tuned decision-level metrics are reported (Sections 5.1, 5.2, and 5.3), the training set is split into a fitting set and a validation set; oracle, bootstrap, and SMOTE samples are generated only from the minority observations in the fitting set, and each classifier is trained on the fitting set or its augmented version. AUROC and AUPRC are computed directly from test scores without threshold tuning, since they depend only on the score ordering. For balanced accuracy and F1 score, we use two separate thresholds maximizing the metrics on the validation set to estimate the best-threshold performance, and the metrics are evaluated at these thresholds on the independent test set. Section 5.2 additionally reports balanced accuracy and F1 score at the fixed threshold 0.5 alongside their validation-tuned threshold counterparts, so that the fixed-threshold values there serve as a diagnostic for threshold tuning rather than as the best-threshold metric studied in Section 4.

5.1

Well-Specified Case

We first consider the well-specified setting of Section 3, in which the fitted score family closely matches the data-generating mechanism. The predictor X ∈ Rp has p = 10 coordinates. The first five coordinates of X are Gaussian with a nonzero mean vector 0.515 and an AR(1) covariance structure, Σjk = ρ|j−k| with ρ = 0.5 (the same AR(1) coefficient used throughout this section), and the last five are multivariate Student-t with ν = 5 degrees of freedom, a nonzero location vector 0.515 , and a comparable AR(1) scale matrix of the same form. The minority class prior is π1 = 0.05, with ntrain = 10,000 training samples and ntest = 5,000 test samples. We consider three well-specified models, each fitted with the estimator matching its generative mechanism: • Logistic: X is drawn from the mixed marginal distribution above, and Y | X = x is then generated as Bernoulli with success probability sη∗ (x) = (1 + exp(−η ∗⊤ x))−1 . The resulting data are fitted by logistic regression. • Probit: X is drawn from the same marginal distribution, and Y | X = x is then generated as Bernoulli with success probability Φ(η ∗⊤ x), where Φ is the cumulative distribution function of a standard normal distribution. The resulting data are fitted by probit regression. • Generative likelihood-ratio MLE (Section 3.1): a class-conditional likelihood-ratio MLE benchmark, distinct from the conditional MLE underlying the logistic and probit rows above. Here Y is generated first with prior π1 = 0.05, and X | Y is then generated from class-conditional Gaussian and multivariate Student-t components. For Y = 0, both blocks have mean location vector 0.515 . For Y = 1, the Gaussian block has mean vector 0.8515 and the Student-t block has location vector 0.7515 . The classifier is the likelihood-ratio statistic obtained from class-conditional densities estimated by maximum likelihood, rather than a fitted linear index. For the logistic and probit rows, the intercept component of η ∗ is calibrated by Monte Carlo root-finding so that the marginal minority prevalence P(Y = 1) ≈ π1 = 0.05, matching the 27

imbalance level used in the other studies. We compare raw training with bootstrap and SMOTE augmentation as synthetic proportion q varies between 0 and 1, reporting AUROC, AUPRC, and validation-tuned best-threshold balanced accuracy and F1 score (threshold tuning protocol above).

Figure 2: AUROC, AUPRC, validation-tuned best-threshold balanced accuracy and F1 score (columns), as a function of the synthetic proportion, for three well-specified models (rows): logistic, probit, and generative likelihood-ratio MLE. Figure 2 shows that, under this well-specified model setting, augmentation provides no meaningful benefit and may even be harmful in some cases. In the logistic and probit results, raw, bootstrap, and SMOTE are visually indistinguishable across the full range of synthetic proportions and across all four metrics, consistent with the prediction that augmentation does not alter the population-optimal ranking when the score family is well-specified. For the generative likelihood-ratio MLE, bootstrap remains comparable to raw, but SMOTE noticeably underperforms both raw training and bootstrap as the synthetic proportion increases, lowering AUROC, AUPRC, and both tuned metrics. Because SMOTE constructs synthetic points by linear interpolation rather than by sampling from the true class-conditional generative distributions, it introduces a synthetic distributional mismatch Psyn ̸= P1 that adds bias without any compensating gain in ranking quality, exactly the failure mode anticipated in Remark 1. These results are consistent with the theoretical prediction that, under well-specified models, synthetic augmentation provides no systematic population-level improvement in score ordering, except for possible finite-sample variance effects and possible degradation from synthetic distributional mismatch. This degradation is better interpreted as evidence of synthetic distributional mismatch rather than as a consequence of model-class misspecification.

5.2

Restricted Logistic Regression across Linear and Nonlinear Likelihood Ratios

We next examine logistic regression as a restricted model class with linear score functions, fitted to four data-generating distributions chosen to span a range of true likelihoodratio shapes. With shared covariance across classes, Gaussian and Gaussian AR(1) classconditional distributions have a likelihood-ratio statistic that is exactly linear in x. Logistic regression is therefore effectively well specified for these two settings, and we include them as linear-likelihood-ratio controls. The t5 setting has a true likelihood ratio that depends nonlinearly on x through the quadratic form in the multivariate Student-t density, so logistic regression is only mildly misspecified there. The fourth distribution, Mixture, serves as the main restricted-model misspecification example in this subsection. Its minority class is a mixture of a multivariate t5 component and a Gaussian AR(1) component with distinct means and covariances, so its true likelihood ratio is genuinely nonlinear and not well approximated by any linear score. For a misspecified model with a restricted score class, such as linear logistic regression, adding synthetic data does not alter the inherent linearity of the model class. Consequently, the approximation errors ϵ∗ and ϵraw defined in Section 4 may both be large. In this regime, the lower bounds in Section 4 need not be positive, and therefore no improvement guarantee can be established. We use the same general configuration as above, with p = 10 predictors, ntrain = 10,000, ntest = 5,000, and π1 = 0.05. The synthetic proportion is varied between 0 and 1. The four data-generating distributions are: Gaussian, with P0 = N (0, Ip ) and P1 = N (µ1 1, Ip ), µ1 = 0.5; t5 , with P0 = t5 (0, Ip ) and P1 = t5 (µ1 1, Ip ); Gaussian AR(1), with P0 = N (0, Σ) and P1 = N (µ1 1, Σ), where Σjk = ρ|j−k| with ρ = 0.5; and a mixture minority distribution, P1 = πA PA + (1 − πA ) PB ,

πA = 0.5,

where PA is multivariate t5 with mean µA = (0.8, 0.6, −0.7, 0.5, 0.4, −0.5, 0.3, 0.4, −0.3, 0.2)⊤ and diagonal scale ΣA = diag(1.4, 1.2, 1.5, 1.0, 1.3, 1.1, 0.9, 1.2, 1.0, 0.8), and PB is Gaussian with mean µB = (−0.6, 0.7, 0.5, −0.8, 0.6, 0.4, −0.5, 0.3, 0.5, −0.4)⊤ and AR(1)-type covariance (ΣB )jk = 1.3 × 0.6|j−k| . We compare raw training with oracle, bootstrap, and SMOTE augmentation. Figure 3 confirms this distinction visually. For the two linear-likelihood-ratio controls, the AUROC and AUPRC curves for raw, oracle, bootstrap, and SMOTE are nearly indistinguishable across the full range of synthetic proportions, well within the shaded variability bands, and the mildly nonlinear t5 case shows the same pattern. This is consistent with logistic regression already attaining close to the best ordering it can represent in these three settings, leaving augmentation essentially no room to help or hurt. However, in the Mixture setting, as the synthetic proportion grows, augmentation visibly improves AUROC while degrading AUPRC. This metric-specific, non-uniform pattern is consistent with the general tradeoff developed in Section 4: when the model class is overly restricted, both the raw and augmented target score functions may be difficult to approximate, and no general improvement guarantee can be established. 29

Figure 3: AUROC and AUPRC as functions of the synthetic proportion, for logistic regression applied to four data-generating distributions: Gaussian, t5 , Gaussian AR(1), and Mixture. Figure 4 complements the ranking-metric results by comparing validation-tuned bestthreshold balanced accuracy and F1 score. For the validation-tuned best-threshold metrics, adding synthetic data provides little to no improvement across the four data-generating distributions. Performance at the fixed 0.5 threshold is also reported for comparison. For the fixed threshold, synthetic augmentation can substantially improve performance because it effectively rebalances the training data relative to that fixed decision threshold. In addition, validation-threshold tuning of the raw score can achieve performance comparable to the best fixed-threshold synthetic-augmented classifier obtained by choosing an appropriate synthetic proportion. This comparison suggests that the large fixed-threshold gains from synthetic augmentation mainly reflect threshold recalibration rather than genuine improvements in score ordering.

Figure 4: Balanced accuracy (top) and F1 score (bottom) at the fixed 0.5 threshold and at validation-tuned thresholds, as a function of the synthetic proportion, for logistic regression applied to four data-generating distributions: Gaussian, t5 , Gaussian AR(1), and Mixture.

5.3

Misspecified Case with Complex Classification Model Class

Finally, we consider a flexible model class, a multilayer perceptron (MLP) with two hidden layers of widths (64, 32), ReLU activations, Adam optimization, early stopping on a validation split, and standardized inputs, applied to the t5 distribution and Gaussian AR(1) distribution with ρ = 0.5, as defined above. Although the Gaussian AR(1) distribution has a linear likelihood-ratio structure, the finite-sample MLP trained under severe imbalance can still behave as an effectively restricted learner. Within this flexible MLP class, the raw imbalanced training objective can select a poor score ordering, even though the population MLP class could represent a better one. Augmentation changes the effective class balance seen during training and can correct this objective-induced ranking mismatch. We compare raw training with oracle, bootstrap, and SMOTE augmentation, reporting AUROC and AUPRC together with decision-level metrics evaluated both at a validation-tuned best-threshold and a fixed threshold of 0.5. The synthetic proportion is varied between 0 and 1.

Figure 5: AUROC (top) and AUPRC (bottom) as a function of the synthetic proportion, for an MLP applied to the t5 distribution (left) and Gaussian AR(1) distribution with ρ = 0.5 (right). Figure 5 addresses the score-ordering metrics AUROC and AUPRC. Oracle augmentation yields substantial and sustained improvements over raw training in AUROC and AUPRC for both distributions. Bootstrap and SMOTE also improve over raw, but nonmonotonically: their gains peak at a moderate synthetic proportion and decline as the proportion increases further. The decline is more pronounced for AUPRC, where the moderate-proportion gain largely fades at the largest synthetic proportions, leaving performance close to the raw baseline. This pattern is consistent with Theorem 9: moderate, high-quality augmentation corrects the objective-induced ranking mismatch, but as the proportion of imperfect synthetic data grows, the synthetic distributional error ϵsyn increasingly contaminates training and 31

erodes the gain, whereas the oracle benchmark sampling from the true P1 avoids this bias and maintains its advantage throughout.

Figure 6: Balanced accuracy (top) and F1 score (bottom) at a fixed 0.5 threshold and at a validation-tuned threshold, as a function of the synthetic proportion, for an MLP applied to the t5 distribution (left) and the Gaussian AR(1) distribution with ρ = 0.5 (right). Figure 6 addresses the validation-tuned best-threshold metrics. It shows that augmentation can improve balanced accuracy and F1 score beyond what threshold tuning of the raw score alone achieves. At the fixed 0.5 threshold, raw training performs poorly. Tuning the threshold of the raw score substantially improves its balanced accuracy and F1 score, and a visible gap to the augmented methods remains. Bootstrap and SMOTE generally outperform the tuned raw score over a broad range of synthetic proportions, with the clearest gains at moderate augmentation levels. These gains narrow somewhat at larger synthetic proportions but stay positive throughout, again reflecting the nonmonotone tradeoff between correcting the ranking mismatch at moderate augmentation and accumulating synthetic distributional error at high augmentation. This is consistent with Theorem 10: when the effective model class is rich enough to represent an improved ordering and the imbalance is severe, augmentation corrects the objective-induced ranking mismatch itself, so that even after validation-based threshold tuning, the augmented score can yield better decision-level performance than the raw score, an improvement that threshold tuning of the raw score alone cannot fully replicate. Together, the three studies trace out the regimes identified by the theory. Under wellspecification, augmentation gives little or no systematic benefit and can hurt performance when Psyn ̸= P1 (Section 3). Under a restricted linear-score model, augmentation has negligible effects on score ordering when the model is effectively well-specified, and has metricspecific, non-uniform effects when it is genuinely misspecified, while the large apparent gains 32

at a fixed decision threshold are mainly threshold recalibration rather than improved ordering. Under a flexible learner that behaves as effectively restricted under severe imbalance, augmentation can improve both score ordering and validation-tuned decision metrics beyond what threshold tuning of the raw score alone achieves, with nonmonotone gains that are clearest at moderate augmentation levels and diminish as synthetic distributional error accumulates at larger synthetic proportions (Section 4).

Discussion

This paper studies when synthetic minority augmentation can improve score-based imbalanced classification. Our results show that the effect of augmentation depends strongly on the relationship between the learned score, the likelihood-ratio ordering, and the synthetic minority distribution. Under well-specified score models, the raw estimator already targets the population-optimal likelihood-ratio ordering, so augmentation cannot provide a fundamental improvement for the score-based metrics considered here beyond possible finite-sample variance reduction. Under misspecification, however, high-quality synthetic data augmentation can play a different role: by changing the effective training objective, it can alter the learned score ordering and correct ranking errors that threshold tuning alone cannot repair. Several limitations remain. First, our theory focuses on binary classification and scorebased evaluation metrics such as AUROC, AUPRC, best-threshold balanced accuracy, and best-threshold F1 score. Extending the framework to multiclass, multilabel, or structuredoutput classification would require new notions of oracle ordering and ranking mismatch. Second, our analysis treats the synthetic distribution Psyn through distributional discrepancy measures such as Wasserstein distance. This abstraction is useful for general theory, but it does not fully capture the algorithm-specific behavior of modern generators such as diffusion models, GANs, or large language models. A sharper theory would connect generator training, minority sample size, and augmentation quality more directly. Finally, the improvement guarantees under misspecification are sufficient conditions rather than necessary ones. The ranking-mismatch functionals identify regimes where augmentation can provably improve over the raw score or threshold tuning, but they may be difficult to estimate accurately in practice because the likelihood-ratio score is unknown. Developing data-driven diagnostics for detecting correctable ranking mismatch would make the theory more practically actionable.

References T. Ahmad, M. M. Kalan, F. Portier, and G. Stupfler. Concentration and excess risk bounds for imbalanced classification with synthetic oversampling. arXiv preprint arXiv:2510.20472, 2025. R. L. Almeida, V. G. Maltarollo, and F. G. F. Coelho. Overcoming class imbalance in 33

drug discovery problems: Graph neural networks and balancing approaches. Journal of Molecular Graphics and Modelling, 126:108627, 2024. R. Blagus and L. Lusa. Smote for high-dimensional class-imbalanced data. BMC bioinformatics, 14(1):106, 2013. D. Breskuvienė and G. Dzemyda. Enhancing credit card fraud detection: highly imbalanced data case. Journal of Big Data, 11(1):182, 2024. C. Bunkhumpornpat, K. Sinapiromsaran, and C. Lursinsap. Safe-level-SMOTE: Safe-levelsynthetic minority over-sampling technique for handling the class imbalanced problem. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 475–482. Springer, 2009. C. Bunkhumpornpat, K. Sinapiromsaran, and C. Lursinsap. Dbsmote: density-based synthetic minority over-sampling technique. Applied Intelligence, 36(3):664–684, 2012. N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer. SMOTE: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 16:321–357, 2002. R. Chen, W. Zhang, B. Liu, X. Wu, X. Chen, P. Xu, S. Liu, M. He, and D. Shi. Boosting foundation models for rare eye disease diagnosis via a multimodal text-to-image generative framework. npj Digital Medicine, 2026. W. Chen, K. Yang, Z. Yu, Y. Shi, and C. P. Chen. A survey on imbalanced learning: latest research, applications and future directions. Artificial Intelligence Review, 57(6): 137, 2024a. Y. Chen, R. Calabrese, and B. Martin-Barragan. Interpretable machine learning for imbalanced credit scoring datasets. European Journal of Operational Research, 312(1):357–372, 2024b. S. Clémençon, G. Lugosi, and N. Vayatis. Ranking and empirical minimization of u-statistics. The Annals of Statistics, pages 844–874, 2008. J. Cook and V. Ramadas. When to consult precision-recall curves. The Stata Journal, 20 (1):131–148, 2020. B. Efron and R. J. Tibshirani. An introduction to the bootstrap. Chapman and Hall/CRC, 1994. I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014. H. Han, W. Y. Wang, and B. H. Mao. Borderline-SMOTE: A new over-sampling method in imbalanced data sets learning. In International Conference on Intelligent Computing, pages 878–887. Springer, 2005. 34

H. He, Y. Bai, E. A. Garcia, and S. Li. ADASYN: Adaptive synthetic sampling approach for imbalanced learning. In 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), pages 1322–1328. IEEE, 2008. J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840–6851, 2020. M. Kannan, D. Umamaheswari, B. Manimekala, I. P. S. Mary, P. M. Savitha, and J. Rozario. An enhancement of machine learning model performance in disease prediction with synthetic data generation. Scientific Reports, 15(1):33482, 2025. N. Keret and A. Shojaie. Glm inference with ai-generated synthetic data using misspecified linear regression. arXiv preprint arXiv:2503.21968, 2025. H. Kim, W. S. Jang, W. S. Sim, H. S. Kim, J. E. Choi, E. S. Baek, Y. R. Park, and S. J. Shin. Synthetic data improve survival status prediction models in early-onset colorectal cancer. JCO clinical cancer informatics, 8:e2300201, 2024. D. P. Kingma and M. Welling. arXiv:1312.6114, 2013.

Auto-encoding variational Bayes.

arXiv preprint

J. Li, B. J. Cairns, J. Li, and T. Zhu. Generating synthetic mixed-type longitudinal electronic health records for artificial intelligent applications. NPJ digital medicine, 6(1):98, 2023. P. Lyu, Z. Ma, L. Zhang, and A. R. Zhang. Bias-corrected data synthesis for imbalanced learning. arXiv preprint arXiv:2510.26046, 2025. Z. Ma and A. R. Zhang. Synthetic augmentation in imbalanced learning: When it helps, when it hurts, and how much to add. arXiv preprint arXiv:2601.16120, 2026. R. Nakada, Y. Xu, L. Li, and L. Zhang. Synthetic oversampling: Theory and a practical approach using llms to address data imbalance. arXiv preprint arXiv:2406.03628, 2024. B. P. Nguyen, H. N. Pham, H. Tran, N. Nghiem, Q. H. Nguyen, T. T. Do, C. T. Tran, and C. R. Simpson. Predicting the onset of type 2 diabetes using wide and deep learning with electronic health records. Computer methods and programs in biomedicine, 182:105055, 2019. G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed, and B. Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57):1–64, 2021. M. Piccininni, M. Wechsung, B. Van Calster, J. L. Rohmann, S. Konigorski, and M. van Smeden. Understanding random resampling techniques for class imbalance correction and their consequences on calibration and discrimination of clinical risk prediction models. Journal of biomedical informatics, 155:104666, 2024.

O. Räisä, J. Jälkö, and A. Honkela. On consistent bayesian inference from synthetic data. Journal of Machine Learning Research, 26(74):1–65, 2025. M. Sadinle, J. Lei, and L. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223–234, 2019. M. Salmi, D. Atif, D. Oliva, A. Abraham, and S. Ventura. Handling imbalanced medical datasets: review of a decade of research. Artificial intelligence review, 57(10):273, 2024. F. Santambrogio. Optimal transport for applied mathematicians: Calculus of variations, pdes, and modeling. 2015. X. Shen, Y. Liu, and R. Shen. Boosting data analytics with synthetic volume expansion. The Annals of Applied Statistics, 2026. K. I. Siddavatam and S. K. Shinde. A hybrid literature review on handling imbalanced medical data: Ai models and open issues. Expert Systems with Applications, page 129004, 2025. X. Tian and X. Shen. Conditional data synthesis augmentation. arXiv:2504.07426, 2025.

arXiv preprint

J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389–434, 2012. R. Van den Goorbergh, M. Van Smeden, D. Timmerman, and B. Van Calster. The harm of class imbalance corrections for risk prediction models: illustration and simulation using logistic regression. Journal of the American Medical Informatics Association, 29(9):1525– 1534, 2022. R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. E. Xia and J. M. Klusowski. Classification imbalance as transfer learning. arXiv preprint arXiv:2601.10630, 2026. Y. Xu. Generative synthetic data for causal inference: Pitfalls, remedies, and opportunities. arXiv preprint arXiv:2604.23904, 2026. C. Yang, E. A. Fridgeirsson, J. A. Kors, J. M. Reps, and P. R. Rijnbeek. Impact of random oversampling and random undersampling on the performance of prediction models developed using observational health data. Journal of Big Data, 11(1):7, 2024. R. Zbinden, N. Van Tiel, M. Rußwurm, and D. Tuia. Imbalance-aware presence-only loss function for species distribution modeling. arXiv preprint arXiv:2403.07472, 2024. 36

H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. Mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09412, 2017. Z. Zheng, J. Xia, J. Luo, L. Du, X. Zhou, X. Yang, Y. Xia, M. Liu, and S. Huang. Using machine learning for early prediction of in-hospital mortality during icu admission in liver cancer patients. Scientific reports, 15(1):40507, 2025.

Supplementary Materials for “When Does Synthetic Data Augmentation Improve Score-Based Imbalanced Classification?” Zhengchi Ma1 , Pengfei Lyu2 , and Anru R. Zhang2,3 1 Department of Electrical & Computer Engineering, Duke University 2 Department of Biostatistics & Bioinformatics, Duke University 3 Department of Computer Science, Duke University

In the supplementary material, we provide the detailed proofs for the theoretical results in the paper.

Proofs of Theorems

Proof of Theorem 1. We prove the statements for AUROC and AUPRC separately. AUROC: First, we show that AUROC is invariant under strictly increasing transformations. If h : R → R is strictly increasing, then for any score s {s(x1 ) > s(x0 )} ⇔ {h(s(x1 )) > h(s(x0 ))} ,

{s(x1 ) = s(x0 )} ⇔ {h(s(x1 )) = h(s(x0 ))} .

Thus the events in the AUROC definition are identical under s and h ◦ s, and thus AUC(h ◦ s) = AUC(s). That is, equivalently AUC(g(Λη∗ (X))) = AUC(Λη∗ (X)). For ease of notation, let ∆s := s(X1 ) − s(X0 ). Then the AUROC can be written as 1 AUC(s) = E 1{∆s > 0} + 1{∆s = 0} . 2 Then for two scores s and s′ , we have 1 |E [1{∆s = 0} − 1{∆s′ = 0}]| 2 1 ≤ E |1{∆s > 0} − 1{∆s′ > 0}| + E |1{∆s = 0} − 1{∆s′ = 0}| 2 ≤ P (Sign(∆s ) ̸= Sign(∆s′ )) . (S1)

|AUC(s) − AUC(s′ )| ≤ |E[1{∆s > 0} − 1{∆s′ > 0}]| +

For the event, it holds that {Sign(∆s ) ̸= Sign(∆s′ )}

⇒ 38

{|∆s | ≤ |∆s − ∆s′ |} .

This holds because the magnitude of one of the two quantities must be no larger than their difference; otherwise, no sign flip can occur. Also, |∆s − ∆s′ | = |s(X1 ) − s(X0 ) − (s′ (X1 ) − s′ (X0 ))| ≤ |s(X1 ) − s′ (X1 )| + |s(X0 ) − s′ (X0 )| . Thus we have the event {|∆s | ≤ |∆s − ∆s′ |}

⇒

{|∆s | ≤ |s(X1 ) − s′ (X1 )| + |s(X0 ) − s′ (X0 )|} .

Therefore by assumption, also condition on the training data such that δn is fixed, it holds that P (Sign(∆s ) ̸= Sign(∆s′ )) ≤ P (|∆s | ≤ |s(X1 ) − s′ (X1 )| + |s(X0 ) − s′ (X0 )|) ≤ P (|∆s | ≤ 2δn ) ≤ 2Cδn ,

(S2)

where the last step holds by assumption when s is taken as g(Λη∗ (·)) and s′ as ŝn . Here δn := ∥ŝ − g ◦ Λη∗ ∥L∞ (P0 +P1 ) = OP (rn ) = oP (1). Therefore 2δn ≤ t0 with probability tending to one. That is |AUC(s) − AUC(s′ )| ≤ P (Sign(∆s ) ̸= Sign(∆s′ )) ≤ 2Cδn = OP (rn ). Thus, by optimality and strictly increasing transformation, we finish the proof. AUPRC: We first show that AUPRC is invariant to strictly increasing transformations. For any strictly increasing function h : R → R, for any threshold u, we have {h(s(x)) ≥ u} ⇔ {s(x) ≥ h−1 (u)}. Therefore the recall Rech◦s (u) = P(h(s(X1 )) ≥ u) = P(s(X1 ) ≥ h−1 (u)) = Recs (h−1 (u)). Similarly for false positive rate and precision, we have FPRh◦s (u) = FPRs (h−1 (u)),

Prech◦s (u) = Precs (h−1 (u)).

Because h is strictly increasing, the map u → t := h−1 (u) is thus a bijection. Therefore, Z Z AUPRC(h ◦ s) = Prech◦s (u)dRech◦s (u) = Precs (t)dRecs (t) = AUPRC(s). Thus we have AUPRC(g(Λη∗ )) = AUPRC(Λη∗ ). Next, we connect the AUPRC difference with score estimation. Define the positive survival transform, Us (x) := P(s(X1 ) ≥ s(x) | x) ∈ [0, 1], 39

and similarly we have Us′ (x). Thus for X1′ , an independent copy of X1 , we have Us (X1 ) = P(s(X1′ ) ≥ s(X1 ) | s(X1 )) = 1 − F1 (s(X1 )) =: F̄1 (s(X1 )), where F1 is the CDF of s(X1 ). We can then define the generalized inverse function F̄1−1 (u) := inf{t ∈ R : F̄1 (t) ≤ u}. By definition F̄1 and F̄1−1 are non-increasing. Thus P(F̄1 (s(X1 )) ≤ u) = P(s(X1 ) ≥ F̄1−1 (u)) = F̄1 (F̄1−1 (u)) = u, where the last step is because of continuity. That is, we have Us (X1 ) = F̄1 (s(X1 )) ∼ Unif[0, 1].

(S3)

For the transformed score, Us (x), we threshold at r ∈ [0, 1] using the rule: predict positive if and only if Us (x) ≤ r, which is equivalent to thresholding the score s(x) at F̄1−1 (r). Then we have the metrics g s (r) := Recs (F̄1−1 (r)) = P(Us (X1 ) ≤ r) = r, Rec ] s (r) := FPRs (F̄1−1 (r)) = P(Us (X0 ) ≤ r), FPR Thus the precision at each recall r is g s (r) := Precs (F̄ −1 (r)) = Prec 1

π1 r . ] s (r) π1 r + π0 FPR

Thus, we have expressed precision as a function of recall through the function F̄1−1 . Taking integral over recall, we have Z 1 π1 r dr. (S4) AUPRC(s) = ] s (r) 0 π1 r + π0 FPR The same arguments also apply to s′ . Then for simplicity, for r ∈ [0, 1], define the function ϕr (z) :=

π1 r , π1 r + π0 z

z ∈ [0, 1].

Therefore, ′

Z 1

|AUPRC(s) − AUPRC(s )| ≤

] s (r)) − ϕr (FPR ] s′ (r)) dr. ϕr (FPR 0

For any z, and z ′ , the ϕr (·) function satisfies |ϕr (z) − ϕr (z ′ )| =

π1 r π1 r π0 |z − z ′ | − . ≤ π1 r + π0 z π1 r + π0 z ′ π1 r 40

Combining this with the trivial bound, we have π0 |z − z ′ | |ϕr (z) − ϕr (z )| ≤ min 1, π1 r

′

(S5)

That is (

Z 1

] s (r) − FPR ] s′ (r)| π0 |FPR |AUPRC(s) − AUPRC(s′ )| ≤ min 1, π1 r 0

) dr.

] s (r) − FPR ] s′ (r)|. Then for any τ ∈ (0, 1], we have Still for simplicity, denote ∆(r) := |FPR the integral Z 1 Z τ Z 1 Z π0 ∆(r) π0 ∆(r) π0 1 1 min 1, dr ≤ 1dr + dr ≤ τ + ∆(r)dr. π1 r r π1 τ 0 0 0 τ π1 q R 1 Then, when 1 < ππ01 0 ∆(r)dr, choose τ = 1, and we have Z 1

π0 ∆(r) min 1, dr ≤ 1. π1 r 0 q R q R 1 1 When ππ01 0 ∆(r)dr ≤ 1, choose τ = ππ01 0 ∆(r)dr, and we have Z 1

π0 ∆(r) min 1, π1 r 0

dr ≤ 2

π0 π1

Z 1 ∆(r)dr. 0

Thus, combining above we have |AUPRC(s) − AUPRC(s′ )| ≤ min

  

Next, we only need to bound

∆(r)dr = 0

µs = Law(Us (X0 )),

s 1, 2

π0 π1

Z 1 ∆(r)dr 0

 

(S6)



] s (r) − FPR ] s′ (r)|dr. Define |FPR µs′ = Law(Us′ (X0 )),

Thus by definition and connection between Wasserstein distance and CDF (e.g. proposition 2.17 of (Santambrogio, 2015)), we have Z 1 ] s (r) − FPR ] s′ (r)|dr. W1 (µs , µs′ ) = |FPR (S7) 0

By the definition of Wasserstein distance, for any coupling Γ of (Us (X0 ), Us′ (X0 )), we have W1 (µs , µs′ ) ≤ EΓ |Us (X0 ) − Us′ (X0 )| . 41

(S8)

Consider the natural coupling where Us (X0 ) and Us′ (X0 ) are coupled through some X0 . Then for fixed X0 , Us (X0 ) = E [1{s(X1 ) ≥ s(X0 )} | X0 ] ,

Us′ (X0 ) = E [1{s′ (X1 ) ≥ s′ (X0 )} | X0 ] .

Thus we have |Us (X0 ) − Us′ (X0 )| ≤ E [|1{s(X1 ) ≥ s(X0 )} − 1{s′ (X1 ) ≥ s′ (X0 )}| | X0 ] ≤ P(1{s(X1 ) ≥ s(X0 )} ̸= 1{s′ (X1 ) ≥ s′ (X0 )} | X0 ) Taking expectation over X0 gives E |Us (X0 ) − Us′ (X0 )| ≤ P(1{s(X1 ) ≥ s(X0 )} ̸= 1{s′ (X1 ) ≥ s′ (X0 )}).

(S9)

Then, combining equations (S7), (S8) and (S9), we have Z 1 ] s (r) − FPR ] s′ (r)|dr ≤ P(1{s(X1 ) ≥ s(X0 )} ̸= 1{s′ (X1 ) ≥ s′ (X0 )}) |FPR 0

= P(Sign(s(X1 ) − s(X0 )) ̸= Sign(s′ (X1 ) − s′ (X0 ))).

(S10)

Define ∆s = s(X1 ) − s(X0 ). By an argument similar to the AUROC case, we have {Sign(∆s ) ̸= Sign(∆s′ )} ⇒ {|∆s | ≤ |∆s − ∆s′ |} ⇒ {|∆s | ≤ |s(X1 ) − s′ (X1 )| + |s(X0 ) − s′ (X0 )|} ⇒ {|∆s | ≤ 2δn } . Therefore by assumption, also condition on the training data such that δn is fixed, it holds that P (Sign(∆s ) ̸= Sign(∆s′ )) ≤ P (|∆s | ≤ 2δn ) ≤ 2Cδn ,

(S11)

where the last step holds by assumption when s is taken as g(Λη∗ (·)) and s′ is taken as ŝn . Thus it holds that Z 1 ] ŝn (r) − FPR ] g(Λ ∗ ) (r)|dr ≤ 2Cδn = OP (rn ). |FPR η 0

Thus, by well-specification assumption, combining equation (S6) for the non-trivial bound, and combining the likelihood-ratio optimality, r π0 rn . (S12) AUPRC(Λη∗ ) − AUPRC(ŝn ) = |AUPRC(ŝn ) − AUPRC(g(Λη∗ ))| = OP π1

Proof of Theorem 2. We prove the results for balanced accuracy and F1 score separately. Balanced Accuracy: 42

We first show that the best-threshold balanced accuracy is invariant under strictly increasing score transformations. Let h be strictly increasing. Then the balanced accuracy satisfies 1 P(s(x1 ) ≥ h−1 (u)) + P(s(x0 ) < h−1 (u)) = BA(s, h−1 (u)). BA(h ◦ s, u) = 2 Taking supremum over all u and noting that u 7→ h−1 (u) is a bijection, we have sup BA(h ◦ s, u) = sup BA(s, τ ). u

That is, we have for any strictly increasing transformation g, sup BA(g(Λη∗ ), τ ) = sup BA(Λη∗ , τ ). τ

Then, for two scores s and s′ , and for a fixed threshold τ , |BA(s, τ ) − BA(s′ , τ )| 1 1 ≤ |P(s(X1 ) ≥ τ ) − P(s′ (X1 ) ≥ τ )| + |P(s(X0 ) < τ ) − P(s′ (X0 ) < τ )| . 2 2

(S13)

We study the first term. It holds that |P(s(X1 ) ≥ τ ) − P(s′ (X1 ) ≥ τ )| = |E [1{s(X1 ) ≥ τ } − 1{s′ (X1 ) ≥ τ }]| ≤ E |1{s(X1 ) ≥ τ } − 1{s′ (X1 ) ≥ τ }| = E1 {1{s(X1 ) ≥ τ } ̸= 1{s′ (X1 ) ≥ τ }} = P (1{s(X1 ) ≥ τ } ̸= 1{s′ (X1 ) ≥ τ }) . We thus have {1{s(X1 ) ≥ τ } ̸= 1{s′ (X1 ) ≥ τ }} ⊆ {|s(X1 ) − τ | ≤ |s(X1 ) − s′ (X1 )|} .

(S14)

Consider δn := ∥ŝ − g ◦ Λη∗ ∥L∞ (P0 +P1 ) = OP (rn ) = oP (1). Combining the above with the assumption, and conditioning on the training data so that δn is fixed, we have |P(s(X1 ) ≥ τ ) − P(s′ (X1 ) ≥ τ )| ≤ P (|s(X1 ) − τ | ≤ |s(X1 ) − s′ (X1 )|) ≤ P (|s(X1 ) − τ | ≤ δn ) ≤ Cδn ,

(S15)

by taking s as the increasingly transformed likelihood g(Λη∗ ) and s′ as ŝn . Also, δn ≤ t0 with probability tending to 1. The same argument for the negative class gives |P(s(X0 ) < τ ) − P(s′ (X0 ) < τ )| ≤ Cδn . Plugging back into equation (S13), and taking s′ as ŝn , we have |BA(ŝn , τ ) − BA(g(Λη∗ ), τ )| ≤ Cδn . 43

Thus we have transformed the difference of balanced accuracy into the score distance. Finally, by the invariance in strictly increasing transformation and the well-specification assumption, combined with likelihood-ratio optimality, we finish the proof for BA. F1 Score: We still first show that the best-threshold F1 is invariant under strictly increasing transformations. Still let h be strictly increasing, and for any threshold u, {h(s(x)) ≥ u} ⇔ {s(x) ≥ h−1 (u)}

{h(s(x)) < u} ⇔ {s(x) < h−1 (u)}.

Hence by similar analysis on recall, precision, and FNR, sup F1 (h ◦ s, u) = sup F1 (s, τ ), u

sup F1 (g(Λη∗ ), τ ) = sup F1 (Λη∗ , τ ).

Consider fixed scores s, s′ and fixed threshold τ . For brevity, denote R := Rec(s, τ ),

Q := FPR(s, τ ),

R′ := Rec(s′ , τ ),

Q′ := FPR(s′ , τ ).

Then the F1 score can be denoted as F1 (s, τ ) = G(R, Q),

where G(r, q) :=

2π1 r . π1 (1 + r) + π0 q

Take derivative, we have 2 2π1 (π1 + π0 q) ∂G = ≤ , 2 ∂r (π1 (1 + r) + π0 q) π1

2π0 π1 r 2 ∂G = − ≤ . 2 ∂q (π1 (1 + r) + π0 q) π1

By the mean value theorem, |F1 (s, τ ) − F1 (s′ , τ )| = |G(R, Q) − G(R′ , Q′ )| ≤

2 (|R − R′ | + |Q − Q′ |) . π1

By similar procedure with equation (S15), condition on the training data, we have |R − R′ | = |P(s(X1 ) ≥ τ ) − P(s′ (X1 ) ≥ τ )| ≤ Cδn , |Q − Q′ | = |P(s(X0 ) ≥ τ ) − P(s′ (X0 ) ≥ τ )| ≤ Cδn ,

(S16)

where we take s as g(Λη∗ ) and take s′ as ŝn . Also, δn ≤ t0 with probability tending to 1. Therefore 4Cδn |F1 (ŝn , τ ) − F1 (g(Λη∗ ), τ )| ≤ . π1 Further, we have sup F1 (ŝn , τ ) − sup F1 (g(Λη∗ ), τ ) ≤ sup |F1 (ŝn , τ ) − F1 (g(Λη∗ ), τ )| ≤ τ

4Cδn . π1

Finally, by the well-specification assumption, and optimality of the likelihood ratio, we finish the proof. 44

Proof of Theorem 3. In the proof of Theorem 1, we have shown that AUROC is invariant under a strictly increasing transformation, that is AUC(h ◦ s) = AUC(s),

(S17)

where h is strictly increasing. For any two pairs of weights w = (w0 , w1 ) and w′ = (w0′ , w1′ ), by assumption, we have sθw (x) = gθw (Λη∗ (x)), sθw′ (x) = gθw′ (Λη∗ (x)) with gθw and gθw′ being strictly increasing functions. Also, because gθw is increasing, it is invertible and gθ−1 is also w −1 strictly increasing. Then the transformation h := gθw′ ◦ gθw is strictly increasing. Then sθw′ (x) = gθw′ (Λη∗ (x)) = (gθw′ ◦ gθ−1 )(gθw (Λη∗ (x))) = h(sθw (x)). w Thus by equation (S17), we have AUC(θw′ ) = AUC(θw ),

(S18)

which means AUROC is invariant to weights in the population weighted objective. For ease of notation, let ∆θ := sθ (X1 ) − sθ (X0 ). By Lipschitz score assumption, |∆θ − ∆θ′ | = |sθ (X1 ) − sθ (X0 ) − (sθ′ (X1 ) − sθ′ (X0 ))| ≤ |sθ (X1 ) − sθ′ (X1 )| + |sθ (X0 ) − sθ′ (X0 )| ≤ 2L∥θ − θ′ ∥. Then by similar steps as in equations (S1) and (S2), combined with assumption, |AUC(θ) − AUC(θ′ )| ≤ P (|∆θ | ≤ |∆θ − ∆θ′ |) ≤ P (|∆θ | ≤ 2L∥θ − θ′ ∥) ≤ 2CL∥θ − θ′ ∥, whenever 2L∥θ − θ′ ∥ ≤ t0 . Here we replace C by max{C, t−1 0 } if necessary, then the bound holds for all 2L ∥θ − θ′ ∥ > 0. Therefore, consider the raw data estimator, condition on the training data, we have ∗ ∗ AUC(θ̂raw ) − AUC(θraw ) ≤ 2CL θ̂raw − θraw ,

For parameter estimation, we have the following lemmas, Lemma S1 (Empirical Estimation Error). Under the assumptions of the theorem, for any δ > 0, and for sufficiently large sample sizes n0 , n1 , there exists a constant c > 0 such that each of the following two statements holds separately with probability at least 1 − δ that s s 2 d log(6d/δ) B c B 2 d log(8d/δ) c ∗ ∗ , θaug − θ̂aug ≤ . θ̂raw − θraw ≤ λ n0 + n 1 λ n0 + n1 + ñ When the two bounds hold simultaneously, we have, with probability at least 1 − δ, that s s 2 c B d log(14d/δ) c B 2 d log(14d/δ) ∗ ∗ θ̂raw − θraw ≤ , θaug − θ̂aug ≤ . λ n0 + n1 λ n0 + n1 + ñ 45

Therefore, by Lemma S1, it holds that, with probability at least 1 − δ, s CLc B 2 d log(6d/δ) ∗ . AUC(θ̂raw ) − AUC(θraw ) ≤ λ n0 + n 1

(S19)

Also, by the strictly increasing transformation invariance, we finish proving the statement for the raw data estimator. Similarly for the synthetic augmented estimator, ∗ ∗ AUC(θ̂aug ) − AUC(θaug ) ≤ 2CL θ̂aug − θaug . n0 In addition, define ρ := n0 +n , and define the risk 1 +ñ

Rρ (θ) =

n0 n1 + ñ EP0 ℓ(θ; x, 0) + EP ℓ(θ; x, 1), n0 + n1 + ñ n0 + n1 + ñ 1

and let θρ∗ denote its minimizer. We then have the following lemma relating the synthetic augmented parameter and the corresponding rebalanced parameter. Lemma S2 (Synthetic Error). Under the assumptions of the theorem, the synthetic parameter error satisfies Lg ñ ∗ θρ∗ − θaug ≤p ϵsyn . 2µLρ n0 + n1 + ñ Thus, by Lemma S2 and the parameter estimation for AUROC, we have ∗ ∗ AUC(θ̂aug ) − AUC(θρ∗ ) ≤ AUC(θ̂aug ) − AUC(θaug ) + AUC(θaug ) − AUC(θρ∗ ) ∗ ∗ ≤ 2CL θ̂aug − θaug + 2CL θaug − θρ∗ s s 2 CLc B 2 d log(8d/δ) ñ + CLg L ϵsyn , ≤ λ n0 + n1 + ñ µLρ n0 + n1 + ñ

(S20)

with probability at least 1 − δ. Finally by the invariance to strictly increasing function, we finish the proof. Proof of Theorem 4. By previous analysis, AUPRC is invariant under strictly increasing transformations of the score, and it is invariant to weights. Equation (S6) gives that   s Z 1   π0 ′ |AUPRC(s) − AUPRC(s )| ≤ min 1, 2 ∆(r)dr .   π1 0 By Lipschitz score, we have {Sign(∆θ ) ̸= Sign(∆θ′ )} ⇒ {|∆θ | ≤ |∆θ − ∆θ′ |} ⇒ {|∆θ | ≤ 2L∥θ − θ′ ∥} . 46

Then by assumption and similar step with equations (S10) and (S11), it holds that Z 1 ] s (r) − FPR ] s′ (r)|dr ≤ 2CL∥θ − θ′ ∥, |FPR 0 ′ where we replace C by max{C, t−1 0 } if necessary, then the bound holds for all 2L ∥θ − θ ∥ > 0. Thus, r π0 2CL∥θ − θ′ ∥. |AUPRC(sθ ) − AUPRC(sθ′ )| ≤ 2 π1

We have thus connected the AUPRC difference to the parameter error. Then, similar to the analysis for AUROC, it holds that for the raw data estimator, r π0 ∗ ∗ ∥. |AUPRC(θ̂raw ) − AUPRC(θraw )| ≤ 2 2CL∥θ̂raw − θraw π1 and for the synthetic augmented estimator |AUPRC(θ̂aug ) − AUPRC(θρ∗ )| ∗ ∗ ≤ |AUPRC(θ̂aug ) − AUPRC(θaug )| + |AUPRC(θaug ) − AUPRC(θρ∗ )| r r π0 π0 ∗ ∗ − θ ∗ ∥. 2CL∥θ̂aug − θaug ∥ + 2 2CL∥θaug ≤2 ρ π1 π1

Finally, combining lemmas S1 and S2, along with the AUPRC invariance to increasing function, we have the results for both raw and augmented data estimators. Proof of Theorem 5. By the proof of Theorem 2, we have the invariance to strictly increasing function of the best threshold balanced accuracy sup BA(h ◦ s, u) = sup BA(s, τ ). u

We proceed with the proof of Theorem 2 starting from equation (S14). Combining the Lipschitz score assumption, we have {1{sθ (X1 ) ≥ τ } ̸= 1{sθ′ (X1 ) ≥ τ }} ⊆ {|sθ (X1 ) − τ | ≤ |sθ (X1 ) − sθ′ (X1 )|} ⊆ {|sθ (X1 ) − τ | ≤ L∥θ − θ′ ∥} . That is |P(sθ (X1 ) ≥ τ ) − P(sθ′ (X1 ) ≥ τ )| ≤ P (|sθ (X1 ) − τ | ≤ L∥θ − θ′ ∥) ≤ CL∥θ − θ′ ∥. ′ Here we replace C by max{C, t−1 0 } if necessary, then the bound holds for all L ∥θ − θ ∥ > 0. The same argument for the negative class gives

|P(sθ (X0 ) < τ ) − P(sθ′ (X0 ) < τ )| ≤ CL∥θ − θ′ ∥. 47

Plugging back into equation (S13), we have |BA(sθ , τ ) − BA(sθ′ , τ )| ≤ CL∥θ − θ′ ∥. Further, taking supremum gives sup BA(sθ , τ ) − sup BA(sθ′ , τ ) ≤ sup |BA(sθ , τ ) − BA(sθ′ , τ )| ≤ CL∥θ − θ′ ∥. τ

Thus we have transformed the difference of balanced accuracy into the parameter distance. The parameter distance for θ̂aug and θ̂raw has been well studied in Lemmas S1 and S2. Therefore, conditioning on the training data, combining the above and by similar procedure with the analysis of AUROC and AUPRC, we have the results for both raw and augmented estimators. Proof of Theorem 6. Proceeding with equation (S16) in the proof of Theorem 2, along with the Lipschitz score condition, it holds that |R − R′ | = |P1 (sθ ≥ τ ) − P1 (sθ′ ≥ τ )| ≤ CL∥θ − θ′ ∥, |Q − Q′ | = |P0 (sθ ≥ τ ) − P0 (sθ′ ≥ τ )| ≤ CL∥θ − θ′ ∥. As before, we enlarge C when necessary so the bounds always hold. That is we have |F1 (sθ , τ ) − F1 (sθ′ , τ )| ≤

4CL ∥θ − θ′ ∥. π1

Further, taking supremum, sup F1 (sθ , τ ) − sup F1 (sθ′ , τ ) ≤ sup |F1 (sθ , τ ) − F1 (sθ′ , τ )| ≤ τ

4CL ∥θ − θ′ ∥. π1

Thus we have transformed the difference of F1 score into the parameter distance. The parameter distance for θ̂aug and θ̂raw has been well studied in Lemmas S1 and S2. Combining the above with invariance under strictly increasing transformations, we have the results for both raw and augmented estimators. Proof of Theorem 7. We first construct a Euclidean packing. For constant α ∈ (0, 1) in Assumption 4, define rα := 1+α , then α < rα < 1. Consider the Euclidean ball 2 rα B2d−1 = {x ∈ Rd−1 : ∥x∥2 ≤ rα }. By Corollary 4.2.11 in Vershynin (2018), the covering number of the Euclidean unit ball satisfies d−1 1 d−1 N (B2 , ϵ) ≥ . ϵ By scaling, N (rα B2d−1 , α) = N

rα d−1 d−1 α B2 , ≥ . rα α 48

Since rαα = 1+α > 1, this covering number is exponential in d. Then let 2α {x1 , . . . , xM } ⊂ rα B2d−1 be a maximal α-separated set. Since every maximal α-separated set is an α-net, its cardinality is at least the α-covering number. Hence r d−1 1 + α d−1 α d−1 M ≥ N (rα B2 , α) ≥ = . α 2α Next, embed rα B2d−1 into the upper hemisphere of Sd−1 by q 2 Φ(x) = x, 1 − ∥x∥2 . This map is well-defined because rα < 1. Define ui := Φ(xi ), i = 1, . . . , M . Then ui ∈ Sd−1 . For any i ̸= j, q 2 q 2 2 2 2 ∥ui − uj ∥2 = ∥xi − xj ∥2 + 1 − ∥xi ∥2 − 1 − ∥xj ∥2 ≥ ∥xi − xj ∥22 . Since the xi ’s are α-separated, ∥xi − xj ∥2 ≥ α. Therefore, ∥ui − uj ∥2 ≥ α,

i ̸= j.

Moreover, since α ∈ (0, 1) is fixed, for d ≥ 2, log M ≥ (d − 1) log where one may take c1 = 21 log

1+α 2α

≥ c1 d.

. Now define the local parameter points

ηi := η0 + hui ,

i = 1, . . . , M.

If h ≤ r0 , then, ηi ∈ B2 (η0 , r0 ) ⊆ Θ. Furthermore, ∥ηi − ηj ∥2 = h∥ui − uj ∥2 ≥ αh, for i ̸= j. Therefore, {η1 , . . . , ηM } is a Euclidean packing of the local parameter space with separation αh, and its cardinality satisfies log M ≥ c1 d. Next, we give a pairwise AUC excess representation. For fixed parameter η, write Qη = P0,η ⊗ P0,η . We first rewrite the AUC excess in a pairwise form. For any measurable score s, ZZ 1 AUCη (s) = H(s(x) − s(z)) dP1,η (x) dP0,η (z), where H(t) := 1{t > 0} + 1{t = 0}. 2 Since dP1,η (x) = Lη (x)dP0,η (x), and since Qη = P0,η ⊗ P0,η , we may write ZZ AUCη (s) = Lη (x)H(s(x) − s(z)) dQη (x, z). 49

Using the symmetry of Qη in (x, z), the same quantity also equals ZZ Lη (z)H(s(z) − s(x)) dQη (x, z). Averaging the two displays gives the symmetrized representation ZZ 1 [Lη (x)H(s(x) − s(z)) + Lη (z)H(s(z) − s(x))] dQη (x, z). AUCη (s) = 2 For a score s, define the pairwise oracle-disagreement loss   0, whenever Lη (x) = Lη (z),     0, if s ranks x, z in the same strict order as Lη , Lη,s (x, z) :=  1/2, if s(x) = s(z),     1, if s ranks x, z in the opposite strict order from Lη . For the pairwise likelihood-ratio contrast ∆η (x, z) = Lη (x) − Lη (z), we claim that ZZ 1 AUCη (Λη ) − AUCη (s) = AUCη (Lη ) − AUCη (s) = |∆η (x, z)|Lη,s (x, z) dQη (x, z). 2 To verify this identity, fix a pair (x, z) and write a := Lη (x) and b := Lη (z). The symmetrized pairwise contribution of s is Cs (x, z) :=

1 [aH(s(x) − s(z)) + bH(s(z) − s(x))] , 2

while the corresponding oracle contribution is CL (x, z) :=

1 [aH(a − b) + bH(b − a)] . 2

If a > b, then the oracle ranks x above z, and CL (x, z) = a2 . In this case, if s(x) > s(z), then Cs (x, z) = a/2, so the excess is zero. If s(x) = s(z), then 1 a b a+b Cs (x, z) = + = , 2 2 2 4 and hence

a a+b a−b 1 1 − = = |a − b| · . 2 4 4 2 2 If s(x) < s(z), then Cs (x, z) = b/2, and hence CL (x, z) − Cs (x, z) =

CL (x, z) − Cs (x, z) =

a b a−b 1 − = = |a − b| · 1. 2 2 2 2 50

Thus, when a > b, 1 CL (x, z) − Cs (x, z) = |∆η (x, z)|Lη,s (x, z). 2 The case a < b is symmetric. If a = b, then |∆η (x, z)| = 0, and the pair contributes no excess regardless of how s ranks x and z. Therefore, for every pair (x, z), 1 CL (x, z) − Cs (x, z) = |∆η (x, z)|Lη,s (x, z). 2 Integrating this pointwise identity with respect to Qη yields ZZ 1 AUCη (Λη ) − AUCη (s) = AUCη (Lη ) − AUCη (s) = |∆η (x, z)|Lη,s (x, z) dQη (x, z). 2 This is the desired pairwise representation of the AUC excess risk. Then the AUC excess R 1 has the exact representation Eη (s) = 2 |∆η (x, z)|Lη,s (x, z) dQη (x, z). Using Qη ≥ cQ Q0 , we get Z cQ |∆η (x, z)|Lη,s (x, z) dQ0 (x, z). Eη (s) ≥ 2 Then we transfer the Euclidean packing into AUC-space separation. Fix i ̸= j. Let ηi = η0 + hui , and ηj = η0 + huj . By previous construction, ∥ui − uj ∥2 ≥ α. Define Rij,h := Rh (ui , uj ) = (x, z) : ∆ηi (x, z)∆ηj (x, z) < 0 . That is, on Rij,h , the two oracle likelihood-ratio rankings are opposite. For any score s, one score cannot agree with both opposite rankings. Therefore, Lηi ,s (x, z) + Lηj ,s (x, z) ≥ 1

on Rij,h .

Using the AUC excess representation, cQ Eηi (s) + Eηj (s) ≥ 2

|∆ηi |Lηi ,s + |∆ηj |Lηj ,s dQ0 .

Rij,h

For nonnegative a, b, ℓ1 , ℓ2 , aℓ1 + bℓ2 ≥ min{a, b}(ℓ1 + ℓ2 ). Therefore, on Rij,h , |∆ηi |Lηi ,s + |∆ηj |Lηj ,s ≥ min{|∆ηi |, |∆ηj |}. Hence

cQ Eηi (s) + Eηj (s) ≥ 2

By assumption,

R Rij,h

Z min{|∆ηi |, |∆ηj |} dQ0 . Rij,h

min{|∆ηi |, |∆ηj |} dQ0 ≥ crk h. Therefore,

Eηi (s) + Eηj (s) ≥

cQ crk h 2

⇒

max{Eηi (s), Eηj (s)} ≥

cQ crk h. 4

c c

Define ϵh := Q8 rk h. Then for all i ̸= j, inf max{Eηi (s), Eηj (s)} ≥ 2ϵh . s

So the AUC-space packing has been derived from the Euclidean packing. Next, we prove the KL divergence control. Let parameters η, η ′ ∈ B2 (η0 , r0 ). Fix y ∈ {0, 1}. Set δ := η − η ′ , ηt := η ′ + tδ. Thus η0 = η ′ and η1 = η. For fixed x, define the one-dimensional function gx (t) := py,ηt (x). By differentiability of py,η (x) with respect to η, the chain rule gives gx′ (t) = ∇η py,ηt (x)⊤

dηt = ∇η py,ηt (x)⊤ δ. dt

Therefore, by the fundamental theorem of calculus, Z 1 py,η (x) − py,η′ (x) = gx (1) − gx (0) =

gx′ (t) dt.

Substituting the expression for gx′ (t), we obtain Z 1 δ ⊤ ∇η py,ηt (x) dt. py,η (x) − py,η′ (x) = 0

Since ∇η py,ηt (x) = py,ηt (x)Sy (x; ηt ), we have Z 1 py,η (x) − py,η′ (x) = δ ⊤ Sy (x; ηt )py,ηt (x) dt. 0

By Cauchy–Schwarz, 2

(py,η (x) − py,η′ (x))

≤ ∥δ∥22

Z 1

∥Sy (x; ηt )∥22 py,ηt (x)2 dt.

Recall the definition of χ2 divergence, χ2 (Py,η , Py,η′ ) = 2

χ (Py,η , Py,η′ ) ≤ ∥δ∥22

Z 1Z

R (py,η −py,η′ )2

∥Sy (x; ηt )∥22

0 p

py,η′

dν. Therefore

py,ηt (x)2 dν(x) dt. py,η′ (x)

(x)

By local likelihood-ratio comparability that py,ηt′ (x) ≤ Blr , we have y,η Thus Z 1

χ (Py,η , Py,η′ ) ≤ Blr ∥δ∥22

Ey,ηt ∥Sy (X; ηt )∥22 dt.

By assumption, χ2 (Py,η , Py,η′ ) ≤ Blr Iy ∥η − η ′ ∥22 . 52

py,ηt (x)2 py,η′ (x)

≤ Blr py,ηt (x).

Since DKL (P ∥Q) ≤ χ2 (P, Q), we get DKL (Py,η ∥Py,η′ ) ≤ Blr Iy ∥η − η ′ ∥22 . (n)

⊗n1 ⊗n0 . Therefore, ⊗ P1,η Further, for the class-stratified sample, Pη = P0,η (n) (n) DKL Pη Pη′ = n0 DKL (P0,η ∥P0,η′ ) + n1 DKL (P1,η ∥P1,η′ )

≤ Blr (n0 I0 + n1 I1 )∥η − η ′ ∥22 ≤ Blr Imax n∥η − η ′ ∥22 . For packing points, ∥ηi − ηj ∥2 = h∥ui − uj ∥2 ≤ 2h. Therefore, (n) ≤ 4Blr Imax nh2 . DKL P(n) P ηi ηj

(S21)

q Let hn := a nd , where a > 0 is sufficiently small. Since log M ≥ c1 d, choose a such that 4Blr Imax nh2n = 4Blr Imax a2 d ≤ β log M 1 for some fixed β ∈ (0, 1). It is enough to take a2 ≤ 4Bβc . For sufficiently large n, we also lr Imax have hn ≤ r0 , and hn ≤ h0 . Thus all assumptions apply. Therefore, the AUC packing radius we choose is r cQ crk d ϵn = ϵhn = hn = c . 8 n To apply Fano’s inequality, let V ∼ Unif{1, . . . , M }. Conditional on V = i, draw the (n) training data from Pηi . Let ŝ be any score estimator. Define the decoder

V̂ ∈ arg min Eηi (ŝ). 1≤i≤M

Suppose the true index is i, and consider the event {Eηi (ŝ) < ϵn }. For every j ̸= i, the AUC-space separation gives max{Eηi (ŝ), Eηj (ŝ)} ≥ 2ϵn . Therefore, Eηj (ŝ) ≥ 2ϵn for every j ̸= i, so the decoder must select i. Hence {V̂ ̸= i} ⊆ {Eηi (ŝ) ≥ ϵn }. Averaging over i, M X

1 X Pη (Eηi (ŝ) ≥ ϵn ) . P(V̂ ̸= V ) = P(V = i)P(V̂ ̸= V | V = i) ≤ M i=1 i i=1 Therefore, M

sup Pη (Eη (ŝ) ≥ ϵn ) ≥ η∈Θ

1 X Pη (Eηi (ŝ) ≥ ϵn ) ≥ P(V̂ ̸= V ). M i=1 i

By Fano’s inequality (e.g. equation (15.31) in Wainwright (2019)), inf P(V̂ ̸= V ) ≥ 1 − V̂

I(V ; Dn ) + log 2 . log M

(n)

For bounding the mutual information, let Pi := Pηi , for i = 1, . . . , M . Conditional on V = i, the training samplePDn has distribution Pi . Hence the marginal distribution of M Dn is the mixture P := M1 j=1 Pj . By the definition of mutual information, I(V ; Dn ) = PM 1 the corresponding densities with respect to a i=1 DKL (Pi ∥P ). Let pi and p denote P M 1 common dominating measure. Since p = M M j=1 pj , we have Z Z pi pi DKL (Pi ∥P ) = pi log dν = pi log dν. P p M −1 M p j j=1 By concavity of the logarithm, M

log

1 X pj M j=1

log

pi P M −1

≥

1 X log pj . M j=1

Therefore, M

1 X pi ≤ log . M j=1 pj j=1 pj

Integrating both sides with respect to pi dν, we obtain M

1 X DKL (Pi ∥P ) ≤ DKL (Pi ∥Pj ). M j=1 Averaging this inequality over i = 1, . . . , M gives M M M 1 X 1 X 1 X (n) (n) DKL (Pi ∥P ) ≤ 2 I(V ; Dn ) = DKL (Pi ∥Pj ) = 2 DKL Pηi Pηj . M i=1 M i,j=1 M i,j=1

By the KL control and the choice of hn , I(V ; Dn ) ≤ β log M. Thus inf P(V̂ ̸= V ) ≥ 1 − β − V̂

(S22)

log 2 . log M

We can choose a small β such that β ≤ 1/4 and recall that the dimension d is larger than a constant such that we can choose d ≥ 2 log 2/c1 . Then after absorbing fixed-dimensional constants, log 2 log 2 1−β− ≥1−β− ≥ c0 log M c1 d for some constant c0 > 0. Therefore, inf sup Pη (Eη (ŝ) ≥ ϵn ) ≥ c0 . ŝ η∈Θ

q Since ϵn = c nd , we have inf sup Pη ŝ η∈Θ

r ! d ≥ c0 . Eη (ŝ) ≥ c n

Finally we convert probability to expectation. For any nonnegative random variable Z, by Markov’s inequality, EZ ≥ tP(Z ≥ t). Apply this with Z = Eη (ŝ), and t = ϵn , we have r d inf sup Eη Eη (ŝ) ≥ c0 ϵn ≥ c . ŝ η∈Θ n Finally, we finish the proof by noting the definition of Eη (ŝ) and the optimality of the likelihood-ratio score. Proof of Theorem 8. Define the best-threshold balanced-accuracy excess risk EηBA (s) := sup BAη (Λη , τ ) − sup BAη (s, τ ). τ

By the population optimality of the likelihood-ratio threshold rule for balanced accuracy (equation (S31)), proved in Lemma 1, supτ BAη (Λη , τ ) = BAη (Bη ), where Bη = {x : Lη (x) ≥ 1}. Also, by optimality of the likelihood ratio, EηBA (s) ≥ 0,

and sup BAη (s, τ ) − sup BAη (Λη , τ ) = EηBA (s). τ

We first derive the balanced-accuracy excess representation. For any measurable set S ⊆ X , write BAη (S) = 21 P1,η (S) + 12 P0,η (S c ). Since dP1,η = Lη dP0,η , we have Z 1 1 (Lη (x) − 1) dP0,η (x), BAη (S) = + 2 2 S with the maximizer being Bη = {x : Lη (x) ≥ 1}. Hence, for any measurable set S, Z 1 BAη (Bη ) − BAη (S) = |Lη (x) − 1| dP0,η (x). 2 Bη △S Therefore, for a score s, writing Sτ (s) := {x : s(x) ≥ τ }, we have Z 1 BA |Lη (x) − 1| dP0,η (x). Eη (s) = inf τ 2 B △S (s) η τ Next, according to the proof of Theorem 7, we can construct a Euclidean packing. Namely, for α ∈ (0, 1) in assumption, there exist points u1 , . . . , uM ∈ Sd−1 such that ∥ui − uj ∥2 ≥ α, for i ̸= j, and log M ≥ c1 d for some constant c1 > 0. For a radius h > 0, define

ηi := η0 + hui , i = 1, . . . , M . For h ≤ r0 , all ηi ∈ Θ. We now prove that this parameter packing induces separation in best-threshold balanced accuracy. Fix i ̸= j. Write Bi := Bηi ,

Bj := Bηj ,

Li := Lηi ,

Lj := Lηj .

+ − Define the directed disagreement regions Dij := Bi ∩ Bjc , Dij := Bic ∩ Bj . By assumption, Z Z min{|Li − 1|, |Lj − 1|} dP0,η0 ≥ cBA h, min{|Li − 1|, |Lj − 1|} dP0,η0 ≥ cBA h. − Dij

+ Dij

Let s be any measurable score. Because best-threshold balanced accuracy allows parameterspecific thresholds, take arbitrary thresholds τi , τj and define Si := Sτi (s) = {x : s(x) ≥ τi },

Sj := Sτj (s) = {x : s(x) ≥ τj }.

Since these are upper level sets of the same score s, they are nested. Thus either Si ⊆ Sj or + Sj ⊆ Si . First suppose Si ⊆ Sj . On the region Dij = Bi ∩ Bjc , the oracle decision under ηi is positive, while the oracle decision under ηj is negative. Because Si ⊆ Sj , the two threshold + sets Si , Sj cannot match these opposite decisions simultaneously. Indeed, for every x ∈ Dij , 1{x ∈ Bi △Si } + 1{x ∈ Bj △Sj } ≥ 1. For the integral, we have Z Z 1 1 |Li − 1| dP0,ηi + |Lj − 1| dP0,ηj 2 Bi △Si 2 Bj △Sj Z Z 1 1 = |Li − 1|1{x ∈ Bi △Si } dP0,ηi + |Lj − 1|1{x ∈ Bj △Sj } dP0,ηj . 2 2 + The two integrands are nonnegative. Hence restricting both integrals to the smaller set Dij can only decrease their values, and therefore Z Z 1 1 |Li − 1| dP0,ηi + |Lj − 1| dP0,ηj 2 Bi △Si 2 Bj △Sj Z Z 1 1 ≥ |Li − 1|1{x ∈ Bi △Si } dP0,ηi + |Lj − 1|1{x ∈ Bj △Sj } dP0,ηj . 2 Dij+ 2 Dij+

We now use the local likelihood-ratio comparability condition. Since ηi and ηj lie in the local dP0,η dP0,ηi (x) ≥ Blr−1 , dP0,ηj (x) ≥ Blr−1 , or equivalently, neighborhood of η0 , assumption implies dP0,η 0

dP0,ηi ≥ Blr−1 dP0,η0 , dP0,ηj ≥ Blr−1 dP0,η0 . Therefore, Z Z 1 1 |Li − 1|1{x ∈ Bi △Si } dP0,ηi ≥ |Li − 1|1{x ∈ Bi △Si } dP0,η0 , 2 Dij+ 2Blr Dij+ and similarly Z Z 1 1 |Lj − 1|1{x ∈ Bj △Sj } dP0,ηj ≥ |Lj − 1|1{x ∈ Bj △Sj } dP0,η0 . 2 Dij+ 2Blr Dij+ 56

Combining the two bounds yields Z Z 1 1 |Li − 1| dP0,ηi + |Lj − 1| dP0,ηj 2 Bi △Si 2 Bj △Sj Z 1 ≥ [|Li − 1|1{x ∈ Bi △Si } + |Lj − 1|1{x ∈ Bj △Sj }] dP0,η0 . 2Blr Dij+ + , by assumption, Since at least one of the two disagreement indicators is equal to one on Dij Z Z 1 1 |Li − 1| dP0,ηi + |Lj − 1| dP0,ηj 2 Bi △Si 2 Bj △Sj Z 1 cBA ≥ min{|Li − 1|, |Lj − 1|} dP0,η0 ≥ h. 2Blr Dij+ 2Blr − The other case is symmetric. If Sj ⊆ Si , then on Dij = Bic ∩ Bj , the oracle decision under ηi is negative, while the oracle decision under ηj is positive. Again, the nested sets Si , Sj cannot match both oracle decisions simultaneously, so the same argument gives Z Z 1 cBA 1 |Li − 1| dP0,ηi + |Lj − 1| dP0,ηj ≥ h. 2 Bi △Si 2 Bj △Sj 2Blr

Because τi , τj were arbitrary, taking the infimum over thresholds gives n o cBA cBA BA BA BA EηBA (s) + E (s) ≥ h ⇒ max E (s), E (s) ≥ h. ηj ηi ηj i 2Blr 4Blr cBA h. Then for every i ̸= j, Define ϵh := 8B lr n o BA BA inf max Eηi (s), Eηj (s) ≥ 2ϵh . s

Now we use the same KL and Fano argument as in the proof of Theorem 7. By the KL-control part of Theorem 7 in equation (S21), for every i, j, (n) DKL Pη(n) P ≤ 4Blr Imax nh2 . ηj i q Choose hn := a nd , where a > 0 is sufficiently small so that 4Blr Imax nh2n ≤ β log M 1 for some fixed β ∈ (0, 1). Since log M ≥ c1 d, it is enough to choose a2 ≤ 4Bβc . For all lr Imax sufficiently large n, we also have h ≤ r , h ≤ h . Thus all local assumptions apply. Set n 0 n 0 q

cBA ϵn := ϵhn = 8B hn = c lr

d . n

Let V ∼ Unif{1, . . . , M }. Conditional on V = i, draw the

(n) training data from Pηi . Given any score estimator ŝ, define the decoder

V̂ ∈ arg min EηBA (ŝ). i 1≤i≤M

Suppose V = i and consider when EηBA (ŝ) < ϵn . For every j ̸= i, the balanced-accuracy n oi separation gives max EηBA (ŝ), EηBA (ŝ) ≥ 2ϵn . Therefore, i j (ŝ) ≥ 2ϵn > EηBA (ŝ), EηBA j i so the decoder must select i. Hence {V̂ ̸= V } ⊆ EηBA (ŝ) ≥ ϵn . Averaging over V , V sup Pη EηBA (ŝ) ≥ ϵn ≥ P(V̂ ̸= V ). η∈Θ

By the mutual-information bound in equation (S22), I(V ; Dn ) ≤ β log M . Therefore, by Fano’s inequality (e.g. equation (15.31) in Wainwright (2019)), inf P (V̂ ̸= V ) ≥ 1 − V̂

log 2 I(V ; Dn ) + log 2 ≥1−β− . log M log M

Since log M ≥ c1 d, for sufficiently large d and sufficiently small fixed β, there exists a constant log 2 ≥ c0 . Thus c0 > 0 such that 1 − β − log M inf sup Pη EηBA (ŝ) ≥ ϵn ≥ c0 . ŝ η∈Θ

Finally, converting this probability lower bound into an expectation lower bound, for any nonnegative random variable Z, by Markov inequality, EZ ≥ tP(Z ≥ t). Applying this with Z = EηBA (ŝ) and t = ϵn , we obtain r inf sup Eη EηBA (ŝ) ≥ c0 ϵn ≥ c ŝ η∈Θ

d . n

Combining with the definition of EηBA (ŝ) and the optimality of the likelihood ratio score, we finish the proof. Proof of Theorem 9. We prove the results for AUROC and AUPRC separately. Proof for AUROC: We first show that high AUROC requires majority score variation. For any score s ∈ S, define V0 (s) = EP0 {s(X) − u0 }2 . We first prove that AUC(s) ≤

p p 1 + Bs (1 + BL ) V0 (s), 2

If s is constant, then all points are tied and thus AUC(s0 ) = 21 . Thus the inequality holds. Now consider any non-constant score s. Let F0,s and F1,s denote the distributions of s(X) under X ∼ P0 and X ∼ P1 , respectively. Let U0 = s(X0 ) ∼ F0,s ,

U1 = s(X1 ) ∼ F1,s . 58

If F0,s is continuous, then ties occur with probability zero. Hence AUC(s) = P{U1 > U0 }. Conditioning on U1 , we obtain P{U1 > U0 | U1 } = P{U0 < U1 | U1 } = F0,s (U1 ), where the last equality uses the continuity of F0,s . Therefore, AUC(s) = E{F0,s (U1 )}. Similarly, since U0 has CDF F0,s , the probability integral transform implies that F0,s (U0 ) ∼ Unif(0, 1). Consequently, E{F0,s (U0 )} = 21 . Therefore, since F0,s is Bs -Lipschitz, the Kantorovich-Rubinstein inequality gives AUC(s) −

1 = EF1,s F0,s (U ) − EF0,s F0,s (U ) ≤ Bs W1 (F1,s , F0,s ) 2 ≤ Bs (W1 (F1,s , δu0 ) + W1 (F0,s , δu0 )),

where δu0 is the point mass at u0 . Recall the definition of Wasserstein distance, for probability R measures µ and ν on R, W1 (µ, ν) = inf γ∈Π(µ,ν) |u − v| dγ(u, v), where Π(µ, ν) denotes the set of couplings of µ and ν. If ν = δu0 is the point mass at u0 , then any coupling between µ and δu0 must have second coordinate equal to u0 almost surely. Hence Z W1 (µ, δu0 ) = |u − u0 | dµ(u). Applying this identity with µ = F1,s , the distribution of s(X) under P1 , gives Z W1 (F1,s , δu0 ) = |u − u0 | dF1,s (u) = EP1 |s(X) − u0 |, W1 (F0,s , δu0 ) = EP0 |s(X) − u0 |. Therefore, by the triangle inequality for W1 , W1 (F1,s , F0,s ) ≤ W1 (F1,s , δu0 ) + W1 (F0,s , δu0 ) ≤ EP1 |s(X) − u0 | + EP0 |s(X) − u0 |. By Cauchy-Schwarz, EP0 |s(X) − u0 | ≤

p V0 (s).

Since dP1 = L dP0 and L ≤ BL , EP1 {s(X) − u0 }2 = EP0 L(X){s(X) − u0 }2 ≤ BL V0 (s). Therefore, EP1 |s(X) − u0 | ≤

p BL V0 (s).

Combining the previous bounds, W1 (F1,s , F0,s ) ≤ (1 + 59

p BL ) V0 (s).

(S23)

Thus

p p 1 + Bs (1 + BL ) V0 (s). 2 Consequently, for any specified AUROC level A, if AUC(s) ≥ A, then A − 12 ≤ Bs (1 + p √ BL ) V0 (s). Hence 2 A − 12 √ V0 (s) ≥ =: κA . Bs (1 + BL ) AUC(s) ≤

Next, we show that high AUROC requires a majority risk cost. By assumption, ℓ(s(x), 0) − ℓ(u0 , 0) ≥ m0 {s(x) − u0 }2 . Taking expectation under P0 , R0 (s) − R0 (s0 ) ≥ m0 V0 (s).

(S24)

Since s0 (x) ≡ u0 minimizes the pointwise majority-class loss, it also minimizes R0 over S. 1 Then, for any AUROC level A ∈ 2 , AUC(Λη∗ ) , by previous analysis, if AUC(s) ≥ A, it holds that V0 (s) ≥ κA . Thus AUC(s) ≥ A

=⇒

R0 (s) − R0 (s0 ) ≥ m0 κA .

So any score with AUROC at least A must pay a majority-class risk cost of at least m0 κA . Next, we show that the raw imbalanced population minimizer cannot pay this majority risk cost. Since s∗raw minimizes Rαraw , that is Rαraw (s∗raw ) ≤ Rαraw (s0 ). Expanding and rearranging, (1 − αraw ){R0 (s∗raw ) − R0 (s0 )} ≤ αraw {R1 (s0 ) − R1 (s∗raw )}. By the definition of D1 , R1 (s0 ) − R1 (s∗raw ) ≤ D1 . Therefore, R0 (s∗raw ) − R0 (s0 ) ≤

αraw D1 . 1 − αraw

(S25)

αraw By the severe-imbalance assumption, 1−α D1 < m0 κA , we have R0 (s∗raw ) − R∗0 < m0 κA . raw If, contrary to the desired conclusion, AUC(s∗raw ) ≥ A, then previous analysis would imply R0 (s∗raw ) − R∗0 ≥ m0 κA , which contradicts the previous strict inequality. Therefore,

AUC(s∗raw ) < A. Let M ∗ = (1 − α∗ )P0 + α∗ P1 denote the augmented feature distribution. Under the augmented population, the conditional probability of class 1 given X = x is ηα∗ (x) =

α∗ p1 (x) = gα∗ (Λη∗ (x)), (1 − α∗ )p0 (x) + α∗ p1 (x)

where gα∗ (·) is a strictly increasing function. For a fixed conditional class probability η, write Cη (u) = ηℓ(u, 1) + (1 − η)ℓ(u, 0). 60

By strict propriety and quadratic calibration, for all u, η ∈ [0, 1], Cη (u)−Cη (η) ≥ mℓ (u−η)2 . Applying this inequality pointwise with η = ηα∗ (x) and u = s(x), we obtain Cηα∗ (x) (s(x)) − Cηα∗ (x) (ηα∗ (x)) ≥ mℓ {s(x) − ηα∗ (x)}2 . Taking expectation with respect to X ∼ M ∗ gives EM ∗ Cηα∗ (X) (s(X)) − Cηα∗ (X) (ηα∗ (X)) ≥ mℓ EM ∗ {s(X) − ηα∗ (X)}2 . By direct calculation, we can write in expectation that Rα∗ (s) = EM ∗ Cηα∗ (X) (s(X)), and Rα∗ (ηα∗ ) = EM ∗ Cηα∗ (X) (ηα∗ (X)). We then conclude that Rα∗ (s) − Rα∗ (ηα∗ ) ≥ mℓ EM ∗ {s(X) − ηα∗ (X)}2 . Since sα∗ minimizes Rα∗ over S, by assumption Rα∗ (sα∗ ) − Rα∗ (ηα∗ ) ≤ ϵ∗ . Therefore, EM ∗ {sα∗ (X) − ηα∗ (X)}2 ≤

ϵ∗ . mℓ

(S26)

Define e(x) = sα∗ (x) − ηα∗ (x). Recall the definition of AUROC, 1 AUC(s) = E 1{s(X1 ) > s(X0 )} + 1{s(X1 ) = s(X0 )} . 2 Hence AUC(ηα∗ ) − AUC(sα∗ ) ≤ P (ηα∗ (X1 ) ≥ ηα∗ (X0 ), sα∗ (X1 ) ≤ sα∗ (X0 )) . On the event {ηα∗ (X1 ) ≥ ηα∗ (X0 ), sα∗ (X1 ) ≤ sα∗ (X0 )}, we have ηα∗ (X1 ) + e(X1 ) = sα∗ (X1 ) ≤ sα∗ (X0 ) = ηα∗ (X0 ) + e(X0 ). Therefore, ηα∗ (X1 ) − ηα∗ (X0 ) ≤ e(X0 ) − e(X1 ) ≤ |e(X1 )| + |e(X0 )|. Consequently, for any t > 0, {ηα∗ (X1 ) ≥ ηα∗ (X0 ), sα∗ (X1 ) ≤ sα∗ (X0 )} ⊆ {|ηα∗ (X1 ) − ηα∗ (X0 )| ≤ t} ∪ {|e(X1 )| + |e(X0 )| > t} . Taking probabilities and applying the union bound gives AUC(ηα∗ ) − AUC(sα∗ ) ≤ P (|ηα∗ (X1 ) − ηα∗ (X0 )| ≤ t) + P (|e(X1 )| + |e(X0 )| > t) .

(S27)

Thus P (|ηα∗ (X1 ) − ηα∗ (X0 )| ≤ t) ≤ Ct. By Markov’s inequality, P (|e(X1 )| + |e(X0 )| > t) ≤

E(|e(X1 )| + |e(X0 )|)2 2EP1 e(X)2 + 2EP0 e(X)2 ≤ . t2 t2

Since EM ∗ e(X)2 = (1 − α∗ )EP0 e(X)2 + α∗ EP1 e(X)2 , we get 2 2 ϵ∗ 2 2 2 2 ∗ 2EP1 e(X) + 2EP0 e(X) ≤ max E e(X) ≤ , , M α∗ 1 − α∗ α∗ (1 − α∗ ) mℓ where Cα∗ is constant determined by α∗ . Therefore, AUC(ηα∗ ) − AUC(sα∗ ) ≤ Ct +

2 ϵ∗ . α∗ (1 − α∗ ) mℓ t2

Optimizing over t yields ∗ 1/3 ϵ AUC(ηα∗ ) − AUC(sα∗ ) ≤ C . mℓ

(S28)

Combining that gα∗ is strictly increasing, and combining this with previous analysis at the AUROC level A, we have AUC(s∗raw ) < A,

∗ 1/3 ϵ AUC(sα∗ ) ≥ AUC(Λη∗ ) − C . mℓ

That is, AUC(sα∗ ) − AUC(s∗raw ) ≥ AUC(Λη∗ ) − A − C

∗ 1/3 ϵ . mℓ

We thus have derived the result at the population level. Next, for finite-sample estimators, by essentially the same procedure with equations (S19) and (S20), but with the simultaneous statement in Lemma S1, the following inequalities hold simultaneously with probability at least 1 − δ that s B 2 d log(14d/δ) CLc AUC(sθ̂raw ) − AUC(s∗raw ) ≤ , λ n0 + n 1 and CLc AUC(sθ̂aug ) − AUC(sα∗ ) ≤ λ

s B 2 d log(14d/δ) 2 ñ + CLg L ϵsyn , n0 + n1 + ñ µLρ n0 + n1 + ñ

∗

α The synthetic size is taken as ñ = 1−α ∗ n0 − n1 . If this is not an integer, we can simply add an O(1/n0 ) term, which is small. This gives s s 1 CLc B 2 d log(14d/δ) ∗ ∗ n1 + CLg L α − (1 − α ) ϵsyn , AUC(sθ̂aug ) − AUC(sα∗ ) ≤ λ n0 /(1 − α∗ ) 2µLρ n0

Combining and absorbing constants into c gives the final bound for AUROC. Proof for AUPRC: We first prove that high AUPRC forces nontrivial variation under P0 . For constant scores, we adopt the standard no-ranking convention under which AUPRC(s) = π1 . Since the AUPRC part considers A > π1 , constant scores are naturally excluded from the subsequent high-AUPRC argument. Write G0,s (t) = P0 (s(X) ≥ t),

G1,s (t) = P1 (s(X) ≥ t).

For a recall level r ∈ [0, 1], let tr be a threshold satisfying G1,s (tr ) = r. Since F0,s is Bs Lipschitz, it follows that F1,s is BL Bs -Lipschitz and hence continuous. Therefore the recall parametrization is well defined. Define the false-positive rate at recall r by qs (r) = G0,s (tr ). Then the AUPRC of s can be written as Z 1 π1 r dr. AUPRC(s) = 0 π1 r + π0 qs (r) If F0,s = F1,s , then qs (r) = r, and hence the precision is equal to π1 for every r > 0. Thus π1 is the no-ranking information baseline for AUPRC. For r ∈ [0, 1], Z 1 AUPRC(s) − π1 = {ϕr (qs (r)) − ϕr (r)} dr, 0

Since Lη∗ ≤ BL P0 -a.s., the score distribution under P1 is dominated by the score distribution under P0 such that dF1,s ≤ BL dF0,s . Moreover, since F0,s is Bs -Lipschitz, dF0,s (t) ≤ Bs dt. Therefore dF1,s (t) ≤ BL Bs dt. It then follows that Z 1 Z |qs (r) − r| dr ≤ BL Bs |F1,s (t) − F0,s (t)| dt = BL Bs W1 (F1,s , F0,s ). 0

Here the last equality uses the one-dimensional representation of the Wasserstein-1 distance. Combining equation (S23), Z 1 p p |qs (r) − r| dr ≤ BL Bs (1 + BL ) V0 (s). 0

Plugging this into the AUPRC stability bound yields 1/2 p π0 AUPRC(s) ≤ π1 + 2 BL Bs (1 + BL ) V0 (s)1/4 . π1 Therefore, if AUPRC(s) ≥ A > π1 , then 

4

A − π1   PR V0 (s) ≥  n  =: κA . o 1/2 √ 2 ππ01 BL Bs (1 + BL ) Next, by equation (S24), R0 (s) − R0 (s0 ) ≥ m0 V0 (s), where s0 (x) ≡ u0 . Therefore, AUPRC(s) ≥ A

R0 (s) − R∗0 ≥ m0 κPR A .

=⇒

Now consider the raw population minimizer s∗raw . We have Rαraw (s∗raw ) ≤ Rαraw (s0 ). Equivalently, (1 − αraw )R0 (s∗raw ) + αraw R1 (s∗raw ) ≤ (1 − αraw )R0 (s0 ) + αraw R1 (s0 ). Rearranging and by the definition of D1 , R0 (s∗raw ) − R∗0 ≤

αraw D1 . 1 − αraw

αraw ∗ ∗ D1 < m0 κPR Under the stated severe-imbalance condition, 1−α A . Thus R0 (sraw ) − R0 < raw PR ∗ ∗ ∗ m0 κPR A . If AUPRC(sraw ) ≥ A, then the previous analysis would force R0 (sraw )−R0 ≥ m0 κA , which is a contradiction. Hence

AUPRC(s∗raw ) < A. We next lower bound the AUPRC of the augmented population minimizer. By the AUPRC stability inequality in equation (S6), AUPRC(ηα∗ ) − AUPRC(sα∗ ) ≤ 2

π0 π1

1/2

Z 1 ] η ∗ (r) − FPR ] s ∗ (r) dr FPR α α

By equation (S10), the integrated FPR difference is bounded by the probability of a pairwise ranking disagreement: Z 1 ] η ∗ (r) − FPR ] s ∗ (r) dr ≤ P (sign{ηα∗ (X1 ) − ηα∗ (X0 )} ̸= sign{sα∗ (X1 ) − sα∗ (X0 )}) . FPR α α 0

By a standard set argument, for any t > 0, P (sign{ηα∗ (X1 ) − ηα∗ (X0 )} ̸= sign{sα∗ (X1 ) − sα∗ (X0 )}) ≤ P |ηα∗ (X1 ) − ηα∗ (X0 )| ≤ t + P |e(X1 )| + |e(X0 )| > t . By the same analysis used between equations (S27) and (S28), it then holds that Z 1 0

∗ 1/3 ] η ∗ (r) − FPR ] s ∗ (r) dr ≤ C ϵ . FPR α α mℓ

Consequently, combining the AUPRC invariance for strictly increasing functions, AUPRC(sα∗ ) ≥ AUPRC(Λη∗ ) − C

π0 π1

1/2 ∗ 1/6 ϵ . mℓ

Combining this inequality with AUPRC(s∗raw ) < A, we obtain the population improvement bound 1/2 ∗ 1/6 ϵ π0 ∗ . AUPRC(sα∗ ) − AUPRC(sraw ) ≥ AUPRC(Λη∗ ) − A − C π1 mℓ Finally, it remains to pass from population minimizers to empirical estimators. By the same procedure with equations (1) and (2), but with the simultaneous statement in Lemma S1, the following inequalities hold simultaneously with probability at least 1 − δ: r 1/4 CLc π0 B 2 d log(14d/δ) ∗ AUPRC(sθbraw ) − AUPRC(sraw ) ≤ , λ π1 n0 + n1 and AUPRC(sθbaug ) − AUPRC(sα∗ ) r 1/4 r CLc π0 B 2 d log(14d/δ) π0 ≤ + 2 2CL λ π1 n0 + n1 + ñ π1

L2g 2µLρ

ñ ϵsyn n0 + n1 + ñ

2 !1/4 .

∗

α Taking n e = 1−α ∗ n0 − n1 , and absorbing constants, we finish the proof.

Proof of Theorem 10. We prove the theorem for two metrics separately. Proof for BA: First, we show that a high best-threshold balanced accuracy requires nontrivial majority score variation. For any score s ∈ S, define V0 (s) := EP0 {s(X) − u0 }2 . Let F0,s and F1,s denote the distributions of s(X) under X ∼ P0 and X ∼ P1 , respectively. For a threshold τ , write Bs (τ ) = {x : s(x) ≥ τ }. Then BA(s, τ ) −

1 1 1 = {P1 (Bs (τ )) + P0 (Bs (τ )c ) − 1} = {P1 (s(X) ≥ τ ) − P0 (s(X) ≥ τ )} . 2 2 2 65

Therefore, sup BA(s, τ ) − τ

1 1 ≤ sup |F1,s ([τ, ∞)) − F0,s ([τ, ∞))| . 2 2 τ ∈R

(S29)

Next, let U1 ∼ F1,s and U0 ∼ F0,s . For any coupling of (U1 , U0 ) and any h > 0, 1{U1 ≥ τ } − 1{U0 ≥ τ } ≤ 1{|U1 − U0 | > h} + 1{U0 ∈ [τ − h, τ )}. Taking expectations, using Markov inequality and the Bs -Lipschitz property of F0,s , and optimizing over couplings gives F1,s ([τ, ∞)) − F0,s ([τ, ∞)) ≤

E|U1 − U0 | W1 (F1,s , F0,s ) + Bs h ≤ + Bs h. h h

The inequality in the other direction can be derived similarly. Therefore taking absolute value and taking supremum gives sup |F1,s ([τ, ∞)) − F0,s ([τ, ∞))| ≤ τ ∈R

W1 (F1,s , F0,s ) + Bs h. h

Choosing h = {W1 (F1,s , F0,s )/Bs }1/2 , we get sup |F1,s ([τ, ∞)) − F0,s ([τ, ∞))| ≤ 2

q Bs W1 (F1,s , F0,s ).

(S30)

τ ∈R

Combining with equation (S29), we have sup BA(s, τ ) − τ

1 ≤ 2

q Bs W1 (F1,s , F0,s ).

Combining with equation (S23) gives 1 sup BA(s, τ ) ≤ + 2 τ

q p Bs (1 + BL ) V0 (s)1/4 .

Consequently, sup BA(s, τ ) ≥ A

⇒

V0 (s) ≥

A − 21 p √ Bs (1 + BL )

!4 =: κBA A .

Next, we show that high best-threshold balanced accuracy requires a majority-risk cost. Combining the analysis with equation (S24), sup BA(s, τ ) ≥ A

=⇒

R0 (s) − R∗0 ≥ m0 κBA A .

We now show that the raw imbalanced population minimizer cannot pay this majorityαraw risk cost under the stated imbalance condition. By the severe imbalance condition, 1−α D1 < raw BA m0 κA , combined with equation (S25), R0 (s∗raw ) − R∗0 < m0 κBA A . 66

If, contrary to the desired conclusion, supτ BA(s∗raw , τ ) ≥ A, then the previous analysis would give R0 (s∗raw ) − R∗0 ≥ m0 κBA A , which is a contradiction. Hence sup BA(s∗raw , τ ) < A. τ

We next control the augmented population score. Let B ∗ = {x : Λη∗ (x) ≥ 1/2} = {x : Lη∗ (x) ≥ 1} = {x : ηα∗ (x) ≥ α∗ }. For any measurable set B ⊆ X , BA(B) = 21 {P1 (B) + P0 (B c )}. Since dP1 = Lη∗ dP0 , Z 1 BA(B) = 1 + (Lη∗ (x) − 1) dP0 (x) . 2 B Thus B ∗ maximizes balanced accuracy, and by strictly increasing transformation, sup BA(ηα∗ , τ ) = sup BA(Λη∗ , τ ) = BA(B ∗ ). τ

Since supτ BA(sα∗ , τ ) ≥ BA ({x : sα∗ (x) ≥ α∗ }), we have sup BA(Λη∗ , τ ) − sup BA(sα∗ , τ ) ≤ BA(B ∗ ) − BA ({x : sα∗ (x) ≥ α∗ }) τ τ Z 1 |L(x) − 1| dP0 (x). = 2 {sα∗ ≥α∗ }△B ∗ On the disagreement set {sα∗ ≥ α∗ }△{ηα∗ ≥ α∗ }, we must have |ηα∗ (x) − α∗ | ≤ |sα∗ (x) − ηα∗ (x)|. Moreover, inverse the relationship, we have Lη∗ =

1 − α∗ ηα∗ , α ∗ 1 − η α∗

|Lη∗ − 1| =

∗

|ηα∗ − α∗ | . α∗ (1 − ηα∗ )

∗

α α Since Lη∗ ≤ BL , 1−η1 α∗ = 1 + 1−α ∗ Lη ∗ ≤ 1 + 1−α∗ BL . Thus

|Lη∗ − 1| ≤

1 BL + ∗ α 1 − α∗

∗

|ηα∗ − α | ≤

1 BL + ∗ α 1 − α∗

|sα∗ (x) − ηα∗ (x)|.

Combining the preceding displays with equation (S26) gives 1 1 BL sup BA(Λη∗ , τ ) − sup BA(sα∗ , τ ) ≤ + EP0 |sα∗ (X) − ηα∗ (X)| 2 α∗ 1 − α∗ τ τ r 1 1 BL 1 − α∗ + α∗ BL ϵ∗ 2 1/2 ≤ + EP0 {sα∗ (X) − ηα∗ (X)} ≤ . 2 α∗ 1 − α∗ 2α∗ (1 − α∗ )3/2 mℓ Hence

1 − α∗ + α∗ BL ∗ ∗ sup BA(sα , τ ) ≥ sup BA(Λη , τ ) − ∗ 2α (1 − α∗ )3/2 τ τ 67

ϵ∗ . mℓ

Combining this with supτ BA(s∗raw , τ ) < A, we obtain the population-level gap 1 − α∗ + α∗ BL sup BA(sα∗ , τ ) − sup BA(s∗raw , τ ) ≥ sup BA(Λη∗ , τ ) − A − ∗ 2α (1 − α∗ )3/2 τ τ τ

ϵ∗ . mℓ

It remains to pass from population minimizers to empirical estimators. By the same procedure with equations (4) and (5), but with the simultaneous statement in Lemma S1, we have the following holds simultaneously with probability at least 1 − δ that s CLc B 2 d log(14d/δ) sup BA(sθ̂raw , τ ) − sup BA(s∗raw , τ ) ≤ , λ n0 + n 1 τ τ and CLc sup BA(sθ̂aug , τ ) − sup BA(sα∗ , τ ) ≤ λ τ τ

CLLg B 2 d log(14d/δ) ñ +p ϵsyn . n0 + n1 + ñ 2µLρ n0 + n1 + ñ

∗

α Taking ñ = 1−α ∗ n0 − n1 and absorbing constants gives the final result for BA.

Proof for F1 score: We first show that a high best-threshold F1 score implies nontrivial majority-score variation. For a fixed threshold τ , define Rτ := P1 (s(X) ≥ τ ), and Qτ := P0 (s(X) ≥ τ ). Then 2π1 Rτ . F1 (s, τ ) = π1 (1 + Rτ ) + π0 Qτ 2π1 The constant-score best-threshold F1 baseline is bπ = 1+π . By direct calculation, 1

F1 (s, τ ) − bπ =

2π1 Rτ 2π1 2π1 {Rτ − π1 − π0 Qτ } . − = π1 (1 + Rτ ) + π0 Qτ 1 + π1 {π1 (1 + Rτ ) + π0 Qτ }(1 + π1 )

Since Rτ − π1 − π0 Qτ ≤ Rτ − Qτ and π1 (1 + Rτ ) + π0 Qτ ≥ π1 , we have F1 (s, τ ) − bπ ≤ 2 |Rτ − Qτ | . Taking the supremum over τ gives sup F1 (s, τ ) − bπ ≤ 2 sup |P1 (s(X) ≥ τ ) − P0 (s(X) ≥ τ )| . τ

By equation (S30), it holds that q sup |P1 (s(X) ≥ τ ) − P0 (s(X) ≥ τ )| ≤ 2 Bs W1 (F1,s , F0,s ). τ

Moreover, combining with equation (S23), q p sup F1 (s, τ ) ≤ bπ + 4 Bs (1 + BL ) V0 (s)1/4 . τ

Therefore, whenever supτ F1 (s, τ ) ≥ A > bπ , we have V0 (s) ≥

A − bπ p √ 4 Bs (1 + BL )

!4 =: κFA1 .

Hence by equation (S24), sup F1 (s, τ ) ≥ A

R0 (s) − R0 (s0 ) ≥ m0 κFA1 .

=⇒

Next we show that the raw population minimizer cannot achieve F1 level A. By the αraw D1 < m0 κFA1 , combined with equation (S25), severe imbalance condition, 1−α raw R0 (s∗raw ) − R0 (s0 ) < m0 κFA1 . If supτ F1 (s∗raw , τ ) ≥ A, previous analysis would imply R0 (s∗raw ) − R0 (s0 ) ≥ m0 κFA1 , which is a contradiction. Therefore sup F1 (s∗raw , τ ) < A. τ

Next we show that the augmented target can approximate the oracle F1 score up to approximation error term. There exists a likelihood-ratio threshold set BF∗ = {x : Λη∗ (x) ≥ tF } = {x : ηα∗ (x) ≥ t∗F }, where t∗F = gα∗ (tF ) and we select tF such that F1 (BF∗ ) = supτ F1 (Λ, τ ). For a measurable set B, write rB := P1 (B), qB := P0 (B), so that F1 (B) =

2π1 rB . π1 (1 + rB ) + π0 qB

Equivalently, writing N (B) := 2π1 P1 (B), D(B) := π1 (1+P1 (B))+π0 P0 (B), we have F1 (B) = N (B) . By Lemma 1, for every measurable set B, F1 (B) ≤ supτ F1 (Λ, τ ) = F1 (BF∗ ). Since D(B) D(B) > 0, this is equivalent to N (B) − sup F1 (Λ, τ )D(B) ≤ 0. τ

Moreover, equality holds at B = BF∗ : N (BF∗ ) − supτ F1 (Λ, τ )D(BF∗ ) = 0. Therefore, BF∗ is a maximizer, over measurable sets B, of the functional B 7→ N (B) − sup F1 (Λ, τ )D(B). τ

Now use dP1 = Lη∗ dP0 . Then Z N (B) = 2π1 Lη∗ (x) dP0 (x),

Z {π1 Lη∗ (x) + π0 } dP0 (x).

D(B) = π1 +

Hence N (B) − sup F1 (Λ, τ )D(B) τ Z = 2π1 Lη∗ (x) − sup F1 (Λ, τ ){π1 Lη∗ (x) + π0 } dP0 (x) − π1 sup F1 (Λ, τ ). τ

The last term does R not depend on B. Thus maximizing the display above over B is equivalent to maximizing B ψ(x) dP0 (x), where ψ(x) := 2π1 Lη∗ (x) − sup F1 (Λ, τ ){π1 Lη∗ (x) + π0 }. τ

R For any integrable function ψ, the set maximizing B ψ(x) dP0 (x) over all measurable B is simply {x : ψ(x) ≥ 0} up to P0 -null sets. Therefore the oracle best-F1 decision region can be written, up to null sets, as BF∗ = {x : ψ(x) ≥ 0}. The F1 difference can be written as sup F1 (Λ, τ ) − F1 (B) = τ

supτ F1 (Λ, τ )D(B) − N (B) . D(B)

The previous analysis gives Z sup F1 (Λ, τ )D(B) − N (B) = π1 sup F1 (Λ, τ ) − τ

ψ(x) dP0 (x).

Since BF∗ = {x : ψ(x) ≥ 0} attains the oracle value, we have 0 = sup F1 (Λ, τ )D(BF∗ ) − N (BF∗ ) = π1 sup F1 (Λ, τ ) − τ τ

Z ψ(x) dP0 (x). ∗ BF

Thus Z sup F1 (Λ, τ )D(B) − N (B) =

Z ψ(x) dP0 (x) −

∗ BF

Z |ψ(x)| dP0 (x),

ψ(x) dP0 (x) = ∗ △B BF

where the last equality uses ψ ≥ 0 on BF∗ and ψ < 0 on (BF∗ )c . Then it follows that R Z ∗ △B |ψ(x)| dP0 (x) 1 BF sup F1 (Λ, τ ) − F1 (B) = ≤ |ψ(x)| dP0 (x). π1 (1 + rB ) + π0 qB π1 BF∗ △B τ Now take Baug := {x : sα∗ (x) ≥ t∗F }. On BF∗ △Baug , we have |ηα∗ (x) − t∗F | ≤ |sα∗ (x) − ηα∗ (x)|. We now bound |ψ(x)|. By definition, it can be written as ψ(x) = π1 {2 − sup F1 (Λ, τ )}Lη∗ (x) − π0 sup F1 (Λ, τ ). τ

Since the oracle best-F1 set is BF∗ = {x : Λη∗ (x) ≥ tF } = {x : ηα∗ (x) ≥ t∗F } = {x : Lη∗ (x) ≥ ℓF }, 70

where

1 − α∗ t∗F tF = , ℓF = 1 − tF α∗ 1 − t∗F

the boundary condition ψ(x) = 0 at Lη∗ (x) = ℓF gives π1 {2 − sup F1 (Λ, τ )}ℓF = π0 sup F1 (Λ, τ ). τ

Therefore, ψ(x) = π1 {2 − sup F1 (Λ, τ )}{Lη∗ (x) − ℓF }. τ

Consequently, |ψ(x)| ≤ 2π1 |Lη∗ (x) − ℓF |, because supτ F1 (Λ, τ ) ∈ [0, 1]. Plugging in Lη∗ and ℓF with respect to ηα∗ and t∗F gives |Lη∗ (x) − ℓF | =

1 − α∗ t∗F 1 − α∗ 1 − α∗ ηα∗ |ηα∗ − t∗F | − = . α∗ 1 − ηα∗ α∗ 1 − t∗F α∗ (1 − ηα∗ )(1 − t∗F ) ∗

∗

α α Since Lη∗ ≤ BL , 1−η1 α∗ = 1 + 1−α ∗ Lη ∗ ≤ 1 + 1−α∗ BL . Also, the oracle F1 threshold satisfies ℓF ≤ BL . Indeed, if ℓF > BL , then {Lη∗ ≥ ℓF } is empty, so the resulting F1 is 0, contradicting the fact that predicting everything positive already gives a strictly positive F1 score. α∗ α∗ 1 Therefore, 1−t ∗ = 1 + 1−α∗ ℓF ≤ 1 + 1−α∗ BL . Thus, F

1 − α∗ |Lη∗ (x) − ℓF | ≤ α∗

α∗ 1+ BL 1 − α∗

|ηα∗ − t∗F | =

(1 − α∗ + α∗ BL )2 |ηα∗ − t∗F |. α∗ (1 − α∗ )

Combining the preceding displays yields |ψ(x)| ≤ 2π1

(1 − α∗ + α∗ BL )2 |ηα∗ − t∗F |. α∗ (1 − α∗ )

Combining the preceding inequalities gives 2(1 − α∗ + α∗ BL )2 EP0 |sα∗ (X) − ηα∗ (X)| α∗ (1 − α∗ ) 1/2 2(1 − α∗ + α∗ BL )2 ≤ EP0 {sα∗ (X) − ηα∗ (X)}2 . ∗ ∗ α (1 − α )

sup F1 (Λ, τ ) − F1 (Baug ) ≤ τ

By M ∗ = (1 − α∗ )P0 + α∗ P1 , EP0 {sα∗ (X) − ηα∗ (X)}2 ≤

1 EM ∗ {sα∗ (X) − ηα∗ (X)}2 , 1 − α∗

Thus, by equation (S26), 2(1 − α∗ + α∗ BL )2 sup F1 (Λ, τ ) − F1 (Baug ) ≤ α∗ (1 − α∗ )3/2 τ 71

ϵ∗ . mℓ

Since supτ F1 (sα∗ , τ ) ≥ F1 (Baug ), we obtain 2(1 − α∗ + α∗ BL )2 sup F1 (sα∗ , τ ) ≥ sup F1 (Λ, τ ) − α∗ (1 − α∗ )3/2 τ τ

ϵ∗ . mℓ

Together with supτ F1 (s∗raw , τ ) < A, this gives the population-level gap 2(1 − α∗ + α∗ BL )2 ∗ ∗ sup F1 (sα , τ ) − sup F1 (sraw , τ ) ≥ sup F1 (Λ, τ ) − A − α∗ (1 − α∗ )3/2 τ τ τ

ϵ∗ . mℓ

Finally, we pass from population minimizers to empirical estimators. By the same finitesample argument as in equations (6) and (7), but with the simultaneous statement in Lemma S1, the following inequalities hold simultaneously with probability at least 1 − δ: s CLc B 2 d log(14d/δ) sup F1 (sθbraw , τ ) − sup F1 (s∗raw , τ ) ≤ , π1 λ n0 + n1 τ τ and CLc sup F1 (sθbaug , τ ) − sup F1 (sα∗ , τ ) ≤ π1 λ τ τ

B 2 d log(14d/δ) n e 4CLLg + p ϵsyn . n0 + n1 + n e e π1 2µLρ n0 + n1 + n

∗

α Taking n e = 1−α ∗ n0 − n1 , and absorbing constants, we finish the proof.

Proofs of Examples and Corollaries

Proof of Example 1. Define the uniform approximation errors abal (K) = inf sup |h(t) − t|, h∈HK t∈[0,1]

aα (K) = inf sup |h(t) − gα (t)|. h∈HK t∈[0,1]

We first study the uniform approximation error of the balanced target. For any h ∈ HK , define e(t) = h(t) − t. Since h is K-Lipschitz, h(1) − h(0) ≤ K. Therefore, e(0) − e(1) = h(0) − h(1) − 1 = 1 + h(0) − h(1) ≥ 1 − K. Hence |e(0)| + |e(1)| ≥ 1 − K, which implies sup |h(t) − t| ≥ t∈[0,1]

1−K . 2

Taking the infimum over h ∈ HK , we obtain abal (K) ≥ 72

1−K . 2

This lower bound is sharp. Indeed, define hK (t) = Kt + 1−K . Then hK ∈ HK , and 2 hK : [0, 1] → [0, 1]. Moreover, 1 −t , hK (t) − t = (1 − K) 2 so sup |hK (t) − t| = t∈[0,1]

1−K . 2

Therefore, abal (K) = 1−K . Because K < 1, this quantity is strictly positive. Hence the 2 balanced target is not exactly representable uniformly as a transformation on [0, 1]. In particular, if Λ is nonconstant, then x 7→ Λ(x) is not exactly represented in SK . Next we study the imbalanced target. A direct calculation gives gα (1) − gα (1 − α) = 12 . Thus gα changes by 1/2 over the interval [1 − α, 1], whose length is α. Let h ∈ HK , and define eα (t) = h(t) − gα (t). Since h is K-Lipschitz, |h(1) − h(1 − α)| ≤ Kα. Therefore, |eα (1) − eα (1 − α)| =

1 h(1) − h(1 − α) − gα (1) − gα (1 − α) ≥ − Kα. 2

Consequently, |eα (1)| + |eα (1 − α)| ≥ 21 − Kα, and hence 1 1 − Kα . sup |h(t) − gα (t)| ≥ 2 2 t∈[0,1] Taking the infimum over h ∈ HK , we obtain 1 aα (K) ≥ 2

1 − Kα . 2

Combining the previous bounds, we get 1−K 1 1 1 1 aα (K) − abal (K) ≥ − Kα − = K(1 − α) − . 2 2 2 2 2 Therefore, if K(1 − α) > 12 , then aα (K) > abal (K). This proves the uniform approximation separation. We now prove the squared L2 lower bound for the imbalanced target. Define the squared L2 (µ) approximation errors Abal (K) = inf Eµ (h(Λη∗ (X)) − Λη∗ (X))2 , h∈HK

and Aα (K) = inf Eµ (h(Λη∗ (X)) − gα (Λη∗ (X)))2 . h∈HK

Let IL = [1 − α, 1 − 3α/4], 73

IH = [1 − α/4, 1].

For t ∈ IL and for t ∈ IH , respectively, by the range of t and α, 2 gα (t) ≤ , 3

4 gα (t) ≥ , 5

t ∈ IL ;

t ∈ IH .

It follows that, for every tL ∈ IL and tH ∈ IH , gα (tH ) − gα (tL ) ≥

2 4 2 − = . 5 3 15

2 − Kα 15

2 .

Averaging this inequality over tL ∈ IL and tH ∈ IH , and using |IL | = |IH | = α4 gives 2 Z α 2 2 eα (t) dt ≥ − Kα . 8 15 IL ∪IH Since the density q of T = Λη∗ (X) under µ satisfies q(t) ≥ q on IL ∪ IH , we have 2 qα 2 2 − Kα . Eµ (h(Λη∗ (X)) − gα (Λη∗ (X))) ≥ 8 15 Taking the infimum over h ∈ HK , we obtain qα Aα (K) ≥ 8

2 − Kα 15

2 .

2 1 If Kα ≤ 1/15, then 15 − Kα ≥ 15 , and hence

Aα (K) ≥

qα 1 q · = α. 8 225 1800

For the balanced target, use again hK (t) = Kt + 1−K , then 2 |hK (t) − t| ≤

1−K , 2

∀ t ∈ [0, 1].

Therefore, (1 − K)2 2 ∗ ∗ Abal (K) ≤ Eµ (hK (Λη (X)) − Λη (X)) ≤ . 4 2

Combining the two bounds, if (1−K) < 1800 α, then Abal (K) < Aα (K). Solving gives the 4 range of α for which this inequality holds. This finishes the proof. 74

Proof of Example 2. We first prove the approximation upper bound for the balanced target. j k For each coordinate j = 1, . . . , p, partition [0, 1] into K + 1 equal intervals, where K := mp . We show that a piecewise affine interpolant has a ReLU representation. Let 0 = u0 < u1 < · · · < uK < uK+1 = 1 ej,K be the continuous piecewise be the grid points of the partition, with uk = k/(K +1). Let λ ej,K agrees with λj at the grid points: affine interpolant of λj on this grid. That is, λ ej,K (uk ) = λj (uk ), λ

k = 0, . . . , K + 1,

ej,K on [uk−1 , uk ] by and is affine on each interval [uk−1 , uk ]. Denote the slope of λ rj,k =

λj (uk ) − λj (uk−1 ) , uk − uk−1

k = 1, . . . , K + 1.

ej,K (t) = λj (0) + rj,1 t. At the interior grid point uk , Thus, on the first interval [u0 , u1 ], λ the slope changes from rj,k to rj,k+1 . Hence the slope jump at uk is cj,k = rj,k+1 − rj,k , k = 1, . . . , K. The shifted ReLU (t − uk )+ is zero for t ≤ uk and has derivative one for t > uk . Therefore, adding cj,k (t − uk )+ changes the slope by exactly cj,k after the point uk , while leaving the function unchanged before uk . Applying this correction at every interior grid point gives K X e (rj,k+1 − rj,k )(t − uk )+ . λj,K (t) = λj (0) + rj,1 t + k=1

Indeed, for t ∈ [uℓ−1 , uℓ ], only the terms with k ≤ ℓ − 1 are active, so the derivative of the right-hand side is ℓ−1 X rj,1 + (rj,k+1 − rj,k ) = rj,ℓ , k=1

which is exactly the slope of the interpolant on [uℓ−1 , uℓ ]. The two functions also agree at t = 0, since both equal λj (0). Therefore the displayed formula is exactly the piecewise affine ej,K admits the univariate ReLU representation interpolant. Consequently, λ ej,K (t) = bj,0 + bj,1 t + λ

K X

cj,k (t − τj,k )+ ,

k=1

with bj,0 = λj (0), bj,1 = rj,1 , τj,k = uk , cj,k = rj,k+1 − rj,k . Thus the interpolant has at most K breakpoints and can be represented by a univariate ReLU network with K hidden units. Define p 1 Xe λj,K (xj ). sm (x) = p j=1

Then

p p p K X 1X 1 XX bj,1 sm (x) = xj + bj,0 + cj,k (xj − τj,k )+ . p j=1 p p j=1 k=1 j=1

This is a p-dimensional shallow ReLU network. Each term (xj − τj,k )+ is a ReLU unit with weight vector equal to the j-th coordinate vector. The total number of hidden units is pK ≤ m. (p) We now verify that this approximant belongs to the norm-constrained class Nm,A . The , . . . , bp,1 . Since each bj,1 is a slope of λj , the linear coefficient vector of sm is βm = b1,1 p p mean-value theorem gives |bj,1 | ≤ ∥λ′j ∥L∞ ([0,1]) ≤ B1 . Therefore ( p )1/2 X B1 2 B1 ∥βm ∥2 ≤ =√ . p p j=1 Next, the ReLU coefficient attached to (xj − τj,k )+ is cj,k /p, and the corresponding weight vector has Euclidean norm one. Hence the ReLU part of the path norm is p K X X cj,k j=1 k=1

1 XX = |cj,k |. p j=1 k=1

For the piecewise affine interpolant, cj,k is the jump in slope at the k-th breakpoint. Let ej,K on the k-th interpolation interval. Then h = 1/(K + 1), and let rj,k be the slope of λ cj,k = rj,k+1 − rj,k . We have Z 1 h ′ rj,k+1 − rj,k = λj (uk + t) − λ′j (uk−1 + t) dt. h 0 Because ∥λ′′j ∥∞ ≤ B2 , the derivative λ′j is B2 -Lipschitz. Hence, for every t ∈ [0, h], λ′j (uk + t) − λ′j (uk−1 + t) ≤ B2 h. Therefore

K X

|cj,k | =

k=1

It follows that obtain

j=1

k=1

K X

|rj,k+1 − rj,k | ≤ KB2 h ≤ B2 .

k=1 cj,k p

≤ B2 . Combining the linear and ReLU contributions, we

∥βm ∥2 +

p K X X cj,k j=1 k=1

B1 ≤ √ + B2 ≤ A. p

(p)

Thus sm ∈ Nm,A . To bound the approximation error, we use the standard interpolation error bound. Fix t ∈ [uk−1 , uk ]. By the classical error formula for linear interpolation, there exists a point ξt ∈ (uk−1 , uk ) such that ej,K (t) = λj (t) − λ

λ′′j (ξt ) (t − uk−1 )(t − uk ). 2 76

Hence ej,K (t)| ≤ |λj (t) − λ 2

∥λ′′j ∥L∞ ([uk−1 ,uk ]) (t − uk−1 )(uk − t). 2

Since (t − uk−1 )(uk − t) ≤ (uk −u4k−1 ) = h4 , we get 2

ej,K (t)| ≤ B2 · h = B2 h . |λj (t) − λ 2 4 8 Because h = 1/(K + 1), this becomes ej,K (t)| ≤ |λj (t) − λ

B2 . 8(K + 1)2

Taking the supremum over all t ∈ [0, 1] yields ej,K − λj ∥L∞ ([0,1]) ≤ ∥λ

B2 . 8(K + 1)2

Therefore, p

1X e ∥sm − Λ∥L∞ ([0,1]p ) = sup {λj,K (xj ) − λj (xj )} x∈[0,1]p p j=1 p

B2 1X e ∥λj,K − λj ∥L∞ ([0,1]) ≤ . ≤ p j=1 8(K + 1)2 Since η1/2 = Λ, this proves inf ∥s − η1/2 ∥L∞ ([0,1]p ) ≤ (p)

s∈Nm,A

B2 . 8(K + 1)2

We next derive the Lipschitz property from the network norm constraint. Let s(x) = β0 + β ⊤ x +

m X

(p)

aℓ σ(wℓ⊤ x − tℓ ) ∈ Nm,A .

ℓ=1

Since σ is 1-Lipschitz, |σ(wℓ⊤ x − tℓ ) − σ(wℓ⊤ z − tℓ )| ≤ ∥wℓ ∥2 ∥x − z∥2 . Therefore, ⊤

|s(x) − s(z)| ≤ |β (x − z)| +

m X

|aℓ ||σ(wℓ⊤ x − tℓ ) − σ(wℓ⊤ z − tℓ )|

ℓ=1

≤

∥β∥2 +

m X

! |aℓ | ∥wℓ ∥2 ∥x − z∥2 ≤ A∥x − z∥2 .

ℓ=1 (p)

Hence every s ∈ Nm,A is A-Lipschitz: Lip(s) ≤ A.

We now prove the lower bound for the imbalanced target. Fix 0 < α ≤ λ− r0 . Define two points in [0, 1]p : α α + − x = (1, . . . , 1), x = 1− ,...,1 − . λ− λ− Since α ≤ λ− r0 , each coordinate of x− lies in [1 − r0 , 1]. For each j, using λj (1) = 1 and λ′j (t) ≥ λ− on [1 − r0 , 1], we obtain Z 1 α α 1 − λj 1 − = λj (1) − λj 1 − = λ′j (u) du ≥ α. λ− λ− 1−α/λ− Therefore λj 1 − λα− ≤ 1 − α. Averaging over j = 1, . . . , p, we get p 1X α Λ(x ) = λj 1 − ≤ 1 − α. p j=1 λ− −

On the other hand, p

1X Λ(x ) = λj (1) = 1. p j=1 +

Since gα is increasing, ηα (x− ) = gα (Λ(x− )) ≤ gα (1−α). A direct calculation gives gα (1−α) = 1 . Also, ηα (x+ ) = gα (Λ(x+ )) = gα (1) = 1. Thus 2 1 ηα (x+ ) − ηα (x− ) ≥ . 2 (p)

Now take any s ∈ Nm,A , and define e(x) = ηα (x) − s(x). Since Lip(s) ≤ A, as proved above, |s(x+ ) − s(x− )| ≤ A∥x+ − x− ∥2 . Moreover, +

(

−

∥x − x ∥2 = Hence

α λ−

√

2 )1/2 =

pα . λ−

√ A pα |s(x ) − s(x )| ≤ . λ− +

−

Using the decomposition ηα (x+ ) − ηα (x− ) = {s(x+ ) − s(x− )} + {e(x+ ) − e(x− )}, we obtain √ A pα 1 + − + − + − ≤ ηα (x ) − ηα (x ) ≤ |s(x ) − s(x )| + |e(x )| + |e(x )| ≤ + 2∥e∥L∞ ([0,1]p ) . 2 λ− 78

Therefore,

√ 1 A pα . ∥s − ηα ∥L∞ ([0,1]p ) = ∥e∥L∞ ([0,1]p ) ≥ − 4 2λ− Since the left-hand side is nonnegative, we may write √ 1 A pα ∥s − ηα ∥L∞ ([0,1]p ) ≥ − . 4 2λ− + (p)

Taking the infimum over s ∈ Nm,A , we obtain inf ∥s − ηα ∥L∞ ([0,1]p ) ≥ (p)

s∈Nm,A

√ 1 A pα − . 4 2λ− +

Finally, combine the two bounds. We have shown that √ 1 A pα inf ∥s − ηα ∥L∞ ([0,1]p ) ≥ − , (p) 4 2λ− s∈Nm,A

B2 inf ∥s − η1/2 ∥L∞ ([0,1]p ) ≤ , (p) 8(K + 1)2 s∈Nm,A

whenever the right-hand side is positive. Therefore, if 2λ− 1 B2 0 < αraw < min λ− r0 , √ − , A p 4 8(K + 1)2 then

√ B2 1 A p αraw − > . 4 2λ− 8(K + 1)2

Consequently, inf ∥s − η1/2 ∥L∞ ([0,1]p ) < inf ∥s − ηαraw ∥L∞ ([0,1]p ) . (p)

s∈Nm,A

(p)

s∈Nm,A

This completes the proof. Proof of Corollary 1. We first consider this model at the population level for general class weights. For brevity, denote the log-likelihood as ℓ(MLE) . Define the weights between class as w = (w0 , w1 ). Then the population estimator is defined as θw∗ ∈ arg max w0 EP0 ℓ(MLE) (sθ (X), 0) + w1 EP1 ℓ(MLE) (sθ (X), 1) . θ

We then show that the induced scores sθw∗ for general weights w are indeed increasingly transformed from the likelihood ratio. By the Bernoulli model, we can explicitly write the population objective as θw∗ ∈ arg max w0 EP0 ℓ(MLE) (sθ (X), 0) + w1 EP1 ℓ(MLE) (sθ (X), 1) θ

= arg max {w0 EP0 log(1 − sθ (X)) + w1 EP1 log(sθ (X))} θ Z Z = arg max w0 p0 log(1 − sθ (x))dx + w1 p1 log(sθ (x))dx. θ

For each x, denote ϕ(x) := w0 p0 (x) log(1 − sθ (x)) + w1 p1 (x) log(sθ (x)). Taking the derivative with respect to t = sθ (x), ∂ϕ w0 p0 (x) w1 p1 (x) =− + = 0, ∂t 1−t t

∂ 2ϕ < 0. ∂t2

Because the loss depends on the parameter θ only through the score sθ , and the score maximizer is attainable by the model class by assumption, the score maximizer is attained by a corresponding parameter maximizer. We derive the maximizer sθw∗ (x) =

w1 Lη∗ (x) w1 p1 (x) = . w1 p1 (x) + w0 p0 (x) w1 Lη∗ (x) + w0

Define the function

w1 t , w1 t + w0 which is a strictly increasing transformation. Thus the population score g(t) =

sθw∗ (x) = g(Lη∗ (x)), is a strictly increasing transformation of Λη∗ , because Lη∗ is a strictly increasing transformation of Λη∗ . Therefore, we have verified that Assumption 2 holds for the MLE model. Thus, the bounds follow by essentially the same argument as in the proofs of Theorems 3, 4, 5 and 6. This completes the proof.

Proofs of Lemmas

Proof of Lemma 1. We prove the results for the four metrics separately. For the four metrics considered, the proofs of Theorems 1 and 2 show that these metrics are invariant to strictly increasing transformations. Note the relationship, Λη∗ (x) =

Lη∗ (x) = g1 (Lη∗ (x)), 1 + Lη∗ (x)

Lη∗ (x) =

Λη∗ (x) = g2 (Λη∗ (x)), 1 − Λη∗ (x)

t t where g1 (t) = 1+t and g2 (t) = 1−t are strictly increasing transformations. Therefore, the values of the four metrics for Λη∗ (x) are equal to those for Lη∗ (x). Thus, for brevity, we can also use Lη∗ (x) as the optimal score.

Optimality for AUROC: We first show that the likelihood-ratio threshold is ROC-optimal at every false-positive level. For any measurable set S ⊆ X , define FPR(S) := P0 (S), TPR(S) := P1 (S). For α ∈ (0, 1), define the best achievable true-positive rate at false-positive level α by n o β ∗ (α) := sup P1 (S) : S ⊆ X measurable, P0 (S) ≤ α . 80

Define the set Cc := {x : Lη∗ (x) ≥ c}. Because L(X0 ) is continuous under P0 , for every α ∈ (0, 1) there exists cα such that P0 (Ccα ) = α. We claim that Ccα achieves β ∗ (α), that is, P1 (S) ≤ P1 (Ccα )

for every measurable S with P0 (S) ≤ α.

To prove this, first consider any measurable S with P0 (S) = α. Since L(x) ≥ cα

L(x) ≤ cα

on Ccα ,

on Cccα ,

we have p1 (x) − cα p0 (x) ≤ 0 on Cccα .

p1 (x) − cα p0 (x) ≥ 0 on Ccα , Therefore, Z

p1 − cα p0 dx.

p1 − cα p0 dx ≥ S

Ccα

Rearranging gives P1 (Ccα ) − cα P0 (Ccα ) ≥ P1 (S) − cα P0 (S). Since P0 (Ccα ) = P0 (S) = α, the cα α terms cancel, yielding P1 (Ccα ) ≥ P1 (S). If instead P0 (S) < α, then S is still feasible for the constraint P0 (S) ≤ α, and P1 (Ccα ) − cα P0 (Ccα ) ≥ P1 (S) − cα P0 (S) ≥ P1 (S) − cα α. We thus still have P1 (Ccα ) ≥ P1 (S). Hence by definition of the supremum β ∗ (α), β ∗ (α) = P1 (Ccα ). So we conclude that the likelihood-ratio threshold rule is pointwise optimal on the ROC plane. Next we show that the ROC curve of any score is dominated by that of Lη∗ . For any measurable score s, define its threshold sets St (s) := {x : s(x) ≥ t}. Its ROC curve can be written as n o ROCs (α) := sup P1 (St (s)) : P0 (St (s)) ≤ α, t ∈ R . Every threshold set St (s) is just a measurable set, so by previous analysis, P1 (St (s)) ≤ β ∗ (α) = ROCLη∗ (α)

whenever P0 (St (s)) ≤ α.

Taking the supremum over all such thresholds t, we obtain ROCs (α) ≤ ROCLη∗ (α)

for every α ∈ (0, 1).

Assume that s(X0 ) has a continuous distribution under P0 . For each threshold t ∈ R, define St (s) := {x : s(x) ≥ t}. Recall that n o ROCs (α) := sup P1 (St (s)) : P0 (St (s)) ≤ α, t ∈ R , α ∈ (0, 1). Recall that the AUROC is defined as AUC(s) = P (s(X1 ) > s(X0 )) + 21 P (s(X1 ) = s(X0 )). R1 We next prove that this definition is equivalent to AUC(s) = 0 ROCs (α) dα, based on the 81

definition of the ROC curve. To achieve this, first define the survival functions of the score under the two classes by F̄0 (t) := P s(X0 ) ≥ t = P0 (St (s)), F̄1 (t) := P s(X1 ) ≥ t = P1 (St (s)). Because s(X0 ) has a continuous distribution, the map t 7→ F̄0 (t) is continuous and nonincreasing, with limits decreasing from 1 to 0. Therefore, for every α ∈ (0, 1), there exists a threshold tα such that P0 (Stα (s)) = F̄0 (tα ) = α. We now show that this threshold attains the supremum in the definition of ROCs (α). The threshold sets are nested: t1 ≤ t2

St2 (s) ⊆ St1 (s).

=⇒

Hence both P0 (St (s)) and P1 (St (s)) are nonincreasing functions of t. Now let t ∈ R be any threshold satisfying P0 St (s) ≤ α = P0 Stα (s) . If t ≥ tα , then St (s) ⊆ Stα (s), and hence P1 St (s) ≤ P1 Stα (s) . If t < tα , then Stα (s) ⊆ St (s). Together with P0 St (s) ≤ P0 Stα (s) , this implies P0 St (s) \ Stα (s) = 0. Since P1 ≪ P0 , it follows that P1 St (s) \ Stα (s) = 0, and therefore P1 St (s) = P1 Stα (s) . Thus among all thresholds with false-positive rate at most α, the maximal true-positive rate is attained at a threshold with equality, and so ROCs (α) = P1 (Stα (s)) = P s(X1 ) ≥ tα . Next let F0 (t) := P s(X0 ) ≤ t be the distribution function of s(X0 ), and define its generalized inverse by Q0 (u) := inf{t : F0 (t) ≥ u}, u ∈ (0, 1). Because s(X0 ) is continuous, we may take tα = Q0 (1 − α), and then P0 (Stα (s)) = P s(X0 ) ≥ Q0 (1 − α) = α. Hence ROCs (α) = P s(X1 ) ≥ Q0 (1 − α) . Therefore, Z 1

Z 1 ROCs (α) dα =

P s(X1 ) ≥ Q0 (1 − α) dα.

Substituting u = 1 − α, so that dα = −du, gives Z 1 Z 1 ROCs (α) dα = P s(X1 ) ≥ Q0 (u) du. 0

Now apply Tonelli’s theorem: Z 1 Z 1 Z 1 P s(X1 ) ≥ Q0 (u) du = E 1{s(X1 ) ≥ Q0 (u)} du = E 1{Q0 (u) ≤ s(X1 )} du . 0

R1 So it remains to identify the quantity 0 1{Q0 (u) ≤ z} du for a fixed z ∈ R. It is easy to see that {u ∈ [0, 1] : Q0 (u) ≤ z} = {u ∈ [0, 1] : u ≤ F0 (z)}. Thus we obtain Z 1 Z 1 1{u ≤ F0 (z)} du = F0 (z). 1{Q0 (u) ≤ z} du = 0

Applying this with z = s(X1 ), we get Z 1 ROCs (α) dα = E F0 (s(X1 )) . 0

We now identify this expectation as a comparison probability. By definition of F0 , F0 (s(X1 )) = P s(X0 ) ≤ s(X1 ) | X1 . Taking expectations and using independence of X0 and X1 , we obtain E F0 (s(X1 )) = P s(X0 ) ≤ s(X1 ) . Hence

Z 1

ROCs (α) dα = P s(X0 ) ≤ s(X1 ) .

Finally, because s(X0 ) has a continuous distribution, for every fixed a ∈ R, P s(X0 ) = a = 0. Therefore P s(X0 ) = s(X1 ) = E P s(X0 ) = s(X1 ) | X1 = 0. We then conclude that AUC(s) = P s(X1 ) > s(X0 ) . Combining the previous displays R1 yields 0 ROCs (α) dα = AUC(s). Thus we have proved the integral representation for AUC that Z 1 AUC(s) = ROCs (α) dα. 0

Now integrate over α. It follows that, Z 1 Z 1 ROCLη∗ (α) dα = AUC(Lη∗ ) = AUC(Λη∗ ). AUC(s) = ROCs (α) dα ≤ 0

This completes the proof of AUROC optimality of the likelihood ratio. Optimality for AUPRC: We first show that for each fixed recall level, a likelihood-ratio threshold minimizes the false-positive rate. Fix r ∈ (0, 1). Since Lη∗ (X1 ) has a continuous CDF under P1 , there exists a threshold cr such that P1 (Lη∗ (X) ≥ cr ) = r. Define the likelihood-ratio threshold set Br := {x : Lη∗ (x) ≥ cr }. Then P1 (Br ) = r. We claim that among all measurable sets S ⊆ X satisfying P1 (S) = r, the set Br minimizes P0 (S). 83

Let S be any measurable set with P1 (S) = r. Since Lη∗ (x) = p1 (x)/p0 (x), we have p1 (x) − cr p0 (x) ≤ 0 on Brc .

p1 (x) − cr p0 (x) ≥ 0 on Br ; Therefore,

Z (p1 − cr p0 ) dx ≥ 0,

(p1 − cr p0 ) dx ≤ 0.

Br \S

S\Br

Subtracting the second inequality from the first gives Z Z (p1 − cr p0 ) dx ≥ (p1 − cr p0 ) dx. Br

Expanding both sides, P1 (Br ) − cr P0 (Br ) ≥ P1 (S) − cr P0 (S). Since P1 (Br ) = P1 (S) = r, it holds that cr P0 (Br ) ≤ cr P0 (S). Because r ∈ (0, 1) and Lη∗ (X) > 0, we have cr > 0. Therefore we conclude P0 (Br ) ≤ P0 (S). So at each fixed recall level r, the likelihood-ratio threshold set Br has the smallest falsepositive rate among all measurable decision sets with that recall. We can then show that, at each recall level, the precision of any score is bounded by the precision of Lη∗ . Now fix any score s. Since s(X1 ) has a continuous CDF under P1 , for each r ∈ (0, 1) there exists a threshold tr (s) such that P1 s(X) ≥ tr (s) = r. Define Sr (s) := {x : s(x) ≥ tr (s)}. Then P1 (Sr (s)) = r. By the preceding argument, among all measurable sets with P1 (·) = r, the set Br minimizes the false-positive rate. Hence P0 Sr (s) ≥ P0 (Br ). At recall r, the precision of s and the precision of the likelihood-ratio score are Prec∗s (r) =

π1 r , π1 r + π0 P0 (Sr (s))

Prec∗Lη∗ (r) =

π1 r . π1 r + π0 P0 (Br )

Since P0 (Sr (s)) ≥ P0 (Br ), we have Prec∗s (r) ≤ Prec∗Lη∗ (r)

for every r ∈ (0, 1).

Thus, the precision–recall curve of any admissible score is pointwise dominated, as a function of recall, by that of the likelihood ratio. Finally, integrating the pointwise bound over r ∈ [0, 1], we obtain Z 1 Z 1 ∗ AUPRC(s) = Precs (r) dr ≤ Prec∗Lη∗ (r) dr = AUPRC(Lη∗ ) = AUPRC(Λη∗ ). 0

Optimality for Best-Threshold Balanced Accuracy: First, we rewrite balanced accuracy in set form. Let S ⊆ X beRany measurable set. By definition, BA(S) = 12 P1 (S) + P0 (S c ) . Using densities, P1 (S) = S p1 (x) dx, P0 (S c ) = R 1 − S p0 (x) dx. Hence Z Z Z 1 1 1 p1 (x) dx + 1 − p0 (x) dx = + p1 (x) − p0 (x) dx. BA(S) = 2 2 2 S S S Therefore, for a thresholded score, 1 1 BA(s, τ ) = BA(Sτ (s)) = + 2 2

p1 (x) − p0 (x) dx,

Sτ (s)

where Sτ (s) := {x : s(x) ≥ τ }. Next we show that the R Bayes set maximizes balanced accuracy over all measurable sets. 1 1 We have BA(S) = 2 + 2 S (p1 − p0 ). To maximize this expression over measurable sets S, the maximizing set includes exactly those x for which p1 (x) − p0 (x) ≥ 0. Thus the optimal set is B ∗ := {x : p1 (x) ≥ p0 (x)}. Equivalently, p1 (x) ≥ p0 (x) ⇐⇒

p1 (x) ≥ 1 ⇐⇒ Lη∗ (x) ≥ 1, p0 (x)

so B ∗ = {x : Lη∗ (x) ≥ 1}. Now let S be any measurable set. Then Z Z 1 1 ∗ BA(B ) − BA(S) = (p1 − p0 ) dx − (p1 − p0 ) dx. 2 B∗ 2 S Splitting the difference into the two set differences gives Z Z 1 1 ∗ BA(B ) − BA(S) = (p1 − p0 ) dx − (p1 − p0 ) dx. 2 B ∗ \S 2 S\B ∗ On B ∗ , we have p1 − p0 ≥ 0. On S \ B ∗ ⊆ (B ∗ )c , we have p1 − p0 < 0. Therefore, Z Z 1 1 ∗ BA(B ) − BA(S) = |p1 − p0 | dx + |p1 − p0 | dx. 2 B ∗ \S 2 S\B ∗ Hence

1 BA(B ) − BA(S) = 2 ∗

Z |p1 (x) − p0 (x)| dx ≥ 0. B ∗ △S

Thus B ∗ maximizes balanced accuracy over all measurable decision sets. Let s be any measurable score. For every threshold τ , BA(s, τ ) = BA(Sτ (s)). Since ∗ B maximizes balanced accuracy over all measurable sets, BA(s, τ ) ≤ BA(B ∗ ), for every τ . Taking the supremum over τ yields sup BA(s, τ ) ≤ BA(B ∗ ). τ ∈R

Also, taking the likelihood ratio itself as the score, BA(B ∗ ) = BA Lη∗ , 1) ≤ sup BA(Lη∗ , τ ). τ ∈R

On the other hand, every threshold set of Lη∗ is a measurable set, so it also gives BA(Lη∗ , τ ) ≤ BA(B ∗ )

for every τ.

Taking the supremum over τ , sup BA(Lη∗ , τ ) ≤ BA(B ∗ ). τ ∈R

Combining the two inequalities, sup BA(Lη∗ , τ ) = BA(B ∗ ).

(S31)

τ ∈R

Therefore, this proves the claim for balanced accuracy. Optimality for Best-Threshold F1 Score: We first rewrite F1 as a function of recall and false-positive rate. For any measurable 2π1 r . Define set S, define r := P1 (S), q := P0 (S). Then F1 (S) = π1 (1+r)+π 0q G(r, q) :=

2π1 r , π1 (1 + r) + π0 q

(r, q) ∈ [0, 1]2 .

Then F1 (S) = G(P1 (S), P0 (S)). The partial derivatives of G are ∂G 2π0 π1 r =− 2 ≤ 0. ∂q π1 (1 + r) + π0 q

2π1 (π1 + π0 q) ∂G = 2 > 0, ∂r π1 (1 + r) + π0 q

Thus F1 is increasing in recall r and decreasing in false-positive rate q. Therefore, among sets with the same recall, the one with smaller false-positive rate has at least as large F1 . Next we show that, for each fixed recall level, a likelihood-ratio threshold minimizes false-positive rate. Fix r ∈ (0, 1). Since Lη∗ (X1 ) has a continuous distribution under P1 , there exists a threshold cr such that P1 (Lη∗ (X) ≥ cr ) = r. Define Br := {x : Lη∗ (x) ≥ cr }. Then P1 (Br ) = r. We claim that Br minimizes P0 (S) among all measurable sets S satisfying P1 (S) = r. Let S be any measurable set with P1 (S) = r. On Br , we have Lη∗ (x) ≥ cr , and hence p1 (x) − cr p0 (x) ≥ 0. On Brc , we have Lη∗ (x) < cr , and hence p1 (x) − cr p0 (x) ≤ 0. Therefore, Z

Z (p1 − cr p0 ) dx ≥ 0,

(p1 − cr p0 ) dx ≤ 0.

Br \S

S\Br

It follows by subtraction that Z

Z (p1 − cr p0 ) dx ≥

(p1 − cr p0 ) dx. S

Expanding both sides gives P1 (Br ) − cr P0 (Br ) ≥ P1 (S) − cr P0 (S). Since P1 (Br ) = P1 (S) = r, this becomes r − cr P0 (Br ) ≥ r − cr P0 (S). Because r ∈ (0, 1), the corresponding threshold satisfies cr > 0. Therefore, P0 (Br ) ≤ P0 (S). Thus, among all measurable sets with recall r, the likelihood-ratio threshold set Br has the smallest false-positive rate. Next, we show that every measurable set is F1 -dominated by likelihood-ratio threshold sets. Let S ⊆ X be any measurable set and set r := P1 (S). If r = 0, then F1 (S) = 0, so S cannot improve over the supremum of the likelihood-ratio threshold family. Now suppose r ∈ (0, 1). There exists a likelihood-ratio threshold set Br such that P1 (Br ) = r,

P0 (Br ) ≤ P0 (S).

Using the monotonicity of G, F1 (Br ) = G(P1 (Br ), P0 (Br )) = G(r, P0 (Br )) ≥ G(r, P0 (S)) = F1 (S). It remains to consider the case r = 1. Let rn ↑ 1 with rn ∈ (0, 1). For each n, let Brn := {x : Lη∗ (x) ≥ crn } satisfy P1 (Brn ) = rn . Since P1 (S) = 1, we have P1 (S ∩ Brn ) = P1 (Brn ) = rn . Also, we know that Brn minimizes P0 among all measurable sets with P1 -mass rn , so P0 (Brn ) ≤ P0 (S ∩ Brn ) ≤ P0 (S). Therefore, F1 (Brn ) = G(rn , P0 (Brn )) ≥ G(rn , P0 (S)). Letting n → ∞, continuity of G gives sup F1 ({Lη∗ ≥ c}) ≥ lim sup F1 (Brn ) ≥ G(1, P0 (S)) = F1 (S). c

n→∞

Hence every measurable set S is dominated, in F1 value, by the likelihood-ratio threshold family in the sense that F1 (S) ≤ sup F1 ({Lη∗ ≥ c}). c

Taking the supremum over all measurable B ⊆ X gives sup F1 (B) ≤ sup F1 ({Lη∗ ≥ c}). c

B⊆X

The reverse inequality is immediate since every set {Lη∗ ≥ c} is measurable. Hence, sup F1 (B) = sup F1 ({Lη∗ ≥ c}) = sup F1 (Λη∗ , τ ). τ ∈R

B⊆X

Now let s be any measurable score and let τ ∈ R. Its threshold set Sτ (s) = {x : s(x) ≥ τ } is measurable, so F1 (s, τ ) = F1 (Sτ (s)) ≤ sup F1 ({Lη∗ ≥ c}) = sup F1 (Lη∗ , τ ). τ ∈R

Taking the supremum over τ gives sup F1 (s, τ ) ≤ sup F1 (Lη∗ , τ ) = sup F1 (Λη∗ , τ ) = sup F1 (B). τ ∈R

τ ∈R

B⊆X

This proves the lemma. ∗ ∥, first note that by the Proof of Lemma S1. For the empirical estimation error ∥θ̂raw − θraw boundedness condition on the centered individual Hessians and the matrix Bernstein inequality, for sufficiently large n0 + n1 , with probability at least 1 − δ/7, ∗ ∗ ∇2 R̂raw (θraw ) − ∇2 Rraw (θraw )

≤ op

λ . 4

Indeed, by the definition of R̂raw and Rraw , ∗ ∗ ∇2 R̂raw (θraw ) − ∇2 Rraw (θraw ) n 0 n o X 1 (0) ∗ ∗ = ∇2 ℓ(θraw ; xi , 0) − EP0 ∇2 ℓ(θraw ; X, 0) n0 + n1 i=1 n1 n o X 1 (1) 2 ∗ 2 ∗ + ∇ ℓ(θraw ; xi , 1) − EP1 ∇ ℓ(θraw ; X, 1) . n0 + n1 i=1

The matrices inside the two sums are independent, centered, and self-adjoint. By the bounded centered-Hessian condition, each summand after multiplication by 1/(n0 + n1 ) has operator norm at most BH /(n0 + n1 ) almost surely. Furthermore, their matrix variance proxy is bounded by 2 2 (n0 + n1 )BH BH = . (n0 + n1 )2 n0 + n1 88

Therefore, the self-adjoint matrix Bernstein inequality (e.g. Theorem 1.4 of Tropp (2012)) implies that, for every t > 0, (n0 + n1 )t2 2 ∗ 2 ∗ ≥ t ≤ 2d exp − 2 . P ∇ R̂raw (θraw ) − ∇ Rraw (θraw ) op 2BH + 23 BH t Taking t = λ/4 gives λ (n0 + n1 )λ2 2 ∗ 2 ∗ P ∇ R̂raw (θraw ) − ∇ Rraw (θraw ) ≥ . ≤ 2d exp − 2 4 op 32BH + 38 BH λ Consequently, if

2 32BH 8BH + 2 λ 3λ

log

14d δ

∗ ∗ ∇2 R̂raw (θraw ) − ∇2 Rraw (θraw )

≤

n0 + n1 ≥

then, with probability at least 1 − δ/7,

λ . 4

∗ On this event, for every θ satisfying ∥θ − θraw ∥ ≤ r, the local Lipschitz condition on the individual Hessians gives ∗ ∇2 R̂raw (θ) − ∇2 R̂raw (θraw )

∗ ≤ LH ∥θ − θraw ∥ ≤ LH r ≤

λ . 4

∗ Together with ∇2 Rraw (θraw ) ⪰ λI, this yields ∗ ∗ ∗ ∇2 R̂raw (θ) ⪰ ∇2 Rraw (θraw ) − ∇2 R̂raw (θraw ) − ∇2 Rraw (θraw )

I op

∗ I − ∇2 R̂raw (θ) − ∇2 R̂raw (θraw ) op λ λ λ ⪰ λ− − I= I 4 4 2 ∗ ∥ ≤ r. for all θ satisfying ∥θ − θraw We next show that θ̂raw lies in this local neighborhood. Assume temporarily that ∗ ) ≤ ∇R̂raw (θraw

λr ; 4

(S32)

this condition will be verified below by the gradient concentration bound. For every θ ∗ satisfying ∥θ − θraw ∥ = r, the fundamental theorem of calculus gives ∗ (θ − θraw )⊤ ∇R̂raw (θ) ∗ ∗ = (θ − θraw )⊤ ∇R̂raw (θraw )+

Z 1

∗ ∗ ∗ ∗ (θ − θraw )⊤ ∇2 R̂raw θraw + t(θ − θraw ) (θ − θraw ) dt

0 ∗ ≥ −r ∇R̂raw (θraw ) +

λr λr2 ≥ > 0. 2 4 89

Since R̂raw is convex, the preceding outward-gradient condition implies that ∗ ∥θ̂raw − θraw ∥ ≤ r. ∗ Indeed, suppose to the contrary that ∥θ̂raw − θraw ∥ > r, and let r ∗ ∗ θ̂raw − θraw . θ = θraw + ∗ ∥ ∥θ̂raw − θraw ∗ ∥ = r and Then ∥θ − θraw

θ̂raw − θ =

! ∗ ∥ ∥θ̂raw − θraw ∗ − 1 (θ − θraw ), r

where the coefficient is strictly positive. Since θ̂raw minimizes the convex function R̂raw , 0 ≥ R̂raw (θ̂raw ) − R̂raw (θ) ≥ ∇R̂raw (θ)⊤ (θ̂raw − θ). On the other hand, the outward-gradient condition gives ! ∗ ∥ ∥ θ̂ − θ raw raw ∗ − 1 ∇R̂raw (θ)⊤ (θ − θraw ) > 0, ∇R̂raw (θ)⊤ (θ̂raw − θ) = r which is a contradiction. Therefore, ∗ ∥θ̂raw − θraw ∥ ≤ r. ∗ and θ̂raw is contained in the region on Consequently, the entire line segment joining θraw which λ ∇2 R̂raw (θ) ⪰ I. 2

Since ∇R̂raw (θ̂raw ) = 0, another application of the fundamental theorem of calculus yields Z 1 ∗ ∗ ∗ ∗ ∇2 R̂raw θraw + t(θ̂raw − θraw ) (θ̂raw − θraw ) dt. −∇R̂raw (θraw ) = 0 ∗ Taking the inner product with θ̂raw − θraw , we obtain ∗ ∗ − (θ̂raw − θraw )⊤ ∇R̂raw (θraw ) Z 1 ∗ ∗ ∗ ∗ = (θ̂raw − θraw )⊤ ∇2 R̂raw θraw + t(θ̂raw − θraw ) (θ̂raw − θraw ) dt 0 2 λ ∗ ≥ θ̂raw − θraw . 2

On the other hand, by the Cauchy–Schwarz inequality, ∗ ∗ ∗ −(θ̂raw − θraw )⊤ ∇R̂raw (θraw ) ≤ θ̂raw − θraw

∗ ∇R̂raw (θraw ) .

Therefore, ∗ θ̂raw − θraw ≤

2 ∗ ∇R̂raw (θraw ) . λ

∗ ) to verify the previous assumption and obtain Next we give a bound for ∇R̂raw (θraw a convergence bound for the parameter. ∗ ∗ By optimality, E∇R̂raw (θraw ) = ∇Rraw (θraw ) = 0. Therefore,

∗ ∇R̂raw (θraw )

n0 n1 X X 1 1 (0) (1) ∗ ∗ ∗ ∇ℓ(θraw ; xi , 0) + ∇ℓ(θraw , xi , 1) − E∇R̂raw (θraw ) = n0 + n1 i=1 n0 + n1 i=1

n0 h i n0 1 X (0) (0) ∗ ∗ ∇ℓ(θraw ; xi , 0) − EP0 ∇ℓ(θraw ; xi , 0) ≤ n0 + n1 n0 i=1

n1 i h n1 1 X (1) (1) ∗ ∗ , xi , 1) ∇ℓ(θraw , xi , 1) − EP1 ∇ℓ(θraw n0 + n1 n1 i=1

(S33)

By union bound and Hoeffding’s inequality, for fixed θ, P

n0 1 X

n0 i=1

(0)

∗ ∇ℓ(θraw ; xi , 0) − EP0

! i (0) ∗ ∇ℓ(θraw ; xi , 0) > t

! ii h t (0) (0) ∗ ∗ ≤ P ∃i ∈ |d|, s.t. >√ ; xi , 0) ∇ℓ(θraw ; xi , 0) − EP0 ∇ℓ(θraw n0 i=1 i d i " ! # 2 n0 d ii h h X 1 X t n0 t (0) (0) ∗ ∗ ≤ P ≤ 2d exp − >√ , ∇ℓ(θraw ; xi , 0) − EP0 ∇ℓ(θraw ; xi , 0) n0 i=1 2dB 2 i d i=1 i "

n0 1 X

where B > 0 is the constant from the bounded-support assumption. Taking s 2B 2 d log(2d/δ) t= , n0 we have with probability at least 1 − δ, n0 1 X

n0 i=1

s (0)

∗ ∇ℓ(θraw ; xi , 0) − EP0

i (0) ∗ ∇ℓ(θraw ; xi , 0) ≤

2B 2 d log(2d/δ) . n0

By essentially the same procedure, we have with probability at least 1 − δ, s n1 h i X 2B 2 d log(2d/δ) 1 (1) (1) ∗ ∗ ∇ℓ(θraw ; xi , 1) − EP1 ∇ℓ(θraw ; xi , 1) ≤ . n1 i=1 n1

(S34)

(S35)

Combining the bounded-Hessian event and equations (S33), (S34) and (S35) yields that with probability at least 1 − 37 δ, s √ p √ n + n 4B 2 d log(14d/δ) 0 1 ∗ ∇R̂raw (θraw ) ≤ 2B 2 d log(14d/δ) ≤ . n0 + n 1 n0 + n1 Therefore, equation (S32) is verified for large enough sample size. Furthermore, with probability at least 1 − 73 δ, it holds by absorbing constants into some constant c > 0 that s c B 2 d log(14d/δ) ∗ . (S36) θ̂raw − θraw ≤ λ n0 + n 1 The same argument gives ∗ θ̂aug − θaug ≤

2 ∗ ∇R̂aug (θaug ) . λ

Also, ∗ ∇R̂aug (θaug )

n0 h i n0 1 X (0) (0) ∗ ∗ ≤ ∇ℓ(θaug ; xi , 0) − EP0 ∇ℓ(θaug ; xi , 0) n0 + n1 + ñ n0 i=1

n1 h i 1 X n1 (1) (1) ∗ ∗ ∇ℓ(θaug , xi , 1) − EP1 ∇ℓ(θaug , xi , 1) + n0 + n1 + ñ n1 i=1 ñ 1X ñ ∗ ∗ ∇ℓ(θaug ; x̃i , 1) − EPsyn ∇ℓ(θaug + ; x̃i , 1) . n0 + n1 + ñ ñ i=1

Similarly, by a union bound and Hoeffding’s inequality, and combining with the boundedHessian event, with probability at least 1 − 74 δ, s √ √ √ p n + n + ñ 6B 2 d log(14d/δ) 0 1 ∗ ∇R̂aug (θaug ) ≤ 2B 2 d log(14d/δ) ≤ . n0 + n1 + ñ n0 + n1 + ñ That is, after absorbing the constants, ∗ θ̂aug − θaug ≤

c λ

B 2 d log(14d/δ) . n0 + n1 + ñ

(S37)

Finally, combining equations (S36) and (S37), we have for some constant c > 0, with probability at least 1 − δ, the following holds simultaneously: s s 2 c B d log(14d/δ) c B 2 d log(14d/δ) ∗ ∗ θ̂raw − θraw ≤ , θaug − θ̂aug ≤ . λ n0 + n 1 λ n0 + n1 + ñ The individual bounds hold by adjusting the probability parameter δ. 92

Proof of Lemma S2. For a differentiable function Rρ (θ) with minimizer θρ∗ satisfying µ ∗ 2 Rρ (θρ∗ ) ≥ Rρ (θ) + ∇Rρ (θ)T (θρ∗ − θ) + θρ − θ , 2 by assumption, we have µ Rρ (θ) − Rρ (θρ∗ ) ≤ ∇Rρ (θ)⊤ (θ − θρ∗ ) − ∥θ − θρ∗ ∥2 2 1 µ µ 1 ≤ ∥∇Rρ (θ)∥2 + ∥θ − θρ∗ ∥2 − ∥θ − θρ∗ ∥2 = ∥∇Rρ (θ)∥2 , 2µ 2 2 2µ √ where the second inequality follows from the fact that 0 ≤ ∥ √1µ ∇Rρ (θ) − µ(θ − θρ∗ )∥2 . ∗ Taking θaug , we have ∗ Rρ (θaug ) − Rρ (θρ∗ ) ≤

1 ∗ ∥∇Rρ (θaug )∥2 . 2µ

Recalling the definitions of Rρ (θ) and Raug (θ), we have ñ EPsyn ℓ(θ; x, 1) − EP1 ℓ(θ; x, 1) . Raug (θ) = Rρ (θ) + n0 + n1 + ñ ∗ , by the first order Taking the gradient with respect to the parameter and evaluating at θaug optimality, we have ñ ∗ ∗ ∗ ∗ 0 = ∇Raug (θaug ) = ∇Rρ (θaug )+ ; x, 1) − EP1 ∇ℓ(θaug ; x, 1) . EPsyn ∇ℓ(θaug n0 + n1 + ñ That is ñ ∗ ∗ ∗ ∥∇Rρ (θaug )∥ = EPsyn ∇ℓ(θaug ; x, 1) − EP1 ∇ℓ(θaug ; x, 1) n0 + n1 + ñ By Kantorovich-Rubinstein duality, for two distributions P and Q, W1 (P, Q) =

sup

∥EP [ϕ] − EQ [ϕ]∥ .

ϕ:Lip(ϕ)≤1

Define ϕ := ∇ℓ/Lg . Then Lip(ϕ) ≤ 1, hence, ∗ ∗ ; x, 1) − EP1 ∇ℓ(θaug ; x, 1) ≤ Lg W1 (Psyn , P1 ) ≤ Lg ϵsyn . EPsyn ∇ℓ(θaug

Combining this with the quadratic-growth assumption near the minimizer, 1 1 2 ∗ ∗ ∗ Rρ (θaug ) − Rρ (θρ∗ ) ≤ ∥∇Rρ (θaug )∥2 . θaug − θρ∗ ≤ Lρ 2µLρ Thus, we have s ∗ θaug − θρ∗ ≤

1 ñ ∗ ∗ EPsyn ∇ℓ(θaug ; x, 1) − EP1 ∇ℓ(θaug ; x, 1) 2µLρ n0 + n1 + ñ Lg ñ ≤p ϵsyn . 2µLρ n0 + n1 + ñ

Record · ID 307004 · SHA-256 35f0d1699f533aa8
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.