The paper investigates the consistency of surrogate loss methods for classification and policy learning when the set of admissible classifiers is constrained, such as by interpretability or fairness requirements. It shows that hinge loss is the only surrogate that preserves consistency when constraints limit only the prediction set, but consistency can fail if constraints also restrict the functional form. The authors derive conditions guaranteeing consistency for hinge-risk-minimizing classifiers and use these results to design efficient hinge-loss-based procedures for monotone classification problems.
By Toru Kitagawa, Shosei Sakaguchi, Aleksey Tetenov
arXiv:2505. 04757v2 Announce Type: replace Abstract: This paper introduces a novel approach to contextual stochastic optimization, integrating operations research and machine learning to address decision-making under uncertainty.
By Louis Bouvier, Thibault Prunet, Vincent Lecl\`ere, Axel Parmentier
arXiv:2604. 27742v2 Announce Type: replace Abstract: A fundamental dichotomy in the theory of classification sets smoothness against statistical efficiency: smooth surrogate losses such as the logistic loss enable fast $O(1/T)$ optimization but yield slow square-root $H$-consistency bounds, while piecewise-linear losses like the Hinge loss achieve optimal linear $H$-consistency rates but are non-differentiable.
By Mehryar Mohri, Yutao Zhong
arXiv:2307.02719v5 Announce Type: replace
Abstract: Uncertainty sampling is a classical active-learning strategy, yet the statistical objective induced by its query rule is often implicit. We introdu...
By Shang Liu, Xiaocheng Li
arXiv:2607. 11947v1 Announce Type: cross Abstract: Typical semi-supervised learning (SSL) methods rely on distributional assumptions, and their performance degrades when these are violated.
By Yushi Hirose, Hiroo Irobe, Takafumi Kanamori
arXiv:2511. 22823v2 Announce Type: replace-cross Abstract: Weakly supervised learning has emerged as a practical alternative to fully supervised learning when complete and accurate labels are costly or infeasible to acquire.
By Miao Zhang, Junpeng Li, Changchun Hua, Yana Yang
arXiv:2602. 23128v2 Announce Type: replace Abstract: Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes.
By Mathieu Bazinet, Valentina Zantedeschi, Pascal Germain
arXiv:2607. 14889v1 Announce Type: new Abstract: This paper studies an optimal linear combination of binary classifiers based on a logical structuration of the dataset via truth tables.
By Jean-Marc Brossier, Olivier Lafitte
The paper presents a polynomial‑time algorithm for robustly learning Boolean concept classes with respect to a fixed distribution, achieving the optimal error rate of η + ε where η is the noise rate. It builds on Blanc’s earlier, computationally inefficient algorithm and introduces no‑regret learners to overcome the previous limitations. Additionally, the authors provide an efficient method that does not require an ERM oracle for any function class admitting sandwiching polynomials under hypercontractive distributions, including a first polynomial‑time solution for learning halfspaces with Gaussian marginals at error η + ε.
By Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
arXiv:2501. 10538v3 Announce Type: replace Abstract: The practical success of deep learning has led to the discovery of several surprising phenomena.
By Ichiro Hashimoto, Stanislav Volgushev, Piotr Zwiernik
The paper investigates the difference between cost‑agnostic and cost‑sensitive loss functions when model capacity is limited. It shows that, unlike in ideal infinite‑capacity settings, optimizing a cost‑sensitive objective can yield a strictly better downstream decision than post‑processing a cost‑agnostic model. The authors prove this gap under a hypothesis class that can recover the optimal decision boundary but not the optimal cost‑agnostic hypothesis, and provide a simple example and empirical evidence on UCI datasets with simple models.
By Jessica Finocchiaro, Sanket Shah, Milind Tambe
The paper investigates minimal‑norm interpolation and λ2‑regularized logistic‑loss minimization for binary classification using univariate two‑layer ReLU networks. It provides exact geometric characterizations of optimal classifiers, showing that unpenalized hidden‑layer biases yield continuous piecewise‑affine functions that tightly follow label switches, while penalized biases produce a unique, sparsest classifier with a single kink per same‑label segment. Adding a free affine skip connection does not change these function‑space solutions but guarantees that every KKT point becomes globally optimal, eliminating suboptimal KKT points that can arise without the skip connection.
By Karolina Drabik, Ben Lewis, Antoni Puch, Etienne Boursier, Piotr Hofman, Matthias Englert, Ranko Lazi\'c