Machine Learning and Algorithms

Neueste Paper

• Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction

  Zonghuan Xu · 7. August 2026

  Model evaluations may fix all tests before observing any responses or select later tests using earlier responses. We study this choice in a conditional-query model on a finite outcome space $\mathcal{X}$ with $|\mathcal{X}|=N$. We first ask which pairs of distribution classes can be reliably disting…

• Optimal Rates for Learning with Monotone Adversaries

  Anay Mehrotra · 7. August 2026

  A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is c…

• An Optimal Agnostic PAC Algorithm

  Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy · 7. August 2026

  Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<\delta\le 1/2$, with probability at least $1-\de…

• Diverse and Plausible Algorithmic Recourse via Tractable Recourse Distributions

  Anagha Sabu, Hrithik Suresh, Narayanan C. Krishnan · 6. August 2026

  Algorithmic recourse seeks to help individuals reverse unfavorable automated decisions by recommending actionable changes that achieve a desired outcome. As an individual usually has several distinct routes to a favorable decision, and different people can act on different ones, a recourse system sh…

• The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

  Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss · 6. August 2026

  We study distributionally robust PAC learning for the $0$--$1$-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order $k>1$ and radius $\rho\geq 0$. For hypothesis classes with VC dimension $d$, we establish realizable and agnostic sampl…

• Sample Complexity of Multicalibration for Multilevel Properties

  Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev, Shiva Prasad Kasiviswanathan · 6. August 2026

  Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined r…

• How Many Labels Are Enough? ALDA: Active Learning Deployment Advisor for Medical Image Classification

  Julia Machnio, Mads Nielsen, Mostafa Mehdipour Ghazi · 5. August 2026

  Active learning (AL) promises to reduce the cost of medical imaging projects by lowering the number of clinical labels required. However, practical deployment requires committing to a sampling strategy before the full annotation budget is spent, and choosing the wrong strategy can increase rather th…

• To Describe or Construct Statistical Learning Models Using the Category-theoretical Language

  Congwei Song · 5. August 2026

  Statistical learning is a fascinating field that has long been the mainstream of machine learning/artificial intelligence. A large number of results have been produced which can be widely applied to real-world problems. It also leads to many research topics and also stimulates new research. This rep…

• Self-Certification of Representation Adequacy: Sequential Certification at Minimum Task Loss

  Zijie Huang · 4. August 2026

  Agents that act on a compressed representation of their history face a structural risk: if the representation aliases histories with different optimal actions, no rule measurable with respect to the representation can avoid an irreducible per-round loss, and the agent may be unable to detect this fr…

• Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

  Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic · 4. August 2026

  We study the round complexity of learning a hidden partition $\mathcal{P}$ of an $n$-element universe using PAIR queries: PAIR($x,y$) tells us whether $x$ and $y$ belong to the same part of the partition or not. While it is easy to learn using $n|\mathcal{P}|$ queries using a basic algorithm and thi…

• On the Identifiability of Masked Prediction: Mode Blindness and Mask Schedules

  Yichao Cai, Javen Qinfeng Shi · 4. August 2026

  Masked prediction learns representations by fitting a schedule-weighted family of conditional laws, but it remains unclear when near-optimal conditional prediction pins down the underlying joint law. We study this question for data with two well-separated global modes, outside the reach of rapid-mix…

• Optimal Unambiguous DNFs and Alon-Saks-Seymour

  Chirag Pabbaraju · 4. August 2026

  We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $\Omega(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in cert…

• Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

  Xin Zou, Jingyuan Xu · 4. August 2026

  AdaBoost.MH reduces multi-class classification to a collection of binary subproblems and enjoys the classical boosting-type convergence guarantee under a weak learning condition. A more structured variant, Factorized AdaBoost.MH, uses base classifiers of the form $\mathbf{h}(x)=\alpha \mathbf{v} \bm…

• BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition

  Jiaorong Feng, Qian Li, Ying Li · 4. August 2026

  Active feature acquisition (AFA) asks which unobserved feature to measure next for each test instance under a budget. Greedy rules are easy to train but can overlook context features whose value is realized only through later acquisitions, while reinforcement-learning and generative approaches intro…

• Fast Rates for Swap-Agnostic Learning of Proper Losses

  Princewill Okoroafor · 3. August 2026

  Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benchmark captures prediction-dependent postprocessing, but appears to require solving a separate agnostic-learning problem …

• Tight Generalization Bound for AdaBoost

  Mikael M{\o}ller H{\o}gsgaard · 30. Juli 2026

  In this paper we show that the generalization error of AdaBoost is $\Theta\big(\tfrac{d\ln(n\gamma^{2}/d)}{n\gamma^2}+\tfrac{\ln(1/\delta)}{n}\big)$, where $\gamma$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample…

• BayesAME: Bayesian Active Model Evaluation

  Paula Cordero Encinar, Taylan Cemgil, Arnaud Doucet, Virginia Aglietti, Silvia Chiappa · 30. Juli 2026

  Evaluating large generative models across benchmarks is time-consuming and computationally expensive. This drives the need for methods that can estimate full benchmark performance by evaluating models on only a subset of items, known as a coreset. Current literature mostly requires the practitioner …

• Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue

  Rohan Chauhan, Ioannis Panageas · 28. Juli 2026

  Learning the natural parameters $z \in \mathbb{R}^n$ of discrete distributions $\mu_z$ from independent samples constrained to a subset $S \subseteq \{0,1\}^n$ is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributi…

• Local Regularization Does Not Characterize Multiclass PAC Learnability

  Eric Hou · 28. Juli 2026

  Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample. Asilis et al. asked whether this principle characterizes multiclass PAC learnability. We give a negative answer. There is a countable class of Daniely--S…

• Learning Distributions from Multiple Data Providers

  Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas · 28. Juli 2026

  Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution $p$ on a finite domain $[n]$. The learner is given a fixed family of queryable sets $\mathscr{…

• Hallucination Rates in Language Generation

  Debmalya Panigrahi, Fan Wei, Ian Zhang · 28. Juli 2026

  Language generation in the limit is an elegant model introduced by Kleinberg and Mullainathan [KM24] to formally study language generation by an algorithm that learns solely based on example strings. In this model, an algorithm is said to correctly generate from a language if it never makes an error…

• Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design

  Martin Anthony, Kaveh Salehzadeh Nobari · 24. Juli 2026

  An initial high-recall stage in an empirical pipeline decides which items pass to later review, labelling, or modelling, and relevant items it misses are lost to every subsequent stage. We study how many audit labels are needed to certify, with finite-sample validity, that this missed relevant mass …

• Optimal Recalibration of an Online Predictor

  Lunjia Hu, Kevin Tian, Chutong Yang · 23. Juli 2026

  We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorith…

• The Tractability Landscape of Sampling with Inexact Scores

  Anming Gu, Kevin Tian, Hubert Yang, Yusong Zhu · 22. Juli 2026

  We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the t…

• Fundamental limits of distributed multiclass classification from simple binary decisions

  Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh, Sidharth Jaggi, Parimal Parag · 22. Juli 2026

  We consider the problem of constructing a $K$-class classifier from the combination of $O(\log K)$ simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundam…