CS Paper Radar

Classification with Abstention Under Class-Conditional Error Constraints

Mohammadreza M. Kalan, Yuyang Deng, Sanaz Hamidi

cs.LG stat.ML ·submitted 2026-09-18 22:45 UTC · v1

Abstract

We study binary classification with abstention under separate class-conditional error constraints, with the objective of minimizing abstention while keeping both errors below prescribed thresholds. We characterize the distribution-free minimax rate of excess abstention risk, up to logarithmic factors, in terms of the complexity of the hypothesis class and the sample size. To make the framework amenable to computation with models such as neural networks, we introduce surrogate-loss formulations and derive finite-sample guarantees for excess surrogate ambiguity risk. We formulate the resulting learning task as a constrained optimization problem and characterize its computational complexity in the convex setting. Finally, we evaluate our approach on various datasets and compare its performance with a competing method for this problem.

Closest papers

Nearest neighbours by meaning across the whole index.

Credal Machine Learning for Risk-Averse Decision Making

cs.LG stat.ML ·2026-10-08 ·Timo Löhr, Paul Hofman, Maximilian Muschalik, Eyke Hüllermeier
similarity 0.64
Abstract

In many machine learning applications, it is necessary to guard against worst-case scenarios and predictions that could result in substantial losses. In principle, this can be achieved by training risk-averse predictive models that minimize loss functions such as conditional value-at-risk (CVaR), rather than relying on models that perform well on average. In practice, however, the effectiveness of this approach to risk aversion is undermined by the learner's uncertainty regarding the true loss distribution and, consequently, the true CVaR. To achieve reliable risk-aversion, we propose a method in which this (epistemic) uncertainty is represented in terms of credal sets, i.e., sets of probability distributions. More specifically, we develop an efficient yet reliable learner that produces predictions in the form of credal sets and combine it with a novel decision rule that maps each credal set to a single predictive distribution for CVaR minimization. Across classification, under distribution shift, and in reinforcement learning, our approach reliably avoids catastrophic decisions, while sacrificing little in expected performance.

0.23

Risk-Averse Decision-Focused Learning: Minimizing CVaR of Regret

cs.LG cs.AI ·2026-11-14 ·Jayanta Mandi, Senne Berden, Victor Bucarey, Concepcion Dominguez, Tias Guns
similarity 0.63
Abstract

Many combinatorial optimization (CO) problems involve parameters that are uncertain when the problem must be solved. In such settings, the parameters have to be predicted from correlated contextual information before a solution can be computed. \emph{Decision-focused learning} (DFL) addresses this by training the predictive model to produce predictions that optimize downstream decision quality. Most existing DFL methods are risk-neutral and minimize the expected regret. In high-stakes applications this can lead to undesirable outcomes, because decision-makers must also account for the tail risk of decision quality. Prior risk-sensitive approaches typically model uncertainty explicitly and solve a stochastic or robust optimization problem at inference time, which increases computational complexity. We instead propose a DFL framework that achieves risk-sensitive behavior while retaining point predictions and deterministic optimization at inference time. Starting from the dual representation of the Conditional Value-at-Risk (CVaR) and adding entropy regularization, we derive a smooth surrogate for the CVaR of regret. Its gradient induces an instance-dependent reweighting within each minibatch that emphasizes high-risk outcomes, so the approach can turn existing surrogate-loss DFL methods, including the SPO+ loss, into risk-sensitive variants. When instantiated with SPO+, the resulting objective admits a generalization bound on the CVaR of the true regret. Experiments on knapsack, portfolio, shortest-path, and energy-aware scheduling problems show substantial reductions in tail regret when the uncertain parameters exhibit heterogeneous tail behavior.

0.09

Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative

cs.LG stat.MLstat.APstat.ME ·2026-10-07 ·Samuel Gruffaz, Muhammad Fawad, Jaakko Nevalainen
similarity 0.63
Abstract

While binary classification is one of the most extensively studied problems in machine learning, the regime in which the goal is to learn a classifier with an almost zero false negative rate remains largely unexplored. In this paper, we introduce the Extreme Binary Classification problem, where the objective is to learn a classifier whose false negative rate $α$ is constrained by $ε_{N_1}=o_{N_1\to\infty}(1/N_1)$, with $N_1$ denoting the number of positive examples in the training set. To address this problem, we propose a threshold adaptation method theoretically grounded in guarantees derived from Extreme Value Theory, together with a feature selection procedure based on a permutation test applied to sample maxima. Experimental results on four real-world datasets of varying sizes demonstrate that our approach compares favorably with state-of-the-art methods. In addition, we illustrate its interpretability through an application to a cancer screening dataset.

0.28

Comparing Corrupted Constrained Learning Problems

cs.LG math.STstat.ML ·2026-08-26 ·Laura Iacovissi, Rabanus Derr, Robert C. Williamson
theory similarity 0.63
Abstract · 53 pages

A key result in statistics is the data processing inequality, originally proved by Blackwell (1951) and later refined by DeGroot (1962) in terms of statistical uncertainty. The latter statement claims that the Bayes risk achieved on raw data always undercuts the Bayes risk on a processed version of the same data. This seemingly contradicts empirical findings in machine learning: pre-training, representation learning, feature learning, data augmentation are techniques used to improve performance of machine learning models. We reconcile both worlds by simply accepting that machine learning problems are constrained learning problems: the model class used does not include all measurable functions. We present counterexamples showing that the classical data processing inequality fails to hold in such a setting. Hence, we formulate a generalized data processing inequality, requiring the constrained Bayes risk of a joint distribution (with respect to a loss function and a constrained model class) to lower bound the constrained Bayes risk on the stochastically modified data distribution, regardless of the choice of distribution. We show this inequality to be equivalent to a set containment condition on a specific function set induced by the loss and model class, called the superprediction set. Finally, we exploit our characterization, derive sufficient conditions for this containment and quantify the inequality-gap.

