Machine Learning and Algorithms

Derniers papiers

• The Stability of Singular Distribution: A Spectral Perspective on the Two-Phase Dynamics of Language Model Pre-training

  Hongtao Zhang, Wenjie Zhou, Chenxi Jia, Wei Chen, Xueqi Cheng · 27 mai 2026

  Large language model pre-training typically exhibits a two-phase trajectory: a fast initial loss drop followed by a prolonged slow improvement. We identify an underlying spectral phenomenon, Stability of Singular Distribution (SoSD), where the trace-normalized singular value spectrum stabilizes earl…

• PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

  Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri · 26 mai 2026

  We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space $\mathcal{X}$ and a label space $\mathcal{Y}$, as in classical multiclass PAC learning, but the learner does not observe the…

• Active Query Synthesis for Preference Learning

  Namrata Nadagouda, Nauman Ahad, Maegan Tucker, Mark A. Davenport · 26 mai 2026

  Efficient learning of user preferences is crucial for many modern decision making systems but typically requires costly labeled data. Active learning reduces this cost, yet standard methods are computationally expensive due to pool-based evaluation. Further, most methods assume all query feedback is…

• Minimax Limits of k-Fold Cross-Validation via Majority

  Ido Nachum, R\"udiger Urbanke, Thomas Weinberger · 26 mai 2026

  We study the mean-squared error of $k$-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds $k$. Despite the widespread use of cross-validation, principled guidance for choosing $k$ is largely absent, mainly due to the complex depende…

• Data Scaling as Progressive Coverage of a Predictive Contribution Spectrum

  Zihui Song, Shihao Ji, Hongxi Li, Shuaizhi Cheng, Chunlin Huang · 21 mai 2026

  We investigate the hypothesis that real-data scaling laws are governed by progressive coverage of a latent predictive contribution spectrum rather than by token-frequency tails alone. We work with a suffix-automaton representation of text corpora and define a data-intrinsic global-KL predictive cont…

• Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

  Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma · 21 mai 2026

  We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples $(x, y)$ from a distribution over $\mathbb{R}^d \times [k]$, with Gaussian $x$-marginal, the goal is to output a hypothesis whose error is comparable to that of the best $k…

