Machine Learning and Algorithms

Derniers papiers

• Deep Networks Learn Deep Hierarchical Models

  Amit Daniely · 5 janvier 2026

  We consider supervised learning with $n$ labels and show that layerwise SGD on residual networks can efficiently learn a class of hierarchical models. This model class assumes the existence of an (unknown) label hierarchy $L_1 \subseteq L_2 \subseteq \dots \subseteq L_r = [n]$, where labels in $L_1$…

• Efficient Active Learning with Abstention

  Yinglun Zhu, Robert Nowak · 1 janvier 2026

  The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This…

• Active Learning with Neural Networks: Insights from Nonparametric Statistics

  Yinglun Zhu, Robert Nowak · 1 janvier 2026

  Deep neural networks have great representation power, but typically require large numbers of training examples. This motivates deep active learning methods that can significantly reduce the amount of labeled training data. Empirical successes of deep active learning have been recently reported in th…

• Theory and Algorithms for Learning with Multi-Class Abstention and Multi-Expert Deferral

  Anqi Mao · 30 décembre 2025

  Large language models (LLMs) have achieved remarkable performance but face critical challenges: hallucinations and high inference costs. Leveraging multiple experts offers a solution: deferring uncertain inputs to more capable experts improves reliability, while routing simpler queries to smaller, d…

• On Admissible Rank-based Input Normalization Operators

  Taeyun Kim · 30 décembre 2025

  Rank-based input normalization is a workhorse of modern machine learning, prized for its robustness to scale, monotone transformations, and batch-to-batch variation. In many real systems, the ordering of feature values matters far more than their raw magnitudes - yet the structural conditions that a…

• Toward Storage-Aware Learning with Compressed Data An Empirical Exploratory Study on JPEG

  Kichang Lee, Songkuk Kim, JaeYeon Park, JeongGil Ko · 24 décembre 2025

  On-device machine learning is often constrained by limited storage, particularly in continuous data collection scenarios. This paper presents an empirical study on storage-aware learning, focusing on the trade-off between data quantity and quality via compression. We demonstrate that naive strategie…

• Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler

  Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian · 24 décembre 2025

  The development of efficient sampling algorithms catering to non-Euclidean geometries has been a challenging endeavor, as discretization techniques which succeed in the Euclidean setting do not readily carry over to more general settings. We develop a non-Euclidean analog of the recent proximal samp…

• Provably Extracting the Features from a General Superposition

  Allen Liu · 19 décembre 2025

  It is widely believed that complex machine learning models generally encode features through linear representations, but these features exist in superposition, making them challenging to recover. We study the following fundamental setting for learning features in superposition from black-box query a…

• Models That Prove Their Own Correctness

  Noga Amit, Shafi Goldwasser, Orr Paradise, Guy Rothblum · 19 décembre 2025

  How can we trust the correctness of a learned model on a particular input of interest? Model accuracy is typically measured on average over a distribution of inputs, giving no guarantee for any fixed input. This paper proposes a theoretically-founded solution to this problem: to train Self-Proving m…

• Sample-Efficient Optimization over Generative Priors via Coarse Learnability

  Pranjal Awasthi, Sreenivas Gollapudi, Ravi Kumar, Kamesh Munagala · 18 décembre 2025

  In zeroth-order optimization, we seek to minimize a function $d(\cdot)$, which may encode combinatorial feasibility, using only function evaluations. We focus on the setting where solutions must also satisfy qualitative constraints or conform to a complex prior distribution. To address this, we intr…

• Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

  Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran · 18 décembre 2025

  A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an analogous result for randomized learners: we show that the optimal expected mistake bound in learning a class $\mathcal{H}…

• Optimal Mistake Bounds for Transductive Online Learning

  Zachary Chase, Steve Hanneke, Shay Moran, Jonathan Shafer · 16 décembre 2025

  We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mistake bound is characterized by the Littlestone dimension $d$ of the concept class …

• Optimal Labeler Assignment and Sampling for Active Learning in the Presence of Imperfect Labels

  Pouya Ahadi, Blair Winograd, Camille Zaug, Karunesh Arora, Lijun Wang, Kamran Paynabar · 16 décembre 2025

  Active Learning (AL) has garnered significant interest across various application domains where labeling training data is costly. AL provides a framework that helps practitioners query informative samples for annotation by oracles (labelers). However, these labels often contain noise due to varying …

