Machine Learning and Algorithms

Neueste Paper

• Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversity

  Enoch Hyunwook Kang · 12. Mai 2026

  Personalized alignment aims to adapt large language models to heterogeneous user preferences, yet the precise theoretical conditions for its statistical efficiency have not been formally established. This paper characterizes the conditions under which personalized alignment achieves O(1) online regr…

• Multi-Armed Bandits With Best-Action Queries

  Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Francesco Emanuele Stradi · 12. Mai 2026

  We study \emph{multi-armed bandits} (MABs) augmented with \emph{best-action queries}, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the \emph{full-feedback} model, where the lear…

• Rubric-based On-policy Distillation

  Junfeng Fang, Zhepei Hong, Mao Zheng, Mingyang Song, Gengsheng Li, Houcheng Jiang, Dan Zhang, Haiyun Guo, Xiang Wang, Tat-Seng Chua · 11. Mai 2026

  On-policy distillation (OPD) is a powerful paradigm for model alignment, yet its reliance on teacher logits restricts its application to white-box scenarios. We contend that structured semantic rubrics can serve as a scalable alternative to teacher logits, enabling OPD using only teacher-generated r…

• Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation

  Fran\c{c}ois Pachet · 11. Mai 2026

  Variable-order Markov models generate sequences over a finite alphabet by conditioning each symbol on the longest available suffix of the generated history. Regular constraints, by contrast, describe finite-horizon control requirements by an automaton: fixed positions, forced endings, metrical patte…

• A Note on Non-Negative $L_1$-Approximating Polynomials

  Jane H. Lee, Anay Mehrotra, Manolis Zampetakis · 11. Mai 2026

  $L_1$-Approximating polynomials, i.e., polynomials that approximate indicator functions in $L_1$-norm under certain distributions, are widely used in computational learning theory. We study the existence of \textit{non-negative} $L_1$-approximating polynomials with respect to Gaussian distributions.…

