Machine Learning and Algorithms

Últimos artículos

• On the Expressiveness of State Space Models via Temporal Logics

  Eric Alsmann, Lowejatan Noori, Martin Lange · 28 de enero de 2026

  We investigate the expressive power of state space models (SSM), which have recently emerged as a potential alternative to transformer architectures in large language models. Building on recent work, we analyse SSM expressiveness through fragments and extensions of linear temporal logic over finite …

• A Refinement of Vapnik--Chervonenkis' Theorem

  A. Iosevich, A. Vagharshakyan, E. Wyman · 27 de enero de 2026

  Vapnik--Chervonenkis' theorem is a seminal result in machine learning. It establishes sufficient conditions for empirical probabilities to converge to theoretical probabilities, uniformly over families of events. It also provides an estimate for the rate of such uniform convergence. We revisit the…

• A Refinement of Vapnik--Chervonenkis' Theorem

  A. Iosevich, A. Vagharshakyan, E. Wyman · 26 de enero de 2026

  Vapnik--Chervonenkis' theorem is a seminal result in machine learning. It establishes sufficient conditions for empirical probabilities to converge to theoretical probabilities, uniformly over families of events. It also provides an estimate for the rate of such uniform convergence. We revisit the…

• Towards a Theoretical Understanding to the Generalization of RLHF

  Zhaochun Li (Beijing Institute of Technolegy, Zhongguancun Academy), Mingyang Yi (Renmin University of China), Yue Wang (Zhongguancun Academy), Shisheng Cui (Beijing Institute of Technolegy), Yong Liu (Renmin University of China) · 26 de enero de 2026

  Reinforcement Learning from Human Feedback (RLHF) and its variants have emerged as the dominant approaches for aligning Large Language Models with human intent. While empirically effective, the theoretical generalization properties of these methods in high-dimensional settings remain to be explored.…

• Learning from Synthetic Data: Limitations of ERM

  Kareem Amin, Alex Bie, Weiwei Kong, Umar Syed, Sergei Vassilvitskii · 23 de enero de 2026

  The prevalence and low cost of LLMs have led to a rise of synthetic content. From review sites to court documents, ``natural'' content has been contaminated by data points that appear similar to natural data, but are in fact LLM-generated. In this work we revisit fundamental learning theory question…

• Next Generation Active Learning: Mixture of LLMs in the Loop

  Yuanyuan Qi, Xiaohao Yang, Jueqing Lu, Guoxiang Guo, Joanne Enticott, Gang Liu, Lan Du · 23 de enero de 2026

  With the rapid advancement and strong generalization capabilities of large language models (LLMs), they have been increasingly incorporated into the active learning pipelines as annotators to reduce annotation costs. However, considering the annotation quality, labels generated by LLMs often fall sh…

• Performance-guided Reinforced Active Learning for Object Detection

  Zhixuan Liang, Xingyu Zeng, Rui Zhao, Ping Luo · 23 de enero de 2026

  Active learning (AL) strategies aim to train high-performance models with minimal labeling efforts, only selecting the most informative instances for annotation. Current approaches to evaluating data informativeness predominantly focus on the data's distribution or intrinsic information content and …

• U-learning for Prediction Inference via Combinatory Multi-Subsampling: With Applications to LASSO and Neural Networks

  Zhe Fei, Yi Li · 21 de enero de 2026

  Epigenetic aging clocks play a pivotal role in estimating an individual's biological age through the examination of DNA methylation patterns at numerous CpG (Cytosine-phosphate-Guanine) sites within their genome. However, making valid inferences on predicted epigenetic ages, or more broadly, on pred…

• Process In-Context Learning: Enhancing Mathematical Reasoning via Dynamic Demonstration Insertion

  Ang Gao, Changshuo Zhang, Xiao Zhang, Deyang Li, Minjun Zhao, Fangchao Liu, Xinyu Zhang · 21 de enero de 2026

  In-context learning (ICL) has proven highly effective across diverse large language model (LLM) tasks. However, its potential for enhancing tasks that demand step-by-step logical deduction, such as mathematical reasoning, remains underexplored. A core limitation of existing ICL approaches is their s…

• Labels or Preferences? Budget-Constrained Learning with Human Judgments over AI-Generated Outputs

  Zihan Dong, Ruijia Wu, Linjun Zhang · 21 de enero de 2026

  The increasing reliance on human preference feedback to judge AI-generated pseudo labels has created a pressing need for principled, budget-conscious data acquisition strategies. We address the crucial question of how to optimally allocate a fixed annotation budget between ground-truth labels and pa…

• Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

  Radu Cosmin Dumitru, Ryo Yoshinaka, Ayumi Shinohara · 21 de enero de 2026

  It is well known that computing a minimum DFA consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the c…

• Learning Randomized Reductions

  Ferhat Erata, Orr Paradise, Thanos Typaldos, Timos Antonopoulos, ThanhVu Nguyen, Shafi Goldwasser, Ruzica Piskac · 21 de enero de 2026

  A self-corrector for a function $f$ takes a black-box oracle computing $f$ that is correct on most inputs and turns it into one that is correct on every input with high probability. Self-correctors exist for any function that is randomly self-reducible (RSR), where the value $f$ at a given point $x$…

• Sample-Near-Optimal Agnostic Boosting with Improved Running Time

  Arthur da Cunha, Miakel M{\o}ller H{\o}gsgaard, Andrea Paudice · 19 de enero de 2026

  Boosting is a powerful method that turns weak learners, which perform only slightly better than random guessing, into strong learners with high accuracy. While boosting is well understood in the classic setting, it is less so in the agnostic case, where no assumptions are made about the data. Indeed…

• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph

  Gautam Kamath, Alireza F. Pour, Matthew Regehr, David P. Woodruff · 16 de enero de 2026

  We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distributions $Q$, we describe an algorithm that satisfies local differential privacy, performs $\tilde{O}(k^{3/2})$ non-adaptiv…

• Large Language Models and Algorithm Execution: Application to an Arithmetic Function

  Farah Ben Slama (SyCoSMA, LIRIS), Fr\'ed\'eric Armetta (SyCoSMA, LIRIS) · 14 de enero de 2026

  Large Language Models (LLMs) have recently developed new advanced functionalities. Their effectiveness relies on statistical learning and generalization capabilities. However, they face limitations in internalizing the data they process and struggle, for instance, to autonomously execute algorithms.…

• An information-matching approach to optimal experimental design and active learning

  Yonatan Kurniawan (Brigham Young University, Provo, UT, USA), Tracianne B. Neilsen (Brigham Young University, Provo, UT, USA), Benjamin L. Francis (Achilles Heel Technologies, Orem, UT, USA), Alex M. Stankovic (SLAC National Accelerator Laboratory, Menlo Park, CA, USA), Mingjian Wen (University of Electronic Science and Technology of China, Chengdu, China), Ilia Nikiforov (University of Minnesota, Minneapolis, MN, USA), Ellad B. Tadmor (University of Minnesota, Minneapolis, MN, USA), Vasily V. Bulatov (Lawrence Livermore National Laboratory), Vincenzo Lordi (Lawrence Livermore National Laboratory), Mark K. Transtrum (Brigham Young University, Provo, UT, USA, SLAC National Accelerator Laboratory, Menlo Park, CA, USA) · 13 de enero de 2026

  The efficacy of mathematical models heavily depends on the quality of the training data, yet collecting sufficient data is often expensive and challenging. Many modeling applications require inferring parameters only as a means to predict other quantities of interest (QoI). Because models often cont…

• On the Emergence of Induction Heads for In-Context Learning

  Tiberiu Musat, Tiago Pimentel, Lorenzo Noci, Alessandro Stolfo, Mrinmaya Sachan, Thomas Hofmann · 12 de enero de 2026

  Transformers have become the dominant architecture for natural language processing. Part of their success is owed to a remarkable capability known as in-context learning (ICL): they can acquire and apply novel associations solely from their input context, without any updates to their weights. In thi…

• On the Limits of Self-Improving in LLMs and Why AGI, ASI and the Singularity Are Not Near Without Symbolic Model Synthesis

  Hector Zenil · 12 de enero de 2026

  We formalise recursive self-training in Large Language Models (LLMs) and Generative AI as a discrete-time dynamical system and prove that, as training data become increasingly self-generated ($\alpha_t \to 0$), the system undergoes inevitably degenerative dynamics. We derive two fundamental failure …

• Learning Multinomial Logits in $O(n \log n)$ time

  Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins · 9 de enero de 2026

  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=\{1,..., n\}$, each assigned a positive weight. A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight. This query model is a…

• Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms

  Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis · 9 de enero de 2026

  In this work, we give a ${\rm poly}(d,k)$ time and sample algorithm for efficiently learning the parameters of a mixture of $k$ spherical distributions in $d$ dimensions. Unlike all previous methods, our techniques apply to heavy-tailed distributions and include examples that do not even have finite…

• Inverse Q-Learning Done Right: Offline Imitation Learning in $Q^\pi$-Realizable MDPs

  Antoine Moulin, Gergely Neu, Luca Viano · 9 de enero de 2026

  We study the problem of offline imitation learning in Markov decision processes (MDPs), where the goal is to learn a well-performing policy given a dataset of state-action pairs generated by an expert policy. Complementing a recent line of work on this topic that assumes the expert belongs to a trac…

• Optimal Lower Bounds for Online Multicalibration

  Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth · 9 de enero de 2026

  We prove tight lower bounds for online multicalibration, establishing an information-theoretic separation from marginal calibration. In the general setting where group functions can depend on both context and the learner's predictions, we prove an $\Omega(T^{2/3})$ lower bound on expected multical…

• Sparse Knowledge Distillation: A Mathematical Framework for Probability-Domain Temperature Scaling and Multi-Stage Compression

  Aaron R. Flouro, Shawn P. Chadwick · 7 de enero de 2026

  We develop a unified theoretical framework for sparse knowledge distillation based on probability-domain softening operators. While the equivalence $p^{1/T} \propto \mathrm{softmax}(z/T)$ is well known, our contribution is an operator-level analytical framework built on this foundation rather than t…

• Beyond Expectations: Learning with Stochastic Dominance Made Practical

  Shicong Cen, Jincheng Mei, Hanjun Dai, Dale Schuurmans, Yuejie Chi, Bo Dai · 6 de enero de 2026

  Stochastic dominance serves as a general framework for modeling a broad spectrum of decision preferences under uncertainty, with risk aversion as one notable example, as it naturally captures the intrinsic structure of the underlying uncertainty, in contrast to simply resorting to the expectations. …

• Context-Free Recognition with Transformers

  Selim Jerad, Anej Svete, Sophie Hao, Ryan Cotterell, William Merrill · 6 de enero de 2026

  Transformers excel on tasks that process well-formed inputs according to some grammar, such as natural language and code. However, it remains unclear how they can process grammatical syntax. In fact, under standard complexity conjectures, standard transformers cannot recognize context-free languages…