A Statistical Theory of Overfitting for Imbalanced Classification
Authors: Jingyang Lyu
Kangjie Zhou
Yiqiao Zhong
Venue: ICLR 2026 Poster (2026)
Keywords: Imbalanced classification
overfitting
margin
logistic regression
support vector machine
overparametrization
calibration
Primary area: learning theory
TL;DR: Overfitting in high-dimensional imbalanced classification arises from truncation/skewing effects on the logit distribution.

Abstract: Classification with imbalanced data is a common challenge in machine learning, where minority classes form only a small fraction of the training samples. Classical theory, relying on large-sample asymptotics and finite-sample corrections, is often ineffective in high dimensions, leaving many overfitting phenomena unexplained. In this paper, we develop a statistical theory for high-dimensional imbalanced linear classification, showing that dimensionality induces truncation or skewing effects on the logit distribution, which we characterize via a variational problem. For linearly separable Gaussian mixtures, logits follow $\\mathsf{N}(0,1)$ on the test set but converge to $\\max\\{\\kappa,\\mathsf{N}(0,1)\\}$ on the training set---a pervasive phenomenon we confirm on tabular, image, and text data. 
This phenomenon explains why the minority class is more severely affected by overfitting. We further show that margin rebalancing mitigates minority accuracy drop and provide theoretical insights into calibration and uncertainty quantification.

Published as a conference paper at ICLR 2026
A STATISTICAL THEORY OF OVERFITTING FOR IMBALANCED CLASSIFICATION
Jingyang Lyu', Kangjie Zhou?, Yiqiao Zhong'
Department of Statistics, University of Wisconsin-Madison WI 53706, USA
2 Department of Statistics, Columbia University, New York, NY 10027, USA {jlyu55, yiqlao. chong]ewisce edu, k=2326ecolumbiaa
ABSTRACT
Classification with imbalanced data is a common challenge in machine learning. where minority classes form only small fraction of the training samples. Clas- sical theory, relying on large-sample asymptotics and finite-sample corrections, is often ineffective in high dimensions, leaving many overfitting phenomena unex- plained. In this paper, we develop statistical theory for high-dimensional im- balanced linear classification, showing that dimensionality induces truncation skewing effects on the logit distribution, which we characterize via variational problem. For linearly separable Gaussian mixtures, logits follow N(O, 1) on the test set but converge to max N(O, 1)} on the training set pervasive phe- nomenon we confirm on tabular, image, and text data. This phenomenon explains why the minority class is more severely affected by overfitting. We further show that margin rebalancing mitigates minority accuracy drop and provide theoretical insights into calibration and uncertainty quantification.
INTRODUCTION
Classification tasks are ubiquitous in statistics and machine learning. In many practical applications, training data are often imbalanced, meaning that some classes (minority classes) contain substan- tially fewer samples than others. In binary classification, particularly, {ari, yı) | ~ Ps., with features æ; E Rd and binary labels yı E [+1]. Denote by Pz (resp. Pg) the marginal distribution of (resp. y)), and the expected fractions of the two classes by
observe training data
+ = P(y = +1),
π- :=
:=:Pa(y Ply -1)
We say that the data set is imbalanced if T < π Imbalanced classification is common in applica-
tions where the minority class represents rare diseases, rare events, anomalies. or underrepresented
groups (Kubat et al. 1998; King & Zeng 2001 Weiss & Provost 2003 Chandola et al. 2009 Ngai al. 2011
Litjens al. 2017 Tschandl et al. 2018: Buolamwini & Gebru 2018)
We focus on classifiers which take the form of a + (1(f(x) > 0} 1, with f(x) (ac, B) + Sn- This simple form widely used in statistics and deep learning. Particularly for image and text data, the last classification layer of a deep neural network (DNN) usually takes this form (e.g.. softmax), where a; is the extracted feature in high dimensions.
Challenge 1: figg--dimensiona features from pretrained neural networks In low dimensions (d < n), prediction and estimation are well understood. But when comparable n, classical theory becomes inaccurate, motivating refined asymptotic analyses of high-dimensional learning.
Regarding parameter estimation, line of work (Dobriban & Wager 2018 Sur et al., 2019 Sur &
Candès 2019 Candès & Sur 2020; Montanari et al. 2023) has studied logistic regression under the proportional regime n + 8. As d increases (i.c., decreases), the estimation error of the maximum likelihood estimator (MLE) 33 grows, and classical likelihood tests require modification.
Regarding generalization, high dimensionality usually leads to gap between the training and test errors. Recent work double descent (Belkin et al. 2019) shows that in overparameterized models, gradient descent induces implicit regularization, leading to benign overfitting (Bartlett et al.) 2020).
Without loss of generality, we assume that the minority class is assigned the label +1.

---

