CS Paper Radar

Zero-Complement Extrapolation: Parameter Recovery and Classification in Severely Imbalanced Logistic Regression under Rank-Deficient Regimes

Chongsun Park

cs.LG stat.MLstat.ME ·submitted 2026-10-29 02:15 UTC · v2
benchmarktheory

Abstract

Parameter estimation and classification in binary logistic regression deteriorate severely when the number of minority class observations ($n_1$) is smaller than the feature dimension ($p$). Under such rank-deficient rarity ($n_1 < p$), maximum likelihood estimators suffer from quasi-complete separation, penalized likelihood methods exhibit severe intercept bias, and convex minority oversampling techniques such as SMOTE collapse into an $(n_1 - 1)$-dimensional affine subspace. In this paper, we propose a novel \textit{Self-Calibrated Zero-Complement} estimator that shifts the paradigm from minority interpolation to majority fringe extrapolation. Grounded in Stein's Lemma, we prove that the conditional expectation shift of the abundant majority class ($Y=0$) induced by logistic truncation uniquely identifies the true hyperplane normal $\boldsymbolβ$ after Mahalanobis whitening. We further establish that extrapolating synthetic minority instances outward from the high-quantile density fringe of the majority distribution along the conjugate direction preserves full-rank covariance regularity ($\mathrm{rank} = p$). To accommodate both semi-supervised environments (with an unlabeled background mean) and strictly supervised subsamples, we introduce a hybrid estimator incorporating the intrinsic third-moment skewness of the majority class alongside a location-shift-invariant zero-boundary intercept calibration. Extensive Monte Carlo simulations and real-world benchmark applications (Wisconsin Diagnostic Breast Cancer and Banknote Authentication) under extreme rarity ($n_1 \in \{3, 5\}$) demonstrate that our approach prevents parameter divergence, recovers the oracle hyperplane with high fidelity, and substantially outperforms Firth's regression and SMOTE in F1-score and estimation stability.

Comment
Submitted to a peer-reviewed journal; 16 pages, 1 figure, 4 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Rare-Tail Statistics For Learning Biased Gaussian Halfspaces with Label Noise

cs.DS stat.MLcs.LGmath.ST ·2026-11-18 ·Arya Mazumdar, Prateeti Mukherjee, Harsh Vardhan
top venue similarity 0.60
Abstract · NeurIPS 2026, to appear

We revisit the classical problem of learning general Gaussian halfspaces in the presence of label noise, with particular focus on the large-bias regime, where information-computation gaps are conjectured in several standard label-noise models. Concretely, we present and analyze the rare-tail mean estimator, an extremely simple one-shot statistic that averages only the observed minority class. In the large-bias regime, classical Averaging (Servedio, 1999) and related global first-moment statistics are provably suboptimal, while the rare-tail mean estimator recovers the target halfspace direction at the information-theoretic sample rate (modulo log factors) under a broad class of label noise models, including probit noise and margin-dependent noise with very slow decay away from the boundary. Notably, our guarantees allow labels arbitrarily close to the decision boundary to be nearly random, while still giving strong directional recovery from a small number of samples. The estimator also cleanly interpolates between the noiseless and noisy regimes: without noise, it attains the same sample rate as classical separability-based methods for realizable halfspaces, and under low noise, or noise that decays away from the boundary, it keeps this rate even after linear separability has been destroyed. As an application, we consider a two-stage curriculum in which source samples, whose noise may be arbitrarily close to $1/2$ near the boundary and decay very slowly away from it, precede target samples, whose noise flips every label at the same rate, i.e., random classification noise (RCN). Since both stages share the same Bayes optimal halfspace, our estimator supplies the directional warm start needed by existing refinement routines, and together they learn the RCN target at the information-theoretic sample rate in the large-bias regime, up to log factors.

0.39

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

cs.LG stat.ML ·2026-11-03 ·Zhijie Zheng
hot direction similarity 0.60
Abstract · 18 pages

