Machine Learning and Algorithms

Últimos artículos

• Candidate Retention for Abductive Learning

  Hao-Yuan He, Yu Liu, Ming Li · 1 de octubre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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 de septiembre de 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.…

• Understanding In-context Learning of Addition via Activation Subspaces

  Xinyan Hu, Kayo Yin, Michael I. Jordan, Jacob Steinhardt, Lijie Chen · 21 de septiembre de 2026

  To perform few-shot learning, language models extract signals from a few input-label pairs, aggregate them into a learned prediction rule, and apply this rule to new inputs. How is this implemented in the forward pass of modern transformer models? To explore this question, we study a structured fami…

• The Free Inference Dimension: Complexity Measure for Zero-Collision Navigation under Hypothesis Mixtures

  Luiz Carlos Castro Guedes, Edward Hermann Haeusler · 17 de septiembre de 2026

  Solomonoff induction frames prediction as a mixture over computable hypotheses, typically leading to identification of the true environment. In a finite meta-reinforcement learning setting with nested constraint families, in our previous work, we observe a different regime: a value-mixture (VM) agen…

• Quantifying the Value of Privileged Information Using a PAC-Bayesian Approach

  Vasily Bokov (aQa, Leiden University, The Netherlands, LIACS, Leiden University, Leiden, The Netherlands, Honda Research Institute Europe GmbH, Offenbach, Germany), Sebastian Schmitt (Honda Research Institute Europe GmbH, Offenbach, Germany), Vedran Dunjko (aQa, Leiden University, The Netherlands, LIACS, Leiden University, Leiden, The Netherlands), Hao Wang (aQa, Leiden University, The Netherlands, LIACS, Leiden University, Leiden, The Netherlands) · 14 de septiembre de 2026

  In practice, various learning scenarios provide access to auxiliary features exclusively during training. Incorporating such data to enhance model performance gave rise to a paradigm known as Learning Using Privileged Information (LUPI). While this extra information is intended to improve the result…