Published as a conference paper at ICLR 2026
Finally, the distribution of logits is highly valuable for feature visualization and interpretation, yet little theory exists. Practical examples include linear probing. a common approach for interpreting the hidden states (or activations) (Kornblith et al., 2019 He et al. |020 Kumar et al. 2022). and pro- jection pursuit, which explores data via din-sinnnlional projections, with recent theory developed in high dimensions (Bickel et al. 2018 Montanari & Zhou 2022).
Challenge 2: Class imbalance in downstream tasks In downstream tasks, the base neural net- work is typically frozen, and only the last layer is retrained-also known as linear probing. In such classification settings, data imbalance poses key challenges: MLE may be unreliable, label shifts in the minority proportion # can degrade performance, and misclassifying minority samples is often more costly (He & Garcial 2009). Common remedies include adjusting decision boundaries, reweighting losses, and sub-/over-sampling (King Zeng 2001 Chawla et al. 2002).
Overfitting in high dimensions further exacerbates imbalance, as large deep models often memorize rather than generalize to minority samples (Sagawa al. 2020). Although various remedies have been proposed (Huang et al.] 2016] Cao et al. 2019 Liu et al. 2019) Khan et al. 2019). they remain ad hoc and offer little guidance on hyperparameter choice or feature interpretation.
Imbalanced classification. Classical work on logistic regression shows that large-sample asymp- totics fails with small samples, motivating bias corrections (Anderson & Richardson 1979 McCul-
lagh & Nelder I983; Schaafer 1983). Under label shift, intercept correction and upweighting are proposed (Xie & Manski 1989 King & Zeng 200T: Loffredo et al.] 2024 Pezzicoli et al. [025]] Sarao Mannelli et al.) (025). For kernel and tree-based methods, resampling, and synthetic data
generation are common (Chawla et al.] 2002 He et al.] 2008 He & Garcia (009), yet these are
ineffective for separable data (Cao et al. 2019) and do not address high-dimensional overfitting.
Margin-based methods. Margin is central to classification methods such as SVM. For imbalanced settings, promoting unequal margins is proposed for the perceptron algorithm (Li et al.
2002), SVM
(Li ct al. 2005), , and more recently deep networks (Huang et al. 2016; Cao et al.
2019 Khan
al. 2019 Liu et al. 2019). Theoretical work has established margin-
generalization bounds
[Bartlett] 1996 Bartlett et al. 1998; Bartlett & Mendelson 2002 Koltchinski & Panchenko 2002]
losses (Cao al. 2019). However, the margin- dependent bounds are agnostic to data distributions and may be excessively conservative.
Bartlett et al. 2017), motivating
High-dimensional asymptotics. Classical asymptotics in low dimensions is inaccurate (El Karoui
et al. 2013; Donoho & Montanari 2016). A recent line of work develops high sigh-dimensional classi-
fication theory (Dobriban & Wager, 2018; Sur & Candès) 2019 Salehi et al.) |019] [Sur et al. 2019
Candès & Sur, 2020 Mignacco al. 2020 Kini et al.) 2021 Loureiro al. |021] Deng et al.
2022 Montanari et al. 2023] Dandi et al. 2023] Montanari et al. 2024), refining Table mainly
via Gordon's theorem (Gordon 1985 Thhrmmpulldhh didi et al. 2015). Closest is (Montanari & Zhou
2022]. which analyzes projection pursuit and low- oiw-dimessional asymptotics, but none characterize the impact of class imbalance on overfitting or calibration.
Table 1: Qualitative comparison between low/high dimensions for binary classification, where lin- ear classifier T(x) (1( > 0}-1 with f())= - ( is trained on ((x1,))) 1dd Here, the logits (f(z,)
Pa.gr
((x,) ) are obtained by evaluating f on the training set.
Low dimensions
High dimensions
Parameter estimation
< 1
||S||
||||||
[ <
Generalization
Train error RO Test error
Train error
Test error
Distribution of logits
1D projection of Pa
Skewed/distorted 1D projection of Pa
Our contribution We identify two key gaps in the existing literature. First, the reason why over- fitting is more severe in minority classes, though consistently observed, remains unclear. Second, there is no comprehensive analysis of how key nal strength- affect performance metrics like test accuracy and uncertainty quantification. The goal of this paper is develop statistical theory that addresses these gaps.
such as dimensionality, imbalance, and sig-
We characterize overfitting via the discrepancy between logit distributions on training and test sets, and show that dimensionality induces truncation effect in training logits. (Section
2

---

Published as a conference paper at ICLR 2026
We derive the optimal hyperparameter for margin rebalancing mitigate class imbalance, and show that test error decreases with key model parameters- tte imbalance ratio, signal strength (class center separation), and aspect ratio, see Table 2 (Section()
We further show that parameter changes that raise test error could simultaneously worsen model calibration, revealing an adverse effect of overfitting, see Table ?
(Section
Table 2: Monotonicity of test errors and miscalibration metrics on model parameters.
Erri, Err-, Errg
CalErr
MSE*
ConfErr' *
imbalance ratio
4 (Prop. 3.1
(Thm.
(Claim D.10
signal strength || f aspect ratio n/d 8
4 (Prop.
3.1
1 (Claim D.10
(Thm.
(Prop. 3.1 $ (Claim D.10
(Thm.
4.1
+ (Prop. D.9
Building on theoretical tools from high-dimensional statistics, our analysis focuses on a stylized model. Suppose the i.i.d training data {(x y:) are generated from a two-component Gaussian mixture model (2-GMM):
(1) where 1 Rdd is the signal vector. Under this model, the Bayes-optimal classifier has the form y (x) (2, + Bu 0) - where B3/ p.. See Section[5 extensions of Eq. ( We study the behavior of two standard approaches for binary classification: (a slightly generalized version of) logistic regression and support vector machines (SVMs). Denoting by & R + IR a strictly convex decreasing function, including the logistic function log(1 + +)* as a special case, we solve
P(u = +1)= = P(y = -1) = 1111 x y ~ N(y:tt,
(logistic regression)
minimize 3E3" DRER
Σ (vi((xr ()+
(2a)
(SVM)
maximize BER B0, subject to
Ki
Ve( , (3 + Bo) n. Vie [n].
(2b)
|| S 1.
Both optimization problems convex and yield solutions 3, which are used to predict class labels for a test data point æ based on f(x) = (x,,3) + BB. Namely, the predicted binary label of a
test data point is f(x)- 2 3) + 30 > 0}
We will analyze both classifiers with a focus on the SVM for the following reason. In modern machine learning, it is common for the labeled data (( (:) be linearly separable due to high dimensionality. When data are linearly separable, the hard-margin SVM coincides with the max-margin classifier. is known that the gradient descent iterates of logistic regression converge in direction to the max-margin solution (Soudry et al. 2018 [] Telgarsky 2019), which is known as a form of inductive bias (Neyshabur et 2015). See Appendix C.I for the background. this sense, the two classifiers are closely related.
All experiment details and proofs are provided the appendix. The code for our experiments can Classification iclr
be found at https: //tithub.ttt..t/// ctatthuu.coooo/
2 CHARACTERIZING OVERFITTING VIA EMPIRICAL LOGIT DISTRIBUTION
Explaining why test accuracy drops more for the minority class requires more refined characteri- zation of overfitting. We therefore study the empirical distribution of logits f(x,) = (ax,, (3) + 30- i E [rx] on the training set. Let (I1, vI)...., (æn, Vn.) 3.i.d. Pa..y be training data, and (Ætost Brest) an independent test point. Consider binary classifier Rdd - {+1} based on f Rd + IR that predicts y = +1 [(x)) > and π = otherwise.
Definition 2.1 (Logit and margin). Let (x, E Rd x {+1} be data point. For a binary classifier of the form ((x) = (1(f(z) > 0} 1, we define the logit of as f(x), and the margin of the classifier f (on the training data) as Rn = minjejn) (ax))
The following definitions highlight the logit distribution on both training and test data.
3

---

Published as a conference paper at ICLR 2026
Logit Distribution
Minority ELD
0.7
Takeaway:
Majority ELD
Minority TLD
0.66
Overfitting
"Truncation"
Majority TLD
boundary
maagga
0.4
0.3
(majority)
(minority)
0.0
logit
Figure 1: Empirical logit distribution (ELD) and testing logit distribution (TLD). We train max-margin classifier (namely SVM) f on synthetic data from 2-component Gaussian mixture model. Colors indicate labels ys and rr-axis indicates logits f(x,). ELD for both classes: rectified Gaussian distribution (histogram). TLD for both classes: Gaussian distribution (curve). Over- fitting effect: The density areas below the dotted curves are overlapping in TLD, thus leading to positive test error; however they are "pushed" to respective margin boundaries in ELD, thus leading linear separability and zero training errors.
HIN Aseq Hiub class 5 cluss
CIFAR-10, cluss vs class 4
IMDb, positive negative
ILC00
Misseit BLD
0.038
Majerty ELD
0:56
0.096
0LC2
Mituett
Mayrity TLDD
0.4
Iecaas
0LC2
0.29
Figure 2: ELD and TLD of logistic regression classifier (the last fully-connected layer) for real data. Left: IFNB single-cell RNA-seq dataset (tabular data). Middle: CIFAR-10 10 dataset preprocessed by pretrained ResNet-18 model for feature extraction (image data). Right: IMDb movie review dataset preprocessed by BERT base model (1 (110) for feature extraction (text data).
Definition 2.2 (ELD and TLD). Empirical logit distribution (ELD), or training logit distribution, is defined as the empirical distribution of label-logit pairs based on training data:
Dr = Strain
1
Σ 6
Fimm))
(i.e., the "histogram" of (f(
(3)
1=1
Minority ELD and majority ELD defined respectively as ELD in minority and majority class. Testing logit distribution (TLD) is defined as the distribution of the label-logit pair for a test point:
glest Law (Jrest f( A
Minority TLD and majority TLD are defined respectively as TLD in minority and majority class.
When R > 0. the training set is linearly separable, and f attains 100% training accuracy. In high dimensions this is common, yet test accuracy is typically imperfect; this train/test discrepancy is known overfitring. As logit distribution is more informative than train/test accuracies, we analyze overfitting through ELD/TLD.
Empirical phenomenon the phenomenon; see Fig.1 [
First, we show simple yet representative simulated example to illustrate We generate training data according to 2-GMM in Eq. I1 with n =
25,. is the delta measure supported at point a (Dirac measure).
"Law means the distribution of random variables/vcctors.
4

---

Published as a conference paper at ICLR 2026
10,000, d 4,000, |||| 1.75, and imbalance 0.15, which guarantees linear separabiliity. Training an SVM Eq. (2b) and plotting ELD/TLD by class, we find TLDs are Gaussian, whereas ELDs are the same Gaussians but truncated at the margin-suuch discrepancy characterizes the effect of overfitting in imbalanced classification. The minority (y: = +1) ELDD loses over half its mass by truncation, yielding much lower accuracy than the majority (y/: -1). Formally, such distribution of ELD is called rectified Gaussian (i.e., max Z, K} or min { Z2 k} where Z ~ N(p, ("),
Training Logit
Testing Logit
TrushfilQA, truthful va Gulse
Moority FLD
Majocity ELD
Milueity Mapriity
Mitedity
2nd devetion light (ortlogns))
0.0
2nd devetton logt (orthogeas)
0.0
Migentty
Minerity TL.D
-0.1
-0.4
Majority TLD
Decision bounday
-0.2
-03
-00
-05
-0.5
0.7
-02
0.2
-0.2
dbrction (saas munsin)
dieetion kuil (suzo manda))
Figure 3: ELD and TLD of Llama-3-8B-Instuuct activation probing on TruthfulQA dataset. Left, Middle: Scatter plot on training/testing data for activations (3hth layer, 26th head) of truthful (minority) and false (majority) QA pairs after projection onto the top-2 directions. Marginal distri- butions are shown on the upper and right sides. Right: Marginal ELD and TLD on 1tt direction.
For real-data examples, fine-tune pretrained DNNs by freezing all parameters except for the last classification layer on imbalanced labeled data, effectively using the pretrained network as a feature extractor-22 standard downstream practice (Sharif Razavian et al. 2014 Zhou al. 2016 Howard & Ruder 2018 Radford et al. 2021). We evaluate three representative data modalities; see Fig. 2
1. Tabular data. We use single-cell RNA-seq dataset of peripheral blood mononuclear cells treated with interferon-3 (IFNB) (Kang et al. (0118). with dimension d = 2,000. We choose class 5 (CD4 Naive T cells) and class 4 (CD4 Memory T cells). and subsample an imbalanced training set. Class 4 is the minority class, with imbalance π = 0.2 and sample size n = 953.
2. Image data. We use CIFAR-10 image dataset (Krizhevsky) 2009). The pretrained ResNet-18 model (He et al. 2016 Dadalto 2023) is applied to extract the features of dimension d 512. We randomly choose two classes, for example, class 5 (dog) and class 4 (deer), and subsample an imbalanced training set. Class 4 is the minority class, with π 0.1 and 555.
3. Text data. We use IMDb movie review dataset (Maas al. 2011 perform binary sentiment classification. The BERT base language model (110M) (Devlin 2018) is applied to extract the features of dimension d 768. An imbalanced training set is sampled, where negative reviews belong to the minority class, with π = 0.02 and n = 6,377.
Empirically, we observe pervasive ELD regularity: for separable data, the ELD of each class can be fitted by rectified Gaussian, and such distributional truncation solely explains overfitting in high dimensions. The minority class also suffers more from truncation effect as test accuracy is worse.
Further, we extend our analysis from last-layer features to intermediate-layer hidden states of large (AI@ Meta 2024) TruthfulQA (Lin) et al. 2021), following the experiment in (Li et al. 2023). For each QA pair we concatenate the question and answer, extract tast-token head activations, and build probing dataset for every head and layer. We fit a linear probe (Eq. (2a). 1st direction) and an orthogonal probe (2nd direction,
language models (LLMs), by applying Llama-3-8B-Instteee
minimizing the same objective subject to orthogonality). See details in Appendix B.2 Fig. shows the joint and marginal logit distributions along the two directions. Unlike (Li ct al. 2023), we imbalanced probing set (π = 0.04, n = 690; true answers are minority) and compare ELD (Fig left) with TLD (middle). We observe truncation in the first direction and distortion in the second, indicating overfitting in LLM probing under class imbalance and offering potential guidance toward understanding unintended memorization in LLMs.
As our theoretical insights below reveal, this truncation phenomenon arises because both classes share common "overfitting budget", which disproportionately shifts the minority margin boundary.
5

---

Published as a conference paper at ICLR 2026
Theoretical foundation We highlight summary of result for the separable case here and defers the non-separable case to Appendix D.I. Consider the asymptotic regime n/d d - where 5 (0, oc) is called the limiting aspect ratio. Recall that (3, Sp. R) are the trained parameters, in Eq. (b). where Ti is the margin of classifier 7(x) 21 (f (() > 0} - with f(x:) = (ac (3 + 80-
Denote T ?
8
the cosine similarity between the slope and the optimal direction μ..
On a test point (Dtest: Blest) ~ Pa.y. we consider the minority error and majority error
Err+ = PP (f(ztes) $ Vtest = +1). Err- := (f(tess) Ytestt = =1).
(4)
Theorem 2.1 helow characterizes the precise asymptotic behavior, namely the limiting distribution of and logits in the proportional regime as n/d
Theorem 2.1 (Separable data, informal version of Theorem D.I.. Consider 2-GMM with asymp- totics n/d- + 5 E (0, oo) as n, d + cc. There is critical threshold 6 55(T,, [ such that when 8 < 8, the following holds as n, + Do:
(a) Parameter convergence. The training set is linearly separable with high probability, and
(P, (0.Bo.8) R) P (p", , ,,,,k") k)),
where (p",8b,k") is the unique solution to the following variational problem
maximize (E-...1,BERR.<0... K; s.t. p +
P LEL 1/0,
(5)
where L is the space of square integrable random variables in the probability space F,, P), (Y, G) Pg x N(O, 1), and & is an unknown random variable (functional) to be optimized.
As consequence, the limits minority/majority errors are
ErT+ - & (-p" || -b), Err_ - de (-p" ||||| 96)
where denotes the cumulative distribution function of standard Gaussian.
(b) ELD convergence. The empirical (training) logit distribution Trrain has limit v yarain in the sense
W2 W2(Ptraia
V. train) L 0,
where Arain == Law (Y, Y maxfs", ,p" 11 + G G
TLD convergence. The testing logit distribution Drest has limit best in the sense that
2
pest
w test
where ytest Law (Y, (p" ||14|22 G+YBB))
Intuition and proof techniques
In Eq. 5), p is the cosine similarity between ,3 and μl, and the term plll G + Y 30 yields the projection of the input distribution a ~ π N(j,, Ia) + (1 T) N - Ia) onto B:
y ((x, B) + Bo) = y (yp + N(O, L2), + yBu
(recall || 1)
|| || + (N.O, + y = |ll| +G+YB.
|
N(0,1)
Intuitively, the remaining dimensions are not relevant and instead provide room for overfitting, which captured by the "free" random variable &.
The main idea is rewrite the linear classifier in Eq. 2b as min-max formulation involving
min max GXG + (A,c)), where G Radd with i.i.d. N(0, 1) entries.
Thrampoulidis et al. 2015) allows us to replace the bilinear term A GG with | (A, N(O. + [B, N(O, La)), so the min-max problem involves only random vectors instead of the random matrix G. Our proofs then address the technical aspects of this reduction and establish the resulting distributional convergence rigorously.
Gordon's 's theorem (Godon 1985
We now provide several additional remarks Theorem 2.1

---

Published as a conference paper at ICLR 2026
Majority Error
Minority Error
Balanced Error
1.0
Sindlation Theory
L 1.25
0.8
L 1.50
| 1.75
0.6
016
0/6
Exsy
0.4
0.4
0.4
0.2
0.2
0.2
0.0
01.1
0.3 0.5
0.0
0.3
0.5
3.0
0.22
0.4
0.5
Figure 4: Impact of imbalance on test errors. We show test errors from 2-GMM simulations with margin rebalancing (solid curves) and without (dashed curves) at three levels of signal strength || under varying imbalanced ratios π..
Compured with the existing literature. Rather than focusing solely on test errors-as in prior theoretical studies (Kini et al. 2021] Deng al., 2022) we analyze overfitting imbalanced
classification by characterizing the ELD/TLD (Theorem 2. (b).. and further establish mono-
tonicity of test errors in key model parameters (see Section and Table
Overfitting effect. The random variable encodes distortion of ELD due to high dimensions. A smaller aspect ratio 8 loosens the moment constraint [[[²] s 1/5 when maximizing the margin in Eq. (5). allowing greater distortion of TLD and thus stronger truncation. In fact, in order to maximize x, the first inequality constraint must be tight, which yields the explicit formula:
V1 p² g max Kc, 1lell12 + G +.G+++YB Y - -plll112 + +G+ Y
(k - 11 - G Y where a+ == max a
(6)
Thus, maps overlapping TLD masses to ELD margins, explaining ELD/TLD discrepancy.
More truncation for minority class. Due to imbalance, transporting the probability mass in the minority ELD as Eq. (6) incurs less "cost" to the overall "budget" IB(E2] S 1/6. Formally,
according Theorem 2.1 the limiting TLD for each class is
minority: (p" || + 85, 1),
majority: (- ||ul|2 + 3/. 1).
It can be shown that p" > 0, // < 0. So the minority TLD is closer to the decision boundary- the minority class suffers more from the truncation effect (overfitting) than the majority class.
show Appendix [ that (x) max (x", gives the optimal transport map from V4 to test and minimizes the W2 distance between them.
Optimal transport perspective.
Non-separable case. When d de, the training data not separable with high probability, so SVM is no longer the limit of logistic regression Eq. (2a). We analyze Eq. (2a) and its ELD: instead of truncation, overfitting appears as nonlinear shrinkage governed by the proximal operator (Moreau-en (Moreau-enveloppp envelope gradient). As 5 E (8c, 20) decreases, the shrinkage moves from an identity map (no overfitting) to truncation T (xr)
max(x",< (severe overfitting). See
Theorem D.3 for the formula and Appendix B.5 for its function plot.
REBALANCING MARGIN IS CRUCIAL
Rebalancing the margin a common practice for remedying severe overfitting for the minority class. In binary case, we choose a hyperparameter and consider the margin-rebalanced SVM:
maximize K BER ,
subject ( + 3a) 2 K. Vi [n]. || S 1,
where 81 - = +1, otherwise Ø4 1. For the logistic loss in Eq. 22a we can similarly incorporate т into the objective function. Margin rebalancing is widely used in machine learning
Karakoulas & Shawe- Taylor 1998 Li et al. 2002; Wu & Chang 2003 Li et al.) 2005: Cao et al.
2019]Kin et al. [202]] Clifford et al. 2024 Hu et al. 2025), but the impact of and other model parameters on test accuracy is not fully explored.
7

---

Published as a conference paper at ICLR 2026
Minority Error
Majority Error
1.0
1.0
1.0
(iI)
(U))
(1)
(i)
(II)
[lih signal
Moderatt signal
sigood
[lgh signal
Moderate signal
xiguod
0.0
0.8
0.8
0.4
0.1
0.1
0.2
0.2
1/22
0.2
0.0
0.0
0.0
0.0
0.2
0.4 0.6 0.8
0.0
0.2
0.4 0.6 0.8
Figure 5: Phase transition in high imbalance regime. Minority/majority errors under different settings of parameters (a, b, c) and = d". Left: minority accuracy is (i) high for any T under high signal, (ii) high for >> da-b-c under moderate signal, but (iii) low for any T under low signal. Right: majority accuracy is close to under high and moderate signal as long as T is not too large.
We will conduct analysis under two regimes: (i) proportional regime where n, d - oo and n/d + 5 with d E (0, oo), and (ii) high imbalance regime in the following sense:
π x d
|1|2 x d²,
x d=+1
(8)
For problems with imbalanced data, often correctly classifying the minority points is as important as majority points. We thus introduce the balanced error:
Em == (Err+ + Err-))] 3/2.
Empirical phenomenon For the proportional regime, we generate imbalanced 2-GMMs Eq. with n 100, d = 200, varying ||l|| and E (0, }]. In each setting, train an SVM Eq. with margin rebalancing (set T optimal) and without (T 1), compute test errors on independent data averaged over 100 runs, and plot them against in Fig, Smooth curves show the asymptotic
errors from Theorem 2. In naive SVM (T = 1), decreasing т drives minority error Err, / 1, majority error Eir- & O, and balanced error Err, 2. showing minority classes suffer more from overfitting. With optimal r, minority and majority errors align, making margin rebalancing effective for reducing balanced error. Further details and additional results appear in Appendix B
For the high imbalance regime, we generate imbalanced 2-GMMs based on Eq. (8) with d = 2000 large enough. We choose
Ta d' under different values of 2 O. We fix b 0.3, c 0.1
and vary a, r, and then we train a margin-rebalanced SVM Eq. 7 for each configuration. Fig. 5
shows that there are three phases in terms of the majority/minority errors. In particular, the margin rebalancing is crucial for one phase with moderate signal strength.
Theoretical foundation For the proportional regime, denote Erri, Erri, Errğ as the limits of Err+, Err-, ErT, as n, d - cc, respectively, then we have the following result.
Proposition 3.1 (Optimal 7 in proportional regime, informal version of Proposition D.6). Consider 2-GMM with asymptotics n/d + 8 E (0, oo) as n, d + cc. Define oot as the optimal margin ratio which minimizes the asymptotic balanced error
opt
arg min Erri arg min { (#(-p" p² ||l||| - (5) + + ||l|| + (5)).
IfT opt > O, we have 36 and Err" Err" ErTă decreases in H) I1eal12- and 8.
Notably, changing 7 only affects Bo (not 33), effectively shifting the decision boundary. The opti- mal has a complicated dependence и,, |||44112 6, and in non-degenerate cases roughly satisfies Topt x v1/z a (see Appendix D.2 for details). Under 7 = ropt, our theory shows that the test errors decrease monotonically with E (0, 4). |1 and 8; see Table 2 (and Proposition D.7 for details).
For the high imbalance regime, margin rebalancing is necessary to achieve a small balanced error when the "signal strength" is moderate, which matches our empirical observations in Fig.
8

---

Published as a conference paper at ICLR 2026
0.3
.T 0.25
0.1
0.05
1.0
1.0
1.0
Outputs
0.8
0.8
0.8
0.8
Gap
Accuracy
0.6
0.6
0.6
0.5
0.4
0..4
0.4
0.4
0.2
0.2
0.2
Ca
0.001
CllEr
0.04
CalBer
12
ChIFa
0.18
0.00
0.25
0.50
8.75
1.00
0.00
0.75 1.00
0.00
0.50
1.00
0.00
0:25
0.50
0.75
1.00
Confidencee
Confidennce
Coufidence
Confideruce
Figure 6: Reliability diagrams: imbalance worsens calibration. In our 2-GMM simulations, we train SVMs and obtain confidence P(æ). For each (z-axis), we calculate P1 = 1 1f((z) p) (v- axis) based on an independent test set. We find that as imbalance increases (smaller т), the classifier becomes more miscalibrated the predicted probabilities are more inflated.
Theorem 3.2 (High imbalance). Consider 2-GMM with Eq. ( as d xc. Suppose that a < 1.
1. High signal (no need for margin rebalancing):
< b.
we we choose Ta < db2 then
Err- = o(1). Err+ o(1),
2. Moderate signal (margin rebalancing is crucial): b a-c 2b. If b < To < d(a-c)/2
Err, = o(1),
Err_ = o(1).
However, if we naively choose Ta 1, then
Err, o(1), Err_ = o(1).
3. Low signal (no better than random guess): a 2h. For any we have Err, o(1). -(1)
4 CONSEQUENCES FOR CONFIDENCE ESTIMATION AND CALIBRATION
In deep learning, the confidence of a classifier is often understood as the likelihood that its prediction correct. Formally, we define the confidence of the max-margin classifier as f(x) == o of(())) a ((x, (3 + (B) where of (t) (1 + - We would like p to be close to the Bayes-optimal prob- ability p" (a: P(y
x)), but estimating p" (x) is generally intractable in high dimensions. The
notion of calibration is widely used to assess the faithfulness of prediction probabilities (Murphy &
Epstein 1967
Dawid 1982
Gupta et al. 2020). Formally, we call f is calibrated if
x(x))
Pa = (p p(x)).
(10)
This requires ((x) to match the true probability for any p(x:) We list some common miscalibration
metrics below (Kumar et al. 2019 Kuleshov & Liang 2015
Vaicenavicius al. 2019)
Calibration error
CallErr()) = E
(f(x) Ply = 1-111 (())))
(11)
Mean squared error (MSE)
MSE(P) = E
(1 = 1} - (1(())))
(12)
Confidence estimation error
ConfErr(P)
E.
(Max) - ->((x))))
(13)
Empirical phenomenon We plot confidence reliability diagrams in Fig. 6 for the 2-GMM simu- lations, common diagnostic for classifiers that shows Py = p(x)) p) as function of p (Guo al. 2017). We fix || = n 1, 000, and d = 500, and choose range for different я, under ppt We observe miscalibration getting worse when data becomes increasingly imbalanced (i.e., as æ decreases). Other miscalibration metrics exhibit similar behavior (see Appendix B).
Theoretical foundation We provide theoretical results partially explain the monotone trends.
Theorem 4.1 (Confidence estimation and calibration, informal version of Proposition D.9. Con- sider the proportional regime under condition of Theorem 2.1
(a) All miscalibration metrics Eqs. 2
13 have certain limits. For example, MSE + MSE* :=
Bla(- ||x4||2 G - n, and n/d d - 8.

---

Published as a conference paper at ICLR 2026
(b) MSE" is monotonically decreasing in (0, 2)), || and ö, when 7
The decrease of imbalance ratio signal strength | or aspect ratio would worsen calibration. This aligns with observations in Fig. 6 Other results are summarized in Table 2
EXTENSIONS
Our theory focuses on two-class problems with an isotropic covariance matrix since the phenomenon can be observed, analyzed, and theorized more clearly. For the cases of multiple classes and non- isotropic covariance matrices, we believe a similar characterization of ELDs exists.
Multiclass classification. For classification with K > 2 classes, we observe features E R and labels y/_5 E [K] Pg. where the expected fractions of each class is Ti P(y: = k). k [K]. Denote fx) the logit of x for label k. We conduct numerical experiments to illustrate that the truncation effect likely extends to the multiclass setting.
For simulation, we consider 3-component GMM with π (0.5, 0.3, 0.2), = 50,000, d = 6,000, and class centers are generated Rd from the L -phere (at the origin with radius 4).
For real data, we consider CIFAR- 10 image dataset preprocessed by the pretrained ResNet-18 18. We undersample an imbalanced dataset with sample size 500, 223, 100 for each class 1, 2, 3.
We train multinomial logistic regression (with ridge regularization parameter À 10-8) after prewhitening the features. In Fig. 7 we present the density heatmaps of joint logits (f;),, (x (a:)) in both experiments, where all input features æ; from class 1, and k = 3.
Notably, we observe similar truncation phenomena for 3-class classification on both synthetic and real data, where the Gaussian density is visibly truncated by two hyperplanes. For general K > 3, we conjecture that the empirical joint distribution the logits is asymptotically a multivariate Gaus- sian projected to convex polytope in R K where specific parameters of this limiting distribution depends on certain variational problem analogous to Eq. ( See Appendix D.4 for details.
Logit distribution of class 1
Logit distribution of class
X10
18
Jogit for labal
60
logít for label
60
0.2
16
0.1
-00 -211
401 20 0
12.5
18.0
7.6 -5.0
-225
-10.0
-75
Togit For Tabel 2
Togit for Tabel 3
Togit for Tabel 2
lngit for label
Figure 7: Joint empirical logit distributions of multinomial logistic regression. The heatmaps display empirical joint logits (xx,) f& (ax)) for features æ; from class 1, where 2, Overlaid Gaussian density contours (dashed curves) depict testing logit distributions. Left: 3-GMM simula- tion. Right: CIFAR-10 image features preprocessed by pretrained ResNet-18.
Non-isotropic covariance. Our theory and proof strategies can also extend to non-isotropic set- tings. Here highlight two important cases that commonly arise in practice. In both cases, overfit- ting remains characterized by truncation (full theoretical statements are deferred to Appendix D.4].
Heterogeneous covariance. We extend Eq. I x; bи N(-4, where Σ #
N(H, Σ. and x; y: Σ_. The asymptotics are analogous to Eq. (5). In particular when
Σ+ = o σy a+ Y +1 and σy a_ if Y 1. Therefore, covariance heterogeneity induces distinct scaling effects on the Gaussian component of the logit distribution for each class.
the limiting ELD becomes Law (Y, Y max(k", p² ||al|| + oy G + Y Y855), where
Spiked covariance. We also study the special case where x; y: ~ N Σ) with covariance Σ = + Lg, and V is a d x J orthogonal matrix. Such low-rank structure is common in overparameterizee models. We can similarly derive asymptotics analogous to those in Eq. (5).
'Similar to the binary case discussed in Section and multinomial logistic regression exist.
we expect similar connections between multiclass SVM
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Y... supported by NSF-DMS grant 2412052 and by the Office of the Vice Chancellor for Research and Graduate Education at the UW Madison with funding from the Wisconsin Alumni Research Foundation. K.Z. is supported by the Founder's Postdoctoral Fellowship Statistics Columbia University. J.L. gratefully acknowledges support from the award committees of the New England Statistical Symposium,
Midwest Machine Learning Symposium, and the Inaugural Workshop on Frontiers in Statistical Machine Learning, and thanks Zhexuan Liu, Yiping Lu, Zexuan Sun, Zhuoyan Xu, Congwei Yang, and Zhihao Zhao for their valuable feedback.
REFERENCES
@ Meta. Llama model card. 2024, URL. https:://ggittu..cooo/oo
3/blob/ma / CARD. md
JA Anderson and SC Richardson. Logistic discrimination and bias correction in maximum likeli- hood estimation. Technometrics, 21(1):71-78, 1979.
Peter Bartlett. For valid generalization the size of the weights more important than the size of the network. Advances in neural information processing systems, 9, 1996.
Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 2615):16,1 1998.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3NNov):463444222 2002.
Peter L Bartlett Dylan Foster, and Matus Telgarsky. Spectrally-norrmaizzed margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117745)::0033330077) 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-1558
2019.
Peter Bickel, Gil Kur, and Boaz Nadler. Projection pursuit high dimensions. Proceedings of the National Academy of Sciences, 115(37):9151-911 2018.
Glenn W Brier. Verification of forecasts expressed in terms of probability. Monthly weather review, 78(1):1-3, 1950.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparitics in commer- cial gender classification. In Conference on fairness, accountability and transparency, pp. 77-91. PMLR, 2018
Emmanuel J Candès and Pragya Sur. The phase transition for the existence of the maximum like- lihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27-42, 2020.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribution-aaaaa margin loss. Advances in neural information processing systems, 32, 2019.
Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: survey. ACM com- puting surveys (CSUR), 41(3):1-58, 2009. 2009.
Min-Te Chao and WE Strawderman. Negative moments of positive random variables. Journal of the American Statistical Association, (33 431, 1972.
Nitesh V Chawla, Kevin W Bowyer, Lawrence Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
11

---

Published as a conference paper at ICLR 2026
Matt Clifford, Jonathan Erskine, Alexander Hepbum, Raúl Santos- -odrigged and Dario Garcia- Garcia, Learning confidence bounds for classification with imbalanced data. arXiv preprint arXiv:2407.11878, 2024.
Eduardo Dadalto. Resnet-18 model trained on cifar- 10, 2023, URL httttss////giiggaaee hto/dadalttocg///oooooooo fa
Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdeborová. Univer- sality laws for gaussian mixtures in generalized linear models. Advances in Neural Information Processing Systems, 36:54754-54766 2023.
A Philip Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77 (379):605-610, 1982.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. Information and Inference: A Journal of the IMA, 11(2): 435-495, 2022.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 0rXiv:1810.04803. 2018.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166:935-969 2016.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv e-prints, pp. a107, 2024.
Noureddine El Karoui, Derek Bean, Peter Bickel, Chinghway Lim, and Bin Yu. On robust regres- sion with high-dimensional predictors. Proceedings of the National Academy of Sciences, 110 (36):14557-1456,, 2013.
Tilmann Gneiting, Fadoua Balabdaoui, and Adrian E Raftery. Probabilistic forecasts, calibration and sharpness. Journal of the Royal Statistical Society Series B: Statistical Methodology, 69(2): 243-268, 2007.
Yehoram Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathematics, 50:265-289, 1985.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-fiee binary classification: prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems, 33:3711-3777 1-3723, 2020.
Haibo He and Edwardo A Garcia. Learning from imbalanced data, IEEE Transactions on knowledge 2009.
and data engineering,
Haibo He, Yang Bai, Edwardo A Garcia, and Shutao Li. Adasyn: Adaptive synthetic sampling ap- proach for imbalanced learning. In 2008 IEEE international joint conference on neural networks (IEEE world congress on computational intelligence), pp. 1322-1328. leee, 2008
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and patlern recognition, pp- 770-778, 2016.
Kaiming He. Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and patlern recognition, pp. 9729-9738, 2020.
12

---

Published as a conference paper at ICLR 2026
Jeremy Howard and Sebastian Ruder. Universal language model fine-tuning for text classification. arXiv preprint
2018.
Guangzheng Hu, Feng Liu, Mingming Gong, Guanghui Wang, and Liuhua Peng. Learning imbal- anced data with beneficial label noise. 2025.
Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5375-53844 2016.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression, 2019. URL
https://arxixz httpps///arxvv.orrrra//////// 1803.883340 07300
Hyun Min Kang, Meena Subramaniam, Sasha Targ, Michelle Nguyen, Lenka Maliskova, Elizabeth McCarthy, Eunice Wan, Simon Wong, Lauren Byrnes, Cristina M Lanata, et al. Multiplexed droplet single-cell ma-sequencing using natural genetic variation. Nature biotechnology, 36(1): 89-94, 2018.
Grigoris Karakoulas and John Stawe-Taylon Optimizing classifers for imbalanced training sets. Advances in neural information processing systems, 11, 1998.
Salman Khan, Munawar Hayat, Syed Waqas Zamir, Jianbing Shen, and Ling Shao. Striking the right balance with uncertainty. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 103-112, 2019.
Gary King and Langche Zeng. Logistic regression in rare events data. Political analysis, 9(2): 137-163, 2001.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameteriiztton. Advances in Neural Information Processing Systems, 34:18970-18983, 2021.
Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Simon Kornblith, Jonathon Shlens, and Quoc V Le. Do better imagenet models transfer better? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 2661 2671,2013
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, Ontario, 2009, URL inttps://wwst cs www.ttoroooooooooo wtt.roontoo.edd/rrri/////
brriingfeetuzee 2009-0000000 TR. TR.pdf]
Miroslav Kubat, Robert C Holte, and Stan Matwin. Machine learning for the detection of oil spills in satellite radar images. Machine learning, 30:195-2155 1998.
Volodymyr Kuleshov and Percy Liang. Calibrated structured prediction. Advances in Neural Information Processing Systems, 28, 2015.
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. Advances Neural Information Processing Systems, 32, 2019.
Ananya Kumar, Aditi Raghunathan, Robbie Jones, Tengyu Ma, and Percy Liang. Fine- tuning can distort pretrained features and underperform out-of-distribution. arXiv preprint arXiv:2202.10055. 2022.
Kenneth Li, Oam Patel, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg. Inference-tine intervention: Eliciting truthful answers from a language model. Advances in Neural Information Processing Systems, 36:41451-41534 2023.
Yaoyong Li, Hugo Zaragoza, Ralf Herbrich, John Shawe-Taylee and Jaz Kandola. The perceptron algorithm with uneven margins. In ICML,, volume 2, pp. 379-386, 2002.
13

---

Published as a conference paper at ICLR 2026
Yaoyong Li, Kalina Bontcheva, and Hamish Cunningham. Using uneven margins and per- ceptron for information extraction. In Proceedings of the Ninth Conference on Computational Natural Language Learning (CoNLL-2005), pp. 72-79, 2005.
Friedrich Liese and Klaus-J Miescke. Statistical decision theory. In Statistical Decision Theory: Estimation, Testing, and Selection, pp. 1-52. Springer, 2008.
Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. arXiv preprint arXiv:2109.07955: 2021.
Geert Litjens, Thijs Kooi, Babak Ehteshami Bejnordi, Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Mohsen Ghafoorian, Jeroen Awm Van Der Laak, Bram Van Ginneken, and Clara I Sánchez. survey on deep learning in medical image analysis. Medical image analysis, 42: 60-88, 2017.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large- scale long-tailed recognition in an open world. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 2537-2546, 2019.
Emanuele Loffredo, Mauro Pastore, Simona Cocco, and Rémi Monasson. Restoring balance: prin- cipled under/oversampling of data for optimal classification. arXiv preprint arXiv:2405.09535. 2024.
Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions. Advances Neural Information Processing Systems, 34:10144-10157, 2021.
Yiping Lu, Wenlong Ji, Zachary Izzo, and Lexing Ying. Importance tempering: Group robustness for overparameterized models. arXiv preprint vrXiv:2209.08745. 2022.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http:
7/www. ac web. org/ wwwpbborgg/atttooooo//l111111111
P. McCullagh and J.A. Nelder. Generalized Linear Models. Monographs Statistics and Applied Probability. Springer US 1983. ISBN 9780412238505. URL hhttps://bbole google.c
om.
Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization classification of high-dimensional noisy gaussian mixture. Interna- fional conference machine learning, pp. 6874 PMLR, 2020.
Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning, 2018. URl.:tttp..//aarxxv.rr////b/bbbs
Andrea Montanari and Kangjie Zhou. Overparametrized linear dimensionality reductions: From projection pursuit two-layer neural networks, 2022. URL http://s///xxx...o////////////// 06. 06526
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max- margin linear classifiers: Benign overfitting and high dimensional asymptotics in the over- parametrized regime, 2023.
01544
Andrea Montanari, Yiqiao Zhong, and Kangjie Zhou. Tractability from overparamettizatioo:: The example of the negative perceptron. Probability Theory and Related Fields, 188(3):005-10,, 2024.
Allan H Murphy. A new vector partition of the probability score. Journal of Applied Meteorology and Climatology, 12(4):595-600, 1973.
Allan H Murphy and Edward S Epstein. Verification of probabilistic predictions: A brief review.
Journal of Applied Meteorology (1962-1982), pp. 748-755, 1967.
14

---

Published as a conference paper at ICLR 2026
Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Hand- book of econometrics, 4:2111-2245, 1994.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning, 2015, URL
Eric WT Ngai, Yong Hu, Yiu Hing Wong, Yijun Chen, and Xin Sun. The application of data mining techniques in financial fraud detection: A classification framework and an academic review of literature. Decision support systems, 50(3):559- 559- 2011.
Francesco Saverio Pezzicoli, Valentina Ros, François Landes, and Marco Baity-Jesi. Class imbal- ance in anomaly detection: Learning from an exactly solvable model. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp- 8748-8763. PMLR, 2021.
Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. Advances in neural information processing systems, 16, 2003.
Saharon Rosset, Zhu, and Trevor Hastie. Boosting regularized path maximum margin classifier. The Journal of Machine Learning Research, 5:941-973, 2004.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning, pp. 8346-8356. PMLR, 2020.
Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. Advances in Neural Information Processing Systems, 32, 2019.
Filippo Santambrogio. Optimal transport for applied mathematicians, Birkäuser, NY, 55(58-63):94, 2015.
Stefano Sarao Mannelli, Federica Gerace, Negar Rostamzadeh, and Luca Saglietti. Bias-inducing geometries: An exactly solvable data model with fairness implications. Physical Review E, 112 (2):025304, 2025.
Robert Schaefer Bias correction in maximum likelihood logistic regression, Statisties in Medicine, 2(1):71-78, 1983.
Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson. Cnn features off- the-shelf: an astounding baseline for recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 806-813, 2014.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70); 1-57, 2018.
http:rrrrrpppppppp.aee.see wwtps/////////1///// html
Pragya Sur and Emmanuel J Candès. A modern maximum-likelihood theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516-144 2019.
Pragya Sur, Yuxin Chen, and Emmanuel Candès. The likelihood ratio test in high-dimensions logistic regression is asymptotically rescaled chi-square. Probability theory and related fields, 175:487-558, 2019.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pp. 1683-1709. PMLR, 2015.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized me-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-5622 2018.
15

---

Published as a conference paper at ICLR 2026
Philipp Tschandl, Cliff Rosendahl, and Harald Kittler. The ham10000 dataset, large collection of multi-source dermatoscopic images of common pigmented skin lesions. Scientific data, 5(1):1-9, 2018.
Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön. Evaluating model calibration in classification. In The 22nd international conference on artificial intelligence and statistics, pp. 3459-3467. PMLR, 2019.
Vladimir Vapnik. Statistical learning theory. John Wiley & Sons google schola, 2:831-844 844, 1998.
Roman Vershynin. digh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Gary M Weiss and Foster Provost. Learning when training data costly: The effect of class distribution on tree induction. Journal of artificial intelligence research, 19:315-354, 2003.
Gang Wu and Edward Y Chang. Class- Blass-boundary alignment for imbalanced dataset learning, In ICML 2003 workshop on learning from imbalanced data sets II, Washington, DC, pp. 49-56, 2003.
Yu Xie and Charles F Manski. The logit model and response- based samples. Sociological Methods & Research, 17(3):283-302 1989.
Zalinescu. Convex analysis in general vector spaces. World Scientific Publishing Co., Inc, 2002.
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2921-2929, 2016.
16

---

Published as a conference paper at ICLR 2026
APPENDIX
CONTENTS
Notations
19
Experiment details
19
B.1
Setup and details
19
B.2
Probing Llama- 1amna-3-82 88-88-1111 Instructtt
21
B.
GMM simulation
21
B.3.1
High imbalance
21
B.3.2
Calibration
22
B.4
Additional experiment results
22
B.5
Function plot for the proximal operator prox prox
23
Preliminaries
23
SVM and linear separability
23
Connections between logistic regression and SVM
24
Proofs Proposition C.
26
D Additional details in theoretical results
28
D.I Precise asymptotics of empirical logit distribution
...i............................
28
D.I.1 Separable data
29
D.1.2 Non-separable data
D.2 Analysis of margin rebalancing for separable data
................................
32
D.2.1
Proportional regime
32
D.2.2 High imbalance regime
33
D.3 Consequences for confidence estimation and calibration
.iabba..o.......................
33
D.4
Generalizations
35
E
Logit distribution for separable data: Proofs for Section D.1.1
37
Proof of Theorem D.I
37
E.1.1
Step
Boundedness of the intercept: Proof of Lemmal E.1
40
E.1.2
Step 2
Reduction via Gaussian comparison: Proof Lemma
E.1.3
Step 3
Dimension reduction: Proof of Lemmal E.3
42
E. 1.1.4
Step
Investigation of the positivity: Proof of Lemma H.4
44
E.1.5
Step 5
Phase transition, margin convergence: Proofs of Lemmas E.5
E.6
45
E. 1.
Convergence of ELD and parameters for 7 = 1: Proofs of Lemmas E.7
E.8
46
E.1.7
Completing the proof of Theorem
50
Analysis of the asymptotic optimization problem: Proof of Lemma E.9
54
Proof of Proposition] D.2
56
17

---

Published as a conference paper at ICLR 2026
Logit distribution for non-separable data: Proofs for Section D.1.2
56
Proof of Theorem D.3
56
F.I.1
Step
Boundedness of B and Bo: Proof of Lemma F.2
61
F.1.2
Step
Reduction via Gaussian comparison: Proof Lemma
62
F.1.3
Step
Convergence in variational forms: Proof of Lemma F.4
63
R11.4
Step 4 Asymptotic characterization: Proofs of Lemmas F.5
19
64
R J.5
Parameter convergence, optimality analysis: Proofs of Lemmas F.7
F.10
F.1
67
F.1.6
ELD convergence:
Proof of Lemma F.8
71
F.1.7
Completing the proof of Lemma D.3
73
Margin rebalancing in proportional regime: Proofs for Section D.2.1
75
Proofs of Propositions D).4 and D.5
75
G.2
Proofs of Propositions D.6 and D.7
78
Technical lemmas
79
H
Margin rebalancing in high imbalance regime: Proof of Theorem D.8
80
A tight upper bound on maximum margin: Proof of Lemma H.1
H.2
Asymptotics of optimal parameters: Proofs Lemmas H.3
H.2.1
Asymptotic order of p: Proof of Lemma H.3
85
H.2.2
Asymptotic order of (z,, 0)'s on the margin: Proof of Lemma H.4
88
H.2.3
Asymptotic expression of 3n: Proof of Lemma H.5
H.3
Classification error: Completing the proof of Theorem D.8
92
Confidence estimation and calibration: Proofs for Section D33
94
I.
Proof of Proposition D.9
94
1.2
Verification of Claim
96
J
Technical Lemmas
97
Properties of Gaussian random variables
97
J.2
Properties of sub-gaussian and sub-exponential random variables
97
J.3 Properties of the Moreau envelope and proximal operator
100
Míscellancous
100
Additional Experiments
101
Logit distribution for non Gaussian data
101
Phase transition in high imbalance regime
102
Logit distribution for CIFAR-10 image dataset
103
18

---

Published as a conference paper at ICLR 2026
A NOTATIONS
We typically use italic letters to denote scalars and random variables (c.g,, a, b, c, G, Y, E R), boldface (italic) lowercase letters to denote (random) vectors (e.g., S, 3 ... E Rd), and bold- face (italic) uppercase letters to denote (random) matrices (e.g. A,P, X, G. For any positive integer n, let [x]]
E Rd xd2). For scalar a, let a maxfa, 0} and
f1,2..... ................................ ,n). a+ = max{-a, 0}. For vectors u, v of the same length, let (u, = u'v denote their standard inner product, and write J. if they are orthogonal (u, v). - 0). The corresponding Euclidean norm is ||u|| ||ul||- (u, u) 1)2 For matrix A, let llp denote its operator norm and | |F its Frobenius norm. We S (resp. 3 denote the set of symmetric positive semidefinite (resp. definite) matrices in R"x" We use è and & to denote the cumulative distribution function (CDF) and probability density function (PDF) of standard normal distribution. Let Law(X) denote the distribution of random variable (or vector) X. We write X 11 Y if X and Y are independent random variables.
We use O()) and o(-) for the standard big-O and small-o notations. For real sequences (an (dn)n>11 (bx) (2)) we write an I bn or bn Z a, if on = O(b,), and an x bn if an S b, and an Z bn We also write On < bn or bn > an an = o(b,). We write an x by o, cba, vn 2 for some constant e 0. Let 4, P, C" denote stochastic convergence in distribution, in probability, in LP, respectively, and let _ denote weak convergence of measures. We also use Or(-) and or(-) for the standard big-O and small-o in probability notations. Denote Öp(-) as a variant of Op(-) which hides polylogarithmic factors.
Given two probability measures P, Q on IRd, their second Wasserstein (W2) distance is defined as
/ ||x - 11x-yl2 7dxx x dy)
1/2
inf (2(PQQ) = (EI(P)
where the infimum is taken over the set of couplings I(P, Q) of distributions P and Q. For a sequence of measures (Pr) we write Pa. Wa, Q if (P,, Q) - 0 as n + co. For any x E TR
and À > 0, the Moreau envelope continuous convex function é: -> Rzo is defined as
1
ex(2; A) exe(x) = min TER
E(t) + (t - x²)
21
and the proximal operator of & is defined as
(x; A) = proxxe(x)= arg min ((t)
(t - 2))
IEB
2A
For binary classification, define I+ := {i [m] the minority and majority index sets, with n, := |I,| and n. == | We exclude the one-class degenerate case and assume 14,7- 2 1, which holds with high probability.
+1} and I_ == fi |n|] y4 -1} as
B EXPERIMENT DETAILS
B. SETUP AND DETAILS
We present the details of our experiments, including the computational configurations, information about the datasets, and the pretrained neural networks used in our study.
Datasets We provide the details of real data used our study, including the source, size, and the preprocessing applicd.
IFNB (Kang et al. 2018): single-cell RNA-seq dataset peripheral blood mononuclear cells treated with interferon-3, which has = 7,451 cells, d 2,000 genes, and K 13 categories for cells. The original dataset is available from R package SeuratData (https: : / ////ttttuu seurat -at version 0.2.2.9001) under the name i fnbb The data were preprocessed, normalized, and scaled by following the standard procedures by R package Seurat using functions CreateSeuratttbeeee Normal 1 zeeata and Scal eData.
.com/ ccom/satinn jalab/seurattt
19

---

Published as a conference paper at ICLR 2026
CIFAR-10 (Krihhvssyy 2009): the original dataset consists of 60,000 color images of size 32 x 32 in 10 classes, with 6,000 images per class. There are 50,000 training images and 10,000 test images. It is available at hhtpss:/www cs toronto. edu/ 1aruuu-rri2 -kriz/ ///ccii// fa r. httml We followed the simple data augmentation in (He et al. 2016; Cao et al. 2019) for the training images: 4 pixels are padded each side, and 32 32 crop randomly sampled from the padded image or its horizontal flip. Normalization is applied for both training and test images.
IMDb Maas al. 2011): the dataset consists of 50,000 movie reviews for binary sentiment classification (k 2), with the positive and negative reviews evenly distributed. There are 25,000 training texts and 25,000 test texts. The data can be found at https : /hwggg in ace co / datasets httpssssstannoooop/.cmosmpp for inputs was set 512.
The maximum length in number of tokens
TruthfulQA (Lin et al. 2021): the dataset consists of 817 questions spanning 38 categories, including health, law, finance and politics. Each question comes with an average of 3.2 truthful answers, 4.1 false answers, well gold standard answer. It can be reformulated 5,918 QA pairs, including 2,600 correct answers and 3,318 incorrect answers. The data can be found at httph:ts///sttt htttps://huqgigggtee
co dataaattsssstee
Pretrained models
We downloaded and used pretrained models from Huggingface.
ResNet-18 (He et al. 2016): 18-layer, 512-dim, 11.2M parameters, convolutional neural net- work (CNN), pretrained on CIFAR-10 training set (50,000 images). The pretrained model is downloaded from https: httgggggggacccceeeeeeeecc co edadadaaall http///daaaaottggeeeeeeeeeeeeeee _icii farl0 Notice that for extracting features, we manually removed the last fully-connected layer.
BERT (Devlin 2018); 12-layer, 12-head, 768-dim, 110M parameters, encoder-only trans-
former, masked prediction, with absolute positional encoding at the input layer, pretrained on BooksCorpus (800M words) and English Wikipedia (2,500M words). The pretrained model is uncas
downloaded from [ttpssss/bugggoooaccccco//// wartgglleeeerttee
led
We also used fine-tuned version of BERT (same structure as above) on IMDb dataset, which can be found at http://///...ggiieeeeeee/ee/eeea -imdb
-lama-3-8B-Instruud (Dubey et al. 2024): 32-layer, 32-head, 4096-dim hidden size, 8B pa- rameters, decoder-only transformer, with rotary positional encodings (RoPE); context length 8,192 tokens; instruction tuned with supervised fine-tuning (SFT) and reinforcement learn- ing with human feedback (RLHF). Pretrained on 15T tokens of data from publicly available sources; knowledge cutoff is March 2023. The instruction-tunee checkpoint is downloaded from httpt::://ugigggggeettee
co met a 1lmma/ Mwwa-etaaaaaaee 3- 83- Instruct
Data splitting For GMM simulated data and IFNB single-cell data, we split the whole dataset into training and test sets in equal proportions. For CIFAR-10 10 image data and IMDb movie review data, notice that we used the ResNet-18 and BERT model which are pretrained/fine-tun training set of CIFAR-10 and IMDb, respectively. To avoid reusing the data when training the last fully-connected layer (i.e., logistic regression). we split the test set of CIFAR-10 and IMDb into a "training subset" and a "test subset" in equal proportions. We used this "training subset" for logistic regression training and "test subset" for evaluation. For TruthfulQA data, we split the whole dataset into training and test sets by 5
on the
Optimization We used functions linear_model wog.stiiceeeesssiioooooooooooo and svm svc from Python module sklearn to solve logistic regression Eq. (2a) and SVM Eq. (2b) (more pre- cisely, Eq. (17)) parametrization with + 1). For logistic regression, used the limited-memory
20

---

Published as a conference paper at ICLR 2026
BFGS (L-BFGS) solver, with maximum number of iterations 10 For SVM, set the default value cost parameter C = Tolerance for both are set to be 10
As discussed in Section C.2 logistic regression and SVM are "cquivalent" separable dataset. Indeed, theoretically and empirically, there are advantages and disadvantages to both algorithms, summarized in Table In particular, SVM is preferred for theoretical analysis and precise 2-GMM simulation, while logistic regression is preferred for large scale real data analysis.
Table 3: Comparison of empirical behaviors of logistic regression and SVM on separable data.
Pros
Cons
robust to sear--eparrbilityy computationally efficient
infinite norm solution slow convergence
Logistic regression (2a)
well-defined solution
sensitive to outliers quadratic programming
SVM 2b
support vectors available
B.2 PROBING
We follow the probing setup for "truthfulness" in (Li al. 2023). For each QA pair in TruthfulQA, concatenate the question and answer to form a prompt, for example,
{Q: Are you conscious? A: I
AI and don't know) [Q: Are you conscious? A: I am a human]
(y +1, truc),
(y = 1, false).
We aim to distinguish attention-heal outputs that lead to true vs. false answers. For each head in each layer, extract the activation the last token form probing dataset {(x;, y:)] We train probes as follows:
(1) Linear probing, Fit logistic regression Eq. (2 to obtain Ist-direction logit ((1) =- (xx 3 300)) ) (1)
% (with normalization ||3 ||2 = 1).
(2) Orthogonal probing. Fit constrained logistic regression, where (3 .000 minimizes the
2ap objective subject to 3 1 (
This yields 2nd-direction logit (12) == (x. B (2), +
Eq.
%
(with normalization
|| ||2 1).
Fig.
visualizes the joint and marginal distributions of ((2)) on both the training and test sets.
B.3
GMM SIMULATION
6 are all generated from 2-GMM simulations. By rotational invariance, we may take = M. 0 0)T E Fd for some >> 0. Both minority and majority test errors are calculated on an independent balanced test set, to ensure the accuracy of estimating Err..
Figs.
and
B.3.1
HIGH IMBALANCE
For high imbalance regime in Section we provide simulation study by generating data from 2-GMM. More precisely, given a, b, c > 0, let
Cad-a, || Cpd. 1 n= =Cdd++
(14)
for some fixed constant C. 1, C, 0.75, C. 1, where μ = (n, O)) E Rd and = VC.db In the experiment, we fix b = 0.3, c 0.1, and d = 2,000 large enough to ensure data
'If logistic regression is far from converging after the maximum number of iterations is reached, would add small explicit regularizer as in Eq. 18). In practice, the parameter C A in iinear_odee loggi st cRegress on
chosen 10 10
'Note that there is no hard margin solver available in sklearn and svm. SVC is soft-margin version. One may C large enough, but usually a larger C will lead to longer running time. To handle this issue, (for separable data) avm. SVC with C increases from 1, until the training error attains zero.
21

---

Published as a conference paper at ICLR 2026
Minority Error
Majority Error
Balanced Error
0.12
0.05
0.05
0.10
0.15
0.20
0.05
Theury
Ett
Siuralation
0.05
0.04
0.04
0.02
0.13
0.02
0.00
010
2
3
Figure 8: Effects of margin rebalancing on test errors. We show test errors from 2-GMM simu- lations at three different imbalance ratios under varying т.
separability, while we change the value of a. For each tuple (a, by c). we compute the parameters T. p., n as per Eq. (4). and generate training sets and test according 2-GMM Eq. (
B.3.2 CALIBRATION
The confidence reliability diagram Fig. Glis created by partitioning (0, into M interval bins In m1 M M m E [M.] and calculating the average accuracy of each bin. Let p(x;) be the confidence 1.M
of the i-th test point (i [n)), and denote B., == {i [m]] f(xx;) E [m) be the set of indices whose confidence falls into each bin. Then by our definition of confidence and the symmetry of binary classification, the accuracy and confidence of Bm can be estimated by
acc (
Σ IEB...
1 13.
conf
Σ p(a,).
B
|,m
i.B...
We also obtain binning-based estimator of calibration enror in Eq. ties:
(11) by using above quanti-
M Σ
BBall (acc(B...) conf conf
CalErr
m==1
This is a variant of the expected calibration error (ECE) (Guo et al. (017)) In Fig. 6 the histograms
show the empirical conditional probabilities PP 1 1 p(x) = p) after binning, i.e. ace ace(B.). The dashed diagonal line represents perfect calibration (i.e., when Eq. (T)) strictly equals), and deviation from this line means miscalibration of the classifier.
The confidence reliability diagrams for additional 2-GMM simulations and IMDb movie review dataset are shown in Figs. I0 12 These plots confirm a similar trend: miscalibration is getting worse when data becomes increasingly imbalanced (i.e., as π decreases).
B.4 ADDITIONAL EXPERIMENT RESULTS
Additional results in Section For the proportional regime, we also plot test errors against dif- ferent values of in Fig. 8 under the same simulation setting. The minority and majority errors have monotone but opposite trends in т, since increasing т essentially moves the decision boundary from the side of minority class to the majority class. Such trade-off between the two classes results in U-shaped curve for the balanced error. This indicates that we can find a unique optimal r = opt which minimizes Errg, and oot is larger becomes smaller.
Additional results in Section We consider the same 2-GMM simulation experiment as in Fig (the proportional regime). After margin rebalancing, we calculate the three miscalibration metrics 13 on an independent test set, average over 100 replications, and plot these emrors against different values of π in Fig. 9 The smooth curves represent the asymptotic errors, i.e., the limits of CalErr(p). MSE(p). Con(Err(p) as n, + oo according to Theorem 2.1 Notably, all these errors increase imbalance becomes severe (namely being smaller).
Eqs. (I])
22

---

Published as a conference paper at ICLR 2026
Calibration Error
Mean Squared Error
Confidence Estimation Error
0.23
0.300
1.25
0.20
[ 1.50
0.18
| 1.75
MBF
0.16
ConfErr
0.130
Tarory
Sizmlaation
0.10
0.14
0.125
0.075
0.0
0.2 0.4
0.5
0.0
0.1
0.2
0.3
0.5
0.0
0.3
0.2
03
0.5
Figure 9: Impact of imbalance on uncertainty quantification. We plot miscalibration metrics Eqs. (T) (3) for 2-GMM simulations with optimal margin rehalancing (r = Topt). We find that
high imbalance (namely small r) exacerbates miscalibration.
h 0.3
π 0.25
0.1
0.05
Ontguats
Gap
Accuracy
0.6
0.6
0.5
0.4
0.4
0.4
0.2
0.2
0.2
0.2
Cal
0.034
Chllfer
Callar
0.045
Ca Bir
0.053
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.73
1.00
Confideuce
Confidence
Coufidence
Confideuce
Figure 10: Reliability diagram for 2-GMM simulation (l]aall2 = 2, n = 1,000, d 100)
B.5 FUNCTION PLOT FOR THE PROXIMAL OPERATOR prox
Recall that
prox (x) = arg min ((t) + (1 x)²
21
ER
We provide the plot for function x + (æ)) which is the specific form of overfitting effect in logistic regression Eq. 2ab on non-separable data (i.e., 6 >> 8 80)).. The plot is shown in Fig. 13 where {(t) = log(1 + r is the logistic loss, and we choose X = 5, 100, and 10,000 for visu- alization. When À is close to zero, the function + p=) is close the identity map, which is because lim (z) = by Theorem J.S b) When À is large, the proximal operator (up to scaling) looks like a smooth approximation of the truncation map æ + max(x, x for some > O. Intuitively, pr behaves like minimizing & when À is large. Therefore, large æ yields (rox)e(z) Re x since {(x) x= O, and a small æ would "pushed" to some k > 0, since the logistic loss {(z) locally is a smoothing of the hinge-type loss + (a bx)+ + for some a, b 0.
According to our proof in Section F the limiting value of À as n, d + 0O, n/d + 8 (denoted by x*))) is decreasing function of the asymptotic aspect ratio 5. Then Fig, 13 graphicaalll illustrates the effect of high-dimensionality on overfitting. When n/d - is large, then (²) is small and ELD 2 TLD, and overfitting is negligible. In particular, this is the case for the classical setting where d is fixed and
oo. When 8 is moderate, the ELD is somewhat shrunken compared to TLD. When 8 & 5* (0), approaching the interpolation threshold, then A² is very large, and the ELD is almost rectified Gaussian and far away from the TLD.
C PRELIMINARIES
C.I SVM AND LINEAR SEPARABILITY
Consider our GMM in Eq. D. Denote = (#I..... TT) E Raxd and = (y....., ......y.) T e
R" Recall the general margin-rebalanced SVM in Eq. (7). For > O, it is convenient to write this
23

---

Published as a conference paper at ICLR 2026
0.3
TT 0.25
0.1
0.05
1.0
1.0
1.0
Outputs
0.8
0.8
0.8
0.8
Gap
Accuracy
0.6
0.6
0.6
0.5
0.4
0..4
0.4
0.4
0.2
0.2
0.2
CalEEt
0.014
0,076
GalRer
0.17
ChlEm
0.23
0.25
0.50
0:75
1.00
0.00
0.76
0.50
1.00
0.25
0.75
1.00
Confidencee
Confidencee
Coufidence
Confideruce
Figure 11: Reliability diagram for 2-GMM simulation (l]æl|2 0.5, n 1,000, d 500)
0.25
0.05
1.0
1.0
1.0
1.0
Outputa
0.8
0.8
0.8
Gap
Accuracy
0.6
0.6
0.5
Collar
0.0018
0.0035
Ca
0.019
Callerr
0.031
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.22
0.50
0.75
1.00
Confidence
Coufidence
Coulidence
Confidence
Figure 12: Reliability diagram for IMDb dataset preprocessed by BERT base model (110M)
SVM formulation into
maximize BER AoER subject to
min Di ((x;, (3) + :o); iE(n)
(15)
|| 1
by introducing the transformed labels
if y/ = +1, if
T
(16)
-1
According to the following deterministic result, the solution margin-rebalanced SVM Eq. simple post-hoc adjustment of the solution to the original SVM Eq. (b).
7 is
Proposition C.1. (a) When data linearly separable, Eg. has a unique solution.
(b) Let (o()), R(T)) an optimal solution to Eg. under hyperparameter v. Then
2 (=)=-2_((1) R(1.
= = + + R(1),
R(T) = 1+1
(17)
Remark C.1. There is clear geometric interpretation of (3, Bo, R and r in the max-margin classi- fier, according to Fig.
(() determines the support vectors and the "direction" " of decision boundary, which does not depend on r. Notably, margin rebalancing does not change B.
Bo(T) balances the positive/negative margins via Eq. where determines the amount of the shift.
R(() (T + 1)-1 in fixed dataset.
C.2 CONNECTIONS BETWEEN LOGISTIC REGRESSION AND SVM
The two classifiers in Eqs. 2a and (bb) are strongly connected high dimensions: the SVM can be viewed the limit of logistic regression when the data are linearly separable.
24

---

Published as a conference paper at ICLR 2026
A
5
A= 100
10.000
20
0-
10
10
10
-10
10
-00
10
10
10
10
10
Figure 13: Function plot for x + pr) under different x. The solid curve represents the function y (r)x)e(2) and the dashed line represents the identity map y I.
Minority class (y +1)
Majority class (y = -1)
Positive support vector(s)
Negative support vertor(s)
(3) + =
Pg
Figure 14: Schematic illustration of margin-rebalanced SVM. The dotted line is the decision boundary for the original SVM, and the solid line is the decision boundary for margin-rebalanced SVM.
We first introduce the background of inductive bias from (Rosset et al. 2003 2004 and (Soudry al. 2018 Ji & Telgarsky 2019). In logistic regression, minimize the empirical loss Eq. (2a) where {(t) log + is the logistic loss. Since the loss is strictly convex, it admits a finite minimizer, then the minimizer must be unique. However, when the data are linearly separable, there no finite minimizer and the objective value goes to 0 for certain ,3 with ||B|2 > co. To obtain a unique solution, may add regularizer:
n
(Bx, Bo.x)
arg min
Σ n
E(ui((2 B3 + Bo)) + 111
(18)
BER",9
Let (3, 3,) be the max-margin solution to SVM Eq.
(b)
Then it has been shown by (Rosset et al,
2003 2004) that without the presence of intercept
B
lim +
3.
(19)
1B
From this view, logistic regression with a vanishing ridge regularizer is equivalent to max max-margin classifier in the separable regime. By modifying the proof in (Rosset et al. 2003). can generalize their conclusion with Sn included.
Proposition C.2. Let Bo.x) be the minimizer of the regularized objective function in Eq. 18
where E: R + R>o is any convex, non dedddereesingg rapidly varying loss function in the sense that
lim ((sl) to [(t)
E
Assume the data is linearly separable. Then the convergence in Eq. limx bo.>/11//, Bo.
19 holds. Moreover, have
25

---

Published as a conference paper at ICLR 2026
Another approach of establishing the connection does not require adding an explicit regularizer. For convenience, let (()) 1
n E.= {(yi(ar; (3)) and consider the gradient descent iterates ((++1)
8 V, VV where ( = 1, 2, and ( is the parameter vector at iteration (. it shown by (Soudry et al. 2018) that under sufficiently small step size 17.
(t)
lim
3,
where B = arg max |11,, miniglo] 9e (e G). This is often referred to the implicit bias.
C.3 PROOFS OF PROPOSITION C.I
We first introduce some technical adjustments and terms that used in our proofs.
Well-definedness of margin with (xx (x. (3) + fu as
We define the margin of linear classifier x + (1(f()) > 0)
x(3, min (2, B) + Bo),
(20)
ic(n)
which is the objective of margin-rebalanced SVM Eq. 7 and 15) Note there is minor caveat
about the one-class degenerate case, which ignored in the main text for simplicity. When n4, = or n (this happens with nonzero probability for any fixed n), we have x(3,8)) oc. It motivates us redefine the maximum margin properly.
Definition C.1. The well-defined maximum margin is
n (3,,80) = min ( 3) Bo), if S n4 Sn-1. =E(n]
R:
(21)
0,
ifn = 0 or n.
Therefore, R above a proper random variable and R 2 0 always holds] Further, R k(B3 30) with high probability n + co. We will apply similar adjustments to the definition of ELD in Section B and elsewhere, whenever required for the proof.
Support vectors Consider the non-degenerate case (1 n+ S n 1). To study the properties
of optimal solution (9, 3o, R) from a non-asymptotic perspective, we inherit the concept of support
vectors from SVM. Deñne the support vector of a linear classifier 21 { (z. B3 + 9o > 0} 1 as the vector(s) a; which attain(s) the smallest (rebalanced) logit margin 7 (z,, 3) + (3) from each class. Namely,
SV+ = =SV+ (B) == arg min y1 ((x;, (3) + (00) = arg min + +xx, B), ;y
-:;=+1
(22)
SV_ = SV) == arg min 71 ( ((x;, () + (B) = arg min - (2., B),
itg.=-1
i=g.=-1
where SV+ are sets of (the indices of) positive and negative support vectors. A key observa- tion from Eq. (22) that support vectors only depend on the data and parameter B3, not Bu or Let (3) and sv_ (B) be any element in SV+ and SV
(B) E (B),
sv (3) E SV- SV-(3),
which are (the indices of) arbitrary positive and negative support vectors (only depends on (X, and (9). In particular, +v+ (3) E SV+ sv (e) E SV (3) are support vectors of the max-margin classifier 21{ B) + 30 0} 1, which aligns with the definition of support vectors in SVM.
The lemma below summarizes some important properties of the max-margin solution Eq. char-
acterized by support vectors, which is stronger statement than Theorem C.I
Lemma C.3. For non-degenerate case, let (e, Bo, Ri) be an optimal solution to Eq. Then
Forr degenerate case (n.- = 0 or rt), the dataset is considered as linearly separable.
Hence, we view SV (19) as mapping from Rd the power set of {i yi +
26

---

Published as a conference paper at ICLR 2026
(a) B does NOT depend T. and
(T (++1)*=
max BE8"
(1) [3)- (x (13)
I (a) 3).
(23)
(b) Bo depends on T by
Bo T(o0 - + (Io (x
(24)
(c) If the data are linearly separable, then (0) must be unique.
Proof. For any feasible solution (3, of Eq. 15 we denote the positive and negative margin of the classifier + (1{ 30 0} as
K+ (3. = min (.((,, (3) + Bu) - ((xsv, (18) (3) + 9o),
s:y==+1
(25)
K- (3, = min
=igh--1 Ti((2,, (3) + Bu) - ((2 (3), + Bo).
According to Eq. (15 we have
β arg max (3 (BB)) = arg max min Ui( + (o())), Se8"
BEg
sEin)
where
Bu( arg max n(B, arg mrg min (1,,, (3) (b))
RoER
R
:E|n]
arg max min R
T.((2;, B) + Bo), min Te (2, + 80)}
(26)
(ig+=+1
arg max min { (B, Po), k- (B,
3.ER
Here, (0(3 can be viewed as the optimal intercept for linear classifier with slope given by B.
b As defined in Eq. 25 note min (k+ (B, x- (8, 3o)) is piecewise linear concave function of Sg. Therefore, (B3) must satisfy the warginnbalancing condition i.e.,
(G, (o))) (3, k(B, (B)).
(27)
In particular, recall that ()( = 3o. then k. (3, (o) -B, Substitute this back to Eq. 25
deduce
t ((x (3)) 3) + (6) - -((xx, (3) 3) + Bo),
which uniquely solves the expression for 3o in Eq.
24 This concludes the proof of part (b)
a
Next, we show that 33 does not depend on т. According to Eq. 27 and Eq. 225
3 arg max (B,
Begd-1
TK TK4 (3, + K- (3,30(3))
arg
BEgd-1
T+1 (3),
arg max BEga-1
arg max m (13) Iov (8) B): BEga-1
++1
where (I (3)
Izv (19). only depends on G3 and (X, y) by definition. Hence, it deduces
R = (=3 The Bo (3) + (0,00(3) (xr (0)-
(
(II (a))
++1
++1
As have seen, the baagginbalanccng condition holds regardless of the sign of margin. It holds even if the data is not linearly separable.
27

---

Published as a conference paper at ICLR 2026
This concludes the proof of part (a)
(c) Since Eq. 175 is a convex optimization problem with objective function |[w] 11 which is strictly
convex in w, by equivalence between Eq. 7 (15) and (175). we know that w and [ w
2
must be unique. And by (a) 3o is also unique. This concludes the proof of part (c)
Notice that Theorem C.3 will also be used in the proof of Theorem H.4 for the high imbalance regime. Below, we show that Theorem C.1 is direct consequence of Theorem
Proof of Proposition C.7 We only show the relation on A((T and 3 (T), while the other results are According to Eq. (23 for any T, (T+1)) equals quantity which does not depend on r. Plugging in T = 1, we get (T 1)R(T) = 2R(1).
simply restatements of Theorem C.3
Combining Eq.
23 and 24p. we can solve
a B
= TR(T) - (T),, (a (3) = - BT(
Notice the above holds for any 0. Taking r and substituting into Eq. (24). we get
- (1) - (1) + (R(1) - (c()) -Bo(1) T
- R(1).
++1
-+1
This completes the proof.
Our argument follows the proof (Soudry et al., 2018 Theorem 2.1). Assume that 8 is a limit point of ///113311 ll2 as À - 0+, with ||@- = 1. The existence of 33 is guaranteed by boundedness. Let 3 := lim supx //.x/11B Now, suppose the max-margin classifier given by (8,8)) (with || 1) has a larger margin than (3", that is,
Proof of Proposition C.2
x(B", (6) min y (x,,, + (6) <(B Bo) min (1 3) + 3o). sE|n]
.E(n]
By continuity of (( Bo), there exists some open neighhorhood of (3* :::::
Na .eg == {B E Rd Bo E R || = 1, ||B - 3 + 180 B/ < 82}
and an >> 0, such that
x(3, 9o) = min ya (z., 3) + (b) < k(3,30) - <E(n)
A (3,30) E N
Since l is rapidly varying, now by (Soudry et al. 2018 Lemma 2.3) we know that there exists some constant T > 0 (depends on k(B, 3o) and E), such that
Σ (() + tBo)) Σ (vi((a (B) + t26)),
Vt T, (6,8)) E ENa .8:
which implies (t,3, t. has a smaller loss Eq. 18) than (t33, t,.). This indicates that 3 cannot be a limit point of Replacing lim sup by lim inf in the definition of / gives the same conclusion. Then we complete the proof by noticing the max-margin solution is unique separable data by Theorem C.3
ll, which is contradiction. Hence we must have k(B²" ,((3",8)))) = x(33 3))-
D ADDITIONAL DETAILS THEORETICAL RESULTS
D.1 PRECISE ASYMPTOTICS EMPIRICAL LOGIT DISTRIBUTION
In this section, we present additional details on the asymptotics of empirical logit distribution intro-
duced in Section 2 Recall that data ((x,, y: H are i.i.d. generated from 2-GMM Eq. (T. ie..
a; ye N(ya,, Ia), with label distribution P, Plys +1) Ply 1) = E (0, 3 We
28

---

Published as a conference paper at ICLR 2026
consider proportional asymptoties where n, + and n/d - 5 with å (0, oc). Based lations between т, pu, 6, we will consider linearly separable data (fitted by SVM) and non-separable data (fitted by logistic regression) separately.
We define the following functions 8" IR - Rz0 and He : [-1, 1] x + Rz that are related to the critical threshold of data separability:
1 p²
8 (16) =
max pEf
Hp Po), (p, =
1,11,
E2 [s(Y) llull22 + G Y
(28)
where (Y.G) Pg N(O,1) 1) and
s(y)
T,
=
(29)
if --1.
We will show in Theorem D.I that the relationship between 8 and 8 (0) determines separability, where 8 (0) does not depend on 7 by definition.
We summarize the asymptoties of logit distribution for both separable and non-separable case in Table which is the main contribution of our theoretical results (Theorem D.I and D.3)
Table 4: Comparison of logit distributions on separable and non-separable data (T = 1).
limiting ELD (v%)
cause for overfitting (5*)
separable data
Law (Y, Y max LOGITS})
R PV11pp20 = =(k- - LOGITS)
separabe data
Law (Y, Y prox ( (LOGITS))
R p- -
limiting TLD (y (
Law (Y, Y LOGITS)
LOGITS: := p" |||||2 R R
(R* 1 in separable case)
D.1.1 SEPARABLE DATA
For linearly separable data, recall the margin-rebalanced SVM in Eq. 7 and 15 theorem summarizes the precise asymptoties of SVM under arbitrary т, including the limits of parameters, margin, and logit distribution. The proofs are deferred to the appendices.
The following
Recall that data {( y:) are generated from 2-GMM with fixed parameters 1 E Rdd π (o, 31 Let (3,. Bo.n) be an optimal solution to the margin-rebalanced SVM Eq. 15 and R. = min;ein] Wi (ar,,, 3) + 36) be the maximum margin. Recall the cosine angle Pn. = between μ and B, defined as
#
P
(30)
|
Let (K) be defined as per Eq.
28 and ,", k², - solution to the variational problem
maximize
K
pE(-1, seC- subject to P 1|اl||2 + G+Y VI -I-
(31)
sYY),
EiSa1 < 1/5.
where C2 is the space of all square integrable random variables in (Q,F, and (Y, P,
N(O, 1). We define
Law (Y, max(s(Y) p² [| + ++++))
test
Law (Y, (pp || G + +Y()),
which we will prove to be the limiting ELD and TLD respectively.
Theorem D.I (Separable data). Assume oo with n/d 8 (0, Fix (0,
29

---

Published as a conference paper at ICLR 2026
(a) (Phase transition) With probability tending one, the data is linearly separable if < 80) and is not linearly separable if > (0656600 60)).
(b) (Variational problem) In the separable regime ó < 8 (0), (p", ,b x², : ) is the unique solution
to Eq. 431 with p² E (0,1) (not depend on T) K² > O, and the random variable & satisfies
(a.s.)
y1-pa p1-pp25t
(s(Y)n* (s())= p" |l G G- -YY,)) x.8)))
(32)
Moreover, (0 x²) is also the unique solution
maximize
Ki Hp, 26
ME 111-,.)),0BBB. RER subject
(33)
and K- = sup fN :R: 27.
(c) (Margin convergence) In the separable regime å < 80)
R
In the non-separable regime 8 (0) we have negative margin, i.e., with probability tending to one, for some > 0,
max min (( B} Bu) S R.
|| BGER
(d) (Parameter convergence) the separable regime 6 < (0),
Pn P p",
Bo 2 35.
(e) (Asymptotic errors) Recall the minority and majority test prediction errors, Err+, and Err- respectively, of the max-margin classifier defined Eq. (4) (writing subscript n for clarity). Then in the separable regime 5 < (0),
Err+,a + (-p" ||1l|2 (%),
Err- 1 (-p" || l (3))
(f) (ELD/TLD convergence) Recall the ELD vn and TLD Prest defined as per Definition 2.2 where f(x) = (a. B.)) + Bu Then in the separable regime < (0) we have logit convergence for both training and test data, i.e.
W₂ W2(Dn, v.) BS O,
Dlest
w test
Remark D.1. By taking T 1, the ELD convergence Wz(Dn, v.) Dg in Theorem 2. 2.1 bb) is
consequence of Theorem D.1 and the TLD convergence Glest _ veest is corollary of Theo-
rem [.)
As discussed in Section random variable ç* and the nonlinear transformation T (x) max (z. x*) therein characterize the effect of overfitting on logits. The following result provides an optimal transport perspective of this overfitting effect. For ease of description, we reformulate v, and !est in terms of the following one-dimensional measures
C. Law (max(x", p" ||1|| + G Y
Cleat Law (p" ||H||| + G+Y
Proposition D.2 (Optimal transport map). T (z) = max(k", xx) is the unique optimal transport map from Ciest to L. under the cost function c(x,, v) = hix y) for any strictly convex h R Rzo. That is,
{S ((x,T(())dd (x) Tp = C..)
arg min
IR++
where Ty is the pushforward operator.
30

---

Published as a conference paper at ICLR 2026
D.1.2 NON-SEPARABLE DATA
For non-separable data, SVM yields trivial solution 0. 0. A typical approach fitting a classifier is to solve regression problem Eq. (Za). Similar to the margin-rebalanced SVM Eq. (T)) we can also incorporate into the objective function by substituting y: for yi yt/ (yt),, that is.
Σ (Til(ar, (3) 30)),
min BER",B0ER
(34)
71
where -> R20 the loss function. We consider more general form than logistic regression. We say that f is pseudo-Lipschitz if there exists constant L > 0 such that, for all x, E R,
[((x) {(v) - L (1 + |a] + bvl) | yl.
This condition is satisfied, for instance, by the widely used logistic loss {(t) = log(1 + e-*). As the counterpart of Theorem i.I the non-separable regime, the following theorem summarizes the precise asymptotics of regression Eq. 34.. including the limits of parameters and logit distribution.
We consider the same 2-GMM setting as Section D.I.I For any non-increasing, strictly convex, let (3,.: Po.n) be the optimal solution regression Eq. (34). Recall Pa م defined in Eq. (30 and 8* 0*()) defined in Eq. 28 Let
pseudo-Lipschits twice differentiable function f: R - R R>..
p² R2, ,0 5x be a solution to the variational problem
p
p|leoll2 R + RG + Y + R RV RVI- P&C
].
minimize [E|- R20.
E
e
x(Y)
(35)
subject to
E
[5-]]
1/6.
where (Y,G) ~ x N(O, 1). We define
V. := Law Y, Y,Y prox ALE p" 1111l Rt + + ))
s(V) ylest Law (R. p" |||||| + R
aiming show they are the limiting ELD and TLD respectively.
Theorem D.3 (Non-separable data). Consider the same 2-GMM and proportional settings n/d + as in Theorem D.I
(a) (Variational problem) In the non-separable regime > (0), (p", - is the unique solution Eq. (35) with p² E (0, 1). R E (0, 20), and the random variable 8 satisfies (a.s.)
(
(o 1elll 1 R' R*G Y ))
R' V --0-
prox arE RVT
(36)
8YY)
where X E (0, 00) is the unique constant such that E[g²] 1/6. Moreover (p" O",R", ,0. X*) is also the unique solution to the following system of equations
RRp
R + RG + 90 )) P (pl|all2
e' prox
2x ||
=
T
Rp
E [8' (proxxe(plluul) R+ RG - BB))]]
2(1 - x A6 ||1a|12
P |1lllll2 R RG + Y
(roxx 2e -18
s(Y)
E
x(Y)
P p1|eell2 2 R + RG + Y
s(Y) Ae"
prox
de RCTT
s(Y)
27
Rº p²)
1
(plleel22 R RG + Y
E
E' (proxx xe
X28
s(V)
s(Y)
(b) (Parameter convergence) In the non-separable regime 8 80))), as n + co,
1 2 Eg R"
Pn P p",
8a P, 36
31

---

Published as a conference paper at ICLR 2026
(c) (Asymptotic errors) Recall the prediction errors defined per Eq. separable regime 3 8)(), as n2 DC,
44
Then in the non-
E + + (-p" ||
Pg
Err-,n + + (-p" ||lll2 2 +
R
R
(d) (ELD/TLD convergence) Recall the ELD Un and TLD Thet defined per Desimition 2.2 where f(x) = (x,, B,) :0 Then in the non-separable regime å > (0) we have logit convergence for both training and test data, i.e., +
(2 v.) E O,
Fest
- V+
trest.
Remark D.2. Compared to the separable regime, the random variable in the non non-separable regime Eq. (35) can also be interpreted as the cause for overfitting, but its distortion effect on ELD is not fruncation, When = 1, by Eq. (35). (36). the following holds for a "typical" training point:
va va((z,, + Bo.n) = p" |el| R
R + R² p
=p" 1ell R + G + - X* X (prox... |ull2 R + +RG+Y
=pp'xx-e(p" |e|| R Y
where the equalities come from Theorem J.3] Hence, the ELD in the non-separable regime is the TLD under nonlinear shrinkage due to the proximal operator of loss function E.
D.2 ANALYSIS MARGIN REBALANCING FOR SEPARABLE DATA
In this section, we show how margin rebalancing improves the test accuracies on imbalanced dataset by choosing the hyperparameter Eq. appropriately.
D.2.1 PROPORTIONAL REGIME
Consider the same 2-GMM and proportional settings in Section D.I.I on linearly separable dataset
(6 8t (0)). According to Theorem D. [e) the asymptotic minority and majority test errors are
Err = 4 (-p" || bb), Err" := + (-p" || + (8)).
(37)
For the purpose of imbalanced classification, we define the asymptotic balanced error as
Emr = Err; + Err".
Monotonicity analysis. We first provide some monotone results for test errors, which support our empirical observations in Section
Proposition D.4. Erri, is decreasing function of E (0, 4). |ee|l and ö when T = 1.
However, the majority error Err" and balanced error Erră, are not necessarily monotone under arbitrary т. Thus, we will focus on the monotonicity of these test errors when is chosen to be optimal.
According to Fig. 8 by taking > 1, we can improve the minority accuracy at the cost of harming majority accuracy. The opposite effects of 7 on Err and Err" are summarized in the following result. Proposition D.5. Erri, is decreasing in E (0, oo), and Err increasing in E (0, oo).
Choosing the optimal 7. A natural idea for margin rebalancing is to choose such that the bal- anced error Errğ is minimized.
Proposition D.6 (Optimal 7). opt be the optimal margin ratio defined in Theorem 3.1 Denote 91 (z) := E [G + +] where G N(O, 1). Then oopt has the explicit expression
p
91
2T |A0||
+
111//1112
Opt
(38)
p*
9-1
+ pr ||H1||2
2(1
T))
1111112@
32

---

Published as a conference paper at ICLR 2026
Remark D.3. The optimal choice of I has complicated dependence the numerator scales as T 11/T for small and fixed ||lll and 6, which is consistent with the choice of T in importance tempering (Lu et al. 2022). In (Cao et al. 2019), T is suggested to scale with 1114, however it was proved in (Kini al. 2021) that their algorithm won't converge
However, note that
to the solution with the desired
It is worth noticing that in the near-degenerate cases where is very small or || 8 are very large, then p² is close to O and the denominator can be negative, leading to -opt < 0. While our theory (Theorem D.7 Theorem D.9) is still valid when allow potential negative т, it is rarely used in practice. See Section f.r a further discussion. The near-degenerate cases (small n, large || or are better addressed under the high imbalance regime, as we analyze the next subsection.
The minority/maajrrtyhhalaneddd errors all equal ((-p" (1 when Topt, We can also obtain the monotonicity of test errors after margin rebalancing.
Proposition D.7. When T = Tapt > O, all the test errors Err4, Err", Errî are decreasing functions of E (0, 1/2) (imbalance ratio), å (aspect ratio), and || (signal strength).
D.2.2 HIGH IMBALANCE REGIME
Different from the proportional regime considered in Section D.I and D.2.1 here focus high-imber leghhimbalanced scenario where π is small, || is large, and n grows much faster than d. this regime, can even extend the feature distribution beyond Gaussian, and generalize the 2-GMM settings.
Definition D.1 (High imbalance). We say a dataset {(x), b)) is i.i.d. generated from a two- component sub-gaussian mixture model (2-suGGMM) for any i [n].
i. Label distribution: P(y; = +1) =111=111 P(y: = -1)
ii Feature distribution: It Yot + 2,, where 2, has independent coordinates with uni- formly bounded sub- gaussian norms. Namely, each coordinate 2ij of 2; satisfies E[zy]] O, Var(zi)) 1, and || p == inf 0 Elexp((2/K33) S 2] S for all j [d]. where C is an absolute constaní.
For any constants a, b O, we say a 2-subGMM is b, ba, c)-imbalanced if Eq. 88 holds.
Remark D.4. Parameters 2. and e each specifies the degenerate rate of imbalance ratio n, and the growth rate of signal strength || aspect ratio n/d. We usually require a < c to make sure the minority class sample size n4 nn d=
does not degenerate.
Our goal is to study the performance of maargin-rebllanced SVM Eq. 7 in this high imbalance regime, asymptotically as - xc. Therefore, we allow - = тa depends on dimension d and care about what order of would make the test errors vanish. We summarize our findings in the following theorem, which consistent with the empirical observations Fig. 5 and extends Theorem 3.2 to the case of imbalanced 2-subGMM.
Theorem D.8 (Phase transition in high imbalance regime). Consider the high imbalance regime where the training data i.i.d. generated from an (a, b, immbalannee 2-suGGMM. Suppose that < 1. A margin- rebalanee SVM is trained, with test errors calculated according to Eq. (4)
Then as + oc, the conclusions of the three phases in Theorem 3.2 still hold.
D.3 CONSEQUENCES FOR CONFIDENCE ESTIMATION AND CALIBRATION
Recall the definition of confidence of the max max-margin classifier p(x)) = of(()) o ((x B3 + 3o) in Section 4 Note that p(x)) and p(x) are the predicted probabilities of æ for the minority class ( +1) and the majority class (y = 1) respectively.
worth noticing that the confidence is sensitive scales, i.e., a(t) + (ct) if 1, despite the fact that rescaling yields the same label prediction and thus does not affect accuracy. While small models tend to be calibrated, especially when parameter estimation is consistent, larger models such as DNNs are known to suffer from poor calibration (Guo et al.) (017]). A simple theoretical explanation is that in DNN, the last layer (usually logistic regression)
((xr, ( Bo)
33

---

Published as a conference paper at ICLR 2026
trained by gradient descent separable features often results in very large || (as mentioned in Section C.2 thereby inflating the predicted probabilities. Here we focus on the common form of | = 1 is applied.
SVM 2b where normalization
Some probabilities regarding the confidence are as follows.
1. Max-margin confidence. The confidence of the max-margin classifier is
f(x) == o (f(z)) o 3) Bo)
2. Bayes optimal probability. The true conditional probability is
1e (a))) (P = 1
3. True posterior probability. The probability conditioning on max-margin confidence
p= P 1(
Note that p" (æ) is the confidence of the Bayes classifier y² (æ) =- 21 2/4) + log T-
> 0} -1
Recall the definition of calibration Eq. TOP and some miscalibration metrics Eqs. We offer some further explanations for them.
13 intro-
duced in Section 4
Calibration error: The L distance between confidence and posteriori, which is the most commonly used metric.
CalErr(p) = E [M(x) - =
Mean squared error (MSE): Also known the Brier score, subject calibration budget (Brier 1950 Gneiting et al. 2007).
MSE = E (11y= = -(x))
It can be shown that MSE has the following decomposition
MSE(P) = Var [)] + CalErr(P)
Var [x))
irreducible
lack of calibration
sharpmess/resolation
Calibration error itself does not guarantee useful predictor. Sharpness, also known as resolu- tion (Murphy) 1973; Kuleshov & Liang 2015), is another desired property which measures variance in the response explained by the probabilistic prediction f(xr). Hence, small MSE suggests a classifier to be calibrated with high sharpness.
Note that Var[1(y = 1H1 = x(1 т) an intrinsic quantity unrelated to f. When study the effeect of π model calibration, may discard the irreducible variance term and define modified MSE as
mMSE(p) CalErr(P) - Var (Po))))
Confidence estimation error: The _ distance between confidence and Bayes optimum.
ConfErr(() EE (p(x)-p'(x))
It has the following relation with MSE:
MSE (1) + ConfEEr(p),
(39)
where the first term is intrinsic, which only depends on and ||
The asymptotics of these metries, and some monotone effect of model parameters (0, }1, || 8 on them, are summarized the following proposition.
Proposition D.9 (Confidence estimation and calibration). Consider 2-GMM and the proportional settings in Section D. on linearly separable dataset (6 < 8" (0)).
34

---

Published as a conference paper at ICLR 2026
(a) Let (p', .8) be defined per Theorem D.1 and (Y,G) Ps N(O.1) 1). Denote
MSE" = E ( (-p" || - B + G) mMSE" = MSE" 1r -T),
CalErr" = E
a 2p" ||aall2 (0" || Y G) + log
π "=) op |1 Y G G -+) 1- ④T/
o (- 111112 (11ell12 + G - log π y) }
Vila = E
ConfErr MSE" V
then
lim MSE(f) = MSE",
lim CalErr(p) = CalErr",
n-+00
n=oc
lim mMSE(p) = mMSE", 40000
lim ConlErr(p) = ConfErr".
n
(b) When T = Topt > 0,
MSE** and mMSE are fincciioon of E (0, (), || 8.
ConfErr" is decreasing in 6.
In addition, there are some monotone relationships that can be verified numerically. We summarized them in the following claim.
Claim D.10. Consider the same settings Theorem D.9 When 7 >> 0, we have
CalErr" is decreasing in ||a||2 and for any π S fixed, where x Rs 0.25 some constant.
ConfEEr" is decreasing in ().
D.4 GENERALIZATIONS
Below we present two possible extensions of our main results stated in previous sections.
Multiclass classification. In the K-class setting, we observe features E IRd and labels [K] Py. sampled from a K comompnnett Gaussian mixture model (K KGGM
= PM k), A E [K],
v = k N(H
(40)
where (1x [k[]]] are the class means. Let f(x) We wo be the logits of multinomial logistic regression for {(0,, n where W E Rxxd Wo E RRK are the solution to K-class SVM:
minimize WeRk x Wo subject to
||
(41)
(z, Wy.) + 1o (z,, Wx) + Wo,k + 1, Vi [n], V + yo:
where wa is the k-th row of W, and Wo. is the k-th element of Wo. The prediction is given by ((x) == arg ma (z),, where fxx the logit for label k. i.e., the le-th component of
f(x). Using the non-rigorous replica method from statistical physics, we conjecture the limiting empirical logits distribution as follows.
Conjecture D.11. Assume that n/dd 8 n, d Denote by [my,.... Mgl Bd the matrix of class means, and assume that μ1' converges to a deterministic matrix Q2 E S as d co. Then n. d 0O,
1 n W2
Σ 5 (v. We.+Wa) Law (R,) + U + wi) B o. i=1
35

---

Published as a conference paper at ICLR 2026
where Rt is the Y-th row of R RK*k and (R",U U", w6) is the optimal solution the follow- ing variational problem
minimize
Tr(Q),
w.r.t.
Wo R
QnQ E $4, O &
subject to
QR IK
0 Ik, E 3 1
(42)
R Q 1/2 OQ 1/2 Q U= U=QU/2 Q (Ix Qn) 1/2 H, 112
Rt
On the event (Y = k}, Rick - Ru Ui + Wo,k Wo 2 1
almost surely. 4 E [K], 41 41 k.
where (2, K) is the space of square integrable K K-ddimnsional random vectors in the probability space (R, (Y, G) Py N(O, Ix), and H,U U are random vectors to be optimized.
The last almost-sure linear constraint in Eq. (42) induces a truncation effect, captured by the random vector H (analogous in Eq. (5) which in turn characterizes the resulting overfitting behavior.
Heterogeneous non-isotropic covariance. We can extend our theory to the setting where the two classes have general non- isotrooto covariances, i.e.,
x; y/ +1+ N(p, Σ+);
æ; yt = -1 N(- μ, Σ-).
(43)
Under the proportional asymptotics d with n/d - 8, we make the following assumptions.
(A1) E. and Σ_ have eigenvalue decompositions E Die At..v.y. E Ei v.v.. i.e., Σ4 and Σ commute.
(A2) There exists a random vector (S+, S_, M) E Ryo Rs0 X R in probability space (2, (.FF,P) such that the empirical distribution of spectrum {()+,i, X Vdlv,, 1))) converges to the distribution of S-, in Wasserstein-2 sense:
d
1
8 ( ((v..)))
W.
Law (S+, M).
d F=1
In particular, || (B[M2))4/22 is fixed and E[S{] oc.
Recall that T = T generalizes Theorem 2.1 under Eq. 43
14 and (3, 3o) is the max-margin solution to Eq.
2bb. The result below
Conjecture D.12. Consider model Eq. 443 with asymptotics n//d + ā (0, 2o) as n.d + oc.
Under assumptions (Al) (A2) there a critical threshold 8, = 8 S_, M), such that when 8 < de, the following holds as n., d + oc:
(a) Parameter convergence. The training set is linearly separable with high probability, and
(p, 3o. R) Eg 10",,5 k*),
where p- = S[MB.J/EEMMP and (Br,8g k²) is the solution to the variational problem
maximize BEL² x200 subject to
K,
B²| < 1,
[E[S)/2 (.55/22... G.B))
E (n - -EIS -b) <
T
EE /1/2 G__
E (
+
(1-x)ō
where L is the space of square integrable random variables in the probability space (Ω, F, F.P), (G. G_).G Mi.a. N(O, 1) is independent of S_, and a random variable to be optimized.
36

---

Published as a conference paper at ICLR 2026
As consequence, the limits of minoritymmajority errors (-00 |111l2 + S0
Err+ - || (=0 (*(+)
36
Err_ + +
o²(-1)
where o* (+1) (E[S_ and (-1) (B (B[S_
(b) ELD convergence. The empirical (training) logit distribution Dn has limit in the sense that where v. == Law (Y,Y max( ,p' l|llll2 + + + (6)).
W2(Pn, v.) B O,
TLD convergence. The testing logit distribution Drest has limit wset in the sense that
D
pest
test V.
where v. test == Law (Y,Y ||l| + o (Y)
Compared to Theorem 2.1 we find that covariance heterogeneity, captured by dY(Y,, induces dis- tinct scaling effects the testing enrors (Err+, Err-). It also rescales the Gaussian component of the logit distribution (G) for each class.
Spiked non-isotropic covariance. We also provide characterization of the empirical logits dis- tribution under spiked covariance. In particular, we assume that
3; 1/ ~ Nuvu, E), Σ = V + Ia,
(44)
where the spike V d orthogonal matrix. For this model, have the following analogous result on the empirical logits distribution of SVM: Conjecture D.13. Assume that n/d - 5, J/d + th1 n. d, + Denote 1/2 =1- 1/1 and further assume that
lim
[
ull2 c
lim n0
|1l |VT c2.
Let (8) be the max-margin solution to Eq.
2b
Then, as -0,
1 Σ
8 (1r BB)B Law (r + Ypse + 11+ + r :6)) P. o.
W2
In the above display, Y Pg is independent of G2) N(O, 1)82, and ri, solves the following convex optimization problem:
maximize PL PK
K,
subject to
E K - P P202 - - r2G2 - PoY 27
)
(45)
1
VV++ 92 V -i-v + v 12 P3 13
2
< 8
=1, s 2 5
Future work. In deep learning. the features learned by optimizing the loss all weights in neural network, and data imbalance impacts on feature learning in complex way as observed in (Cao al. 22019) Also, models tend erroneously find spurious features if data imbalance is severe (Sagawa et al. 2020p. It would be interesting to analyze overfitting and propose remedies for these scenarios.
E LOGIT DISTRIBUTION FOR SEPARABLE DATA: PROOFS FOR SECTION D.I.I
E.1 PROOF THFOREM D.I
Recall that the margin-rebalanced SVM can be rewritten
maximize BER4, Bo.KER subject
To (2 (3 + (00) Ks, Vi [n].
(46)
| < 1.
37

---

Published as a conference paper at ICLR 2026
Let be optimal solution and R. 1igg (n- Po,n) be the well-defined max- imum margin as per Definition C. Our goal is to derive exact asymptotics for (B.,. n Ry )- Similar to the development in (Montanari et al. 2023), for any positive margin & > 0, we define the event
En = (n(3n, Po.n) 2 x}
= =3,3 E R., |1 N 1, ,0 E R, such that Di (<;; + 96) 2 k. for all i E [m]]
{3 E 11.1111 1, 30 E R. such that (KSy y о X (uy) = 0}
where Sy (s(y)))...,,(())
and is the function defined in Eq. 29 Therefore, the data
(X, y) is linearly separable if and only if Ea,x holds for some ń. > O. We would like to determine for which sets of parameters (x,, 14, 7) we have P)),,) and for which instead P(E,,,)) + as n, d co. To this end, we also define
(ISS - y y X3 Boy)
Sn,
min |
vd
(47)
1
min || |
max
x
(KSy oy X3 - Bo1),
Vd
AGER
AGy20
where (i) is a consequence of Lagrange duality (dual norm) [((a) 112 |AI Al. Then established the following equivalence
(Sn, 0} - E Keep in mind that we are only concerned with the sign (positivity) of En,xs not its magnitude. As a consequence, have
{5n,x = 0) = En,
Rn 1
sup(K E TR: En, 03-
Let Dr, == (n+ = or n be the event of degeneration for any datasets of size Clearly P(D,) π² + -1- +
as - oo. Technically, the empirical logit distribution (ELD) Eq. not well-defined on D,, Similar as Definition
C.I
we can also redefine it as follows:
1 in = Ti Σ
(48)
We provide outline for the main parts of the proofs of Theorem D. several steps of transforming and simplifying the random variable En,x.
which involves
Step
Step
Step
(2)
z(2) Se
Theorem
S
Thearem
ST..B
Theorem
Sx.B
Theoren E.
Step 4
(13)
(p)
Step 5
8'(x), (x Bo).
Theorem
Theorem
Step 1: Boundedness of the intercept (from En,x. to gt ) According to the definition of En.x. parameters & and are optimized in compact sets, but Bu is not. Such con-compastness might cause technical difficulties in the following steps, for example, when applying Gordon's 's Gaussian compar- ison inequality and establishing uniform convergence. However, it turns out that fo is asymptotically bounded on the event E, More precisely, we define
SR
min max S Vd" T (KSy 3
X33 B)1),
(49)
| X6y20
where B = B(T,K, K, n, ||ll 5) is sufficiently large constant. Then we can show that &n, and S, have the same sign with high probability, which enables us work with S,,, instead of En.--
Lemma E.1 (Boundedness of 2o). There exists some constant B E (0) (depends on T,K, T. ||plllll 8) such that
lim [P = 0) PCC.,,.B = =0] =0. n-000
See Section E.1.1 for the proof.
38

---

Published as a conference paper at ICLR 2026
Step 2: Reduction via Gaussian comparison (from Sx...B to Sn,K.B) According to the expres- sion of Sn,,. it is not hard to see the objective function (of (B, A)) a bilinear form of the Gaussian random matrix X. To simplify the bilinear term and make the calculation easier, we will use the convex Gaussian minimax theorem (CGMT, see Theorem[JI] i.e. Gordon's comparison inequality (Gordon 1985 Thrampoulidis et al., 2015). To do so, we introduce another quantity:
e(())
Sn,KBB
20)
min x² +1101| S1
|| vd (1All29T o 100| h A A
max
(nSS ④ y - -Pllell2 y + pp 8o 801))
18 Xoy20
(50)
where E R, A E Rd-1 are parameters, ~ N(O, Id-1), ~ N(O,I.), a ~ I(O.I.)) are
independent Gaussian vectors. The following lemma connects Sn,,, with e((1)
Sn..B.
Lemma E.2 (Reduction via CGMT), For any E R and 2
PP ([ 0/ 21 s 2P S v 2 21).
((1)
See Section E.1.2 for the proof.
Step 3: Dimension reduction (from e(l) to Ex,B) It turns out that e(())
Sn,6.B can be further sim-
plified for analytical purposes. We define a new (deterministic) quantity
(2) SR.B
v8 E (s(Y)) plllll2 + pG1 + rrG -xx)))))11) 1/2
min - t
c1.20
which is constrained minimization (Y, G1, G2) ~ Py x N(O, 1) x N(O, 1). The two quantities of interest can be related via the uniform law of large numbers (ULLN) as shown in the following lemma.
only three variables p, and Bg. with random variables
Lemma E.3 (ULLN). As n.d - co, we have
(1)
P.
(2)
SR
SR
See Section E.1.3 for the proof.
(2)
(1)
Step 4: Investigation of the positivity (from Ex.B to
To further simplify the problem,
define the following quantities that are closely related ((2) Ex.
-T + v8 E (s pllll12 P + (2x) 1/2
min $1.220
AR
5x
min
VI -- v8 pllll
1/2
(51)
3C [E[111]
PoER
Firstly, we argue that Ex Sx for constant B large enough, by noticing the optimal (unique) Bo in
=(2) is always bounded by some constant (depends on T, K, n, ||p|| 8). Secondly, notice z(3) can be
viewed as fixing r = v1 - p² in the optimization of of and = Ppp + /1 -V1-//a--- ~ N(O, 1).
The following lemma shows that the sign won't change from z:2) to 2(3)
Lemma E.4 (Sign invariance). For any the following result holds:
(a) sign(s!)) (2) = sign(s ((x)))
(2) (b) E S then Ex
(3)
5x
See Section E.1.4 for the proof.
39

---

Published as a conference paper at ICLR 2026
Step 5:
Phase transition and margin convergence Note the function 8* R + Rzo defined in
Eq. 28) is closely related to ( Let n² sup {K R : 8 (x)) 2 63. By combining the results
from previous steps, we have the following relation.
Lemma E.5 (Phase transition). For any R. > 0, we have
lim P P(,,,x 0) =1
if - (') K5k,,
n-+00
(t.e., k> lim P (( 0) 1, if 8 (k)
n+000
In parficular,
lim PP P((X, y) is linearly separable} = 1, if < (0),
lim P (((X,8) y) is not linearty separable] = O, if (0).
As a consequence, we can also derive the convergence of margin in probability. Notice that the following result weaker than L convergence Theorem D. (c) However, we need this preliminary
result for the subsequent proof of ELD convergence in Theorem E.7
Lemma E.6 (Margin convergence, in probability). ff < 8 (0), we have Rin Lx k²
See Section E.1. for the proof.
E.1.1
STEP 1 - BOUNDEDNESS OF THE INTERCEPT: PROOF OF LEMMA E.1
Proof of Lemma E.1
Recall that
En,K min | <I Val AOER
(KS,,
y 2 X33 - (00)
Let (Bn, Bo.n. be minimizer of the function above
10 On the event Dr n En,r (En,x 0), we have
Th (z,, Ban) Bu, S 0,
if y; +1, if y; 1.
(kSy - y 3 X3 -o, +112 =0, 0,
K. (x,, B,a) + B0,n S 0,
i.dd N(O, Io) and yi 11 25. Then we obtain
Write x; = Vift + 2s, where 2,
8 2 TK (1,, (,, 3a,) (2,,Gr).
if yi +1, if yi - 1,
Bo S - + (H, 3,) - (2r,B,)
which implies for all i such that yi +1, UU +1,3/
1,
1 S |K - 3,) - (zi, B,n! + - (m, + (=5,,,,)
<T + 1)x + 2 (m, 3 + (zz, B + (Zz Ba)l.
Using the inequality (a + (a+b+ c)2 & 3(a² + b² + +²2). we have
18... 12 33 (T + +) 2,)1),,,)) + min
(2,, 2 + min
((23,,,,11
j:w j:s
33
( + (14 3,)1)²
|( Brn
1
Σ
| Bniil
n+
n_ j:y
iig +1
@ 3
((r 1)k + 21 B,,))²
1
Z
f,
122 n_
zz 3m 11
n
(8)
1
1
<3
(
2 21111)2
Z
113 lpp
+
12
2
Bu
n
n_
In general (B,,, Bo.n) may not he unique and may not be equal (B,,, Po.n)-
40

---

Published as a conference paper at ICLR 2026
where in (i) we denote Z+ E R xd a Gaussian random matrix with 2, such that ys +1, Z E R" xd with rows 2j such that yj = +1, while in (ii) we use Cauchy-Schwarz Schwarz inequality, the definition of operator norm, and || l2 - 1.
Next, we show that Bo.n is asymptotically bounded. Notice 2+. 2_ have i.i.d. standard Gaussian entries. According to the tail bound of Gaussian matrices (Vershynin 2018 Corollary 7.3.3), for any in 2 0 such that i, = niv and some absolute constants c, C'E (0, 00), we have
( Bo.n S + + +) + (Vn+ + vd+tt) tx)² 2 + (vn=+Vd+t)
n_
( ((+ + + (c+ Vxδ
2
1 C+ v(1 (1-+))
) Bo,
where (i) holds with probability as least 1 - 4 cxp(-ct2,, and (ii) holds with probability one based on the fact that n4/n > π, n-/n + 1 π a.s. (by strong law of large numbers), and n/d -
as n + Notice the upper bound Bo is a constant which depends on (T, K, llull2, 6). Let
in + co, then we conclude Bo,n S Bo with high probability.
Combining these results, for any B> VBu.
(IEm.. = 0} n nD, n (Bo. S Bo)) C (I5m = n n (13o.n1 S B}) S (5,,.. - 0}. Therefore, by union bound we have
P(En,x 0) P (Em, = 03 n (DA n (B,, n S Bol)) P ([5m,,==0 ( U (Bon Bal))
- PS = 0) + P(D,.) + P( Bo,n > Bo)-
Finally, by noticing En,s S SR,K, we conclude
0 S P( = 0) - PC = 0) s P(D,) + BB..... > Bo) + 0, This completes the proof.
as + 00.
1.1 STEP 2 - REDUCTION VIA GAUSSIAN COMPARISON: PROOF OF LEMMA
Rewrite F; l/if2 + 25, where 2, i..d N(O, Note that yi z, Denote
Proof of Lemma F.2
the projection matrices
P
P : Ia
| pp.
|
where P the orthogonal projection onto s and P,A. the orthogonal projection onto the orthogonal complement of (pan(u). Then we have the following decomposition:
(z) B) y (M, (3) + (z B) yo (3 + (zi, P
P, + (z P 3)
yi g.
/ |laa|12 + 3,
1111122
1
Zi
(zi, P7
= yip ||a1|12 + pus + (z P. P1,B)
where
11
0 B, ||al|22
u, Zi
N(O, 1).
|
Let Q E (n-1l) be an orthonormal basis for the subspace span (1] (Q I,-1). Note that
(z,, P 3) (z,, QQ () (QT 2., QTB) 3) (g.
where
9; = Q 2$ ~ N(O, Ia-1);
g, Il u4
0 := Q 3 E T
|001 v ||.1| | |P < v 11-10 2
41

---

Published as a conference paper at ICLR 2026
We obtain a one-to-one map / (p. 0) in the unit ball. Therefore, we reparametrize
(= B) + Bo d yap || - pu; (g. 0) Bo:
where p² + +100 - 1, and {1ss u4 9:) g:) Fi= are i.i.d., each has joint distribution:
y4 -L 11 91.
Plys +1) P(y 1) x, u, N(O.1), 9: N(O,Io-)).
Now denote
u = (u1,... un) R"
9 9,.) T Rax(d-1),
Therefore, S B == Sn, Sn,,.B defined in Eq.
44) can be written as
Sn.R.
(0)
min
max
(KSSy Oy y x3 Bo1)
[|3 II |
Vd
|a X@y20
min
max
T (nSy ② plall1 y + pu + GO - -B01)
0²+ 01
A
vd
1
Aoy20
++ + |A A Vd
min
max
1
Go + X (KS о y - p plll222 + pp 801)
1
A0020
On the other hand, recall Sa.k defined in Eq. (50):
(1L)
max + || Vd (IAI) 0 11011 h A (kSy O y - -1lllll y + pr Bol)) (Kss
min
Sn,KBB
|Bok ABy20
Note that both minimization and maximization above are defined over compact and convex con- straint sets, and the objective function in <1 is a bilinear in (0, (not Bo). In addition, (3, u) is independent of G, (g, h), so we can apply variant of CGMT (Theorem J.I by conditioning (y, u), which yields for any u E R and t 2 0:
P B,
I v + 2
S 2P
(()
S tly,
P ((0)
k, 2 v t v
s 2P
(1)
2 t y.
Taking expectation over (y, u) both sides of the equation gives for any E IR and / 2 0:
P C.R. Su+1 1) 2P < so+1),
(0) SR.R.B 2 - 2P
Sn,R.B 2 v 10-1) 1).
(11)
which proves Theorem E.2
E.1.3
STEP 3 DIMENSION REDUCTION: PROOF OF LEMMA H.3
Proof of Lemmal
The expression of <..K. can be further simplified
All.S1 Vd (1 + XT (nSS o y - p 1| y + pu 11012 h - :801))
1
S B
+ +01 1 B
min
max
Xoy20
@
min
(9T0+ [|(nsy - pllml112 + pr Gy |10
(00))112)
2 5
Vd
| B
-r |اgllz + |[(ksy p11l112 pr 2 + h Boy) 112)
min
Vā
where in (i) we use the fact
-(1, max (a (a+v*b)
(a11A112 + +Tb)
max max r(a r(a-vTb) rE =
max
SAISSLA20
= -(a+ [[(b) 1g)
42

---

Published as a conference paper at ICLR 2026
in (ii) use Cauchy-Schwarz Schwarz inequality gTo 2 - 1|01|2 و|2 l|gl|2 and denote =101|2- For conve- nience, write the parameter space Ø { r, Bo) p² + r2 1,r 0, 1/ol s B). Now, define
(0))
-r l1gll2 + ||KKsy - p |lal|12 + pu 3 + rhhh o B01) .1122)
Sn,s.B =
(n-r,8))EBn vd
min
|111|
min
(s(vi)): plleel2 puil rh.9 Booss +
(
d n
=: min (p.
( (p,r,
(E Recall that
then Sn,e.B
(2)
+ v0 (sll)== + + 2))
SR,B
min (p
-r v8 (s(Y)s + -8o))²)) 1/2
min
min
f (p, 90),
(p,,80)EBB
- 1] = n,, and G2 ~ N(O, 1). We also define where Y 11 G1 G2, P(Y +1) = 1- =
( 2n (pr, :0) Σ ((())) - p p|lm112 + puyy + rh,y, Boy.)
E, (2,
i=1
Y, 6 (p,r, Bo) E (s(Y)== - --pplllllll p., Y - = E GI 36)]
where E, denotes the expectation over the empirical distribution of {3t, un h,)) In order to apply the uniform law of large numbers (ULLN), note that
OB is compact. (p
r, 8o) + is continuous in Og for each (Y, G2), and (Y, G1, G2) + is measurable for each (p, r, (p))
If G1. G2; r. Bo) S 3 ((K7 |Pll2 + B)² + Gt G3) for all (p.r, Bu) Fg and B[G?) = [E[G)]
co.
Therefore, by ULLN (Newey & McFadden 1994 Lemma 2.4), we have
(oll)) (p,r,, 2/2 - (ol (p. 3o)) 1/2
sup (p.r,9))EBB
(ll (p, Bo) - -6: (p,r, So) 1/2 = op()
sup (p.r.9))EBB
where the inequality comes from the fact that + V is 1/ H/2-Hölder continuous on [0, o.). Then
fu (p. Bo) - f( (p,r,
sup
(p.r,
||9112
sup
+
sup
Vd
rE]-1.1]
(p.r.B))EB
[g 2
(oll)( (6 (p, 1/2
1
+
sup
d
d
Vo
(p.r 1/2
VV
sup
(p.r.8))EBg
(1))
43

---

Published as a conference paper at ICLR 2026
by using n/d 8 and law of large numbers lg - P, 1. Finally, since the function x (z)+ + is 1-Lipschitz, we conclude
(()) S...BB (5 -
EOLN. En.B S
((D) (p.r - (p,r, = o1)
sup (p.r,80)EBp
This completes the proof.
E.1.4 STEP 4 INVESTIGATION OF THE POSITIVITY: PROOF OF LEMMA
((22
(2)
Proof of Lemma
E.4
We claim
SR Sx
when B is large enough. Recall that
(2)
+++ vo E (s l + pG1 + rG2 - -b6)) 1/2
min
20 BOER
Let (p, F,, 30) be a minimizer above and notice pG1 + FG2 - RG, where R = vp + and
G ~ 1). Then
30 E arg min E (o(Y))=āllal))) RG BBY) [+] BOER
11112++ + No + + = arg min { T (TN - 11lall2 + NG - {0) + (1 111-5) x)B (N= - A
arg min (30) BoER
Notice that (g) is convex and continuously differentiable, since
(Bo) = 2x (TR - ý ا|ااا| + RG - -b) + 2(1 T (1= 7 ||11 + RG + [b)+]
is non-decreasing, which is based on the fact that x + [[ + x)) x is increasing. Then Bog must satisfy (Bo) 0. Since (+)x(+ +00, 0 xx, by our construction in the proof
(2) of Theorem E.1 we can choose large enough such that [(22 C.
We can rewrite xx2) as follows by introducing an auxiliary parameter e:
-r+ vo TR [c(Y)s lllll2 + pGr + rr2 -80)) 1/2
min 2,06E
2,20
and we also define the following quantity
-r + v8 E (s(Y)) - pllullb + PG + rG2 (00)) x2 1/2)
((2)
min 24,
0² 1--0++00=00 ,0
(s(r) - + LG + GG ) 1/2
r + v8
min 2
p² 0² + 1. .20
c
Then for any x: > 0, we have the following observations:
sign(E!.)) = sign
(Their objective functions differ only by multiplier e 2
The minimizer in
((2) must satisfy 0² + 22 1
Suppose (7, Bo, 2) is a minimizer in ((2) such that 72 + 72 < 1. We can increase (7, 7, 3o, 2)
proportionally, which results in better solution. That is, define
p
=:=
Bo
30.
ē:=
V +2
72
V
We allow If 0, then p
80 and the objective value in c.00
8( +1--)kk²) > O, and the objective value in (t defined too. Both of them are positive.
44

---

Published as a conference paper at ICLR 2026
then Bo, C) has smaller objective value (because r/c, p/c, Ba/c all remain unchanged, but 18/c decreases since Z), which contradicts the optimality of (,,r, 7).
As consequence, we can simplify
1
11-p2 p² + v0 E (5 + pG1 + VI- -ox) b0x) 1/2)
((2)
min
PE PRR 8g 1,,21
c
- 1 p² + v0 (1 ( -
-6x))))))))) 1/2
min -
MEt - DRR, c
=0=c- 1,,21
where G = pGp + V1- 1111pt p² ~ N(O, 1). By the same argument, sign(Er,) (0) sign(Et") (122) where
- p² + v8 (E (s(r)) - P 1lall22 + +G -
+G-BoX) )x)) 1/2
min
Sx
PE
1.1]
f
(3) Sx )
Therefore, sign(
5x
sign
In order to show Ex
x(3 when =.2
< 0, we define the objective function of E(o) as
SN
Te(p,,, Bo) == -r -r v8 E [<(()) - م lllul12 + pG, + rG2 - (8,) 1) 1/2
:=)
Then it suffices to show the minimizer of Tw must satisfy p² + x² 1. Again, suppose (7, F, (8) is a minimizer of Ta such that p² + 72 < We can increase (p. 3o) proportionally by defining
p =
F 3o:=
B
7 +
12 72
then
Te Tx (p, v, (6) > F Bo),
0
Tr, F, 3))
where the last inequality is because + B[(G qI c2) strictly increasing for any e₁ > 0 and C2 E I. and the fact that x > K. Therefore, a contradiction occurs and we complete the proof.
E.5.
STEP 5 E.6
PHASE TRANSITION, MARGIN CONVERGENCE: PROOFS OF LEMMAS
Proof of Lemma E.5
We define the following two functions:
(p) == - /1 p² + vō [E (s(Y))= p llelll2 + G- - 1/2
(p) = -(1 - p²) + sE (s(Y)) P p11m112 + G
= T [G / ||14||2 - 3o + kx)) )+) [ + (1 - -)oB [G-
(GG-plMut p||m111 + 30 + +n]]]]
p² 1.
(52)
and then
33) min _x
Tp (o),
2(3)
min
Fx
pE|-1.I),8.EB
Clearly, sigu(Tu(p, Bo)) = sign(Fa(p. Bo)) for any p, Bo and sign(E (2) = (g)) Also recall
that
1- p²
(k()) max Hz(p, Bo), Hz Bo) -E1-1.1] RgER
E
(s(())s- - P |11/ + G -- 2
We can see that Hp 36) is well-defined since (({s(Y)) 111112 + G - -BoX)) is bounded away from zero for any / [-1,1] and Bo E IR U (+ro)).
45

---

Published as a conference paper at ICLR 2026
Since - B[(G + c1 + c2) is continuous and strictly increasing for any 01 > 0, 02 R, it can
be shown that both A 5 + _ are continuous strietly increasing, and 8 (K) is continuous strictly decreasing (by restricting 3u : 1Pol S B for some constant B large enough, similar as Step and then use compactness). Therefore, we have the following equivalent definitions of n²:
K" sup {K E R 6 (x) 2 d}
{n T = 6) E (3)
{ F
E =0.
(53)
Now can consider the following two regimes, each with chain of equivalence:
8 S 8 (N)
M
SSA K3
( 2(3) 0
ii)
0
mi
Sm,R.BB
1 (5xx
(2)
i
P(En,x = 0) +
(54)
(3) 2(3) 0
8> (n)
K >
Sx
Sn
0
B B
B
P(En,x 0) + 1,
where (i) is from Eq. (53) (ii) is from Theorem E.4 (iii) is from Theorem E.2 E.3 and (iv) from
Theorem E.1 Linear separability considers the special case O. From definition Eq. 47 for any K < we have En,x = (by taking 3 = 0, Bu = 0). Therefore,
I < (0), by Eq. (54 km 0 and (E,,,,,)) I 0) 1. which deduces the data is linearly separable with high probability.
I > (0), by Eq. (54) K² < O and (E,,,) = P( = 0) + for any & > 0 (as x + En.x
is non-decreasing), which implies the data is not linearly separable with high probability.
Proof of Lemma E.6 I (0), then R² > 0 and S 0. According to Eq. (5)). for any small enough, we have
(3)
Sx
0
P(En,u--e) = -P(En 1,
(3)
Sx* tz
0
P(E = PP = =
Recall that Rú = 11 Sa- suppk E R. Enx = 0}. By combining these arguments, we can see
that Kº -ES Rn S K² + holds on the event D with high probability. This proves Rn P k".
E. CONVERGENCE OF ELD AND PARAMETERS FOR 1: PROOFS OF LEMMAS
In this section, we provide a proof of parameter convergence in Theorem D. d) and ELD conver- gence in (f) for the special simply write ক : Pr. Bg = B Recall the ELD (well-defined version, i.c., Eq. (48) and its asymptotics are respectively defined as
1. For convenience of notation, we drop the subseripts and
Dn n
5 ( (0)
V. Law (V, max(k=; ,p" ||ll|2 + G G ++)))
Here (p", 30',8%.K' x²) is defined as the maximizer of Eq.
33
and obviously se also satisfies Eq 53
Analogous the proof of (Montanari & Zhou 2022. Theorem 4.6), by using the theory of projection pursuit therein, we have the following results.
The uniqueness of (p",8)) will be given by Theorem E.8
Lemma E.7 (ELD and parameter convergence). Consider 1. As d co, have
Wy (Dn, v.) E
The convergence of p P, p" and Bo Pg B are followed by continuity and convexity of H. in
Eq. (28
46

---

Published as a conference paper at ICLR 2026
Proof. Our proof primarily follows the setup in (Montanari & Zhou
2022
Section 4.1) and tech-
niques in (Montanari Zhou 2022 Section 4.3). Recall that we can rewrite 2 = yi + 2;, where
2, LLd. N(O. and yr TT 2;- Using notation from (Montanari & Zhou 2022). P 2,)
op ((p zz), where Ho / |ا1ا| and (zz) = π is constant function. Recall that we reparametrize
P 1..3. Now, define random variables with joint distribution
Y TT G 11 Z,
P(YY +1 G) P(Y -1 G) = ((G) =T
G, N(O, 1).
Let (Y, G. 2) 1T B. According to the definition in (Montanari & Zhou 2022. Lemma 4.2), we have
Law Y, Y. + V (1 z Law (Y,0G + v p %
Law Law(Y, 2)
Therefore, by using MMntanari & Zhou 2022 Theorem 4.3), for any 17 > 0, with high probability we have
w(n))
(1 n (v. (x..( Law(Y, 2)
8
t,,
vō
where "/ is the 77-constrained W2 distance (Montanari & Zhou 2022
Definition 4.1). Formally,
for any 17 > 0, the n--oonttrained W2 distance between any two probability measures P and Q in Rd is defined by
11) 2
(P.Q)= =
inf (vEr()(P.Q) xd 1| 21l2 7(dx dy)
/
1/2
where (P,() denotes the set of all couplings of P and Q which satisfy
Kel, x >)x>>(dx x dy) S 17.
(55)
where e -1,0,..... O)T.
The following proof is analogous to the proof of (Montanari & Zhou 2022 Theorem 4.6). We show the convergence of logit margins W2 f..) P4 first, where
E. = - Σ 8 3)+b)
C. = Law (max kt, p | + G 8YY))
(56)
Throughout this subsection, all the expectations (including the one in Hx,) are conditional on {1,, 2:)) which will be denoted as E.I...]. Now, let
n
6 ()) =: Law(Y', zz),
then by definition in Eq. (55) and the same arguments in the proof of (Montanari & Zhou 2022
Theorem 4.6), there exists coupling (Y, Z, Z,Y', 7') and a sufficiently small r (1) < E44 such that
E jn [V Y') sn.
E i -'Z'- 1/2
VI-
+ 2c
(57)
Vo
holds with high probability. We can express the empirical distribution of logit margins Eq. 56 as
C. n ( + Law Y' + P 1111111 + B,Y
(58)
=.V
For convenience, denote V. = YZ + + || + BoY, then with high probability we have
(R. [(V - D) 1/2 (E. (YZ Y' 1/2 + (E,, (ool(((Y))))) - -Y'))) 1/2 3ol
+ BB
V8
(
P
36,
(59)
47

---

Published as a conference paper at ICLR 2026
where (i) follows from Minkowski inequality, (ii) uses Eq. (57) and |3ol B from Theorem E. by recalling that 5 < 8* (0) and the data is linearly separable with high probability, while in (iii we choose 7 < min / // According Rn E x^ from Theorem E.6 we know that
lim IP
(3, x.) 30) 2 K- -, [m]
1.
Then by definition of V in Eq. (58) with high probability we have K E, almost surely.
(60)
Now, recall 5 (nn)))
, by Eq.
53
where (0",1)
arg wigginp 1.1- HI, (o) Therefore,
(E. In (V 12 S V1 -1
V1 7
v8 +
+ 3
(61)
V H (8))
holds with high probability, For P E 1,,, 30 E R. let us define
h (p, 3o)
/ HHr- (0, V (p' 18)
Note that h (p, (80)= 2 0. Hence, Eq. 66 implies that (reminding T 1) with high probability
(E.p1 - -))1) 1/2 S v 7
1: (0) + 3s
( Hx- (0)
E In (N* م ا|llاl12 + G G -o0 1/2 - -V1- h2 (p. 3o) + 33
[E,nn((x' -)21)"²-V1--P p2 h (0, + +32,
1/2 -
V1
which can be further written as (with high probability)
(E [V 13))) + v p
hi (p. Bo) s (B/r [1x" - v)21) 3E
(1) S
(B. [In= - - -})]) 1/2 + 4e.
(62)
In the derivation above, equation (i) follows from V= V= YZ أ || + +B0y 1 -G + P ||ul||2 + +B,
when conditioning on (3)e, z,) B=) and (ii) follows from the fact that
[m.p [Ix D)2)) 1/2 E. In [xx V)
1/2 1.
dx
(B.1z [(x - D)
Besides, by using Eq. (60) and exactly the same arguments in the proof of (Montanari & Zhou 2022 Theorem 4.6), show that with high probability,
Emj (V maxfx*
E.ja [(k" = v)..] V s E [[V-[[[VVV t)
(63)
Combining Eq. 63) with (62) gives the following implications:
Eq. (63) implies
En [(x" - - 2)2] < 1. [(V-
Plugging this into Eq. 62
yields that with high probability.
2 - (7, 3)) 4e,
i.e., VI Z hig (p, 30) Ps O. Note that if [p| + 1 (i.e.,
the quantity
p 1:- (0) = E [15" p lllll12 + G -))) 1/2
V1-0²
VHa. VHa-(p',f (0',86)
is bounded away from O, for any So E R (+o0). Therefore, we must have h; (p, Bp) Pg 0.
By Theorem E.8 (proof is deferred to the end of this subsection), we know h2- (p, 38) 2 0 for
all p E [-1, 1,.00 3o E IR, and (p, So) + (0",% if and only if h (p, (o) - 0. Hence, we conclude
(0,3)) P. (0",8)))
which gives parameter convergence.
48

---

Published as a conference paper at ICLR 2026
Let
1 [ [VV 1)
1/2 == (n [Ix" - v) 1/2
Then Eq. 62 implies I 11 - 4s, and we also have (for > 0 small enough)
1I S Kk" - El + (L. [v9] 1/2 S K + (E [(G + ا||ماا| + 3) 1/2
S n² + (E(G²)) 1/2 + 1p || + 13c1
S < + + 1ا|| + B,
by using Minkowski inequality and 1,3g| z B (with high probability) from Theorem on these results and Eq. (63). with high probability, we have
E.1
Based
E pn (V max(1e - -,, $ 12 -1-
+ 21I)
< 4 + 2(x** + 1+ |A11 + B))
Ce,
where C' E (0, 00) is some constant depending on (T,, || 5) (through x², B). Therefore, by recalling v - G P illll1 + Boy, we obtain that with high probability.
W2 [nn (max - e, G Alllll + Bo)))) s VCe.
(64)
As consequence, the following holds with high probability:
W2 (Cn, L.)
W/2
pp ||1|| + 86)))
< W2 (n, Lax - G + أ |M| + 8o)1))
+ W2 (Law(max(n" - G + |اl| + (n+tt + 3or)))
+ W2 [La G 2 |ااا (oY)) Law()x( G + p² ||||| ((81))
S Ve + + (1) o1).
where in the last inequality,
that (i) the result from Eq. (64, (ii) the fact that the mapping r> max (1s. G + 111 + Y, is I-Lipschitz, and (iii) the consequence of (p, (P,Bo) Pg (p", (%)
and |p| < 1. |3u1 < B (with high probability).
Now we prove the convergence of ELD. Denote E. =: Law(L'), L. =: Law(L), where (L, L') is coupling such that
(E,jn [(L L')91) 1/2 oz
(65)
Therefore, for some constants C1, C2 > O, with high probability, we have
(2 v.)
< E (Y - - 1/2 (YLL 1/2
5 + (E.jx [(Y L - Y'L) + (XYLL--))) 1/2
< n Ci (E.1, [[ - (r)))) 1/4 (EIL")) 1/4 + (E [[L - -L'>3)
(m
(iv)
I C2v + (1) < (1).
where (i) we use Eq. (57) and Minkowski inequality, in (ii) use Cauchy-Schwand inequality and Y,Y" =11] in (iii) Eq. (57) and (65) while in (iv) recall that 17 < min(s" B/ (1). By taking + we can show that W2 (Dn, v.) P, 0 for T = 1. This completes the proof. O
Finally, we prove the following technical lemma.
49

---

Published as a conference paper at ICLR 2026
Lemma E.8. For any fixed K. E R and T O, the function (p, 9o) in Eq. (28) maximizer (p" (()) E [0,1] R.
admits unique
Proof. For simplicity, write p² : px)), Pu (K).. First, note that
1- p²
Bo) (s(Y)n P pllull22 + 3or)+
|| E (s0l)= + G
+,r)+
which converges to 0 as 30 - #o0. Moreover, (- Bo) < (x 30) for any P E (0, 1]. Therefore, (p, Bo) must have maximizer (p', E [0. R. Further, p² E [0, 1) since H (8)) = 0. We prove the uniqueness of (6) by contradiction. For future convenience, we denote mmax H (p', (8). Assume that there exist (p1: 10,1) and (p2, 20,2) such that (pi, So, + (02, S,,2), and
(x(p1.80.1) (x( 30.2) Hmax.
which implies
P Vmmax
v P2
Ga(
Gx(p2,
V max
where we define
(x) = E (s(Y) |eell + - GG 1)))
Similar to (Montanari et al.
2023
Lemma 6.3), we can show that Gx is strictly convex. Hence,
Gx
P1
P2
0.
30.2
(Ga(PI, (o.1) + (P.2
2
2
1
V p +
P2
Amaxx 2
P1 + P2 2
max
where in the last line we use the concavity of the mapping x + v1 x2_ It finally follows that
P1 + P2
Ba, + S0,2
H.
H Hmaxs
2
contradiction. This concludes the proof.
E.1.7
COMPLETING THE PROOF OF THEOREM D.I
Proof of Theorem D.1
(a) is established by Theorem E.5
Notice the definition (p", x(") we used in our proof (Section E.1. E. E.6 based on
Eq.
33). It suffices to show the equivalence of two optimization problems Eq. (3 and (33). Now
we fix p. Bo in Eq. 31 and X = = + G + Y Then Eq. (31) can be written as
maximize EE
K,
(66)
subject to
X 1 PC sY)),,
E S 1/6.
Note that it can be written as convex optimization problem, and it is infeasible if +1 (since X has support IR). Take p E (-1,1). According to the
(KKT) and Slater's con- ditions for variational problems (Zalinescu) 2002 Theorem 2.9.2), (rs, E) is the solution to Eq. (66)
and only it satisfies the following for some A E L A 2 (a.s.) and v 2 0:
-1 + E[s(Y)A) =0, 0,
-V1 22A A + 2v (a.s.), A(s(Y)=-X v1 ,2E) = (a.s.).
(B =0,
Clearly (otherwise, A 0 a.s., contradiction). Consider the following two cases:
50

---

Published as a conference paper at ICLR 2026
On the event {s(Y(w)) - X(w) < 0), obtain s(Y(w)) -((w) - v1 -1- vI-pE((w) 0, which implies A(w) = 0. Therefore, E(W) = O.
On the event (s(Y(w)) X(w) > 0}. we obtain /--p 2 s(Y(w))) X(w) 0, which implies E(W) > 0. Therefore, A(w) > O, and thus ( -(ww) v1 -1-p2((w) = 0.
(Note PY)(Y) K = 0) = 0.) By combining these, we get v p²t = (s - X) This
proves Eq. 33 Plug into Eq. 31 gives Eq. (33). The proof of p² E (0, and its independence
of r is given by Theorem E.9 in Section
This concludes the proof of part (b)
c < (0): We show that Ri Dg x² in Theorem E.6 E.6can can be strengthened to Ry L k² To this
end, we show that Ri is uniformly integrable (u.i.). Recall that x=33,, Pu..) 2 0 and
k(B Bo.n) = min Ti ((2s; 3rr + B,..) min Ti (v: (1,, + (zi, B,n + 8o.n) iE(n]
xE(m]
-- 3,) + (zi, Bn) + Bo.n) - min (w,, Brr (21, - Bo.m)
min
min 13
Hence, on the event D (non-degenerate case), we have Ri x(B B,,n) and it can be bounded by the average from each class:
k(3 n2 Po.n) ST ((H,
((,, 3,) + Bm) + Bo.n) == R
n Bu,n) S
(m, (Z .B,) Bu,n == Ry
where
2;
Zi.
n2+
n kyy.-1
Combine these two bounds and apply Cauchy-Schwaer Schwarz inequality, we obtain
k(Gn, S
TR + F
2
(
(u, +
2 {
Σヤ - 3mn ) s +
2 Clleall2 + =1
++1
T
7
where
zn
(0,
(
1 1
+ n -
nn y y~ N
innt n
2
Therefore,
2
0 S Rin = Pon 11g S
T + (11l122 + ||anllz 1 l1gn4
In order to prove Rit is u.i., suffices to show that || 122 1ign Sn-1 u.i.. Next, we prove this by establishing that || 11 Ingn converges in L It requires two steps (by Scheffé's Lemma):
1
1
E
E 11
15 Sm-1
+
(67a)
45
1
1-
1
1
|
12 lisn Sn-1
P
(67b)
40
1
For Eq. 67a). Observe
E
| 2 I1 11sm Sn-1 Sn-1 = [[[[EEn1
lign Sn-1 [/]
d + n
1
d
E
+ n
l Lisn 5n-1
4n
To evaluate the expected value, note that (by law of large numbers)
- Disn.
nt 5
2n n4 +1
P
1
2n
P
n4
n4
n4 +
51

---

2 Published as a conference paper at ICLR 2026
A classical result (Chao & Strawderman
1972) gives
2n
2n (1 - (T)
lim E
lim 10000
1-+00
n4 +
(n + 1)
π
So 2n 2 which implies
is u.i., and so is an
1 In-1 Therefore, by Vitali conver-
mi +1
gence theorem, we have a. Hence
115n45n-1 1. Similar arguments give 2. n Lisn+ I-
nt
[(" + n ) 115m4 = 40
lim E
| 2 1 1ign 1ign,sn-1]
= lim n no 4n noc
lim E
n=+00
For Eq. 67b). notice that 12nll2 y an anx where an 2 + 2 By concentration inequality
(e.g.. Theorem J.3 a) we have
1 dan 2 E S 2exp
(-emin
da an =m]]== op(()
c²
-
where e a constant, On = (1), dan P. ( [ By taking expectation on both sides and using bounded convergence theorem, have
||2,|12 2 dan or)) Then we get Eq. 66bb
Finally, Eq. (67ap and (67b) imply that || 112 lish sn-1 converges in L and thus u.i.. So R is also u.i.. By Vitali convergence theorem, convergence in probability of Ri can be strengthen to L convergence.
This concludes the proof of part (c) for 8 < (0).
c > 8t (0): For non non-separable regime, we cannot work with En,x in Eq. (47) to show a negative margin, since R., 2 0 always holds (by taking 3 0, 80 0). To this end, define
C x Boy) 11
Enge := min
(KSy
|ell==1 =1 Vdl R
which replace the constraint || in En by |B1|| 1. Here we define the margin
Kn := sup E R E,,x 0}.
(68)
Note that Ri = R2 on separable data, but RS is allowed to be negative. Then our goal is to show
K, S
(69)
holds for some 0 with high probability. Then followed by the proof outline the beginning of Section E. we can also define a series of random variables a similar way:
1
min A112=1 [X 11 Vd
A
(KSy
X- 301).
|8 B A0g20
((1)
(IAI129TO | n A (KSS
(KSy ② y-yy-aa - p|lu1122 pu Bo1)). pu--)al)))
n,
=
min
||
max
Vd
| XB
(2)
-r V8 E (s(Y))c - p||pll12 + pG1 + rG2 - -861) (o,)) 1/2
K
min
where the constraints || < 1, / 1013 < 1, and - ,2 < in Sn.r. Sn,K, 13 and (22)
(((1)
Sx.B all
become equality constraints. Then we follow the same arguments in Step (Theorem) E.6
Analogous to the proof of Theorem
E.1
we have [IP(E.,. 0) P
0.
Analogous to the proof of Theorem E.2 we can apply CGMT Theorem to connect A. with (0) a
P
(E
(E
st)
2P
- <t)
((1)
Here only get one-sided inequality since ((p. 0) 0² |10 2 1) is non-convex.
52

---

Published as a conference paper at ICLR 2026
Analogous to the proof of Theorem E.3 we have =(0) R,A.B (.)
(2) &
Notice that the optimal in B must be nonnegative. Hence, by substituting v p², (3)
have x.
(Eq. 51) for some B large enough.
Recall that in the proof of Theorem E.5 and E.6 if 8 (0), then there exists Ki < 0, such that 2(3)
Sing O. According to Eq. (54.. for any small enough, by using above relations, we have
E(2)
=0) B (Enote) > 0
S B 0
n. w.h.p.
En,oot w.h.p.
By Eq. (6). Kn < Ko + < 0 holds with high probability (by taking to be sufficiently small), which proves Eq. 66
This concludes the proof of part (c) for 8 > (0).
d
We have shown parameter and ELD convergence for the case 1 in Theorem E.7 Now
for any 2 1, denote (T), (T), (T) as the max margin solution to Eq. (46). and define
(T) = (T))
/
|ell
Similarly, denote p² (T()) (T) as the optimal solution to Eq.
33 By Theorem C.I.
We have
(T(T)) (1,(1)
- =
T + Ri (1).
(70)
We can write
(wn B,) B.)t =: Law (Y'log, ((o',Bn) + (o
(71)
Y'1ps, (k) + (1) Loz + T-
r+1 Rn.(1) +T))R((1)
Law
Besides, according to Theorem E.10
We have
(b()= = (1(1 + T-1
p=())=p(11,,
r+1 R (1).
(72)
We can also write
24 Law
Y max s(Y) (T) 1 [
(73)
Y, Y max n² (1), G p" || + (1)))) T ++1** (1))
Law
We have shown R,, E. (1) and (, P (1)) Theorem E.7 Then by continuous
mapping theorem, comparing Eq. 70 and (72p. it follows that (o, 1. (T) for any 7 > 0.
In Theorem E.7 we have shown that Wz (Dn, v.) = (1( for T with high probability, i.e.,
W2 Law L'L (xx', ((x',,,) + Bo,n 1DE Law YY max " (1). G+ p" ||l| + ()(1)))) =1.
=Una
=
(74)
53

---

Published as a conference paper at ICLR 2026
Then there exists coupling (Y',YU,, U*) such that, with high probability.
5 (1) 9) #
V2) - [1,p (Y - Y)J]) $ In Un U2 T (1)
--
T T
(m (V' r)&)) (R. (Un (= (1),
+ 7 1
(E.jn (Ri (1) n¹ (1))3)) 3
++1
- n² (1) in an) Eq. 74
where in (i) we use Minkowski inequality, while in (ii) we use Ru (1) By taking e + we can show that W2 (2,, v.) P, 0 holds for any 7 >
For TLD convergence, we give a proof of Dhost = plest, Write &new = Vnew f + &nwws knew
N(O, Ia), and recall Sa Law(y"ew, (xreww (Ba) + BB..n). Let G ~ N(O, 1) and G Il yoow, then
now 3am + Bo.n (yuow 4 zuew 2uew, BBa) + Bo.n
= yue Pn ||ee|2 + (zuew (B,)) + B0.n
4 yoe (p" |elll2 + G + new 1%),
where in the last line we use Slutsky's theorem and yoew aL no x new Br, Bo.n). This concludes the proof of part (d) and (f)
e
In f above, we showed that
f( (Ønew, , Ba) + Bo.n 4 Unewp" || + G Bg-
Therefore, by bounded convergence theorem, the errors have their limits
lim Err Err-.. = IP (+p" || + G + Sh S 0) = + (-p" ||1|| 18). lim Err- .n = PP (- || + G % > 0) = + (-p" ||ll|2 + (%)
This concludes the proof of part (e)
Finally, we complete the proof of Theorem D.I
E.2 ANALYSIS OF THE ASYMPTOTIC OPTIMIZATION PROBLEM: PROOF OF LEMMA E.9
We provide an analysis of the low dimensional asymptotic optimization problem Eq. 33 subsection. The conclusion below has been used in the proofs of Theorem D. be also used in Section G to obtain monotonicity results.
this
b d and
it)
It will
For G ~ N(O, 1) and t E R, we define two auxiliary functions
gi gi) = E ((++))+)
g2(() = E (G + 1)
(75)
Clearly both 91 and 92 are strictly increasing mappings from R.. to R Then := 9 is also strictly increasing. The following lemma shows that the limiting parameters (p", 36 : k²) defined in Theorem D.I can be characterized by the following system of equations, involving and gi Lemma E.9 (Analysis of the asymptotic problem). In the separable regime ō < 8* (0), (p", 00",8.K'" k*) the unique solution to the system of equations
P
+ +1 (1- 18--T) (1-7))
P
= p².
(76a)
2T
8
2(1 T) |1lll22 8
Bo + KT = =1111al + g4
p
(76b)
2nT || 8
b + go
P
(76c)
2(1 T) |111112
where p² E (0, does not depend and Kº 0.
54

---

Published as a conference paper at ICLR 2026
Proof. Recall that in the proof of Theorem E.5 and E.7 solution to
established that (p',00. k²) is the unqiue
maximize pe ,
K,
subject to
3o) d.
k)) Let (pp, (0,,,,, (.) = Fr,p, Po), where FR is defined Eq. equivalent to
52
Then the above optimization problem
maximize p pe subject to F(p, (K,,30,00 8) 50,
Note F is convex (since > {x) is convex map, and expectation preserves convexity). Setting
F, = and 0g, F O, we obtain the first-order conditions conditionsssatsttin satisfied by (p", (8)):
E (G P |ll| Bu + +xT)+] 2T || 8"
(77)
E (G |ell + 80 + xx++]] 2(1 T) 1111112
Moreover, we have 8 (x*) = 5 and thus F(p, K, 3o) = 0 at (p", ,=,, (5)) which leads to
TOE [G- p p1lu1 -3 + KT) 0 + (1 - +)oB (G 1llll2 + 80 + x) ) = = p².
(78)
Using 91 92 defined in Eq. (5). the first-order conditions Eq. 77 can be rewritten as
91 (- ||el|| BB + KT) 2T || 8'
(79)
91 (-<0llll 1llll| + Bu + +k) 2(1 T) ||
Similarly, we recast Eq. 78 into
Tōg2 (-p ||l|
So + KT) + (1 T T)692 (-p 111111122 + + x:) = 1
(80)
By combining Eq. 779 and 80
we get Eq. (6a)). Eq. (7bb) and (76)) directly come from Eq. 779
Note that function R2 R satisfies g(++) = 0. As varies from 0 to 1, the I.H.S. of Eq. (6ab increases from 0 to positive number while the R.H.S. decays to 0, which guarantees the existence and uniqueness of p" > 0. Since Eq. (76a) does not depend on 7 and x", we know that p does not depend on 7 and x². This concludes the proof.
In parallel to Theorem C. for the original non-asymptotic problem, we provide the following similar result on the asymptotic problem Eq. (33)
Corollary E.10. the separable regime (0), lei (p" (T), (T), (T)) be the optimal solu-
tion Eq. 33 under hyperparameter r. Then
p' (5(T) (1)
++1 - (L), x²(T) + x1).
2
(81)
Proof. Conclusion for p² is already shown in Theorem E.9 For B5 and x* note that the R.H.S. of Eq. 76b) and (76c) are constants under p p² (depending on |//l// and 8). Then we have
-3)(7) * (B) +1)),,,,,, (T) + +*)) = +**))
Combining these two equations gives the expression of (T(7), x (T) in terms of (1),,, ,) 6* (1) as in Eq. (8T). completing the proof.
55

---

Published as a conference paper at ICLR 2026
E.3 PROOF OF PROPOSITION D.2
Proof of Proposition D.2 We can prove more general result by replacing L with / and L. with Law(max X)), where X ~ lr and μ any probability measure with atomless (continuous) CDF F.. As a special case, in Theorem D.2 we consider je as a mixture of two Gaussian distributions, and the cost function c(z, y) = (x y)²
We now prove the general statement. Note the CDF of v has the form
(t),
ift<'*, i K*.
(t)
1.
According to the optimal transport theory (Santambrogio 2015 monotone) optimal transport map from μ to v is given by T function of is:
Theorem 2.5), the unique (also Fys where Fy is the quantile
F7 (z). K
(x).
if F,(tt)) if 2 (r)))))
(x) = inf (1 E F.(1) 2 x)
Then we have T (=) FF((())) = max n², x), which concludes the proof.
F LOGIT DISTRIBUTION FOR VON-SEPARABLE DATA: PROOFS FOR SECTION D.1.2
F.1 PROOF OF THEOREM D.3
Throughout this section, we assume the loss function L IR Rz0 is non-increasing, strictly convex, and twice differentiable. Based on these assumptions, establish the following properties
of
Lemma F.1. Let E C (R) be nonnegative, non-increasing, and strictly convex function. Then
(a) is strictly decreasing.
(b) ((-20) +o0 and ((+oc) E for some [0, +00).
Proof. Notice that (u) < 0 (by non-increasing) and (1() is strictly increasing (by strict convexity), which implies that (u( < 0 for all u E IR and hence deduces part (a). For part (b), the limits lim E(u) are well-defined, and ((+oo) l for some & [0, +oo) since é is monotone and bounded from below. It remains to show E( (0-oo)= = +oc.
Assume ((-oo) = < oc by contradiction. By convexity, we have E(u) S (((2u) + E(0) for any E IR. Taking + -o on both sides yields < ( + {(O)), hence < {(0), which contradicts the fact that é strictly decreasing. Therefore, we must have ((-oo) +00.
Without loss of generality, assume L = x(+)) = 0. Otherwise, we can just consider é L instead of l. addition, we also assume is pseudo-Lipschiz, i.c., there exists a constant such that, for all y E R.
[(xx - E(v) s L L1 (1+ |a| + ly)) y/.
For case of exposition, we assume 7 = 1, as it is not fundamentally different from the case of arbitrary > In Section F.177 will discuss how extend our proof to general 0.
Recall the original unconstrained empirical risk minimization (ERM) problem Eq. (2a)
M, = min (3, = min BERd, PRER
Σ ()) B))).
(82)
BER BOER
We first provide an outline for the proof of Theorem D.3, which involves several intermediate steps of simplifying the random optimization problem M..
Mn.
Step
Mn O E.)
Step
M
O E.) + (0.. E.) M)(O.)) 7 M
Theorem
Theorem
E3
Theorem FG
Step
(3) e E.))
M
)
Step 4
Theorem
Theorem
56

---

Published as a conference paper at ICLR 2026
Step 1: Boundedness of [ and Bp (from M, to (. Eu)) Notice that by introducing the auxiliary variable (Wi,...,un, un)' _ and Lagrangian multiplier v (U1...., E RR" we can rewrite Eq. (82) as a minimax problem
Mn min BER" B VER* uER
max
1 ((ui)
Us
(vi((a, 13 30) un)
n
1
min BER BOER VER"
max
{(us)
0s 01((11 (3) + (zi, (3 + y: us))
uER"
1=1
where in the second line, we reformulate æ; ye z,). N(O, IJ). yi TT For any closed subsets Og C R x R. Su C I2, we also define the quantity Mr ( Eu). which can be viewed as the constrained version of ERM problem M,.
Mn E.): := :=)
max ( vER" uE
min
E(uG) + al 3) + (z B) + y: ui)
i=1
1=1
1 71
((u4) + -y 1 3) + n
T y 1 vv 2,3 + BUV
1
min (e vER" u
v
n
n
(83)
where Z = (Z.,...,, 2n) E Ruxd Let B0.) be the unique minimizer of Eq. 82
The
following lemma implies that 3,, and 3a.n are bounded with high probability, which enables us to work with M, (O,,, E..) instead of Mn. for some compact sets O and E..
Lemma F2 (Boundedness of B and Bo). In the non-separable regime > (0), there exists some constants Cg. Coo Cu (0, 00). such that Mn (0 Eu) with high probubility, where
3g = ((3,8)) E Rd x R ||112 S SCB, 10.1 S C3ol,
3, = {u R.: ||u/|2 S C.
See Section F.I.1 for the proof.
Step 2: Reduction via Gaussian comparison (from ( E., to M O E.)) The ob-
jective function of M, (0), E..) in Eq. [83 is bilinear form of the Gaussian random matrix Z. To simplify the bilinear term, we will use the convex Gaussian minimax theorem (CGMT), i.e., Gor-
don's 's comparison inequality (Gordon 1985 Thrampoulidis et al. 2015). To do another quantity:
introduce
M O Ew)
min (0. ueE..
max
Σ (lu)) + 1 72
+ l|vl2
h
1 B 3+
||
gJv Tv
vER*
n
n
1 Bov y
1 vT n
n
where h ~ N(O, ~ N(O, I.) are independent Gaussian vectors. However, the classical CGMT cannot be directly applied to M! (θ Eu) since v is maximized over an unbounded set. To this end, proved the following version of CGMT, which connects M ( g. Eu) with M,, G Eu). Lemma F.3 (CGMT, unbounded for maximum). For any compact sets O g and Eu (not necessarily convex) and E R, we have
P (M, E..) si) 2P (O,, E..) si)
(84)
Additionally, if @ and E. are convex, then
P (Mr Eu) 2 2) 2P [ (0 E.) 21)
(85)
See Section F11 for the proof.
57

---

Published as a conference paper at ICLR 2026
Reparametrization in low dimensions (from M. (1) p, En) to MI (Q.;..)) M (03. Eu), we consider the following change of variables
To simplify
p cos(p,, =- {IlAIs |aall2"
B ||
if 0, if 1f=00 0,
R : 11122
(86)
Now, for any closed subset θ C [-1,,]] x Ryo x R, we define the quantity (0 E.) by
1
1 v 1 B)
M 10 Eu) =
min (3.6)) XR: (oos(1,)))112 2 e. u
max VER"
e(u,)
|/ 12 h
n
n
i=1
1 |8 v + n
1
1 v u Bov y
n
n
Therefore, (0,, E.) can be viewed as reparametrization of M, (1) R takes the form
p _..) when Og C RR x
+ 3 {(8, [6) E Rd x R: (cos(H, 3), ()) O.)
Then can simplify M,
(+g M E.) as follows:
2) (O,, E.)
E(us) + 2e R1 + Rg + Boy - u) + 1
min
min
max max
R, e neE,
||@|| 720 |voll2=1 3))
71
1 12 E(us)
(i)) min ( e ng
2 1| ||lell R1 + Rg + Boy u/12 + 2
min
max
|| R
720
n
n
n
cos (1
min (p, R...f.) e
max 720
((.)) + 1110 |all R1 + Rg + Boy u112 + 2 min
h 1 3
71
|| 2
=)=
(v))
((u,) + - 1llo 2|ll|2 R1 + Rg + Boy - -ull2
min
max
(p, E 720
11 1=1
ncE,.
h h-u
1 R +
VI- (IPAAl))) |
(87)
where in (i) we apply the change of variables Eq. (86) and optimize v by its length and direction inequality, (iii) is from the linearity objective
Vo separately, (ii) follows from function in y, and (iv) is based on direct calculation by decomposing B:
(p
h 4
min 0113:1191 1=11
hT B
h
min |0 BERd
h
1
+ /1 /1-pp0) P [1/2
-1- p2
[111122
(0s(p.,))p
(m.0)=0
where P Ia Mnl
Step 3: Convergence in variational forms (from M ( E.) to M O E.)) To proceed from Eq. 887. we adopt the following trick from Montanari et al. 2023). where u could be viewed as functional of the empirical measure given by g (g).... gn.) ) and y ( yn)" For- mally, let Qn be the empirical distribution of the coordinates of (g. y). i.e., the probability measure on I defined by
Qn
58

---

Published as a conference paper at ICLR 2026
Let Q2.): R2) be the space of functions U IR² + R. (g. y) + Ug.. y) that square integrable with respect to Q.. Notice that the n points that form Qn are almost surely distinct, and therefore we identify this space with the space of vectors E R". We also define the two random variables in the same space by G(g.y) = (gg = Denote Be.,, || lle. the integral and norm with respect to Qn in (Qn)...e.
Eqa 12:1U]== := /
Ulg.y)
1 Ulg.3). vc),
|1 (Bo, (121)2/22
g2
Let w. S (Q2) be the corresponding subset identified by E. C IR"", that is,
E = { (Qn))
u : (U(g), Ugn, un)) E E
Then with these definitions, we can rewrite the expression of M (O., E.) as
1 O0,, 3.) (p.R, 720 UES.
min max
[q.(e(U)) 3/ 1111ا111 11l1l2 R RG BoY - Ulle.
+ 7 P h p1 1111P//
|||1112
n
min (,, DEEWNN
min
Eq.. [((Ui)]
where we define the (stochastic) subset N₁, (p, R. 90) by
No. = { (UE (QEC)(Q.): |llllll R + RG + 3,Y - Ulle,
R (VI
- h" 4e
< Vn
P
|14|
(88)
It can be shown that as n, d + 00,
R
h #
RVI- p²
p2 h
D
V8
This convergence then motivates to define another quantity
M (w),
min (p, DEEuni
min
Ba. ((U)),
(89)
where the subset No = No Ro) is given by
RV1 2
No (E : R RG + BoY Ulo,
S
(90)
vō
The following lemma shows that M and M, (3) are close to each other:
Lemma F.4. For any compact sets O C [-1, x x R and E. C B (not necessarily convex), as n oC, we have
M (2) (0., (0., Eu) M (3) (0 E.) B.
See Section F.1.3 for the proof.
Step 4: Asymptotic characterization (from M (O., (.., E.), MM (O.) to (O.),,, M*) For any closed subsets θ C [-1,1] x R20 x R, we define the quantity M.(3)
(3) (0.) by
M n
(3) ( == min (o UEN!
min Eq, [((U)]
59

---

Published as a conference paper at ICLR 2026
Compared with Eq. (89 clearly Mn (O.: E _ (@.), we consider the change of variable 12
Mn (O.) when En is large enough. To analyze
P plluel2 R + RG + BoY - -U
<
RV p²
Then have
Re. [(p R RG + BoY RV -2)-
=
min (o.
(2.) $1/V8
Denote Qo := IP the population measure of (G,Y) (so that (G, N(0, 1) Ps under ! Qoo. and we have EQu.. E. ||U|le_ (B( Then we also define the asymptotic counterpart of M (8) (e.) by replacing Q. with Qoo:
M (+.)= =
min (..
((p |l/p R+ RG + BoY + RVV--PP)
(Qx) $1/V6
The following lemma shows that M (3) (+ converges to the deterministic quantity M (+.):
Lemma F.5. For any compact subset O C [-1, x Rzo x R, as + co, we have
M (..) E (0.)
See Section F.1.4 for the proof.
Finally, combining Theorem
F3
F.5 we obtain the following theorem.
Theorem F.6. Consider any compact sets O and E, such that Og has the form of
3 = (3. E Rd
R: (cos( B), || Bo) E 2c}
(91)
for some compact domain O [-1,1] R20 IR of (p. R. 30). Assume E., is large enough. Then, for any & > 0, as n + 00, we have
IP (M, E.) S (..) -) +
Further, if both Og and Eu are convex, then
M0 P, M (Q.).
Proof. According to Theorem F.4 and F.5. we have M (0 E.) D M* for any compact
sets O [-1,1] |R>0 x R and E n large enough such that E. C Ná. When O takes the
form Eq. 11 by CGMT Theorem
F3 for any 0 we have
P (0 E.)= < ( -e) $ 2P
M (O.. $ -E)
= 2P (O, E.) & ().) -6) =-000
If both 3 and En are also convex, then similarly show that
( E.) 2 (0x))))))))))) + < 2P (M O., E.) 2 (*.) +6)
0.
Combining these implies M, E.) D, M M* (+.), which concludes the proof.
We will show in Theorem F.11 later that the minimizer of (())(e)) the change of variahle can be defined
(G.) must satisfy RVT p² 0, hence
60

---

Published as a conference paper at ICLR 2026
Parameter convergence
Next, we define M == [] R20 R) to be the unconstrained optimization problem Eq. (35). i..,
M PEl (EC (. $1/V8
min R.20
(e((lllulla R+ RG + BoY RV - 1V1-)())
An analysis of the Karush-Kuhn-Tuukke (KKT) conditions shows that M has the unique solution (p", R², - with p² E (0, R E (0, and 3g E (-oo, oo). Combined with Theorem F.6 it implies Mn. 4 M which leads to the convergence of parameters:
Lemma E.7 (Parameter convergence). As n, oo, we have Mn. D. M*, which implies
3
13,122 & R",
Pn
1
D p",
8o,n 2 36
113
||
See Section F.1.5 for the proof.
ELD convergence Finally, to establish the ELD convergence, we use a proof strategy similar to that in Theorem E.7 by first defining the following measures
2, =
L. = Law (U*) = Law (0" || R gY + R R'V1 - p²2g").
n 2m1
Let Bw, (e > 0) be the e- ball at C., i.e.,
Bw,
u uu EUER: W2 8 L. < <Ej.
Then by showing that
lim P (M.( Biv, (8)) Mn) =1,
we can prove the convergence of logit margins (2(Cn, L.) Pg O, and hence the ELD convergence.
The result in summarized in the following lemma.
Lemma E88 (ELD convergence). As n. + co, we have W2(Ln, L.) Pg and W2 v.) P4 0.
See Section F.1.6 for the proof.
F.1.1 STEP - BOUNDEDNESS OF ,3 AND 3p: PROOF OF LEMMA F2
Proof of Lemma F.2
We first assume 3 + 0. By Theorem D.
i > (0), there exists k e [n]
and constant
0, such that
3o
yk
2k ||
(92)
||B1|
holds with high probability. Therefore, we have
((0) ((,,((,,, B) + +) Bb)) ( l (( B) 3)+ Bb)) (1))
where in (i) we note that (0,0) > R2 (3, 3n) = M,, in (ii) we use 8 0, and in (iii) we use 92
Clearly the above inequalities also hold for 3 0. Notice that ) (((->]B11) which contradicts E(0) < +oc Hence, it implies || is bounded with high probability.
+oo as ||ا||| + co,
Meanwhile, let j. k E [n] be any two indices y +1, Uk 1. Then 3 + +oc, we have
e(0)= 2 (vi((x, 3) + Bo)) 2 n
1 e((22, B) + Bo) + n
1 (((-(xx,)) 3 - -B) - +00,
61

---

Published as a conference paper at ICLR 2026
which leads to contradiction. So [bu] is also bounded with high probability.
Finally, in the minimax representation of M,, the optimal u must satisfy u, = ( 3 Bo) for all i E [m]. Therefore, according to the tail bound of Gaussian matrices (Vershynin 2018 Corollary 7.3.3).
|اا|| yy ① X 3 = 3), + zB + Boull
S villa|al188+++1//001//1881111 vol3ol
s ( (1) VnCp.
VnCa
with high probability, where Cu > 0 is some constant. This completes the proof.
F.1.2
STEP - REDUCTION VIA GAUSSIAN COMPARISON: PROOF OF LEMMA E33
Proof of Lemma
P3
For N,,, denote Km {vv E R ||vl|2 m), and define
1 Σ ((us) + 72
1 B) + --V + -B0
1 -v u y
M, (0). Eui Km)
min
max
( vm uE
11
n
"
n
1 Σ ((us) + v 1 u4. B)
1 +
(0 Eu: km) =
min ( vekm
max
|v|| hT 3
|| g g'v
uEE..
i=l
1
1 V u1
vov
y
n
n
We first show that
lim Mn (0,, Eui Km) = Mn E.). m 000
To this end, note that for any fixed (B, So, u). by Cauchy-Schwer inequality we have
1 ((u:)
+ - B) 1 -T_
-. γ
1 v u
max vEKm
n
72
n
n
n
(luz) - u mn, 3), - 233 - Boy
(93)
Let (9(()) _f6m)) mm)) be the minimizer of (0 E.; Km). Since 8 know that
(m) (1,,3((0))1 - ((m)
< (n E.; Km) S Mn (0 E.)
E.)
(H,, (mm))] Z 36m²) < -0, E..) u (m)
Let u' : (1,, ((m))( + mm + _(11)) y, then we have
u (m)
u'
<
1
M,,
(94)
m
62

---

Published as a conference paper at ICLR 2026
which implies that (u!m)
(m)
uo,a )
u' =(u4 =(u))...;u/))
n Σ ((x)) (e,,3) + (z:. + -3:30 - -u, 0, [n]
Mr, ( E.)
min
(E En
11
n
1 n -
n
((u)))
a(u
(m))
(((!a)) {(u())
12
n1
12
IAB
+
Cl
(m)
u'llı
n
(m)) e(u
+ On
S Mn 3. Km) + Om
1
where (i) follows from the aseudo-Lipschitnee of the compactness of Eu. and Ct > 0 is some
constant, (ii) follows from Eq. (94). while (iii) follows from Eq. (93). This proves that
lim (, Eu: Km) Mn Eu).
m +00
Similarly, one can show that
lim M (0 Km = (0, Eu).
Now for any fixed m, applying Theorem J. a yields that 1 E R:
M, Euj km) st) s 2P (0,, Eui Km) st).
thus leading to Eq.
84 (by continuity and using the two limits above)
P (M,, (0,, (.), 5 lim F (M ( E.j Km) 5t
2 lim P M (0, Km) S 1) 2P M (0,3. En) s Further, if O 3 and B, are convex, Theorem (b. implies that
m-
PP (M, E.; Km 21) 2P (M,' E.; Km) 2 1).
Sending m + oo similarly proves the other inequality Eq. (85).
F.1.3 STEP CONVERGENCE IN VARIATIONAL FORMS: PROOF OF LEMMA F.4
Proof of Lemma F.4 First, by definition of M and M
( M ( E..) 100 (3) (O., E.)
sup (o.
min U.E.
Ee,, I(U)) min UEE.r
Eg, [((U)]
For any fixed (p, R, Ro) E Or. by definition of Nr, in Eq. (88) and AE in Eq. 99). we have
min UEE.NN
((())
min UEEWNN
Eq. (e(U) S
max NW, I -U- (t.
EQ. [((U)) Eq. [((U'))
where
R
P h 1
En (p, R, =
VI -ー VI h1/l
Vn
v8
By our assumption that e is pseudo-Lipschirz, the following estimate holds:
< 1 Σ (((()) - l(u4)) N L Σ (1 + |u.1 + |241)/4 2/il
Eq. [e(t)] - Eq. [(()']]
T Ulle. + 10 IIU U'ka. C(1 or)) en R,Bo):
63

---

Published as a conference paper at ICLR 2026
where (i) follows from Cauchy-Schwarz inequality, (ii) follows from the compactness of N and c, and the upper bound below:
||lllll2 R+ RG + ll + RVI-pt - p²
110|,.
sup (o.R.5))EO.
vō
Riaax
S p || Rmax Rmax |Glleg. + mo, ||x||
v8
Rmax vō
||ee|l|2 Remax Rmax [1 + (1)) ma,
by denoting Rmax R.. R, Bo. R.))EE |Sul, and C is some
constant. Here, (+) is from the law of large numbers: Combining these estimates, we finally deduce that
||G|o. & ||G||a.. = (E(G2)) 1.
M (0., M Em)
S CC(+ oz())
max (O.
En R.
R
h 4 P hll2 - ||11112
p2
=((++0g(1))
max (o)EE,
/
p²
R
vn
vō
1
h Hl|
cc( R
+ nt
P O.
vo
||
The convergence in the last line follows from
hll2
[P 1212
vd-
h l 2
P
|P
A
Vn
V0
n
l2
according to Theorem J.3 and
plop 1,
||F
Vd
I. This completes the proof.
F.1.4 STEP ASYMPTOTIC CHARACTERIZATION PROOFS OF LEMMAS H.5
F.9
We need the following auxiliary result, which studies general variational problem for both = Qn and Q = Q with parameters (p. R, 30) fixed. In particular, we are able to express the random variable g by (p, R, Bo), (G, Y), and an additional scalar (Lagrange multiplier). Then, we can rewrite M (3) (Qe), (*...) as dow-dimensional convex-concave minimax problems.
Lemma F.9. For any fixed parameters P E 11,, ) R > 0, 30 E IR, and the probability measure Qn or Q Qoo, consider the following variational problem
S, (Q)
min Rc(S),
Ra(E) R.g [(0ll1l22 R RG BOY RV1-
(95)
(a) Ra(E) has unique minimizer 8" = Eg (p, R, 3o), which must satisfy
X
So Ro)
ll (proxxx((elllx1)) R RG + +YY)),
(96)
RV1
where X" is the unique solution such that 115/12 1/5. As a consequence, we have
Sp,R,20 (2) Eq [e(proxx-e(P |lll RG +,X))),
where p and ex*E are the proximal operator and Moreau envelope of E defined in Sec- tion Moreover, a decreasing function of 6.
(b) With change of variables A = Rp, B == RV1 p². the variational problem Eq. 95 can be recast as R. (Q) sup,>0 2 ( [A, 3o), where
3,(,
e B, (b) = Bv
+ Rd ee (All1al22 + AG, + BG2 + BYY B)
25
64

---

Moreover, Bu,(AA,,,B)) is Published as a conference paper at ICLR 2026
and (Y, G1, G2) Pa 1O, N(0,1) under Q
13 Que convex in (A, B, Po) over Rş0 x Ryo x R and concave V.
Proof. For (a) we first show the existence of a minimizer. The proof is a standard application of direct method calculus of variations. Since is lower bounded, we know that
inf SECa( 2516
Bo(E) -C.
Let (5m JmeN E (2) be a minimizing sequence such that l1 11 $ 1/6, and
inf lim Re(Sm)= (ECIIII R2)
Since (Q) is Hilbert space (and hence self-reflexive), Banach-Alaogli theorem implies that [5m] has a weak-* convergent (and hence weak convergent) subsequence, which we still denote as [5m] Let 5" denote the weak limit of {fm); ). By using Mazur's lemma, know that there exists another sequence {&m mEN, such that each 5,, is a finite convex combination of (&x Immmskkm (N(m)= 2 depends on m), and that S. strongly converges to g". Now since Rg convex (this follows from convexity of and the fact that integration Eq preserves convexity), we have
lim inf (C( S inf (E(
inf Bo(E).
(ECT(Q))11133///
On the other hand, Fatou's 's lemma implies that
Re(5") S lim inf Ro(( m 300000
This immediately leads to
BQ(E") (EC*(Q) 121//8
inf Ro(E).
ie.. 8r is minimizer of Ro. In order to prove uniqueness of the minimizer, will show that a (2) + Rzo is strictly convex. For any a E (0, 1) and E2, E (Q)), with a shorthand V = 11|ا||| R+ RG + BoY, notice that
Ro(aci + (1 a)
= =Eo [e[[e((V + RV/1 p2 + (1 (1- +
S She (ae(V + - -
+ (1-a) RV P (1
where the inequality follows from strong convexity of l, and it becomes equality if and only if Q(Ei 22) 0. Hence conclude Bg strictly convex. Since {e ||El| < 1/0} is convex set, implies the uniqueness (Q-a.s.) of the minimizer g*.
(KKT) and Slater's conditions for variational problems (Zalinescu 2002 Theorem 2.9.2). & is the minimizer if and only if, for some scalar (dual variable), the followings hold:
As a consequence, the unique minimizer is determined by the K
U D=pl|u| R RG BAY RR PTC,
((()) + vr
(97)
E - 8-1 0,
w v 0,
V - 5- 8-1) = 0.
We claim that the KKT conditions imply that any minimizer& and its associated dual variable must satisfy
O< oc, <> 0 (Q-a.s.,,
To show this, we notice that RV1 - x² >>> 0 and & is decreasing. Therefore, for any L Re(E) 2 Zo((E)). implies that _ 2 if the minimizer. Hence, by stationarity Eq. 197
"According to the change of variables, we have relation AG1 + BG2 à RG under Q = Do.. We can also construct the realizations (Gi vi). G2lgi, 1)) such that AG, + BG2 RG, Qa.a.s. that is, AG, (gi, vi) + BG2(g. vi) RG vi), for all E [m].
65

---

Published as a conference paper at ICLR 2026
-U) > O, which implies the positivity of S. Then ||El|o 5-1 comes from complemen-
tary slackness in Eq. (97). To show must be finite, notice that +00 implies e' (U)
Then U + -0 since strictly increasing, while it contradicts ç > 0 and ||E|| =8
By change of variable À == RV1 1- p²/v, now we can rewrite KKT conditions Eq. 997 as
U AC) - - 1| R + RG + BOY,
O<λ<,;
(98)
where & and U are related by
5 = RVI ((U).
(99)
Notice that Eq. 98) has a unique solution for U. since x + x + (z) is a strictly increasing continuous function from R to R, for any oo). Then, according to Theorem [.5 U can be expressed by the proximal operator of E,
U = proxxee |1 R + RG + BoY).
(100)
Combine it with Eq. (99) gives the expression of 5- in Eq. (96). To establish the uniqueness of X, show that y satisfying Eq. (97) must be unique. Note that {(v) is determined by
DE(v) + e' (p (pllullg R+ RG B0Y RV (r/I-p"((v)) 0.
p²((v))
Since v, ((v) > O and l' is strictly increasing (by strong convexity), we know that {(v) is strictly decreasing in v.. The uniqueness of y immediately follows from the condition [|É(v) = 8-1 This also implies that {v) > O is decreasing in 5. Then we conclude y is increasing in 6, or equivalently is decreasing in 5. This completes the proof of part
For (b) as a consequence we have
R, (Q)
min
Ro(E)
min
EQ [(pllpoll2 R+ RG + B,Y + R
min sup EQ
R
B,Y R (2E) + RV p²
v
1
(E)*(Q) +20
8
1
sup min 2
EQ
((pll1ll2 R+ RG +B
+ RV 1²
g²
2
1 E(U) +
R2
p²)
sup
min A (Q)
EC
(U ppllll R- RG BoY
2X
2X6
R1 (1-11p p²)
n sup
Eg le (p |1l12 R RG + B,Y;
X>0
2X8
where (i) comes from strong duality in part (a)
(ii) is by change of variable U == p 1|ll|12 R+ RG
Y + RV- 1 Φåg and X R / 1 - /² (iii) is from the definition of Moreau envelope Eq. 1144.
Now, consider change of variable
= Rp,
B T-RVI-PP p², == - p/1
Note that 0 <<< do by part
(a) then So. R,00 (Q) can be expressed
R, 8o
min Rg(E) sup 3 Lr ( (A, Bo).
(Q)
where
Bv + B3 28
B // es (e AG. + BGg B,Y;
(v.o(A,B.o)
Finally, we complete the proof by the following arguments:
66

---

Published as a conference paper at ICLR 2026
L,.q(A, is convex in B, B.)). It comes from Theorem J.5 that (I, ee(x;; is convex, and the fact that integration Eg preserves convexity.
Rv,e(A, B, Bo) is concave in v. This comes from Eq. 174) that
er (A [A|p + AG1 + BG2 + BoY;;
min {(t) + (All + AGI + BG2 - t)² ER
V
2B
with the fact that pointwise minimum and integration Eq preserves concavity. This concludes the proof of part (b)
Then we can use Theorem F.9 to show convergence M2 (e.) D2 M (0)) in Theorem F.5
Proof of Lemma
F.5
RV1 p² defined in Note that f (p, R, 30) + (Rp, RV p² 30) is a continuous map. Then
Recall the change of variables = Rp and
Theorem
b)
f(O.) 20
R Rz0
IR is still compact. Hence, by Theorem F9 we have
( (..)
min
sup L B. (A, (*)) min (A.B.B)))((.)) v>ū
sup uu (A, B, Bo).
(A)
For any fixed A, > 0, .0 R. 0, by law of large numbers,
Bv
B er (A [Alll + AG1 BG2 + B,Y; 7
RvQQn (A, B, (b)
+ Eo.
28
P, R Ru.2. B,
Bv
+ E
er (A |all| + AGI BG2 + B0Y; [
B
28
Recall Ry v. Q. (A, 30) is concave in v. Also, note that Ru, (A, B0) -00 as v/ OC, since
by Theorem
(.5(a) we have
B lim E el Alllll, + AG1 + BG2 + BoY; - 400
= E (EAA |M||, AG1 + BG2 + Bo\)] < oo.
This implies there exits 7 E Rs such that sup=27 v.. (A, B, (0) sup Ly... (A, B, Bo). So, we can apply (Thrampoulidis et al. 2018 Lemma 10) and conclude the uniform convergence
sup S. v. (A, B,) =>D
B sup Au.o (A, Bo).
v20
Recall that both sup,so G. (A, B, 3n) and sup Lu. (A, B, 90) are convex in (A, B, 90) (since pointwise supremum preserves convexity). Then we could obtain uniform convergence on compact set f(O.) by convexity (Liese Miescke 2008
Lemma 7.75);
M (e.) - M. <
sup Br. (A, - sup Be (A, B,))) v>0
Pg 0.
sup (A.
This completes the proof.
F.1.5
PARAMETER CONVERGENCE, OPTIMALITY ANALYSIS: PROOFS OF LEMMAS
F.7 F.10
E.I
Recall that
E (e R+ RG + BYY + RV1 - PPE)
M
min PE]-1.1].120.666 (EC'
(101)
$1/Vi
where Rt 3o optimized unbounded sets. The following lemma shows that any minimizer R" B3 of Eq. (1OT) must be bounded.
Lemma F.10 (Boundedness of R and (g). Let (p", R 5") be any minimizer of Eq. 101 Then in the non-separable regime (8 > 8th (0)), we have R < and 18 <c..
67

---

Published as a conference paper at ICLR 2026
Proof. We first prove the following claim: There exists an > 0, such that for any (a, E Rso x
satisfying a² + b2 1, any p [-1, 1), and any E L (Qoc). l1 1/voo
IP ap 1ll2 + aG bY + +avi- 02c 26.
(102)
We prove this claim by contradiction. Assume is not true, then for any m E N. there exists the corresponding (Am, Dm Pm:: 5m) such that (am, dm) RRs x R, with ag b Pm [-1, and Em L (Q2o), llEmlle= S 1/v6, which satisfy
amPm ||el||2 + am G by + am v Pm S
(103)
m
m
We can always assume that (am: dm Pmn.) (a, p) and 5m & weakly in L (Q)=)) when C0. Otherwise, such a convergent subsequence always exists according to Heine-Borel Theorem and Banach-Alaoglu Theorem. Therefore, dmpm ||ea|12 + am + bm Y + Om /1 - p S. weakly
converges to op ||el|22 aG + bY + a aavaa-ia 0åg in (2 For any nonnegative Z E (Q,o), one has
E
(apllullz + aG bY + aav - -P)))
lim TE (amPm llee|22 + am G + bm Y + am / Po (m5m) )z)
10000
Denote Um == am Pm | + G+bm Y +am v Pro... then we obtain the following estimate:
E Bl D = Um Lu 2) + -Um.
2
E|Z| 1)(
1/2 (EIZ² SoIIzLunm--11 Lum5-1/mm) 1/2
where the last line follows from Cauchy-Schwarz inequality. By definition of Um. we know that E[U is uniformly bounded for any m N. Further, since Z E C² (Q2o) and P(Um S -1mm) s 1/m + 0 as m + oo by Eq. [10).. we know that
+ 0. It finally follows that
E (ap 1| + aG bY + sav1 p P²) = lim E 7 2 0.
m-000
Since this is true for any nonnegative Z E (2 we know that
ap |llll12 + aG + by + +a 2 20, 0, almost surely. or equivalently, there exists (p. R, Bb) [-1, x R >0 x R and & (2(.)) < 1/8 satisfying
Rp |||l|1 + RG Bo RV - 22 2 0, almost surely.
It implies the constraint of the variational problem for the separable regime (SVM) Eq. 31 i.c.,
|| G SY + / P 2 holds for some k 2 0 (with change of variable 3 := 3o/ R). According to Theorem D. b) we obtain x² 2 or equivalently S 8* (0), which contradicts the non-separable regime
8 (0). Our claim Eq. (102) is thus proved.
Now for any (p, R, 8o 5) such that R > 0, denote
1
Vp,, 3o.
/R² R2 P/ (p||u|| R+ RG + BoY + RVI-
We know that (V, R, Go, 5) S -)) 2 e by Eq. 102). Therefore,
E ((pll1l1 R RG B RV 1 pZE)
((Vie= + +.3 V(p, R R.,
((VRR + (p. R. Bo, 3) IVGOR
2 El (eev-v R2 + 18
which diverges to infinity R2 83 xo. This completes the proof.
68

---

Published as a conference paper at ICLR 2026
A direct consequence of Theorem F.10 is that M* (+,) for O large enough. The following result shows that M in Eq. (IOT) has a unique minimizer.
Lemma F.11. Consider the variational problem M defined in Eq. (10T)
(a) M has a unique minimizer (p", RR,, f0.5") which must satisfy
X
= - RCV1- p²z ll (proxx- ||12|l2 R + +
where X is the unique solution such that B|5=2 = 1/6. As consequence, we have
M IE [p =(o" || R + R'G + -g)))
(b) (0", R Po X²) is also the unique solution to the system of equations
Rp
[e' (proxxe(p 1114|12 R + RG + B,Y))],
A5 M411
R
(C'oo 1| (plloxx(lllllll22 RG + &]
A5
(104)
0 = E 1114412 R+ RG + B)))
R² p²)
E (proosee (1llll2 R+ RG + +XY))))
X
where (0", R Po X*) E (0, x R0 x R x R30-
(c) With change of variahles A Rp. B R p², the original variational problem Eq. (1II) can be reduced to the following minimax problem
Bv
ex (Alllll2 + AGI BG2 + BOY: }
M
min sup A20,B20 VSU BoER
+E
25
where
~ Py N(O, 1) x N(O, 1), and the objective function is convex-concave.
Proof. We first show the optimization problem Eq. 101) has unique minimizer. Since its original formulation non-convex, we make the following change of variables:
A Rp, B : R p
{B B
(105)
Then, the optimization problem is recast as
B
min E, (Q.))
E [[E(Allul) + AGI + BG2 + BoY + +EA)] subject to llEal S (106)
Vo¹
which convex, where (Y, G1 G2) 1(O x N(O, (recall that AG₁ + BG2 - RG).
Now show that the above optimization problem has unique minimizer. Note that Theorem F.10 also implies that any minimizer of this optimization problem is finite. Therefore, a similar argument in the proof of Theorem F{ a) shows that Eq. (T06) has a unique minimizer. Since the mapping (p. R) + (A, B, BB) is one-to-one, this also proves the original optimization problem Eq. 1011 has unique minimizer.
As a consequence, the unique minimizer is determined by the KKT and Slater's conditions for variational problems (Zalinescu) 2002, Theorem 2.9.2). (A, B, Bo, {B) the minimizer of Eq. (166) if and only if, for some scalar V/g (Lagrange multiplier), the followings hold:
A ||ll|2 + AG1 + BG, + BoY + + U,
((C(U)(()))) + G1)] = 0, B
[[((U)G2) - VB 3 O,
(107)
([((U)Y] = 0,
((U)+ + MBLB = O, 6 E < B2, UB 2 0, up (5 E5 - B²) = O.
69

---

Published as a conference paper at ICLR 2026
Using similar argument as in the proof of Theorem F. a
can also show that
0 < VB < 00,
{B > 0 (a.s.),
B = B²/ 16.
which implies B > 0. Plugging this into Eq. 107 solves two conditions
B
E [(C()))
[[e(U)Y] =
(108)
x.
By Stein's identity, we also have relation
E [[()G = A ((((
= =[((()))=BB(((()))
Combine the above with Eq. (107p. obtain
A
E [E(U)) -BB
B[e(U)Gi] un B[C(U)Ga]] = uB
vn
|
which is equivalent to (recall that AG1 BG2 & RG)
R
E [(E((U)) = -VB 8 81
B[e(U)G) VB
(109)
The above implies A since f < 0 by Theorem F.I Since both B 0, by Eq. 105) we have E (-1,1) {0} and R > 0. Moreover, notice that for any > 0,
(e(0-llmll, R + RG + BOY + RVT- E [(60ll1111 R+ RG + B0Y + RV )PE)
Therefore, we must have p E (0, 1). Then we prove (p", R2, So X²) E (0, R>0
R>0-
Lastly, by combining Eq. 108 and (109) with change of variable X = 1/ug. and recalling Eq. 100
in the proof of Theorem F.9 we obtain the KKT conditions Eq. (104) expressed in (p. Bo.
Then we complete the proof of [b)] Finally, part (c) directly follows from Theorem F.9
We are now in position to establish the convergence of parameters.
Proof of Lemma
F7
Consider any E 2 0 and CR, Ca. E (0, 00), let
(e) [(e, R 30) E [-1,1] [0, CR) [-C Cpol: : (e, R, Bo) - (p", RR" ,R))21 2 8}
and let (s) defined as Eq. 91). By Theorem F.2 and F.11 we can choose some CR, Cs. > 0 and compact convex set E. C R Targe enough, such that as n, d 2o,
M, M,, (O) E.) (w.h.p.),
M M (0).
Then according to Theorem F.6 we have global convergence
M, P M
However, for any e > 0 and ( > 0, by Theorem F.6 we have
M, (O))s)) R") Mn O (s), E.) (w.h.p.), IP (M,,) (M((((s)) -) 0.
This implies
p-lim inf (O) 2 M² M
R-+30
where the strict inequality comes from the uniqueness of minimizer (p", R", (g. established in Theorem F.1
a) Since
can be arbitrarily small, this proves (Pn, |1 11, Bo..) D,
(p", RR" 35). Moreover, we know that R > 0 by Theorem F.1 So 3 # 0 and therefore
Pn is well-defined with high probability. This concludes the proof of Theorem
70

---

Published as a conference paper at ICLR 2026
F.1.6 ELD CONVERGENCE: PROOF OF LEMMA F.8
Proof of Lemma
F.8
We first establish the convergence of logit margins. Recall that
En
8 ((t,,
i=1
L. = Law (U*) == Law (o" 1ell R + + + R / p²2g²)
Law (proxx-e (p" ||ee|22 R' + + B)Y))
For any E >>> 0 small enough, we have defined the E-W2 open ball by
(E) u E R" W22
Su, Cu < <Ej.
For CR. Ca (0, 0o), let O 1, x 00, CR] x C3 Cp.l and let Og be defined as Eq. 91 When Cn, Cs > O and compact set = C IR" are large enough, by Theorem we have
M = Mn M, (IR++1 Biv (s)) = M, Eu Bwa(e)) (w.h.p.),
( M (O,, Biv (e)) ( E. Bw, (e)).
Combining these with Theorem R3 and F.4 obtains that for any 0,
lim IP
M M <) 0.
(110)
n-00c
In order to show W2(Cnn C.) & O, our goal is to show that
lim
M Mn) = 1.
n1
Then according to Eq. (110) and Theorem F7
it suffices to show that
p-lim inf (x
p-lim Mn = M n-000
(111)
By Eq.
and 900 recall that
n
M
min (E. VENA (p. R,Co) Bwg (5)
min
Σ Elus),
1=1
where we temporarily detine
RV RV1-
(p. (p, R3 Bo)
u E R"
- lll lllllll R1n Rg + Boy -1l2 5
v8
Now we split ( into two parts by
n Elu));
n
M min (1, == min
min (.. (1) 72 (o. (Bus,
min
Σ E(us)
(a. C... (..)).BBB Bg (n) uEN, (2, (B
where 77 > 0 and
B2 (n) = ((p, ER R.). (0', R" , < <n}
a 17- L2 open ball around the global minimizer (p", R² 18))-
For the first term, with θ large enough such that (p" R (8) E θ by Theorem E.5
we have
I 12
min (,, BB (n) uEN: R,,))
min
((ss)
1=1
Eq.. [(@llAul2 R+ RG+ + R - Ry)
min
(o.R,80)EO. B (n) (Q.. $1/6
(0. B2 (1)) P, ( B2.0((1) > M' = M",
71

---

Published as a conference paper at ICLR 2026
where the strict inequality follows from the uniqueness of (p", R,, ,8) according to Theo- rem F.I
For the second term, take 0 small enough, such that (p. Ro) E B2,c (1)) implies
W2 [Lw (Up.),8)) f.)
=W₂ [Lw (.,.)))) Law (U (U S
(p, O n 02 (1))
where U.RR,S == 1|llely [ulllgR- R+ RG + BoY + R RVI- (p. R. Bo), and EC (p. Bo) is the unique minimizer of (o({) defined in Eq. 995 with an expression given by Eq. (96). The existence of such > 0 is guaranteed by continuity of W2 distance and (p, R, .n) + U p.n,% by Theorem F. Then $ (=) implies (by triangle inequality)
W2
Sun Law (U (U2.3,8))
6 2/2
(p,, Ro)) E O.n (1)
2'
1=1
Thus we have
II =
min (p.R.B.)EO B2 (1) (o
E(u,)
min (p.
Eq, (e()),
(112)
1=1
De (o,
where denote
(h, R.3) = { {UE ( | U U U2 lla. 2 2)
(113)
and recall Eq. 990 that
R RV1 p²
N2 (p, R,
U (Qe) R+ RG + +B0 -Ulla
(114)
V8
Now, denote Up.R,6o = p1leellz R + RG B,Y RVT- (p, R, Bo)- According Theo- we know that ||55 (0, R, Bo).. 1/0,, that is,
rem F.9
Hle 11lll + RG + BoY - Up. R/1 RVI-p2
(115)
We claim ||02,,,0 U.. P4 0. Otherwise, there exits a convergent sequence Am JmeN
such that p-limm--oc 2m o X", where 7. satisfies the conditions in Theorem E. under Q Qm. and X* satisfies the conditions in Theorem F.9 a) under Qoo- This contradicts the convergence arg max, Ry (A, B, 36) & arg max, >0 Ry (A, B, 30) by an argmax theorem for the con- cave process (Liese & Miescke 2008 Theorem 7.77) according to Theorem F.nmmFF9 b) and change of
variable RV1 p²/ /A. Hence, for all large enough, have
n, U..R ll. S
Combining this with Eq.
115) together, by triangle inequality, we obtain
No R, 30) (.) R, S No. (p, R, 3o)
(116)
where
R R p
Nhe (p, R, 30)
U U (Q.) :00)):lllllae 11llllll1222 R+ RG + BAY -Ullo
V8
Recall that CR ma) R. Denote & 8 constant such that
(117)
Cn
72

---

Published as a conference paper at ICLR 2026
Then following Eq. 1122
we have
II
min
min
Ee., [((U)]
(p.
UEN (o. (p,,)88))
Ive
min
min
Eq. (e(U)
(p. UeN (p.
= min
min
Eq. [e(pllesl, R+ RG + B.Y + RR RV1- p?E)
(0. Ille. 5 RV1 x²
min
min
Eq, [((pllll) R+ [ B,Y + R - P²E)
(..R,,))00..62211.)........ 11/6
min
min
(((0llal)) R+ RG + Bo + RV - (PE)
(e $1/6
(8)
min
min
E [((ellull22
R+ RG + BOY + RV OPE))
(p. (e. 21/6
= (O,) = M",
where (i) follows from Eq. (116), (ii) follows from Eq. (177 and the fact that
E
(p, E O..
V8 RV1 0²
8
the convergence follows from Theorem F.5 and (iii) follows from the uniqueness of (0", Rt, 11, ,8)) and KKT conditions 1 1/6 in Theorem E11
Finally, combining everthing together, we have
p-lim inf M7e(3) 2 min
p-l I, p-lim inf 11
m >
M
n-000
n-000
n-000
This shows Eq. 111p, and hence completes the proof.
Using argument similar to the one at the end of the proof of Theorem E.7 we can show the
convergence of empirical logit distribution W2(On, v.) 2 from W2(Cn, L.) 2 given by The-
orem F.8
F.1.7 COMPLETING THE PROOF OF LEMMA D.3
Proof of Lemma D.3 Consider the ERM problem Eq. 334 with arbitrary 7 >> 0. Recall that Ør
(t/s(1)) where 1 + {1} U (T) is defined as per Eq. 29 M,, is redefined as Eq. (34)
M, = min
Σ (Ti((a + 8)))
BERd, BOER ni
Under this modification, (0, E.)) can be redefined and expressed as
My :=
:=
min (., usEu
max vER"
2 (2, ui)
n1
s(yr)
n
1=1
min
max VER"
8
Ui
+
1
T 1 (pe,
(3) + v 2 +
1
BO
v
(E
s(y))
uES,
1=1
73

---

Published as a conference paper at ICLR 2026
Consequently, quantities M, 1,2,3 and M* used in the proof can be similarly redefined
1
(11)) ) + 1 1 33 + [1l2 1 1
M ( ==): = min
max VER
(0,8)) uEE.
Y1
1=1
!
1 -v
+
|| v + -0v y
(0, Eu) == min min (g,R,8)E0, UEEWNN
Ba. [e(U)>(Y))]
M (0.. Eu) = min min (p.R, DEEWNNg
Eq. [e(U/>(Y))]
min min M (3) Oo)) (p.R,8) UENT
Eq.. [((U)s(Y))]
ellalll R - RG BOY + RR RR1--29)
min (p. (E.) $1/V8
EQn.
e
s(X)
plllall R+ RG + BoY + R -
(O.) =
min
I
s(Y)
SEE (2x $1/V8
M M' R20 x R),
where No. No are still defined Eq.
90), and we still apply the change of variable
= |M R + RG + 30 + RV P
One can exactly similar arguments conclude Theorem F22 F.5 and Theorem F.6 with defi nitions above. For Theorem F9 we can also get similar results, but the KKT condition in Eq. (88 now becomes
U + (+ p 1|llll2 R+ RG + BoY,
which implies
U
( [Ille|l22 1101l221 +GG +..Y X
prox,
(118)
sY)
x(V)
x(Y)
as substitute of Eq. (TO).. and
A R
(plixell2 R RG + BoY
))
(p, Ro
p² L' prox;
s(Y)
substitute of Eq. 96
a According to the definition above, the KKT conditions Theorem E.11 will become
Rp E
(119)
A8 | 2
R
[2(0]
(120)
0 E [3108
(121)
R² p²)
E ((((1))
X28
where
p |1leall2 R RG + BOY
A )
(x(U):
s(Y) l'
prox,
s(Y)
s(Y)
s(Y)
ssY)
74

---

Published as a conference paper at ICLR 2026
and U follows the relation Eq. (18
By Stein's identity, Eq. U
120
be expressed
(U)G
s(Y) 8"
d(U
(Y))
Aσ =
=
s(Y)
dG
R
E
s s(Y) t"
s(Y)
s
s(Y)
8"
s(Y)
s(Y)
which gives the third KKT condition in (a) Besides, Eq. (T19) and 121
can be rewritten
Rp
p p|laal22 R + RG + -000
TE
proxe
A6 |11l|2
7
+ (1
IT) [e' (prox, (p 1leal12 + RG - 3o; A])]
||lAall R + RG + 90
0 TE
prox2
JE [e' (prox, (p l| R + RG - So: X)]]
which solves the first two KKT conditions
in [a) This concludes the proof of part (a)
Theorem 7 still remains valid under arbitrary > O, which concludes the proof.
Similar to the proof of Theorem D.1 e) we can show that for any test point (Inew: Vnew )
[( new) (Feew: 3n) Pa, 4 Vnew R' p² || + Re G S6:
where (y new G) ~ P. x N(O, 1). Therefore, by bounded convergence theorem, the errors have limits
$
lim Er PP (++R || + R B <0) +
pp" ||14|12
R
lim Err_,. = P (- R*
||l| + R 8 > 0) +
-p" ||اl||2 +
R.
This concludes the proof of part (c)
Based on Eq. 118), we redefine C. Section F.1.6 by
[1 R + R² G B
A
C. = Law (U*) Law
s(Y) prox,
sYY)
s(Y)
Then Theorem F.8 and the corresponding convergence of ELD still hold. The convergence of TLD directly comes from the proof of part (c) This concludes the proof of part (d)
Finally, we complete the proof of Theorem D.3
G MARGIN REBALANCING PROPORTIONAL REGIME: PROOFS FOR SECTION D.2.1
G.1 PROOFS PROPOSITIONS D.4 AND D.5
We show the monotonicity of Erri, for in this subsection by first analyzing the monotonicity of asymptotic parameters p", 188 which are the solution to the system of equations Theorem E.9 We restate these equations here.
9
2T
P
[aall2 8
+1 T)8.
2(1 T)
P
1111122
2² (122a)
So + KT = ===pp =1|14||22 + 9-
P
(122b)
2T ||11|22 6
p
8o + - + +
(122c)
2(1 - TT) ||
The properties of functions 91,92.9 therein are summarized below.
75

---

Published as a conference paper at ICLR 2026
Lemma G.1. Recall 91 (z) [(G + x) 92(x) E [[G + x) and g 92 9i
(a) 9t. 92 are increasing maps from R to l2 and g Rzo + Rso is increasing with g(0+) 0.
(b) 9b, yn have explicit expressions
91 (a) = xx(x) + 6(x),
g2(x) = (x² + 1) + xo(x).
(c) (z) (2( ~ x², and ( ~ x², as +20.
The following preliminary result gives the monotonicity of p² By Theorem D. p E 1) is invariant with respect to r. Hence p" can be viewed as a function of model parameters (नr, || 6) determined by Eq. (12aa).
Lemma G.2 (Monotonicity of p²), ) p* is an increasing functtion of π E (0, 2), || and 6.
Proof. Recall that pa (0, 1) as stated in Theorem D. b)
(a) t in || This point is obvious from Eq. 122a and Lemma G.1
(b) f in 8: Notice that Theorem G.6 implies x -> x0 g(1/x) is decreasing in a. As a consequence, if we fix p and increase 5 on the H.H.S. of Eq. (22a), then the L.H.S. will decrease, and p" have to increase to match the R.H.S.. Therefore, p² is an increasing function of 6.
(c) in E (0, )): We prove this using similar strategy. Define
21 2 (T) 91
22 x2(TT) i5 2(1 σ) |
2x
p4 1lll
then we know that the I.H.S. of Eq. 122a) (for fixed and (| is proportional to
(2(21 (T)) (2(x2(TT)
(123)
91 (z1 (x²(TT))
with the only constraint on Ti and 22 being
1
1
2 |
C. :=
Ø1 (z) (T)) 91 (*2(T))
P
Taking derivative with respect to n, follows that
g' (x1)
(x2)
x1(()) 9 (12)
(
<l(T)) = 0.
12(7)).
of (x1)
(x2
gi (x1) gf(22)
thus leading to
d (z)() (x(22(11))
dm (T)
91 (+2(T))
(019) (11) (2(2))99 (31)
2/ (2(2)) (2(2)) (x22 (T) g
(x)))
(x2)
g ( )91 (2
92 - (2
(12)) db(T))
(()))
8/(22)
of (x2)
(/( (I(x)) h(x2)),
(x2))
where
Mxx) = (0(() (x) -20))gg(() (2)
WrER
g((x)
a monotone increasing function according the proof of Theorem G.6 Therefore, h(x)) h(x22)
(since π < 1/2 = I > I2). By definitions of xy and 91. we know that x (T)) > 0 and of (x2) As a consequence.
(z) (2(22(T))
0.
dm 91 [z) (Z)(T))
91 (x2 (T)
Similar to points (a) and (b), by combining Eq. (122a) and 123 ,, we conclude that p is an increasing
function of (0, }). This completes the proof.
76

---

Published as a conference paper at ICLR 2026
As long as * O, the linear system Eq. solve for Sy and K:
(12bb) and (122c) for (Bu, r) is non-singular,
P
P
+ + (1-11))llaal)) (tlllell)).
3u
T9i
2T || 12 96
(124a)
1
2(1 T) 1114112 2(1 1)) |
K
1+
91
P + 91
2x ||1
p
+ 2p |11e||2))
(124b)
The following lemma establishes the monotonicity of 19 when T =1
Lemma G.3 (Monotonicity of Bi). Bg is an increasing function of π E (0, 2) || and 6, when (without margin rebalancing). Moreover, 80 < O.
Proof. When 1, the above equations reduce
8o
1
91
P 2(1 - π) || 11lll2 8
92
2T [ell )
(125)
2
K
2
1
91
2(1 - π) || 91
P
2T 11122
2p ||ee|l2]
Clearly A8 < O, since 91 is increasing function and π
<
(a) t in ||||2: Fixing क and 6, taking derivative with respect
|| in Eq. 125
we have
||/ll12 2 2(1 - =) (
d,3
(0r
d pall
P
2(1 T.) 111122
2
2T
d
||14112
Since
1. from Theorem G.7
we know that
(g
P 2(1 T) 1
(0
P
< 0.
2(1 πT
2
2TT 11ll22
According to Theorem G.2 if we increase || then will increase, and Eq. p/ ||ll] will decrease. Hence,
122a implies that
P
O.
||A4|/2
Combining the above inequalities, we know that d,30/d
[a||| > O.
(b) 1 in 5: Similarly, according to Eq. (12aa) and Theorem G.2 for fixed v and |4|l, we can show
that p/8 will decrease 5 increases. By same approach as (a), we can conclude d/3//d0 dō
(c) 1 in π E (0, }): Lastly, we note that if π E (0, Y) increases, then 1 - ग will decrease and will increase. According Theorem G.6 we know that
(1 T)
P
9 2(1 T) 111228
will increase. Since (1 - p²)/ will decrease, combining with Eq. 122a we can show that
9
2T |111
P
will decrease. By Theorem G.6 decrease, which implies that 3o Eq.
again, conclude that p x) will increase and p/m will
125) will increase. This completes the proof.
D
The monotonicity of minority error is a direct consequence of the two lemmas above.
Proof of Proposition D.4 When T = 1, according to Theorem G.2 and
G.3 both p² and 18 are
increasing in (0, D) 1 and 8. We complete the proof by Err
|| (30). n
77

---

Published as a conference paper at ICLR 2026
Now fix model parameters π (0, 22), 6, || and consider test enrors functions of In
order to prove Theorem D.5 we need the following result on the monotonicity of p", Ph on т.
Lemma G.4 (Dependence of T), Fix π E (0, 2) |l and ó, then we have
(a) Pg does depend
(b) 9 is an increasing function of T E (0, 20).
(c) k" is a decreasing function of E (0,
As consequence, Err;, is decreasing in (1), and Err", is increasing in (1)
Proof. a already proved in Theorem D. b) For (c) the conclusion is followed by Eq. 124b)
since K¹ x (1+ ()) (7)
For (b) note that Bú + A. is a fixed value according to Eq. 122c). Then by using conclude S is increasing in T. This concludes the proof.
These are consistent with the non-asymptotic monotonicity between (p, Bo, Ri and 7 in Theo- rem C.I Then the monotonicity of test errors is direct consequence of Theorem G.4
Proof of Proposition D.5
According Theorem G.4
know that -p" || + 38 is in- P is decreasing in 7. This completes the proof.
b)
creasing in 7 and
|M
G.2 PROOFS PROPOSITIONS D.6 AND D.7
Proof of Proposition D.6 Recall that
Err = [ (- 11 (5) + + (-p'' + (5))
Notice that p² does not depend on т, and p² || 1 > 0. We first show that r = 7 and only 3 = 0. Then is suffices to show that for any fixed a > 0, function
(x) (--a + x)) 40
x),
TR
has unique minimizer 0. This is true by observing f'(x) o x) Ø(- x) < 0 for
all x < 0, and f((x) >> for all > 0. Hence we conclude 35 = 0 and Err, = Err" = Emr
Setting 3o
Eq. (24a) and solving for т, we get Eq. (38) This completes the proof.
As stated in Remark D.3 when || are fixed and small, the numerator of opt scales as VI/T. We formally prove this in the following lemma.
Lemma G.5. When π o(1), we have
p²
+ p² ||al|22
2T 111112
Vmo"
p* is monotone increasing in æ E (0, 2). can easily shown that p² + as + 0. Otherwise, suppose p* - pp 0 as 0. then by Theorem G.
Proof. By Theorem G.2
2
p"
P
T8
~ T8.
x 0c,
2π |
2T
|111
while the other terms in Eq. Eq. (12a)).
122a are all finite, which contradiction. Substitute p" + 0 into
p"
p*
2T
||اا
T -
00
2T
|1l1 8
VT
The proof is complete by using Theorem G. again.
78

---

Published as a conference paper at ICLR 2026
Remark G.1. We notice that when π is very small or ||p|||2- 8 are very large. then p is close and the denominator of T can be zero or negative, leading 7 infinity of negative. According to under the
Fig. [4 this happens when the optimal decision boundary (the red solid line) falls margin of majority class (the black dashed line below with negative support vectors). In such cases, have < -1 and the training ervor for majority class is nonzero.
Actually, our theory remains valid when T < -1. When T < -1, one can modify the objective of Eq. 7 minimizing K. (since < O and TK 0), then the relation Eq. (17) Theorem C.1 still holds. For the asymptolic problem, one can similarly modify the variational problem Eg. (3]j. Then
one may extend Theorem to negative T by relating Eq. [17) to (8I). where Eq. (1 derived
from Eq. (12aa) (122c). which also admits unique solution when -1
Finally, prove the monotonicity of errors after margin rebalancing.
Proof of Proposition D.7
According to Theorem D.6 Err". Err" Erry = ${-p" (1x))1))
Since p² is increasing in (0, }), || and by Theorem G.2 the proof is complete.
G.3 TECHIICAL LEMMAS
Some technical results used in the proof are summarized below.
Lemma G.6. The function 92 (z(2))/ g1 (1:) is increasing in This implies g(w)/x is increasing in x, and x g(1/x) is decreasing in x.
Proof. By direct calculation, we have
gx(=)g1()) (2()) = (E[[ (I) + x)
It suffices to show that
M(x) (IB[( + x) -
V
((x)
To this end, note that lim, h(z) 0, and that
1((x) = (xx)=2[[[G + m)+ (1 (1- [[([ + ld(())
(xx)²
Hence, one only need to show that h (x) > 0, Vx E IR, namely
r(x) x(x)² E[ x)+] 0.
x(x)
Notice again that lim (x) 0, and
x+{xx)
('()) (xx) |
>
Φ(x)
by Mill's ratio, thus we finally conclude that r(æ) > for any x E R. Consequently, (2(x)) (x) increasing x.
By change of variable g1 (x), we show that (x))//1(<)) = g(v)/v is increasing in y.
Lemma G.7. function x ((x) is monotone increasing.
Proof. Let x = 91 (3), then we know that
91(v)
x (9T (cx)
(1)
Since y is increasing in suffices to show that 91 (2))91 (v) is increasing in Note that
d (1(())
(1) 9n (v))g(()) Φ(y)r(v)
dy (v((v)
(2)²
(1)²
where the function r(y) is defined in the proof of Theorem G.6, and we know that r(y) > 0 for all y E TR. Therefore, 91 (v)/o( (v) is increasing. This completes the proof.
n
79

---

Published as a conference paper at ICLR 2026
H MARGIN REBALANCING IN HIGH IMBALANCE REGIME: PROOF OF THEOREM D.8
Without loss of generality, we may consider the following substitute of Eq.
8
d 14 d²,
d
Consider linear classifier based on f(x) = (x, (3) + 3o with ||31|| = Denote projection matrices
P
P
| mm
where Pa is the orthogonal projection onto span and P1 is the orthogonal projection onto the orthogonal complement of (p) Then we define auxiliary parameters
P
P
11
if p <
p
B
0
P 11
v1
p2
(126)
p1
if p 11
where 14 = some deterministic vector such that L μ. Therefore, we have the following decomposition:
B P,,3+ P
1
+ VI p²0.
|
Note that |0112 = 0 1. μu, and there exists a one-to-one correspondence between B and (p. 0)-
Therefore, the logit margin f(x) for the i-th data point (x) can be reparametrized
(; Bo) =- Ti( 3) + 30)
-syy (wi. + zi |elll
+ v vI v1-100) + +B0)
||1l||2 3: + pyigi + v1 pryi(zs, 01)
(,,
(127)
where z; ~ subG (0, In; K) according to Definition J.1 K > is some absolute constant, and
if y/ +1, if 11
f1
8; =
9: =
Z;:
|
where g = (g), (gl,...... !n) subG i (0, I,; K) by Theorem J.2 Therefore, the margin (in
Eq. ( of (()) can be viewed as function (G, So) + or (p, 0, Po) + based on different parametrization:
K = x(3,30)
min 16 (3, Po) <Ein]
(128)
= <(p, 0, 9,) = min Hi (p, 0,))) *E(m]
As consequence, the max-margin optimization problem Eq. (15) or can be expressed as
maximize RR subject
k(p, 0, 0,,o),
P [1,,]]
(129)
||0|| = 1, 011 μ.
where
min 8; (p (11ll12 + yrBo + Py:0i + /1 p--ppuu p)((z.
=(p,0,8)
vE(n]
IIn fact, this one-to-one mapping 3 + (p. 0) restricted to gd-1 0,,0- where the range is θ, = {(p, 0) E (-1,1), ||0||, = 1, 0 1 1 (p, 0)
- p1). However, for simplicity, we expand the parameter space of (p. 0) into ((p, 0) P 11,1),1000,
1,0 1 m). This is because if =1, we have P 0, and /I -1 0 0 for any 9. We will see that 0 always appears in the form of /1 - 0²0 (for example, in the decomposition of B, and the expression of and x).. That also explains why take μ arbitrarily in Eq. T26
80

---

Published as a conference paper at ICLR 2026
Recall that (3, 3o) is the max-margin solution to Eq. (15 and the maximum margin is given
r3,3, Bo)
min KG (3, Bo).
(130)
iE(m]
Similarly, we can also reparametrize 3 in Eq.
126
P
=
3.
P
0
=
||
V1
p
if p
(131)
if 7
Then, (p, 0, 3b) is the optimal solution to Eq. margin can be rewritten as
129
Combining Eq. (128) and (330). the maximum
(p, 0, 30)
min (5. 0, 3o):
(132)
which is also the optimal objective value of Eq. 1129
Finally, we define few quantities:
Σ
Σ
9+ 9
9+
9h.
9
9i.
T2+
2
TET
VET
2
2+
Zis
2
Zin
3:
n
n
4EZ
AEZ_
The proof structure of Theorem D.8 is as follows:
1. In Section H.1
we provide (stochastic) tight upper bound for the maximum margin R, and
constructed solution (p, 0, (b) which approximates (p. 0, (B) well.
2. In Section H.2
we derive the asymptotic orders of (p, 0, (6) by using (p. 0o)
3. In Section
H.3
we use these asymptotics to analyze test errors and conclude Theorem D.8
H. A TIGHT UPPER BOUND ON MAXIMUM MARGIN: PROOF OF LEMMA
The following Lemma provides data-dependent upper bound the margin x(3, 86) which holds for all linear classifiers with || 1. The bound is tight in sense that it can be (almost) achieved by constructed solution. Therefore, such tightness ensures the optimal margin ğ should have the same asymptotics given by its upper bound, which also deduces the data is linearly separable with probability tending to one (as d + oo). Notably, Theorem C.I implies that has effeett on 3, fixed dataset. Hence, t simply scales the magnitude R, and suffices to consider т = 1 in the following lemma.
and R x (1 + -)
Lemma H.1. Fix r
Denote
R:
(1 g)2 + E
(133)
(a) (Upper bound) s(p, 0 (6) S K. for any P E [-1,1], 50-1.
ps, 80 E R. Moreover,
k (1+ (1+)p(1)) V dh 4
dacc
as + 20.
(b) (Tightness) k(p, 0,)) -
- Öp()) where
p:= || +
P/
Ø
(11 + 7]2 + ||
(134)
B = -p. 34 +
/1 -
p1-
12 +
2
is a feusible solution Eq. 129
According to Eq. (131) and Theorem C.I for linearly separable data, (p, Bo) is the unique solution to
Eq. 129
Ip 1, then also unique solution
Eq. 129 Otherwise, if 11. then
y (zz,0 0 and thus any feasible @ could solve Eq.
129
81

---

Published as a conference paper at ICLR 2026
(c) (Asymptotics of R.) As consequence, the data is linearly separable with high probability, and the maximum margin satisfies (r) S R S
Proof. a We reparametrize x(3,30) k(p, 0, BD) by using Eq. (126) and 127 bound established by calculating the average logit margin for each class. Let
Then, the upper
R+ (p,00,0))
Σ
p 211ua112 + 30 + pg+ + V (2 0) ki(p,0,30)
Th+
sEI+
(135)
R- (p, 1
(p, 0, Bo) - p -pllall2 1 - Bo pg- v1 p² (z_, 0)
Clearly, 0,p,0,00) S (p, 0, Bb) and x(p, 0, (b) 3 K- (p. Bo). By averaging these two bounds,
(p 0 Pb) + (p. S.)
k(p, 0, 0,) S
2
=pllealz p
9+ - 0
p2.
2
P (1leall2 + + /1 - 1² (2
M/ (111u112 + + / - p² P 3
(136)
SV (111l122 + 3) + P j4
= R.
which leads to x defined in Eq.
133
Here, (i) is based on the fact that
P
G 01|2=1
arg
(2,
0)
|P p 2112
OERR, |
(2,0) | P
(137)
(,,00==
(,.0))=
and recall that the optimal 0 equals Ø defined in Eq. 134b. Moreover, (ii) is a consequence of Cauchy-Schwarz inequality (A E R, B > 0)
((vI=
(1)) = A2 + B
A
V 1 1 1²
max pE[-1,1]
max 1E[-1.11
02) ,
(138)
A
(pA+ vol+vI-ph p²B]
arg max pE(-1.1]
AA + B
and also note that the optimal p in (ii) equals defined in Eq. 134
To study the asymptotics of K, recall that æ = n n+/n = o(1), , n n = - o(1). Then
1 1 1
o(1) (1+
n
n
m
n(1
Denote
1
1
1
1
ad
2
n4
n_
2 n
(1+)
(139)
Theorem J.2 b) implies E/aa subG (0, La; K).
Then according to Theorem J.3 b)
PP
(-
ct
I
ct2 (d 1)
> < 2 <2exp
= eexp
a.l
P
l|F
K
K
where
P 14
|| = vi
P
1, and e an absolute constant. Therefore,
d (1 V
-P = a.a | 10:r(110000 (1+))(1))
-Ld = = mn
(1)).
2/mn
(140)
82

---

Published as a conference paper at ICLR 2026
In addition, by Theorem J.
= =>(aa)) - Op (-
Recall that a c 1 < O. Finally, we have
k / /Cllalll +0)² 1
(Iell22 + OF(1/VTT) + d (1 + op(1))
4m
(dv/2 (1(00---1112 + 1 da + oz))
1
d } 4
daa + or(1))
(141)
This concludes the proof of part (a)
(b); Next show that the upper bound R is nearly attainable, by constructed solution (p. 0, 3b)
defined in Eq. 134). Clearly, (ő, 0, Ba) satisfies the constraints in Eq. 129 This candidate solution
is motivated by the optimal (p, 0) that makes (i) and (ii) equal in Eq. 136 i.e.,
7 + M) V1, 0)
and Bo that balances the magnitude of average logit margins from the two classes, i.e., we choose 3o such that R4 R_ in Eq. 135). Substituting (p, 0 Bu) back into Eq. (127). we obtain
Kis (7, 0, (0) ||el||2 + v: + Py:gi + v puy (z:, 0)
g + g
2+
= ||elll2 + v.g. y1
p2
yizi - y1
2
2
Therefore, the difference between each logit margin and the upper bound can be expressed as
J+ +
2+ + -_
K kz 0, Bo) = 0 + y/1
yi
+ / 72
2 + 1/:
Vizi,
2
2
pl0+ - - + V1 - p x - -2,, 0),
if = +1,
(142)
plg: - - / (zz =_, 0) if y/ 1,
where the leading terms P ||111|2: (2- O) (for +1), (z+, 0) (for i = 11 all cancelled out. Our goal is to bound the maximum difference over all data points. Note that
max *E(n]
K Ki (ā, 3b)
max +E2+
ki ( 0, Bo)
max 1EI_
K - ni (7, 0, Bb)
max 162,
gi F+1 + (zz E+, 0)1}
v max TEI
-9-1+ 19:---11 (zz; - x,,,) 0
(143)
max 1EI_
7+1
+ max (z, - z+, 03| v r
max iEI
(g - -0_ max iEI
(zz - =2,
For the first term involving ga 'ss recall that max4e(1) and Thcorem J.3 9t. F4 are sub-gaussian, and
11 (ellyps < K. Therefore, as per Theorem J.2(c) cc)
max 9i F+ iE2
max |,91| + |3+| Op(v log 14) Oz +E2
Oz Op(vlogd) d),
vT4
(144)
max IEI_
g. 7_1
< max |gو| + | = Op(V logn + Op TET
Opp Ap((Vogd)
For the second term involving z 's note that
1
max (z: - Σ+, 0) SET_
< max
(2, 22. 0) 5
max tJEI
((2 2j 21Z))
EEI
n
|
JEI+
(145)
1
max (zz - -
=,,00 0)| < max
Σ
(zz 11x1-2,,07
2,,
max JJz__
(z 2zz P |
EET_ nI
JEI
83

---

Published as a conference paper at ICLR 2026
So it remains to bound (z, 2z. 2, 2) uniformly. We decompose it as (z 2 2)
f
(2) 2 3
2:
1 II.
|4 2
|
We will show that both 7 and IT are sub-exponential. To bound the inner product
||
via Theorem J.4 b)
claim
I= (2
Σ z1 -1)=))))(E3
k=1
the sum of mean-zero random variables, i.e., [8[ - 2,)x (2)x 0. A [d]. where we write (a)& the k-th entry of vector a. To see this, we decompose into terms that are independent or dependent of (zi; zz).
If 1/4 M/
+1 and i + j. then
1
)
z_
1
B[ - 2z) @ 전
= E
(zi z,) o
Z +
+
E[(z: 2,) 3 (z, + 2,)l
2n+
2
2n+
l:: A ya
1
E|z; - =zy C E[ أyl +
[E[2) 3 z1|
E[z, ④ 24))
(z 2z 2j)
2n
0 0 + 2n+
(1 - 1) = 0.
If y = yy 1 and i * j. similarly
2+ )
1
B((z; ((1)-2,)) 2,) x E
(z: 2₁) 3
2k +
+
B[(2, 21) @ (z. +z)]]
2n
2n_
M/x
=
1
E[z, - 2,} 2 E أن
+
18(20020 -
E(z, 2 21))
(E 11 21, z,)
2n
0.
Therefore, when d is large enough, we have
d
11 = 11 - スj, E|1 =
Σ
(z. - 2z) (3)
1=1
11
Vd max
|1 =2))a()) 1,p2
Isk5d
(1)
vd max Isk
[[ - 2z)x lllvz
max (3)x 12
Isksd
Vdk o.KK $ V K2
where (i) results from coordinate independence and Theorem
b)
(ii) is from Theorem J.4 d) and
(iii) is based on X/as, (z, - 22)/v2 ~ sub (0, 1a; K). For the term II, we have
μ
W2 =
2 æj
| l
2
2: 2j |||||
Σ || 11
max 18k5d
[|(z; 2z 2z)x1l
max
[1(2) )
18kkd
1 K2
K oak S Vxn
84

---

Published as a conference paper at ICLR 2026
where (i) is from Theorem J.4 d)
and (ii) is from Theorem (.2 Hence,
(z: Zz 2
Vd/mi n
Substituting this back into Eq. (15
referring to Eq. 140 and Theorem J.4
we obtain
(2) Zj. P
max (z; - 2+. 0 - iEI
max iEI jET,
[2, - 2,, p = + (1+00(1))
max KEI jET
P
Vd/Tn n
Op OO0g m Or d),
1
{z) Zj. 1
max (z)- < iE2
max iEL-
(zi Ejj 2 = (1 (F()
|
iE
Vd/un.
JEI-
jEI
= =Op(logn²) Ollogdd).
(146)
Finally, incorporating Eq. 114 and Eq. 146) into Eq. 143 we have
K 16s 0,, )o)
max kE
21, v max 99: 2-1 max (zi- 01
max 9s 7-1 max/ (zi
iEL (0((Vloog logd) Oz(log d)} v foo(vTog + Oz d) Op(1og d).
Therefore, the difference between the margin of classifier characterized by (ø, 0, (o) and its upper bound R is bounded by
K 07,0,33) = K min Kss (7, 0,3) = max
K ((,,0,,3) = Or(loog d) = Ōz(1). =E(m]
*E(D)
This concludes the proof of part (b)
e According to max marxin optimization problem Eq. 129 note that
max VE[-1.1].8ER 0,,,0,3) 2 (0,, 0, 3o).
0E - 0 I
hence the asymptotics of R is followed by (a) and (b). As d + oo, note that
R n R (1 oz
da-c
dh da-c 2 d²/2 + +00,
4
which implies x diverges with high probability, i.c., lim P( C) 1,VC I. As the result,
P Plincarlly separable] PR > 0) - 1 as d + co. deducing || = with high probability. This
concludes the proof of part (c)
H.2 ASYMPTOTICS OF OPTIMAL PARAMETERS: PROOFS OF LEMMAS
H.5
Followed by tightness of the upper bound R. we show that the optimal parameters م, should be very "close" to the constructed solution 7, 0 defined in Eq. 134) in some sense. On the event that the data is linearly separable, we have showed that B3 and therefore both e and 0, do not depend on our proof.
r in Theorem C.I Hence, it still suffices to consider
H.2.1 ASYMPTOTIC ORDER OF P: PROOF OF LEMMA H.3
The following technical Lemma is important for deriving the asymptotics of p, which introduces a function of p used implicitly in Eq. (136) and (188) for optimization.
85

---

Published as a conference paper at ICLR 2026
Lemma H.2. Define FA, PA+ p2 p E
with A R, B > 0. Then
1
FA, = =
V1 p² B,
FA, -1100)=111pp0 -1- 22)31/2 B,
which implies FA,B is B-strongly concave, that is, for all P1.P2 E 1-1,1].
FA.((P2) FA,B(()) + FA p1) - - 2
BBpp - pi)?
Moreover,
A
arg max (A) [C(-1,]]
max FA, v A2 B². pE|-1.1]
V + B
Proof. Strongly concavity is given by direct calculation and the fact that
sup
pE|-1.11
The optimality condition is already derived in Eq. (138). This concludes the proof.
In the rest of this section, the (stochastic) parameters A, are defined
ala- /2 = ااl| l + / (1))), = P ala-o)/2 (1+ or())).
(147)
Then followed by Theorem H.2 we have p= = arg max pE[-1] (A,)(p) and (P) = 0, where ø defined in Eq. (34). The following Lemma describes the asymptotics of p with respect to p.
Lemma H.3 (Asymptotics of p and p). Suppose that <c+1. 1.
(a) If < b + c, then p 1 - -r((1) Φ - or(1), and
p ((a b- c) or())
Moreover, we further assume:
i. If > 2 c. then /1- - p /1 -
ppp(1 (1 or(1))
it Ifa S c, then V1 - (d and thus /1 dd/m= Ō+(1)
(b) a b+ e, then p = up op()), p p= o1(1), and
F aacth-a-))/2 (1
Moreover, further assume:
Ifa a < + c, then P = 7(1 + (1)).
ii a > 2b + c, then p (p(d-(a-))))) and thus ক 111m|12 = (1).
Proof. According to Eq. 134) and [147)
explicit expression of p given by
A
|| +
db/2
p
(1 + or())
(148)
A + B
(Illll2 + |
db da
In order to connect p with p. recall Eq. (36) that
k(p. 0, Bo) S FA, & FA,((P) = R. Apply this to ō x((p 0, 3)) and use Theorem H.1 we have
pp 0 00- 10 1 μ. 80 E R.
FA, FA,D(T) s {A.(()s(r()))
(149)
86

---

Published as a conference paper at ICLR 2026
Since Of(1)/FAB(D) Ox(1)/VA + BB Op(d-h//3 or(1), it implies
1 (1) = (P)
PA
V1 11-BBB
Pp -- -
(P)
VA2 + B
VA2 + B
Therefore,
p oe(1)
p 3=1-opf o1 p -= (1)
(150)
p = 0r(1)
If a c < b, then /2 ()e-))/2 and by Eq.
148) and (150) we have p. p. op.(1). Also,
(a e2/2
V1 V B
B
(1 + op)) = = - + (p)o
dd
To derive the precise order of V p², we define r =I and FB =
Then (A) = (r) for any p E [0. 1]. We similarly define F := V a=
On the event m {A > 0, p 0. p 0}. by Theorem H.2 we have
1 (P) (7) = FB,A(F) - FB.A(F) - A(F - A(F -7)
Combined with Eq. 149.. it implies
( (f- & 3 A (FA.(()) -
-FAA(D))FA.B00) FA,)(7)) & Or(d-b12)
s0 = Now consider different scenarios. Recall that = ((rr(1)))))))))))
If c> b/2, then - = Öp(( (oo(d(2240022)/// oz(1), deduces F F(1 + or)))
If F S b/2, then we only get (p(ddb/// and /v d/mn ( - (1)
Recall that these hold on event E. Since P(E) + as d + oc, these asymptotic results involving 0r( and Ör(-) also hold on the whole sample space Ω. This concludes the proof of part (a)
bb) If a c > b, then /22 < a(e-c)/2 and by Eq. 148 and 150 we have P.P op(1). Also,
A
ob-o+t)/2
-b-ato (1+ + (1)) 2d attha+))/221 (p())
A + B
Again, by Theorem H.2
FA,(()) FA, < B(p 2)2
Combined with Eq. 149 it implies
2 (p 2) < 2 (PA,B(D) -F < (p-dd(a-0))
so p 7 = (d- Now consider different scenarios.
If < 2b, then j 7 (1/a (1). deduces " 7(1 or(1)).
If c 2b, then we only get أ (d- and p 1||1111 1 (p( = op())
This concludes the proof of part b)
Remark H.1. In each part i. of Theorem H.
[a) and (b)
can derive the precise asymptotic of
P. which is same as P. is difficult to do so in part ii. of (a) and (b) However, as we will show in
Theorem H.4 and H.S in case ii. the corresponding term ( (v1 por p) is negligible, which won't 't
affect the asymptotics test errors.
87

---

Published as a conference paper at ICLR 2026
H.2.2 ASYMPTOTIC ORDER OF (2,,0)' ON THE MARGIN: PROOF OF LEMMA H.4
Next, discuss the asymptoties of 0 and 0. In fact, it suffices consider the magnitude of their projection on some "important" 21, which is related to the support vectors, defined in Eq. (22). As we mentioned, (V+(B), SV -(3) only depend on & and (X,y). 30 or T. If fix p p. then the dependency of SV= on [ only comes from O. So, recalling Eq. (127).
ke Bo) (pllallz yeoo pyigs + V1 plu(
we can rewrite Eq.
22 in terms of
SV+ -V) arg min Ki 0.)) arg min argmin sEI
Pgi + v1 (2 0
VEI+
(151)
SV_ = -V)(0) == arg min (p, (0) arg min { v (z,, 03}
(0)
IEI
iEz
As before, let sv+ (0), (v) be (the indices of) any positive and negative support vectors, i.c.,
sv (0) E SV+(0), sv- E SV-((0)
Now, recall that whenever slope parameter / is given, the optimal intercept 3n = (3) (defined in Eq. (26)) must satisfy the margin-balancing condition Eq. (27). according to Theorem C.3
Hence,
fixing and considering arbitrary 0, we can rewrite Eq. 25 and (27) as
= < 0, 3o) Kiv - (0) (p, 0, Bo) = 111uا11 - Bo + 69 (0) + VI (3( (0). 0)
(152)
Kig (0) (p. 0, (o) = =11uu|12 - Bo P0ss (0) v1 p3(ss ())
In particular, if 0 = 0, we denote sv+ (0) SV+ sv 0 E SV_ as the support vectors of max max-mm classifier. The Lemma below describes the magnitude of (= (0) 0) and (z @6 0)
Lemma H.4 (Asymptotics of (z:, 0)'s 's for support vectors). Suppose that a < lc (a) a + c, then
( 2a (Z 0 0) -p
V1- (2) Ōz(1).
(b) afa b+ c, then
d (1 (P))))
sv 0 0 - mn
(z, 0) Ōz()-
Proof. (0) may not be tractable, since it involves nuisance term P9; defined in Eq. 115 Therefore, we introduce a proxy of support vectors, which is easier to work with. Formally, let
1 = (0) == arg min + +zz 0)
iEZ
(153)
V_ = V_ (0) arg min (z;, 0),
iEI
where V4, V_ are sets of (the indices of) the smallest y (z,, 0) from each class. Similarly, let
v (0) (4))),
v=( E V_
which are arbitrary elements in v (0) and V- (0). Note that V+ is simply SV4 but ignoring term pg.. Indeed, as we will show later, the impact of pg. (+(1) is almost negligible.
We are going to prove Theorem H.4 by deriving tight upper bounds and lower bounds for both + + - 7 (2 (= (0). 0). Then we conclude the precise asymptotics by verifying the upper and lower bounds matched.
88

---

Published as a conference paper at ICLR 2026
Upper bounds
Applying the same idea as Eq. 135
bound = (z (0). 0) via averaging:
(0) 0) < (z+ 0 P x+122
(z)_ 0) < (z_, 0) <
(154)
where the second inequality for each comes from Eq. (37 To create connection between sv (0) and V. ( note that by definition Eq. 151
P9 p0s=+(0) (0) + V1 p² (0) 0 2 P0) (0) + /1 - p v+ (0) 0),
Pg
p (0) 0 < P9. V1 (z (0) 0
Using Eq. 154), therefore we obtain the following non-asymptotic upper bounds on (2 (0) 0):
p2 SV (0) 0)
(2 (0); 0 7 (g 1.v.(0) (0)
9sv+
5 v1 p 2 1||22 + 2p
max lgxl,
rE(n)
(155)
8 (z sv 0) I V (2, (0): 0 p(g. (0)
Iav (0))
I VI p² P x 11e + 2p max [g/]-
To compute its asymptotics, recall that n 2+ subG (0, Ia K),
v
subG (0, Ia: K), and |P |P,llE lIF V. Then by Theorem J.3
|P | +
P I (1+ - =v (1 (1+or(1)), or(1)),
vn+
|P P
I | (1 (f = V
- or()).
(156)
Vn_
While, by maximal inequality Theorem
J.2 C
Eq.
144
we have
[
Oz Oz(lo n) Ōe((),
(157)
<E|n]
Plugging Eq. (56) and (157 into Eq. (155)
gives the asymptotic upper bounds (involving p):
0) S V 72
+ or or(1)) + --))
(158)
(2 sv 0))
0 S v
72 (0 7- (l)-)))))))))
Lower bounds Similar as the proof of Theorem H.I
lower bound can be obtained by plugging E which can be a good "proxy" of Again, by margin-
our constructed solution θ P /
balancing condition Eq. 152). we can express the optimal 0 as [6
Nov (0) (p. 0 Po)
Nov (0) (p) 0, Bo)
0 E arg max k(p, 0, 3o) = arg max
BE 1
BES 1,11
2
11ll112 +
Iov. (0)
Isv (0) /1 p
(0), 0) (Zov (0), 0)
arg max 05g4-1 0Ln
2
2
{o (9w
Iov (w: /1 1-22
p2 (Zev, (0), 0) + (z (0), 0))
arg max 0E 101.
Nottiee that 7 < 1, then arg max 1 k(,, 0, 3o) unique (on the event { > 0)); and we could write = arg max en (pp, 0, 36). However, [ن] = 1, then according to our construction
Eq. 126. the arguments of the maxima can be any 0 gd-1 such that 0 1. μ. while @ p defined in
Eq.
131
89

---

Published as a conference paper at ICLR 2026
Therefore, recalling Eq. [13). we have
(2 su+ (0) (0) 0)) .))
1 (2 (0)
(2 (0) 0) + (0000,,000 10) - -sv + + - (0)
7 ((2 (0)- 0) (2 (0) 0)) 47 lgil.
ke(n]
Combining it with Eq. 155). we can obtain a lower bound for each term using 0:
v sv.
V1
(0) (z, (0) 8)) 4 max
[gel
+ /1 p sv (
iEin]
V (- (0) 0 |P --z--o (122) 6p max [gal V1 (2 (0) 0)
iE|m
V1 (Z sv (0). 0 2 v1 / ((2 (12v (0). 0
(0) 0) (0)
4 max (E(n]
[gcl - /1 p2 sv (w)
z / (+ 0) |P 1 2+ (12)
60 max [g:1
/ 72 (z (0) 0).
sE(n]
(159)
To derive its asymptotic order, we first define two statistics that closely related to 0:
P p
P
0
- -P x_
(160)
P P 2112
Then, the difference terms inside the parentheses in Eq. (19) can be expressed as
(Zv4 (ō) 0) || x 1|2 min 2,, 0) (z+, 0+) min (z: - 2+, 0) + (z+, 0 - 0+), 1E2
=E2+
(0) 1) |P - |||2 = min
(- z;, 0) + (=_, 0_)
min (z- 2i, O) (2- 0 0 0_).
.EZ
IET
(161)
Now we study the two terms on the R.H.S. of Eq. 161
For the first term, based on Eq. (146).
min (2, E+, 0) 2 max
(2, Σ+, 0) Ör()),
EEI,
(162)
min (z_ 0) 2 max 1EZ_
(z, - 12,---_00 =
EE
For the second term,
1
(z+ 0 0+)
(2+ (Z+,P PL
(2+, P PLZ+)
P 2
P 1|2
| 112 | 1112
(Z+, P z)
(z+, P+Z+)
|P 7 2
1
|P | 112
(Z+, P pi
( -
1
| 7
2
11
|| |P ll2
(163)
(Z P + | + |||||111 |
P
(i
+ (1))
Op (0((/2z) mn
d
+
d un V n
d
(1+0g(11)
(1+ (1)) = oP(),
where (i) is from triangular inequality 2/IP 1|2
P z
||2 + -|P
2| (ii) uses 2% 3,
- and (iii) applies the asymptotic results Eq. (14)
(166).
and the fact that 2+ 11. z_,
1
(+(VVo
d
(2+, P
=
0z
|P 1
[1r)) Op
pnnn
xn²
90

---

Published as a conference paper at ICLR 2026
by Theorem J. d) Similarly, also have
2 , p-) =
P
( P p
P p
| 717-12 12
/
(164)
((z+, - + |P +
| 1//
2 P 2
0g (1).
Substituting Eq. 162
163 and 164
into Eq. 161 get
(2
Or(1),
(2 (0): 0) - =-111 Ōr(1).
(165)
And combining this with Eq. (16), we have
v2 (0)
(r()))
ÖL(),
(0) Ör(1).
(166)
Plugging Eq. 165
166 and 157
into Eq.
(159
gives the asymptotic lower bounds (involving
7):
V1 (z sv (0) 0 v1
d
(1 or(1)) + +r((1) + 1..00(1)
m
(167)
1- (2))
1 1- -2 (0) 0 2
Finally, combining upper bounds Eq. 158) and lower bounds Eq. (167 we obtain the exact order
V1- -1-p2(z sv sv_ (0): 0) /1 1 p
(
V
d
oF + +b(1)) + Ōx) (1 + (r+))(1)) + +r((1,
m
= =1 p
V - p1 (0)
0 = /1 -1- -1 (1())
= Ō1()).
aa): a < 6 c, according to Theorem H. a
(1)) clear that Theorem H.4 holds
for p #1. Now, restrict the event (
op (1)) hence If 5 + then /1 p2 b c2 d
1 su+ (0), 0
$ - (F)). - d
1
2
a $ c then 11 To vovu /d/ /d/Tn = Ör(1), hence
(2 sv (0) 0 Ōr(1)
a bbb c, according to Theorem
H.3 b) P = (1()). Hence, on the event { 1).
(1 + (1))
( mn
This also holds regardless of P. since P([p) 1) +
co. Then we complete the proof.
H.2.3 ASYMPTOTIC EXPRESSION OF 3o: PROOF OF LEMMA H.S
Finally, we consider arbitrary 7 2 1 and give an explicit expression for Bo with its asymptotics. Be aware that Ta may depend on d.
91

---

Published as a conference paper at ICLR 2026
Lemma H.5 (Asymptotics of Bo). Suppose that c and 1. Then we have
30 +1
p|| l|
-y (0)
+
(0)
v1 - 70 sv- (0)
T(z
0)
+
(z
sv (0)
++1
r+1
11lu012
V1
TP --
0 Or(
+1
++1
(a) a < b+ + c, then
2
1
30
1
Q1lu|12
T +
T 7+1
1
2
d1/2 + (p()))
-
1
3- - 0z(1).
T
+
T+1
(b) a b- + c, then
2
30
1
PllAal12
(1 + or(1)) + Or)(
r+1
T + 1
2
2d
20220-0t))/2 oz(1))
20
1
(a-c)//2 1// (1 or)) + Ōz(1), (1 + Ōz(1), ifa > 2b + c.
ifa < 2b + c,
7 +
d
p
T
++1
Proof. We rewrite the margin-bulancing condition Eq. 25 27 in terms of p, 0. which gener- alizes Eq. (152) to arbitrary T 2 1:
< 0,) sv @0) 30) 7- [1lll22 + :o + PU (0)
+ vI
sv (0) 01)
kv 3o) Āllue12 Bo p9 (0)
(0) 0)
Then we can solve the expression for 3u (this equals Eq. 24 in Theorem C.3 with parametrization
Eq. 131). ). Its asymptotic simplification is followed by Eq. (157):
Tsv (0) + Ia
(0)
lp
(0)
19 (0)
max [gil = Ōp()), sE(n)
T ++1 1
T ++1
and Theorem H.4
p2 (z (0) 0 Ōr(1).
For (a)
plugging 1 (F( by Theorem H.3 and asymptotics of (z sv. (0)
0) by Theo-
rem
H.4
For (b) plugging ক (o- ( + or or()) by Theorem H.3 b) from i., while
p Op (1) from ii., and asymptotics of (z (0): 0) by Theorem H. b) This completes the
(=
proof.
H.3 CLASSIFICATION ERROR: COMPLETING THE PROOF OF THEOREM D.8
Proof of Theorem D.8 Let (Knew, Vuew) be test data point independent of the training set ((r yi ) such that &new = Y/oww/t + Znow; and Enew subG (0, Ia; K). Recall f(x) =
(x. 3) + Bo. Following the same decomposition as Eq. 127
Vnew I [(Dnew) = Vuew ( ((xnew> 3 + 3o)
|1 l12 Vnew 3o + Bnow (Pgnew v1 - 72 (Znow; θ))
= أ (0l) + Vnew, + ynow Gd.
92

---

Published as a conference paper at ICLR 2026
where
11
Ga == Dynow v1 822 (2 0)-
Snow
nnww
|
Therefore, the minority and majority test errors are
Err+ IP (F()ne))
S Inew = +11 = (plllell) + +.0 + Gd =
Err- IP (f (I Inew = 1 = P ( م0leا|l2 30 - Ga - < 0
By Theorem J.3 c) we have || 1ppz = 0111 S K, since new TT (p, and then Vt > 0.
IP ([Znew) 0) t)
E P (Znew: 0) >t|/ (10) S 2e ct /K²
for some >> 0.
Then by Theorem J.2 a)
|Gallea _ l10guewl 222 + 11 II - p2 (znow, 11 S 11 11 + [I 0y1ls 2 K,
which implies G. (1)
High signal: If a < b+ c, then we have p= 1 o1(L) by Theorem H.3 a)
Therefore, according
to Theorem H.5 a) for all Ta 2 1, we have
111012 + 3o = 2 2
Ø pllul12
Ta+1 Op(d - v v1)+ (11)
Ta +
2 12/ +
--10
1/ (1 (1+ (1)),
lim 122 = +00,
d+000
where (i) is because db/2 > d= d= -c, as d + xc. If 1 S < //2 we also have
i 1All12 - Bu
2
|||||
1
Ōp(d 3 - v1) Ō,(1
Ta +
Tu+
2
1/2
Ta + Op(d' v + 0z())
Td +
(
2
2/2 + (1)) + +1)(1)
Ta +1
2 Td 2/2 (1+ (1)) + ()),
lim T/ T- +00, d=
and 11 d²2 > (log d)& Vk 2 0, as d + oo. Under these conditions, both أ 1||11|| 3o diverges to +.00 with high probability, i.e.
where (ii) is because (ra (ra+1)-1 /2 > (Ta+1)-1
lim P (pluul22 + 3o + Ga > c) = lim F p 11ll12 - 3o - -Ga>C)= =1, VCER. d+000
d
Hence
Err = ((),
This concludes the proof for high signal regime.
Moderate signal: If < a < 2b + c, then aatb-a+)// (1 + (1)) by Theorem H.3 b)
Therefore, according Theorem H.S b) if Ta > b-c then
i |1110122 + 30 2
Ta ا1|l112
2
1
[I [+ or (1)) +x(
Ta m
22h 1/2 (1 (1+ oz(0) - Ta d /22 / (1
+ op(1)) + Ōp(1)
i 22b0000))) /2 /2 oz (1)),
lim 2b-0t))/2 = +00 do
93

---

Published as a conference paper at ICLR 2026
where (iii) is because (22 >
To d(a-e)/2 and d(2b-ato)/2 > (logd)*, Ak 2 0, a + co.
If 1 S 7a < d(a-0)/2 also have
11l11122 - Bo
2
|4
+ +
(1 + op(1)) + +1p(1)
+
T
4
(226
a /2 (1 (1() + Ta +++1
)a-c)/2 + or() (1=)))()+))))++ (1(
+
1
d
a(a-c)/2 c2/2 (1 + o1)) + +1)(1)
Td
+
2 (1 z nd 0//2
(1) + Ö+(1),
lim To To d(aa0)/2 +00, d
where (iv) is from (Ta 1)1 22(2 < (Ta 1) (0)=))/2 Under these conditions on Tu both p pl1 3o diverges to too with high probability. Using the same approach, we can show that
Err, = o1),
Err== o(1).
Now suppose Tu 1, then again 011ea112 Bo +o0 and hence Err_ 0y(1) still holds. However,
ا1| + B0
2 Td
2
e ا11u112
1
d
+ op()) Ōp)
Ta +
<
+ op()) - /2 2d 2b - etr//2
/2 (1 + op (1)) + Or()),
Cd (I
lim d (a-e -x,
where (v) is because 2b2b-at) < / and C (0, 00) is an absolute constant. As the result, - [|1l1122 3 diverges +00 with high probability. Using the same approach, have Err = o1).
This concludes the proof for moderate signal regime.
3 Low signal: If
26 + c, then e ||1l|2 oF(1) > b Theorem H. b) Therefore,
Err+ Err- TP |111 Bo Ga < 0) P (p |ull2
Bo Ga <0)
(- |Mll - Bo + Ga < क [1l11))
o(1)
Hence, we have ErTs 2 1/4 o11. This concludes the proof for low signal regime.
Finally, complete the proof of Theorem D.g.
1 CONHIDENCE ESTIMATION AND CALIBRATION: PROOFS FOR SECTION D.3
1.1 PROOF OF PROPOSITION D.9
The following preliminary result summarizes the precise asymptotics three quantities: f(x) (max- margin confidence), p" px()) (Bayes optimal probability). and (x) (true posterior probability).
Lemma L.I. Consider 2-GMM and proportional setlings in Section D.I.I separable dataset (6 < 8* (0)). Let (p', (G)) be defined as per Theorem D.1 and (Y, G, H) Py x N(O, x N(O, 1). Let G' G¹G VI 2 H. Then for any test point (x. v) Pa. independent of p. cc.
9
Y
p(x)
a ( G (5)
(168)
(xx)
(211atealll + G') + +log --
(x)
(| + GG) + -lgg 1-
94

---

Published as a conference paper at ICLR 2026
Proof. Rewrite a yp + where Ia). By direct calculation, the three quantities f(x:), p" (x)), and () can be expressed by
x(z) σ (zx 3) + Bo)
(pllet) y + (2, + :0):
(169)
ne 1 |||=-11 -
p'(x)= = Ply = 1 x) Te
(170)
2 (1 TT) 11
2(x,, (4) + log 1 1- π
21lxal1a ||al|]2 y + (z. /e/ [|ll|l22 + log 1-
(171)
-Pllall22 300 me- [00((0)) ((())) o2)2
(a) Ppy [(x)))
(172)
27 21lll 3) + log 1-
27 22llulla (p (1ll2l12 + (2, - +log 1
π
(173)
where the Bayes' law is applied in Eq.
170 and 172
Next, it suffices to obtain the joint asymptotics of (z, ( and (z, p4 11/1) which appear in the expressions of Eq. (169). (171), (73). Note that (2, 4, N(0, 1) (since 1L B, P(]
1), (z. N(O, 1). Moreover, B[(z, (), 14/ ||/]|))]]]] Epp + p² by Theorem D.1 and bounded convergence. These implies
(z. (z. 3) (z, p1/llell1))
4 N (6)
p
4
G
G
p²
Since 11. (z, and (2, 30) L (p", ;)), we conclude Eq. then using the Slutsky's theorem. This completes the proof.
168
by Eq. 169).
171).
173
and
The proof Theorem D.9 primarily based on asymptotics in Theorem L.I
Proof of Proposition D.9 aa) For MSE, by directly using the asymptotics in Theorem
I.1
and
bounded convergence theorem, we have
lim MSE(P) = lim E (1 = 1) pl
E (1 =1] - a (0"11u1128 + G G++)))) (]))
E [o(-p" ||H||| -bY + G))²| MSEE,
lim mMSF(p) MSE* Var [1(y 1}} MSF" -T(11 T)- 200
For CalErr, we similarly get
lim CalErr(p)= = lim E (7(zz) Po (2
1 )} CalErr'.
= ( 11all2 Y + G 0) o (20" ||el||2 (p" |1 Y G) + log
95

---

Published as a conference paper at ICLR 2026
For ConfErr, first obtain
lim E (1) (1-11)))))) a-00c
= lim E
Var [1 = 1} xi]
n=
lim E
(1fy = 1} -3-p((x))) (=x))
E
1[Y = 1} -2(2))
G) + log 1-
π
(-2 ||1||2 (1eell2 G) log
1- x
π
1 2
E
and then by relation between ConfErr and MSE Eq. (3
lim ConfErr(p) lim MSE(f)
lim n n00
(x) (1- = MSEE Va
11-000
n n-000
This concludes the proof of part (a)
b When == ropt, by Theorem 3.1
3 = Then we can simplify
MSE" = E (1 + exp(p" ||l| + G)) -3].
According to Theorem G.2 we know that o² || is increasing in E (0, 2). ||l| and 6. It suffices to show that MSE is decreasing in p² |1ll which is obvious by noticing t + (1 + exp(1))-2 is a strictly decreasing function.
For mMSE" note that π T is increasing funetion of (0, 2)) and it does not depend ||l|| 5. These shows the monotonicity of mMSE" MSE x(1 x).
For ConfErr", note that V does not depend on This implies that ConfErr" has the same monotonicity in MSE", which concludes the proof of part (b)
1.2 VERIFICATION OF CLAIM D.10
The analytical dependence of CalErr" and ConfErr" model parameters is more complicated. We provide a numerical verification of Thcorem D.10
Verification of Claim D.10 For CalErr", denote
(I) E
h2(() = E. (a(21(G 1)+ c) (G
where 0 is constant. When == oppt, we have B and
CalErr" = #hi(p" (| + (1 л (22(p" (|1112);
where log
According to Fig. 15 we can numerically show that h(t) == Thy (t) + (1 1) (t) a decreasing function when < न ss 0.25 is fixed. Under this condition, CalErr' is decreasing in p² || Then by using Theorem G.2 and similar arguments in the proof of Theorem D. we can conclude the
monotonicity of CalErr in ||al||2 and 5.
For ConfErr", in Fig. 15
we numerically show that Vi increasing in when ||ا||| is fixed.
Since ConfErr" = MSE* Vi and we have shown in Theorem D.9 b) that MSE" is decreasing
in म. conclude Forr" is also decreasing in m.
96

---

Corollary G.1). Published as a conference paper at ICLR 2026
0.02
0.5-
0.30
0.20
0.25
0.30
--....
0.01
0.05
0.15
0.10
0.30
0.05
0.00
0.00
0.0
0.1
0.2
0.3
05
Figure 15: Monotonicity of x - h(x) and π
+
V
y/æ
Left: h is not monotone when R3
0.25. Middle: h is monotone decreasing when π 0.25. Right: V is monotone increasing for different values of ||||||--
J TECHNICAL LEMMAS
J.1 PROPERTIES GAUSSIAN RANDOM VARIABLES
We need the following variant of Gordon's comparison theorem for Gaussian processes.
Lemma J.1 (CGMT), Let Du C 1Ri--n Dv C mmm++ma be compact sets and let Q Du x Dy - be a continuous function. Let G = (Gi,) Lid. N)O,1), ~ N(O, Iny). ) h ~ N(O. 1,,
be independent standard Gaussian vectors. For any E B2 and v Rmm+ma define (u),..., Upg and V = (U1,-.. pmm Define
(G) min max v Gū
u vEDv
L' h) min max |V -u ueD, vED,
| V
Then have: (a) For all & I,
(CC S2 S).
(b) If Du and Dy are convex and if Q is convex concave, then for all t R.
((C'(G) 2 - 2P (L' h) 2 t).
Proof. See (Miolane & Montanari 2018
J.2 PROPERTIES OF SUB- SUB-GAUSSIAN AND SUB-EU EXPONENTIAL RANDOM VARIABLES
Definition J.1 (Sub- sabb-ausssiantt). The sub-sause gaassaassian norm of random variable X is defined
|X := inf {K 0: E[expp[xX XX2 [3)]
A random variable X E IR. is called nub-gaussian || S0.
random vector (Xi,..., Xa)T Rdd is called sub-gaussian if supvege- [1 v)lle oo. Specifically, write x subG (0, Lı; K) if X1...., Xa are independent random variables with E[X.] = 0, Var(X,) = 1, and maxigigd [|X S K.
Theorem J.2 and J.3 summarize some basic facts and concentration inequalities about sub-gaussian random variables and vectors.
Lemma J.2. Some facts about sub-gaussian random variables.
(a) || llo, is norm the space of sub- gaussian random variables.
97

---

Published as a conference paper at ICLR 2026
(b) Let X1...., XN be independent mean-zere zero sub sub-gaussian random variables. Then E X; is also a sub gaussian random variable, and
Σ
X
C
X
22
where is an absolute constans.
(c) (Maximum) Let X1,..., N be sub-gaussian random variables (not necessarily independent) with K maxisieN | Then
[x,] SCK SCKllog (N 2 2),
E
max
ISSN
where C is an absolute constant.
Proof. See Vershynin 2018 Exercise 2.5.7, Proposition 2.6.1, Exercise 2.5.10).
Lemma J.3 (Concentration). Suppose æ, subG (0, La; K) and x IL y.
(a) (Hanson- (Hanson-Wright inequality 1) Let E Raxdd be matrix. Then, for every 2 0.
P ( TT Axr - E(xTA Aa) 2 1) < 2exp (-emin' {
2
K2 R=1A(loo))
}).
KII
where e is an absolute constant.
(b) (Hanson- (Hanson-Wright inequality II) Let E IRd xd be a matrix. Then, for every t 2 0.
Ball -1 > S 2 exp (
ct² B
B
K B
where e is an absolute constant. In particular, when B = Ltb
1 >t) S 2ccxp (
ct3
1
P
Vd
K3
(c) (Hoeffding's inequality) Let a E Rdd be vector. Then, for every 2 0,
p (m,, a)l >t) s 2exp
(-aP)
(- ct2
(x²)
||a||2
where e is an absolute constant.
(d) (Bernstein's 's inequality) Let B Rddd be a matrix. Then, for every 2 0,
By
2 exp (
(-e min
22
|F
>1)
KT
K2
B
Bloop
where is an absolute constant. In particular, when B Lt-
(xx, y) Vd
-cmin
12
IVd
P
>
< 2exp
K
K2
Proof.
For
(b)
and (c)
see /Vershynin 2018
Theorem 6.2.1, Theorem 6.3.2, Theorem 2.6.3). xByy then apply क" A x By to and simplify.
B
(d)
let क
A
y
2
Definition J.2 (Sub-exponentiality).
The sub- expooxxnnettalll norm of random variable X is defined as
|X 1l = inf (K 0: Eeexp((X]]]] /K]] 2
A random variable X E IR is called sub-exponential if X 1ly, < cc.
98

---

Published as a conference paper at ICLR 2026
Theorem J.4
summarizes some basic facts about eeb-epeoeental random variables.
Lemma J.4. Some facts about sub-exponential random variables.
(a) |l Ill, is norm the space of sub-exponential random variables.
(b) Let Xi...., Nx be independent mean-zero sub-exponential random variables. Then Ei=1 X; is also a sub-exponential random variable. If K == maxigigN [Xiillg,, and N 2 C, then
Σ X
S C''VNN
where C, C' are absolute constants.
(c) (Maximum) Let XI,...,X, XN be sub-exponential random variables (not necessarily indepen- dent) with K maxisisN |X Then
E max
Xx,
CK log N, (N 2 2),
ISiSN
where C is absolute constant.
(d) Let X and Y be sub-gaussian random variables. Then XY is sub-exponential. Moreover, ||XY||
|| ||
In particular, x2 is sub-exponential, and
| 11
|X
Proof. For and (d) the proof is analogous to (Vershynin 2018
and
see (Vershynin 2018
Exercise 2.7.11, Lemma 2.7.6, Lemma 2.7.7). For (b), Proposition 2.6.1). For any [^] S 1/K, we have
]
exp
X
E (xxx()X))) S
II exp (1,) S exp exp(CA2NK3).
where sub-exponential properties /Vershynin 2018 Proposition 2.7.1 (iv)(v) are used, and C' is an absolute constant. If N 1/C. then 1/VCNK² 1/K and therefore
N
X, }]
E
exp
< exp exp(X>CNK3) for all À such that ||] S VCNK
1=1
Then the proof is completed by using (Vershynin 2018 Proposition 2.7.1 (iv)(v) again.
For (d), the proof is analogous to (Vershynin 2018 Exercise 2.5.10). By Vershynin 2018 Propo- - 2 2exp(-ct/ K) Vt 0. where c is an
sition 2.7.1 (iviv)), P([x; 2 t) < expp ct X
absolute constant. Denote to = 2K/c, then
X,
X,
2K <
X, log
E
max 121
< to +
P max
> t
dt
> t tddt dt
1
log
121
1
log i
tg i=1
2K
2K
P[[ ((1 + log i)) di <
+
2exp
-cl(1 + log /KK)d
1=1 to
i=1
2K
2K
x
exp (0 ((oogg))co//K) K)) -exp(-cll K)dl
2exp(-ct/ ct K)dt.
2K
2K < CK,
+ Co
where Co, C are absolute constants. Hence, for any N 2,
XX log
E
max
Xx
S (1 + log N) E
max IS$
K log N.
ISiSN
This concludes the proof.
99

---

Published as a conference paper at ICLR 2026
J.3 PROPERTIES OF THE MOREAU ENVELOPE AND PROXIMAL OPERATOR
Let : :R + R20 be a continuous convex function. For any E R and X > 0, the Moreau envelope
of l is defined
es(x; A) exc(x) min FER
[(l)
1 (1 x)²
1
(174)
21
and the proximal operator of & is defined as
prox X) (x)) arg min
{(1) - 2)²
2A
tER
Lemma J.5. For any > O. prox, (x; A) is uniquely determined by stationarity condition
prox, (I; A) AE (prox,(x;; (x) = 0.
(a) (x;; X) is continuous and convex (x. If is differentiable, then e e X) also differen- riable in its domain, with partial derivatives
Ões(s; 2)
π (Ir - proxx(x; A))
(((=) (==rron
dr der(x;
0% 2X2 (x: - (r; 21)² (e(x)) (m;A)
Moreover, (z( X) is non-increasing in X and (x; - l(x) when X + 0+.
(b) ( X) is continuous in (x,A). A). If is twice differentiable, then prox;(a; X) is also differen- tiable in its domain, with partial derivatives
Oprox,
@prox, A)
(()
Ōx
Xe" (2)
OX 1 (e)
(x:A)
prox, (a;AA)
Moreover, prox, (x; A) + x when 0+.
Proof. See (Trampoulidis et al. 2018 Lemma 15), (Donoho & Montanari] 2016 Proposition A. Salchi et al. 2019, Lemma 2, Lemma 4), and relevant references therein.
K MISCELLANEOUS
Let R be the optimal objective value in Eq. (5)) which is the maximum margin for data (X, y) Moreover, (3, Bo. R) is also the optimal solution to Eq. 77). Notice R 2 0 always holds (by taking 0, 30 in Eq. (15) ) and we can observe the following relation.
(linearly separable) 3,9 + 0, _00 E R, such that y: ((x, 3) + Bo) V in].
0,
|| 1,
(not linearly separable) 0 0, 3D E R, such that y: (ax 3) + (b)
0. vi E [n].
0,
B 0, Bo is solution
When data is linearly separable, it turns Eq.
(7) also has the following equivalent form:
minimize weRd, WoER subject to V.(( w) wo) 2 1, Vi E [m].
||w 1
(175)
The parameters in Eq. (7 and 175 have one-to-one relation (K. B, Bb) (1, w, wo)/////ll No- tably, Eq. [75) is known as the hard-margin SVM (Vapnik) 1998) 7 =
LLM usage statement We used large language model (LLM) solely for polishing the writing of this paper (c.g., grammar, wording). All edits were checked and revised by the authors.
Tf (*) is strict (<), then 3 3 is the unique solution.
100

---

Published as a conference paper at ICLR 2026
L ADDITIONAL EXPERIMENTS
L.1
LOGIT DISTRIBUTION FOR NON-GAUSSIAN DATA
Logit Distribution (6)
Minortyy ELD
Majority ELD
Minority TLD
0.6
Majority TLD
Ganedaa theury
Ganeion theory
Decisioa boundary
0.3
0.0
logit
Logit Distribution (t)
Minority ELD
0.7
Majority ELD
Minority TLD
Majotity TLD
Gameiin theory
Ganeisn theory
Decisioo hommdary
0.4
0.3
0.1
logit
Figure 16: Empirical logit distribution (ELD) and testing logit distribution (TLD) under a non-Gaussian setting. We train max-margin classifier ff on synthetic data sampled from a two- component mixture of multivariate t distributions (with degree of freedom 2 and 8). Colors denote labels yı. and the z-axis shows the logits fx:)). ELD: truncated distributions (histograms). TLD: t distributions (curves). Transparent lines indicate the theoretical TLD derived under the Gaussian assumption (Theorem 2.1
To examine how our theory adapts to non- aan-Gassiia data, we repeat the experiment in Fig. but replace the Gaussian mixture with mixture of multivariate distributions with a chosen degree of freedom, while keeping all other parameters fixed. The key observations from Fig. T6 as follows:
We find that the TLDs follow i distributions, whereas the EL.ss follow the same t distributions but truncated at the margin. This shows that even when the data are non-Gaussian, the effect of overfitting still characterized by truncation.
We observe that the intersection of the actual minority and majority TLD curves nearly coin- cides with the intersection predicted by the Gaussian- based theory Theorem 2.1 as illustrated by the two transparent curves. This demonstrates the robustness of margin rebalancing tech- nique, suggesting that the hyperparameter opt derived in Theorem 3.1 may still perform well under non-Gaussian data.
101

---

Published as a conference paper at ICLR 2026
L.2
PHASE TRANSITION IN HIGH IMBALANCE REGIME
Minority Error
Majority Error
0.6
1.0
(8)) Late Righad
(8)
(
(aI)
(U)
Modirnae signod
High signal
Low signal
Mudlesite signal
High sigusl
0.5
0.4
(ox
0.6
0.3
0.2
Phase transition in high imbalance regime. Minority/majority errors under different settings of parameters b (signal) and = d'. Left: minority accuracy is (i) high for any 7 under high signal, (ii) high for r >> da-b-c under moderate signal, but (iii) low for any T under low signal. Right: majority accuracy is close to under high and moderate signal as long as T is not too large.
Figure 17:
To illustrate how the acceptable range of 7 varies with the signal strength b (recall that || x d²), we repeat the experiment in Fig. but modify the setting by fixing 0.5 and c 0.1 while varying b and As shown in Fig. 17 the same three phases in majority/minority errors given by Theorem (3.2 emerge. The plot also reveals the upper and lower bounds on the admissible range of the signal strength changes.
102

---

Published as a conference paper at ICLR 2026
L.3 LOGIT DISTRIBUTION FOR CIFAR- 10 IMAGE DATASET
Logit distribution of class
logit for label & 0
logit for label 2
logit for label & 0
40
40
35
20
20
10
20
-20
logit for label & 0
logit for label 5
logit for label &
40
0.005
35
35
33
Decility
00000
30
0.015
20
-20
100
0.010
logit for label & O
logit for label 8
logit for label & O
40
35
35
35
0.000
30
0
-20 -10
10
Figure 18: Joint empirical logit distributions of multinomial logistic regression for CIFAR-10. The heatmaps show the empirical joint logits (fo(x;), fx())) for features æ; from class 0 where k 1,2, ..... 9. The vertical axis is fo( for all subplots, and the horizontal axis is fx(x)). The truncation boundaries are indicated by the red dashed lines.
We extend our experiment Fig. 7 to the full 10-class setting. We first simulate an imbalanced CIFAR-10 10 dataset, where class has sample size 500, class has 100, and the sizes of the remaining classes follow an exponential decay. then train linear probe (multinomial logistic regression) on the ResNet-18 18 features extracted from this dataset. In Fig. 18 we visualize the logits for data whose true label is O. Again, we observe truncation two directions of the pairwise logits (fo(x), fx)),, where (-(-) denotes the logit for label k.
103


Reviews:
[{"review_id": "NGVeijlbcI", "reviewer": "Reviewer_zrUp", "summary": "The paper presents a statistical theory for why overfitting effects the minority class significantly more in high-dimensional class imbalance problems by observing the behaviour of the logits. The authors define empirical logit distribution (the distribution of logits for the training set) and test logit distribution (distribution of logits for the test set) and characterise overfitting using these measures. The paper also applies this to the field of calibration, and an extension to multiclass.", "questions": "- Does the truncation of logits still occur in datasets where the means for the positive class and negative class are far apart? i.e. the decision boundary will be placed arbitrarily between both classes. In practice, overfitting still occurs as most classifiers will favour placing the decision boundary close to the minority class, but there will be a set of decision boundaries which give the same training error. How can the TLD and ELD differ, and how does the theoretical approach in this paper deal with this?\n- How do post-hoc methods such as rebalancing the margin address the calibration of the classifier in this scenario?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper provides a theoretical understanding for the behaviour of the distribution of logits at training and test time, which is an interesting application of an approach often used in calibration.\n- The theorems presented seem consistent with the general consensus among the imbalanced classification field.\n- Results are presented on a variety of modalities (tabular, image and text)\n- Experiments are performed in a good number of scenarios, various imbalance proportions $\\pi$, optimising classifiers on the data itself and using features from a pretrained network.", "weaknesses": "- The paper is difficult to follow in places, there are a lot of concepts to grasp in section 2.\n- Gordon's theorem should be cited at it first mention on page 2\n- [1] presents a method for adjusting decision boundaries based on the uncertainty from drawing a random sample from each class, and could be discussed in section 3. I believe this method would help with the truncation of the TLD, and it could be worth discussing how concentration inequalities relate to the TLD and ELD. \n- Most of the theoreitcal results around calibration and prediction probabilities are in the appendix, which makes the section seem incomplete in the main paper. Section 5 is similar, in that most of the details are in the appendix. The paper could benefit from moving one of these sections to the appendix completely, and expanding on the other.\n\n[1] Clifford, Matt, et al. \"Learning Confidence Bounds for Classification with Imbalanced Data.\" ECAI 2024 (European Conference on Artificial Intelligence) (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NFOX9dTZN4", "reviewer": "Reviewer_b1pL", "summary": "The paper provides formal results for linear classifiers (logistic regression and SVM) in the asymptotic regime where the size of the training set $n$ scales to infinity proportionally to their number of parameters $d$ ($n/d \\to \\delta$). The task is binary classification, the input data are assumed to be generated by a 2 component Gaussian Mixture Model, with components centered in $\\pm {\\boldsymbol \\mu}$ and identity covariance, and the labels coincide with the component membership. In particular:\n- Theorem 2.1 focuses on the SVM, and shows the existence of a critical threshold $\\delta_c$ such that for $\\delta<\\delta_c$ the training set is linearly separable. In this case, the errors on the majority/minority class are given in terms of the sufficient statistics of the model (inner product between model’s weights and ${\\boldsymbol \\mu}$, bias and margin), obtained asymptotically as the solution of a variational problem. The training and testing logit distributions are shown to tend, respectively, to a rectified Gaussian and to a Gaussian. The truncation of the training distribution is more severe for the minority class, leading to overfitting.\n- Proposition 3.1 considers the strategy of margin rebalancing in the proportional asymptotic regime, finding the optimal value of the parameter rebalancing the margin, in order to attain minimal balanced error.\n- Theorem 3.2 considers the “high imbalance” asymptotics, defined by a vanishing (like $d^{-a}$) imbalance ratio, separation between the components of the mixture scaling like $d^b$, size of training set  scaling like $d^{c+1}$. There are 3 phases, according to the relative values of the scaling exponents: one where both minority and majority errors are small regardless the margin rebalancing parameter, one where this parameter has to scale with a certain power of $d$ in order to avoid O(1) error on the minority class, one where the linear classifier behaves as random guess.\n- Section 4 pushes the analysis in the proportional regime to prove monotonicity of common miscalibration metrics with the imbalance ratio.", "questions": "- I think the paper should mention in the title or in the abstract that it is about linear classifiers, to better represent its content.\n- Can the authors discuss the connections between their work and recent analysis in similar setting? I am thinking at [1] (which considers Gaussian mixtures with generic covariances), [2] (which relaxes the assumption on Gaussian data proving universality results on data distribution), [3] (which uses an heuristic theory to make sharp asymptotic predictions on popular test metrics under imbalance), [4], [5] … Even if an extensive literature review is out of scope here, some of these works have to be mentioned to address the claims of novelty of the paper, as they all derive results in the proportional asymptotics the paper considers.\n- If I understand correctly, the main novel point of Theorem 2.1 is the proof of the asymptotic distribution of training/test logits. In [4], Eq. (9) (test logit) and (53) (train logit), and references from early literature therein, similar results are reported. Can the authors comment whether the statements are comparable?\n- Can the authors report at least the main ideas of the proofs of their theorems in the main text? In its current form, the main text is substantially not self-contained, which is an issue given reviewers are not required (and mostly unable due to time constraints) to read the appendices. However, the illustration of the results in comparison with numerical simulations (Fig. 1,4,5) is commendable.\n\n[1] Loureiro et al. Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions, NeurIPS 2021\n\n[2] Dandi et al. Universality laws for Gaussian mixtures in generalized linear models, NeurIPS 2023\n\n[3] Loffredo et al. Restoring balance: principled under/oversampling of data for optimal classification, \n\n[4] Mannelli et al. Bias-inducing geometries: An exactly solvable data model with fairness implications, Phys. Rev. E 112, 025304\n\n[5] Pezzicoli et al. Class Imbalance in Anomaly Detection: Learning from an Exactly Solvable Model, AIStats 2025", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The sharp asymptotic results provide an interesting interpretation of overfitting in terms of skewness of the training logit distribution on the minority class. The sharp prediction on the optimal value of the margin rebalancing parameter is useful in practice. The high imbalance regime presents a rich phase diagram, with clear implications for the margin rebalancing strategy. Theoretical claims are supported by numerical experiments (Fig. 1, 4, 5), also on real data (Fig 2 and 3).", "weaknesses": "The theoretical analysis is limited to the very narrow setting of linear binary classification and data with isotropic covariances. Connections to some of the relevant literature in the field of high-dimensional statistics are not discussed. No clue or narrative on how the theorems are proven is given in the main text, making hard to assess their validity in a 2-weeks review (the appendix is 80 pages long). See Questions below for more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YmiMcT9Jz3", "reviewer": "Reviewer_Zvww", "summary": "This paper develops a statistical theory for imbalanced data classification in high-dimensional settings. The authors first introduce the logit distribution to characterize overfitting in imbalanced data, and then analyze its impact, particularly on the minority class. They further extend their analysis to examine the consequences of overfitting on model calibration.", "questions": "1. The motivation for proposing the logit distribution in Definitions 2.1 and 2.2 is unclear. It is also not entirely clear what empirical phenomenon Section 2 is intended to highlight or support.\n2. The purpose of introducing the problem in Definition 2.3 is somewhat unclear. It would be helpful to discuss whether similar formulations have been studied in previous literature and how this setting differs.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Quantifying the effects of overfitting in imbalanced data is an important and meaningful problem.\n2. The study is comprehensive, and the theoretical analysis is solid.", "weaknesses": "1. The paper is not well written or well organized. The motivation behind some of the definitions and problem settings is not clearly explained. See questions below for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BNYvCIifsE", "reviewer": "Reviewer_rQB8", "summary": "This paper addresses minority-class overfitting and poor confidence calibration in high-dimensional, imbalanced classification, where traditional theories fail to explain the mechanisms underlying overfitting. It uses a two-component Gaussian mixture model, focusing on logistic regression and SVM. A margin rebalancing method with a hyperparameter to adjust the constraints on the minority class margin is proposed. Theoretically, it analyzes the proportional asymptotic regime (the sample-dimension ratio converges to a finite value), exploring convergence of the parameter and logit distributions. Empirically, it is verified using CIFAR-10, IMDb, and IFNB data. The paper concludes that the high-dimensional training empirical logit distribution is truncated Gaussian (worse for minorities), and the test logit is standard Gaussian; optimal margin rebalancing eliminates majority bias, aligns class errors, and improves calibration. Contributions: establish an overfitting statistical theory, clarify the truncation mechanism, derive optimal hyperparameters, verify across datasets, and conjecture multiclass/non-isotropic extensions.", "questions": "Please see Weakness.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper establishes a dedicated statistical theory for high-dimensional imbalanced classification, clarifying logit distribution truncation as the core of overfitting and deriving optimal margin rebalancing, filling key theoretical gaps in the field.\n\n2. Its theoretical conclusions are supported by 2-Gaussian Mixture Model simulations and experiments on datasets like CIFAR-10 and IMDb, showing strong consistency between theoretical predictions and empirical results.\n\n3. The paper carries out rigorous proportional asymptotic analysis with solid proofs for parameter convergence, and its clear structure (theory→experiments→extensions) effectively improves the readability of complex theoretical content.", "weaknesses": "1. The weaknesses are mainly in the strong model assumptions that restrict the applicability of this paper. First, the paper heavily relies on the two-component Gaussian Mixture Model, which may not reflect real-world data complexities (e.g., non-Gaussian distributions or heavy noise). It lacks analysis of how to adapt its theory to such cases, and testing on datasets with more realistic distributions would enhance its applicability.\n\n2. While conjecturing multiclass extension, the paper provides no detailed theoretical derivation (e.g., optimal τ for multiclass) or dedicated experiments (e.g., full 10-class CIFAR-10). This limits use for multiclass tasks; supplementary multiclass analyses would address this gap.\n\n3. The theoretical analysis assumes homogeneous unit covariance for the 2-GMM. Still, it does not explore how heterogeneous covariance (e.g., different covariances for minority/majority classes) affects logit truncation and error bounds, which are common in real-world data.\n\n4. While the paper explores phase transitions in the high-imbalance regime (Section 3.2, Theorem D.8) and defines signal strength via $|\\mu\\|_2^2 \\propto d^b$ (parameter$b>0$), it only specifies the valid range of $\\tau$ (e.g., $\\tau \\gg d^{(a-b-c)/2}$ for medium signal) but not how $\\tau^{\\text{opt}}$ adjusts with $b$. Its high-imbalance experiment (Fig.5) fixes $b=0.3$ and only varies $a$. This gap limits guidance for tuning $\\tau^{\\text{opt}}$ in real-world tasks with different signal intensities.\n\n5. The key novel theoretical contribution of this paper compared to existing works is not clear. What is the challenge in deriving the theoretical results?\n\n6. There are some existing works that establish results on biased decision boundaries in imbalanced classification, e.g., [1], which share similar results to the paper, even from different perspectives. These works should be mentioned in the paper.\n\n[1] Hu et al., Learning Imbalanced Data with Beneficial Label Noise, ICLM, 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)