We give a proper constant-factor agnostic learner for affine halfspaces under full-dimensional log-concave marginals. For arbitrary binary labels, the algorithm uses independent labeled samples and returns a single affine halfspace with error at most $C\mathrm{OPT}+\varepsilon$. Its sample and real-arithmetic complexity are polynomial in dimension, inverse accuracy, and the logarithm of the reciprocal failure probability. The mean and covariance of the marginal need not be known, and the sample complexity can be made linear in this logarithmic confidence factor. The main geometric result compares global disagreement with disagreement on a balanced restriction: for a minority halfspace of mass $p$, global disagreement is within universal constant factors of $p$ times conditional disagreement, provided the latter is sufficiently small. To construct the restriction from noisy labels, we estimate the minority cap's mean and covariance robustly, approximately minimize the classical zonoid-depth dual objective, and expand a superlevel set to a marginal quantile. The disagreement comparison cancels the noise amplification caused by conditioning and allows the learned halfspace to be used on the entire space. The analysis combines degree-four sum-of-squares moment bounds for log-concave laws with a translation-based reduction from balanced affine learning to homogeneous halfspace learning.

0.35

Benign Overfitting under Heterogeneous Input Fusion

cs.LG stat.ML ·2026-10-07 ·Houzhen Liu, Xiaobo Xia
similarity 0.58
Abstract · 51 pages, 6 figures

Benign overfitting is extensively studied when learning from a single high-dimensional input, but its behavior under heterogeneous input fusion remains largely unexplored. We study this question for minimum-norm linear interpolation under a heterogeneous Gaussian design, comparing two statistically dependent input blocks with their fusion while holding the underlying population task fixed. For regression, we identify a full-spectrum covariance certificate whose asymptotic status is independent of the cutoff threshold and prove that it is preserved by every positive-semidefinite joint covariance consistent with the two marginals. This protection is sharp, yet it does not extend to all benign regression problems: outside the certified regime, two benign marginals can have a harmful fusion. For one-sparse Gaussian classification, benignity in the regular regime is characterized by the balance between surviving predictive signal and nuisance contamination. Fusion can move these two quantities in opposite directions, and within this model class every marginal-to-joint benign/non-benign pattern is attainable. We further show that the same fused input can have qualitatively different effects on regression and classification. These results establish that benign overfitting under heterogeneous fusion is determined by the joint signal and spectral geometry created by input interaction, rather than by marginal benignity alone.

0.20

A Convex-Analytic Reformulation for Poisoning Attacks on Logistic Regression

cs.LG math.OC ·2026-11-12 ·Carina Moreira Costa, Maria Eduarda Pinheiro, Martin Schmidt
similarity 0.58
Abstract

We study data poisoning attacks on logistic regression with $\ell_2$-regularization, where an attacker chooses the features of a fixed number of injected observations with prescribed labels to maximize the logistic loss on the clean training data. Strong convexity of the defender's problem yields an exact reformulation through its first-order optimality conditions. Using convex conjugacy of the softplus function, we replace the sigmoid relations by a single convex optimality-gap inequality and express the attacker's objective as a concave function. A change of variables makes the stationarity condition affine, leaving bounded bilinear equalities as the only nonconvex constraints. We derive finite bounds on all variables involved in these equalities, including a global bound on the coefficient norm and tighter bounds obtained by preprocessing based on convex optimization. Experiments on eight binary classification datasets evaluate attack effectiveness and compare the two reformulations when solved with SCIP. Attacks obtained by local optimization degrade predictive performance on most datasets, while the convex-analytic formulation produces substantially stronger reported dual bounds within a fixed time limit.

0.22

Assumption-lean logistic regression with missing covariates

cs.IT stat.MLcs.LGmath.ST+1 ·2026-10-05 ·Jyotishka Ray Choudhury, Kabir Aladin Verchand, Richard J. Samworth, Ashwin Pananjady
similarity 0.58
Abstract