• The Optimal Approximation Factor in Density Estimation

  Olivier Bousquet, Daniel Kane, Shay Moran · 9 décembre 2025

  Consider the following problem: given two arbitrary densities $q_1,q_2$ and a sample-access to an unknown target density $p$, find which of the $q_i$'s is closer to $p$ in total variation. A remarkable result due to Yatracos shows that this problem is tractable in the following sense: there exists…

• In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learning

  Tomoya Wakayama, Taiji Suzuki · 9 décembre 2025

  This paper develops a finite-sample statistical theory for in-context learning (ICL), analyzed within a meta-learning framework that accommodates mixtures of diverse task types. We introduce a principled risk decomposition that separates the total ICL risk into two orthogonal components: Bayes Gap a…

• Limitations of Membership Queries in Testable Learning

  Jane Lange, Mingda Qiao · 3 décembre 2025

  Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the \emph{testable learning} model of Rubinfeld and Vasilyan [RV23], membership queries cannot decrease the time complexity of testable learning algorithms beyond the c…

• From monoliths to modules: Decomposing transducers for efficient world modelling

  Alexander Boyd, Franz Nowak, David Hyland, Manuel Baltieri, Fernando E. Rosas · 3 décembre 2025

  World models have been recently proposed as sandbox environments in which AI agents can be trained and evaluated before deployment. Although realistic world models often have high computational demands, efficient modelling is usually possible by exploiting the fact that real-world scenarios tend to …

• Cohort-Based Active Modality Acquisition

  Tillmann Rheude, Roland Eils, Benjamin Wild · 3 décembre 2025

  Real-world machine learning applications often involve data from multiple modalities that must be integrated effectively to make robust predictions. However, in many practical settings, not all modalities are available for every sample, and acquiring additional modalities can be costly. This raises …

• Limitations of Using Identical Distributions for Training and Testing When Learning Boolean Functions

  Jordi P\'erez-Guijarro · 2 décembre 2025

  When the distributions of the training and test data do not coincide, the problem of understanding generalization becomes considerably more complex, prompting a variety of questions. In this work, we focus on a fundamental one: Is it always optimal for the training distribution to be identical to th…

• The Active and Noise-Tolerant Strategic Perceptron

  Maria-Florina Blacan, Hedyeh Beyhaghi · 2 décembre 2025

  We initiate the study of active learning algorithms for classifying strategic agents. Active learning is a well-established framework in machine learning in which the learner selectively queries labels, often achieving substantially higher accuracy and efficiency than classical supervised methods-es…

• Samplability makes learning easier

  Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan · 2 décembre 2025

  The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable …

• Testing Transformer Learnability on the Arithmetic Sequence of Rooted Trees

  Alessandro Breccia, Federica Gerace, Marco Lippi, Gabriele Sicuro, Pierluigi Contucci · 2 décembre 2025

  We study whether a Large Language Model can learn the deterministic sequence of trees generated by the iterated prime factorization of the natural numbers. Each integer is mapped into a rooted planar tree and the resulting sequence $ \mathbb{N}\mathcal{T}$ defines an arithmetic text with measurable …

• Distance-based Learning of Hypertrees

  Shaun Fallat, Kamyar Khodamoradi, David Kirkpatrick, Valerii Maliuk, S. Ahmad Mojallal, Sandra Zilles · 1 décembre 2025

  We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hypertrees that we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm…

• Cleaning the Pool: Progressive Filtering of Unlabeled Pools in Deep Active Learning

  Denis Huseljic, Marek Herde, Lukas Rauch, Paul Hahn, Bernhard Sick · 1 décembre 2025

  Existing active learning (AL) strategies capture fundamentally different notions of data value, e.g., uncertainty or representativeness. Consequently, the effectiveness of strategies can vary substantially across datasets, models, and even AL cycles. Committing to a single strategy risks suboptimal …

• One-Shot Learning for k-SAT

  Andreas Galanis, Leslie Ann Goldberg, Xusheng Zhang · 1 décembre 2025

  Consider a $k$-SAT formula $\Phi$ where every variable appears at most $d$ times. Let $\sigma$ be a satisfying assignment, sampled proportionally to $e^{\beta m(\sigma)}$ where $m(\sigma)$ is the number of true variables and $\beta$ is a real parameter. Given $\Phi$ and $\sigma$, can we efficiently …