Machine Learning and Algorithms

Derniers papiers

• Useful to Whom? Sample Value Is Defined Only Relative to the Learner

  Yangze Liu, Xiao-Long Yin, Zhongyi Han · 2 octobre 2026

  What kind of data does a model need in order to learn? Coreset selection makes this question concrete: under a budget, keep the samples most useful for training. Easy-first and geometric coverage criteria can win in different budget regimes, separated by a crossover boundary. We ask whether this bou…

• Four Ways to Grow a Classifier and Why One of Them Cannot Learn

  Cagri Temel · 2 octobre 2026

  Constructive classifiers add structure while they train: a level to a tree, a unit to a hidden layer, a split at a leaf. This paper asks what each of four such growth decisions actually buys, measured under one fixed protocol in tree-structured and constructive models, and gives an exact diagnosis a…

• Nous: Learning and Certifying Memory Decisions Before Source Calibration

  Pranav Singh · 2 octobre 2026

  Belief-based agent memory needs reliable decisions about current state, yet its evidence may be noisy, copied, or stale. Must a memory calibrate its sources before it can improve its decisions? We separate learning, calibration, and revision certification. On one four-model hidden Markov family, lea…

• Candidate Retention for Abductive Learning

  Hao-Yuan He, Yu Liu, Ming Li · 1 octobre 2026

  Abductive learning combines neural perception with symbolic reasoning, using explanations generated by abduction to supervise the perception model. Multiple valid explanations of the same symbolic target can assign conflicting labels to the same inputs. Common policies select a single candidate as a…

• An Active-Bottleneck Mechanism for Weak-to-Strong Generalization

  Mohammad Zeinalpour, Amir Najafi · 29 septembre 2026

  Weak-to-strong generalization (W2SG) occurs when a student trained on a teacher's predictions outperforms that teacher. We study when this happens under fully converged, ridgeless two-stage learning, with no early stopping, no explicit regularization, and no assumption that the student is more expre…

• Active Feature Acquisition With Incomplete Training Data

  Reza Rezvan, Valter Sch\"utz, Han Wu, Linus Aronsson, Morteza Haghir Chehreghani · 29 septembre 2026

  In many prediction tasks, acquiring all features can be a prohibitively expensive or outright impossible task. Further, in many cases a static subset of features may not be enough to solve the problem sufficiently across various instances. Active Feature Acquisition (AFA) addresses these problems by…

• Information Design Against Gaming and Learning Adversaries

  Madhava Gaikwad · 29 septembre 2026

  A principal who deploys a binary classifier with an abstention option must decide which queries the mechanism abstains on. The right choice depends on the adversary. A gaming adversary already knows the classifier and tries to manipulate features across the boundary, so the principal does best by ab…

• Audit-First VAPO: Risk-Certified Selective Updates under Imperfect Verification

  Miaobo Hu, Shuhao Hu, Xiaobo Guo, Xin Wang, Bokun Wang, Rui Chen, Daren Zha, Jun Xiao · 29 septembre 2026

  Imperfect verifiers can assign a harmful update direction even when clipping and regularization bound its magnitude. We introduce Audit-First VAPO, which separates discrete directional admission from continuous magnitude control. An observation-only accept-appeal-abstain policy uses a finite seconda…

• ALF: An Active Learning Framework for Scientific Discovery

  Shikha Surana, Alex Hawkins-Hooker, Olivia Gallup, Christoph Brunken, Jules Tilly, Paul Duckworth · 28 septembre 2026

  Machine learning for scientific discovery is almost systematically data bound. Producing relevant high quality data, under budget constraints, is amongst the most promising ways to advance the field. Active learning (AL) offers promise wherever labelling requires expensive experiment, measurement, o…

• Mentored Decoding: Faster Inference meets Boosting

  Vivien Tran-Thien, Richard Nock · 28 septembre 2026

  Speculative decoding is a successful technique speeding up inference of a target autoregressive language model via a fast drafter model. Lossy speculative decoding allows a drift with respect to the target to further improve speed. Interestingly, it has been observed experimentally that the resultin…

• Time-Varying Bayesian Optimization Without a Metronome

  Anthony Bardou, Patrick Thiran · 25 septembre 2026

  Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing a time-varying, expensive, noisy black-box function $f$. However, most of the asymptotic guarantees offered by TVBO algorithms rely on the assumption that observations are acquired at a constant frequency. As the GP infe…

• Optimal Recovery Meets Bayesian Learning: Where Worst-Case Bounds Pay Off

  Gordei Verbii · 25 septembre 2026

  Worst-case Optimal Recovery (OR) and Bayesian learning describe the same Gaussian-quadratic-Hilbert problems in two vocabularies. We sharpen the correspondence - the radius of information equals a nugget-optimized GP posterior variance and is attained by the posterior mean at a closed-form balance n…

• An Order-Theoretic Characterization of Consistent Inductive Inference

  Zhou Lu · 25 septembre 2026

  When can a learner make only finitely many prediction errors along every infinite sequence labeled by a fixed, unknown hypothesis? We characterize this form of consistency for arbitrary binary hypothesis classes in ZFC, without requiring a uniform mistake bound. The characterization uses a single li…

• An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

  Guangjian Zhang · 25 septembre 2026

  We construct, for every function class $\mathcal{F}\subseteq[0,1]^{\mathcal{X}}$ and every accuracy $0<\alpha\le 1$, an agnostic sample compression scheme for the empirical squared loss: for every finite sample $S\in(\mathcal{X}\times[0,1])^m$ with arbitrary (noisy) labels, the scheme stores at most…

• Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

  Guangjian Zhang · 25 septembre 2026

  We study realizable multiclass PAC learning with bandit feedback: the learner observes an i.i.d. instance, predicts one of $K$ labels, and learns only whether the prediction was correct. Hanneke, Meng, Moran, and Shaeiri (arXiv:2605.25678) characterized the optimal sample complexity via the bandit D…

• Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

  Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu, Yilan Wei, Yankai Zeng, Bojun Lin · 25 septembre 2026

  Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of $M$ tasks with $L$ binary paths per task under the hard budget $(M+t)K$, where each path costs at most $K$ responses or e…

• On the Sample Complexity of Active Learning with Membership Queries

  Ganghua Wang, Shaddin Dughmi · 24 septembre 2026

  This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, we find that this seemingly mild change in query ability may dramatic…

• Even Sharper Bounds for Transductive Learning and Its Applications

  Yingzhen Yang · 24 septembre 2026

  We introduce Sharper Transductive Local Complexity (STLC), a localized complexity method for transductive learning under uniform sampling without replacement. The construction starts from a Bernstein-type concentration inequality for the supremum of the test--train empirical process. Its proof uses …

• Statistical Gains from Looped Estimation under Parameter Budgets

  Xinyu Tian, Xiaotong Shen · 23 septembre 2026

  Growing memory demands in artificial intelligence motivate learning with fewer trainable parameters. We ask whether a looped estimator, which repeatedly applies one fitted operator with parameters shared across iterations, can improve statistical accuracy under a common parameter budget. Its convent…

• Counting and Covering in Nearest-Neighbour Representations of Boolean Functions

  Martin Anthony · 22 septembre 2026

  We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification. There are two distinct settings: the prototypes may be arbitrary points of Euclidean space, or they may themselves be required to lie in the Boolean cube. For unrestricted prototypes, we stre…

• When and Why Do Linear Bias Probes Fail? A Geometric and Statistical Theory of Bias Detectability in Large Language Model Representations

  Mo Hai, Haifeng Li · 22 septembre 2026

  Linear probing is the standard instrument for detecting social biases in the hidden representations of large language models. Yet reported probe accuracies come almost exclusively from \emph{counterfactual} evaluations in which every input carries an explicit demographic marker. Once only a fraction…

• Classification with Abstention Under Class-Conditional Error Constraints

  Mohammadreza M. Kalan, Yuyang Deng, Sanaz Hamidi · 22 septembre 2026

  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 factor…

• Extreme classification: beating chance with one training example from each class

  Kevin Bleakley (LMO, CELESTE), Aaditya Ramdas · 21 septembre 2026

  We study a minimal classification problem: Given independent labeled observations $X\sim P$ and $Z\sim Q$ from two unknown distributions $P,Q$, and given an independent target $Y$ drawn with equal probability from $P$ or $Q$, can one classify $Y$ strictly better than chance whenever $P\neq Q$? The o…

• Sparse Priors for Efficient Distribution Learning

  Saumya Goyal, Barnab\'as P\'oczos · 21 septembre 2026

  Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported in $d$ dimensions from $n$ samples degrade as $O(n^{-1/\Theta(d)})$, though shown to be minimax optimal. We hypothesize that present bounds are too pessimistic becaus…

• How Many Posterior Samples? Calibrated Stopping for Adaptive Sensing

  Vincent Corlay, Andriy Enttsel · 21 septembre 2026

  In classification-oriented adaptive sensing, posterior samples characterize uncertainty at the current measurement state and can serve two roles: they may guide the next sensing direction, while their class labels provide votes for the candidate classes and determine whether sensing should continue.…