Missing covariates are frequently encountered in supervised learning problems, and classical methods for estimation using such data use carefully chosen imputation schemes for missing data, or likelihood approximations that lead to nonconvex $M$-estimation problems. These methods and their relatives are suitable for scenarios in which the covariate distribution is known, and more broadly, have enjoyed tremendous success in linear models. But even in basic nonlinear problems such as logistic regression in moderate dimensions, such methods can experience drastic failure modes when the covariate distribution is unknown. Motivated by the need for reliable alternatives, we consider the problem of parameter estimation in logistic regression with missing covariates. Crucially, we operate in the assumption-lean setting where the covariate distribution is unknown (but bounded). We design a stochastic approximation method that is based on $Z$-estimation with a novel monotone operator, and establish that our algorithm is computationally efficient and achieves provable signal recovery at parametric rates under the hypothesis that covariates are missing completely at random. Our theory sharply characterizes the $\ell_2^2$ risk of the estimator in terms of the missingness profile, accommodating heterogeneous observation probabilities. Importantly, it shows that our method always outperforms the de facto ``complete-case'' estimator that ignores observations with any missing data. Even in the setting with homogeneous missingness (in which each covariate is observed independently with probability $q$), our bounds exhibit intricate and nonstandard dependence on $q$ that can yield significant improvements over using only complete cases. We complement our upper bounds with new information-theoretic lower bounds that show that this intricate dependence on $q$ is fundamental in a minimax sense.

0.25

Reweighting for Transfer Classification: Exact Risk Conversion and Minimax Adaptation

cs.LG math.STstat.ML ·2026-11-06 ·Aoran Chen, Yang Feng
similarity 0.57
Abstract · 87 pages, 5 figures. Main text (32 pages) followed by the Supplementary Material

A source can make a training mixture easier to learn while making its accuracy less valuable for the target. We study how the training problem a source creates and the finite-sample error of learning it jointly determine target-risk guarantees under reweighting. For binary classification, for each pair of laws and each positive target weight, we derive the sharpest target excess hinge-risk bound implied by mixture excess alone, uniformly over clipped predictors. This exact conversion curve is determined by density-weighted local votes. A two-sample oracle inequality for weighted support vector machines supplies the mixture excess, and the composition becomes explicit for Gaussian kernels. On a tilted-boundary class, we establish the all-procedure minimax classification rate $[n+s_+^2/(m^{-1}+τ^2)]^{-1}$ in the transferable strength $s_+$ and the tilt $τ$, separating source sampling uncertainty ($m^{-1}$) from relation uncertainty ($τ^2$). A target-checked Gaussian-SVM selector adapts to unknown $s_+$ and $τ$ up to a logarithmic factor for fixed dimension, and retains the target-only rate up to the same factor against arbitrary independent sources under the stated target model. On a separate smooth opposition class, the minimax risk within the family of exact Gaussian SVMs fitted to the original labels with nonnegative weights is exponentially larger than the unrestricted minimax risk whenever the target sample is at most half the source sample, despite arbitrary data-dependent weighting and tuning. The value of a source thus depends on the training problem it creates, on what accuracy there means for the target, and on whether the permitted use of the source can implement the needed correction.

0.27

Outliers and the Hard-Margin Linear SVM in High-Dimension, Low-Sample-Size Settings

cs.LG stat.ML ·2026-11-10 ·Yugo Nakayama
similarity 0.57
Abstract

We study how outliers affect the hard-margin linear support vector machine when the dimension grows while the sample sizes remain fixed. For one-sided contamination, the centered Gram matrix converges to a constant inlier block plus an outlier-diagonal component, and the limiting dual problem has a closed-form solution. All outliers act through one effective distance. This representation yields explicit thresholds for loss of inlier support, margin shrinkage. intercept displacement, and asymptotic misclassification. We then treat contamination in both classes. The limiting intercept is the multiplier of the class-balance constraint, and the two classes pull it in opposite directions. Consequently, at most one class can collapse or be asymptotically misclassified, whereas symmetric contamination leaves the limiting discriminant function unchanged even though the margin shrinks. Seven numerical experiments verify the dual allocation, phase transitions, and discriminant limits.

0.24

Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle

cs.LG ·2026-09-01 ·Angshul Majumdar
published similarity 0.56
Abstract

We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least a fraction 1 minus epsilon of good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least 1 divided by 1 minus 2 epsilon. This matches the classical median-of-means bound and proves that the trimmed-block oracle constant 1 divided by 1 minus epsilon cannot be attained within the convex class. We then introduce a nonconvex block-Lp family for p between 0 and 1 and derive finite-sample deterministic robustness bounds for all global minimizers. As p decreases from 1 toward 0, these bounds continuously approach the trimmed-block oracle constant. For sufficiently small p, the global minimizers coincide with those of the oracle under a mild separation condition. We also show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite 2 plus delta moments and high-dimensional extensions to robust mean estimation and sparse regression.

0.41