• The Minimax Rate of Second-Order Calibration

  Kamil Ciosek, Banafsheh Rafiee, Sina Ghiassian, Nicol\`o Felicioni · 11. Mai 2026

  We characterize the minimax rate of estimating the second-order calibration error for binary classification, which quantifies whether a higher-order predictor's epistemic-uncertainty estimate matches the conditional variance of the label probability on its level sets. Our key observation is that the…

• Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

  Idan Attias, Steve Hanneke, Arvind Ramaswami · 11. Mai 2026

  Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-ef…

• A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning

  Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel · 11. Mai 2026

  Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an input string (prompt), the generator is applied for $M$ steps, and the last generated token is taken as the final output. [J…

• Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift

  Adam R. Klivans, Shyamal Patel, Konstantinos Stavropoulos, Arsen Vasilyan · 11. Mai 2026

  Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al. (2024)). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In co…

• SMT-Based Active Learning of Weighted Automata

  Tiago Ferreira, Kevin Batz, Alexandra Silva · 11. Mai 2026

  We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/L*-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness an…

• Hypothesis generation and updating in large language models

  Hua-Dong Xiong · 8. Mai 2026

  Large language models (LLMs) increasingly help people solve problems, from debugging code to repairing machinery. This process requires generating plausible hypotheses from partial descriptions, then updating them as more information arrives. Yet how LLMs perform this form of inference, and how clos…

• Algorithmic Task Capture, Computational Complexity, and Inductive Bias of Infinite Transformers

  Orit Davidovich, Zohar Ringel · 8. Mai 2026

  We formally define algorithmic capture of combinatorial tasks as the ability of a transformer to extrapolate to arbitrary task sizes with controllable error and logarithmic sample adaptation, providing a sharp scaling criterion for distinguishing logic internalization from statistical interpolation.…

• Contrastive Identification and Generation in the Limit

  Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao · 8. Mai 2026

  In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, Kleinberg and Mullainathan [2024] introduced generation in the limit, where the learner instead must …

• Weak-to-Strong Generalization is Nearly Inevitable (in Linear Models)

  Scott Geng, Dutch Hansen, Jerry Li · 8. Mai 2026

  Weak-to-strong generalization is a phenomenon in post-training whereby a strong student model, when finetuned solely with feedback from a weaker teacher, can not only surpass the teacher, but can improve upon its own capabilities. Recent work of Burns et al. (2023) demonstrated that this can occur i…

• Autolearn: Learn by Surprise, Commit by Proof

  Kang-Sin Choi · 8. Mai 2026

  We propose Autolearn, a framework that enables language models to learn from documents they read, with no external supervision. Passages that produce anomalously high per-token loss are flagged, verified through a self-generated Q&A chain, and trained on with conviction-proportional $\beta_2$ adjust…

• Realizable Bayes-Consistency for General Metric Losses

  Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich · 6. Mai 2026

  We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond $0$-$1$ classification \citep{bousquet_theory_2021, hanneke2021universalbayesconsistencymetric} and real-valued regression \citep{attias_univers…

• Gradient-Discrepancy Acquisition for Pool-Based Active Learning

  Mohamadsadegh Khosravani, Sandra Zilles · 5. Mai 2026

  The effectiveness of active learning hinges on the choice of the acquisition criterion by which a learning algorithm selects potentially informative data points whose label is subsequently queried. This paper proposes a novel gradient-based acquisition criterion, derived from a generalization bound …

• Active multiple matrix completion with adaptive confidence sets

  Andrea Locatelli, Alexandra Carpentier, Michal Valko · 5. Mai 2026

  In this work, we formulate a new multi-task active learning setting in which the learner's goal is to solve multiple matrix completion problems simultaneously. At each round, the learner can choose from which matrix it receives a sample from an entry drawn uniformly at random. Our main practical mot…

• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

  Tim Sinen · 5. Mai 2026

  We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under the uniform distribution in the model of \citet{KM25} where each input coordinate is independently flipped with probability $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves complexi…

• Efficient Parameter Estimation of Truncated Boolean Product Distributions

  Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos · 5. Mai 2026

  We study the problem of estimating the parameters of a Boolean product distribution in $d$ dimensions, when the samples are truncated by a set $S \subset \{0, 1\}^d$ accessible through a membership oracle. This is the first time that the computational and statistical complexity of learning from trun…

• Selective Prediction from Agreement: A Lipschitz-Consistent Version Space Approach

  Mohamadsadegh Khosravani · 5. Mai 2026

  We consider selective classification with abstention in the fixed-pool (or transductive) setting, where the unlabeled pool is given beforehand and only a subset of points can be queried for labels. Our main insight is to view selective prediction through agreement: given queried labels and Lipschitz…

• Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals

  Jizhou Huang, Brendan Juba · 30. April 2026

  We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples $(\mathbf{x}, \mathrm{y})$ drawn from an unknown distribution on $\mat…

• A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound

  Francesco Orabona · 30. April 2026

  In Orabona and P\'al [2016], we introduced the shifted KT potentials, to remove the $\ln \ln T$ factor in the parameter-free learning with expert bound. In this short technical note, I show that this is equivalent to changing the prior in the Krichevsky--Trofimov algorithm. Then, I show how to use t…

• On the Learning Curves of Revenue Maximization

  Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas · 30. April 2026

  Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm's error for a fixed underlying distribu…

• Bayesian Inverse Transition Learning: Learning Dynamics From Near-Optimal Trajectories

  Leo Benac, Abhishek Sharma, Sonali Parbhoo, Finale Doshi-Velez · 29. April 2026

  We consider the problem of estimating the transition dynamics $T^*$ from near-optimal expert trajectories in the context of offline model-based reinforcement learning. We develop a novel constraint-based method, Inverse Transition Learning, that treats the limited coverage of the expert trajectories…