• Testing Support Size More Efficiently Than Learning Histograms

  Renato Ferreira Pinto Jr., Nathaniel Harms · 21 mai 2026

  Consider two problems about an unknown probability distribution $p$: 1. How many samples from $p$ are required to test if $p$ is supported on $n$ elements or not? Specifically, given samples from $p$, determine whether it is supported on at most $n$ elements, or it is "$\epsilon$-far" (in total va…

• Iterative Chow Filtering for Learning with Distribution Shift

  Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan · 19 mai 2026

  Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled training examples, unlabeled test examples, and must make correct predictions on the test set but is allowed to abstain…

• Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

  Rita Adhikari, Shiwei Zeng · 19 mai 2026

  Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when…

• Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification

  Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci · 19 mai 2026

  Many inference-time language-model pipelines combine a cheap reward signal with an expensive verifier, such as exact answer checking in mathematical reasoning or hidden-test execution in code generation. We formalize this setting using a learning-theoretic lens as generative active search: a cost-…

• Statistical Unlearning of Distributions: A Hypothesis Testing Approach

  Aaradhya Pandey, Sanjeev Kulkarni · 19 mai 2026

  Machine learning systems increasingly face requirements to forget not only individual data points, but entire domains of information, such as toxic language, copyrighted corpora, or demographic biases. This raises a fundamental dilemma of statistical-computational tradeoffs: removing all samples fro…

• Complexity of Non-Log-Concave Sampling in Fisher Information

  Sinho Chewi, Andre Wibisono · 18 mai 2026

  We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution; this is a sampling analog of finding an approximate stationary point in optimization. Our algorithm is based on the proximal sampler, which is an implicit d…

• Silent Collapse in Recursive Learning Systems

  Zhipeng Zhang · 15 mai 2026

  Recursive learning -- where models are trained on data generated by previous versions of themselves -- is increasingly common in large language models, autonomous agents, and self-supervised systems. However, standard performance metrics (loss, perplexity, accuracy) often fail to detect internal deg…

• A Mutual Information Lower Bound for Multimodal Regression Active Learning

  Leonardo Ferreira Guilhoto, Akshat Kaushal, Paris Perdikaris · 15 mai 2026

  Active learning for continuous regression has lacked an acquisition function that targets epistemic uncertainty when the predictive distribution is multimodal: variance misses modal disagreement, and information-theoretic targets like BALD are designed for discrete outputs. We introduce a Two-Index …

• FrontierSmith: Synthesizing Open-Ended Coding Problems at Scale

  Runyuan He, Qiuyang Mang, Shang Zhou, Kaiyuan Liu, Hanchen Li, Huanzhi Mao, Qizheng Zhang, Zerui Li, Bo Peng, Lufeng Cheng, Tianfu Fu, Yichuan Wang, Wenhao Chai, Jingbo Shang, Alex Dimakis, Joseph E. Gonzalez, Alvin Cheung · 15 mai 2026

  Many real-world coding challenges are open-ended and admit no known optimal solution. Yet, recent progress in LLM coding has focused on well-defined tasks such as feature implementation, bug fixing, and competitive programming. Open-ended coding remains a weak spot for LLMs, largely because open-end…

• InfoSFT: Learn More and Forget Less with Information-Aware Token Weighting

  Mahdi Sabbaghi, George Pappas, Adel Javanmard, Hamed Hassani · 15 mai 2026

  Supervised fine-tuning (SFT) provides the standard approach for teaching LLMs new behaviors from offline expert demonstrations. However, standard SFT uniformly fits all samples -- including those with low likelihood under the base model -- which can disproportionately drive training updates toward o…

• Multi-Armed Sampling Problem and the End of Exploration

  Mohammad Pedramfar, Siamak Ravanbakhsh · 14 mai 2026

  This paper introduces the framework of multi-armed sampling, which serves as the sampling counterpart to the optimization problem of multi-armed bandits. Our primary motivation is to rigorously examine the exploration-exploitation trade-off in the context of sampling. We systematically define plausi…

• A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning

  Jason Gaitonde, Frederic Koehler, Elchanan Mossel, Joonhyung Shin, Allan Sly · 14 mai 2026

  We introduce a family of synthetic languages with hierarchical structure -- generated by a broadcast process on trees -- for which the role of context length and reasoning in autoregressive generation can be analyzed precisely. At the heart of our analytic approach is an \emph{exact $k$-gram ansatz}…

• Teaching and Learning under Deductive Errors

  Jan Arne Telle, Brigt H{\aa}vardstun, Jose Hernandez-Orallo · 14 mai 2026

  Most models of machine teaching and learning assume the learner makes no errors in its internal deductive inference. However, humans and large language models in few-shot learning regimes are two important examples of learners where this does not hold. They fail on some consistency checks, and they …

• Strategic PAC Learnability via Geometric Definability

  Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich · 14 mai 2026

  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hyp…

• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

  Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, Tom Waknine · 14 mai 2026

  We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every $\gamma>0$, uniform convergence at sca…

• AcquisitionSynthesis: Targeted Data Generation using Acquisition Functions

  Ishika Agarwal, Sofia Stoica, Emre Can Acikgoz, Pradeep Natarajan, Mahdi Namazifar, Jiaqi Ma, Dilek Hakkani-T\"ur · 14 mai 2026

  Data quality remains a critical bottleneck in developing capable, competitive models. Researchers have explored many ways to generate top quality samples. Some works rely on rejection sampling: generating lots of synthetic samples and filtering out low-quality samples. Other works rely on larger or …

• What is Learnable in Valiant's Theory of the Learnable?

  Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis · 14 mai 2026

  Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized varia…

• Learning U-Statistics with Active Inference

  Xiaoning Wang, Yuyang Huo, Liuhua Peng, Changliang Zou · 13 mai 2026

  $U$-statistics play a central role in statistical inference. In many modern applications, however, acquiring the labels required for $U$-statistics is costly. Motivated by recent advances in active inference, we develop an active inference framework for $U$-statistics that selectively queries inform…

• Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing

  Takayuki Kuriyama · 13 mai 2026

  We study positive-data learning of bounded-fan-out linear multiple context-free grammars under a fixed explicit finite monoid homomorphism \(h\). The main obstacle beyond the context-free case is that an MCFG nonterminal derives a tuple whose components may be placed in a surrounding sentence in dif…