0.31

Efficient Robust Learning at the Information-Theoretic Limit

cs.DS cs.LGstat.ML ·2026-09-15 ·Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
similarity 0.63
Abstract · Corrected the arXiv abstract to match the pdf

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $η+ \varepsilon$ where $η$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2η+ \varepsilon$. Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). Here we resolve this problem and give such an algorithm. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits low-degree polynomial approximators with respect to hypercontractive distributions. This captures basic settings including halfspaces with respect to Gaussian marginals. Our techniques make new connections to various types of online convex optimization algorithms. As a surprising consequence, we show that efficient SQ learnability in the agnostic setting implies efficient learning with contamination (with respect to Gaussians or uniform over the hypercube).

0.37

Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners

cs.LG ·2026-10-30 ·Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma
published similarity 0.62
Abstract · Full version of the paper appearing in FOCS 2026. The abstract was shortened due to requirements from arXiv

We develop a new algorithmic framework for learning Boolean concept classes under logconcave distributions. Our framework applies to broad families of multi-index models and yields significantly faster robust learners than were previously known in these settings. It extends to partial classification and testable learning. Consequently, we obtain improved learners for several fundamental concept classes, including functions of halfspaces and multiclass linear classifiers, under logconcave marginals. Our starting point is a new boosting framework based on weak partial learners. Classical boosting approaches require often-intractable distribution-free weak learners or yield weak approximation guarantees. We show instead that weak learners for partial classification, where labels may be undefined on part of the domain, suffice for strong agnostic learning. The key challenge is that boosting requires a weak learner that succeeds under conditioned distributions that are not guaranteed to be logconcave. To address this, we develop a recursive moment-based partitioning procedure: given a logconcave distribution $X$ and a conditional version $X'$, we partition the space into polynomially many convex regions so that, on most regions, the low-degree moments of $X$ and $X'$ approximately agree. On each good region, a well-behaved multi-index model correlates with a low-degree polynomial, giving a weak hypothesis. Combining these hypotheses yields the required weak learner. A key ingredient of our approach is an efficient method for detecting moment discrepancy. Specifically, we show how to find a low-dimensional subspace that captures any non-trivial discrepancy between $X$ and $X'$, if one exists. Our approach combines spectral analysis of moment tensors with recent progress on isoperimetry for logconcave measures. This discrepancy-finding procedure may be of independent interest.

0.16

Information-Theoretic Generalization for Set-Input Optimization-Valued Objectives

cs.LG stat.ML ·2026-11-07 ·Futoshi Futami, Masahiro Fujisawa
similarity 0.61
Abstract

Modern machine learning is increasingly evaluated using criteria such as multicalibration, CVaR, and Cressie-Read DRO, which target subgroup reliability, tail risk, and distributional robustness rather than averages of fixed per-example losses. Existing information-theoretic generalization bounds for pointwise losses do not directly apply, because these empirical criteria depend on the entire batch and involve a post-hoc auxiliary optimization over witnesses, thresholds, or reweightings. We formalize this structure as set-input optimization-valued objectives. In the balanced supersample setting, we bound the expected optimized validation-training gap in terms of an objective-dependent sub-Gaussian parameter and the square root of the prediction-based conditional mutual information (fCMI) between the learned supersample prediction table and the selector vector. Combining this with fixed-predictor population-validation comparisons yields unified algorithm-dependent generalization bounds. We verify sub-Gaussianity of the selector gap using stability and convex L2-Lipschitz certificates, obtaining concrete bounds for multicalibration, CVaR, and Cressie-Read DRO, with a stability-based single-index refinement.

0.21

How Accurate Is Accurate Enough?

cs.LG ·2026-09-30 ·Ningkang Peng, Qianfeng Yu, Jingyang Mao, Xiaoqian Peng, Yanhui Gu
similarity 0.61
Abstract · 24 pages, including supplementary material

How accurate must a numerical approximation be within a learning system? Primitive error alone cannot answer this question: errors of the same magnitude can have very different consequences for losses, predictions, and gradients at different learning states. We study this question through the learning objective itself. The objective weights classwise numerical errors nonuniformly according to the current state, so the importance of an error depends not only on its magnitude but also on the class it affects and the weight that class receives. For softmax cross-entropy, we characterize this coupling between class weights and errors and derive the exact extrema of the signed loss change over pairings of fixed non-target probability and score-error multisets, with the target probability and target score error held fixed. Building on this structure, we establish finite-error guarantees that propagate primitive error to losses, probabilities, predictions, and feature gradients, then invert these guarantees to obtain a certified primitive tolerance for the current state under prescribed learning-level error requirements. We give a complete instantiation of the framework in high-dimensional von Mises-Fisher learning. Controlled interventions and a large collection of saved learning states show that identical primitive error can produce substantially different learning consequences, while certified numerical tolerances vary by orders of magnitude across states under the same learning-level requirements. These results show that the adequacy of a numerical approximation must be assessed in relation to the current learning state and the quantity to be preserved; numerical accuracy should itself be treated as part of the learning objective.

0.25