Machine Learning and Algorithms

Neueste Paper

• Learning-Augmented Robust Algorithmic Recourse

  Kshitij Kayastha, Vasilis Gkatzelis, Shahin Jabbari · 28. April 2026

  Algorithmic recourse provides individuals who receive undesirable outcomes from machine learning systems with minimum-cost improvements to achieve a desirable outcome. However, machine learning models often get updated, so the recourse may not lead to the desired outcome. The robust recourse framewo…

• Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set

  Yikai Wu, Haoyu Zhao, Sanjeev Arora · 28. April 2026

  AI methods, such as generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on the Maximum Independent Set (MIS) problem. Strikingly, eve…

• The Optimal Sample Complexity of Multiclass and List Learning

  Chirag Pabbaraju · 28. April 2026

  While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite…

• An Analysis of Active Learning Algorithms using Real-World Crowd-sourced Text Annotations

  Varun Totakura, Ankita Singh, Yushun Dong, Shayok Chakraborty · 28. April 2026

  Active learning algorithms automatically identify the most informative samples from large amounts of unlabeled data and tremendously reduce human annotation effort in inducing a machine learning model. In a conventional active learning setup, the labeling oracles are assumed to be infallible, that i…

• Learning to Think from Multiple Thinkers

  Nirmit Joshi, Roey Magen, Nathan Srebro, Nikolaos Tsilivis, Gal Vardi · 28. April 2026

  We study learning with Chain-of-Thought (CoT) supervision from multiple thinkers, all of whom provide correct but possibly systematically different solutions, e.g., step-by-step solutions to math problems written by different thinkers, or step-by-step execution traces of different programs solving t…

• Pliable rejection sampling

  Akram Erraqabi, Michal Valko, Alexandra Carpentier, Odalric-Ambrym Maillard · 27. April 2026

  Rejection sampling is a technique for sampling from difficult distributions. However, its use is limited due to a high rejection rate. Common adaptive rejection sampling methods either work only for very specific distributions or without performance guarantees. In this paper, we present pliable reje…

• Towards Multimodal Active Learning: Efficient Learning with Limited Paired Data

  Jiancheng Zhang, Yinglun Zhu · 24. April 2026

  Active learning (AL) is a principled strategy to reduce annotation cost in data-hungry deep learning. However, existing AL algorithms focus almost exclusively on unimodal data, overlooking the substantial annotation burden in multimodal learning. We introduce the first framework for multimodal activ…

• Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation

  David Holzm\"uller, Francis Bach · 24. April 2026

  Sampling from Gibbs distributions and computing their log-partition function are fundamental tasks in statistics, machine learning, and statistical physics. While efficient algorithms are known for log-concave densities, the worst-case non-log-concave setting necessarily suffers from the curse of di…

• The Sample Complexity of Multicalibration

  Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth · 24. April 2026

  We study the minimax sample complexity of multicalibration in the batch setting. A learner observes $n$ i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most $\va…

• Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms

  Yaiza Bermudez, Samir Perlaza, I\~naki Esnaola · 23. April 2026

  In this paper, it is shown, for the first time, that centralized performance is achievable in decentralized learning without sharing the local datasets. Specifically, when clients adopt an empirical risk minimization with relative-entropy regularization (ERM-RER) learning framework and a forward-bac…

• Energy-Based Open-Set Active Learning for Object Classification

  Zongyao Lyu, William J. Beksi · 23. April 2026

  Active learning (AL) has emerged as a crucial methodology for minimizing labeling costs in deep learning by selecting the most valuable samples from a pool of unlabeled data for annotation. Traditional AL operates under a closed-set assumption, where all classes in the dataset are known and consiste…

• Revisiting Active Sequential Prediction-Powered Mean Estimation

  Maria-Eleni Sfyraki, Jun-Kun Wang · 21. April 2026

  In this work, we revisit the problem of active sequential prediction-powered mean estimation, where at each round one must decide the query probability of the ground-truth label upon observing the covariates of a sample. Furthermore, if the label is not queried, the prediction from a machine learnin…

• Diverse Dictionary Learning

  Yujia Zheng, Zijian Li, Shunxing Fan, Andrew Gordon Wilson, Kun Zhang · 21. April 2026

  Given only observational data $X = g(Z)$, where both the latent variables $Z$ and the generating process $g$ are unknown, recovering $Z$ is ill-posed without additional assumptions. Existing methods often assume linearity or rely on auxiliary supervision and functional constraints. However, such ass…

• Metric-agnostic Learning-to-Rank via Boosting and Rank Approximation

  Camilo Gomez, Pengyang Wang, Yanjie Fu · 17. April 2026

  Learning-to-Rank (LTR) is a supervised machine learning approach that constructs models specifically designed to order a set of items or documents based on their relevance or importance to a given query or context. Despite significant success in real-world information retrieval systems, current LTR …

• Tight Bounds for Learning Polyhedra with a Margin

  Shyamal Patel, Santosh Vempala · 17. April 2026

  We give an algorithm for PAC learning intersections of $k$ halfspaces with a $\rho$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, \rho^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/\rho) \log k})\right)$. Notably, this improves on prior work which had an expone…

• Identifying Information from Observations with Uncertainty and Novelty

  Derek S. Prijatelj (University of Notre Dame), Timothy J. Ireland (Independent Researcher), Walter J. Scheirer (University of Notre Dame) · 17. April 2026

  A machine that learns a task from observations must encounter and process uncertainty and novelty, especially when it is to maintain performance when observing new information and to select the hypothesis that best fits the current observations. In this context, some key questions arise: what and ho…

• Autonomous Evolution of EDA Tools: Multi-Agent Self-Evolved ABC

  Cunxi Yu, Haoxing Ren · 17. April 2026

  This paper introduces the first \emph{self-evolving} logic synthesis framework, which leverages Large Language Model (LLM) agents to autonomously improve the source code of \textsc{ABC}, the widely adopted logic synthesis system. Our framework operates on the \emph{entire integrated ABC codebase}, a…

• Do We Still Need Humans in the Loop? Comparing Human and LLM Annotation in Active Learning for Hostility Detection

  Ahmad Dawar Hakimi, Lea Hirlimann, Isabelle Augenstein, Hinrich Sch\"utze · 16. April 2026

  Instruction-tuned LLMs can annotate thousands of instances from a short prompt at negligible cost. This raises two questions for active learning (AL): can LLM labels replace human labels within the AL loop, and does AL remain necessary when entire corpora can be labelled at once? We investigate both…

• Labeled TrustSet Guided: Batch Active Learning with Reinforcement Learning

  Guofeng Cui, Yang Liu, Pichao Wang, Hankai Hsu, Xiaohang Sun, Xiang Hao, Zhu Liu · 15. April 2026

  Batch active learning (BAL) is a crucial technique for reducing labeling costs and improving data efficiency in training large-scale deep learning models. Traditional BAL methods often rely on metrics like Mahalanobis Distance to balance uncertainty and diversity when selecting data for annotation. …

• An Optimal Sauer Lemma Over $k$-ary Alphabets

  Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri · 15. April 2026

  The Sauer-Shelah-Perles Lemma is a cornerstone of combinatorics and learning theory, bounding the size of a binary hypothesis class in terms of its Vapnik-Chervonenkis (VC) dimension. For classes of functions over a $k$-ary alphabet, namely the multiclass setting, the Natarajan dimension has long se…

• Loss-Driven Bayesian Active Learning

  Zhuoyue Huang, Freddie Bickford Smith, Tom Rainforth · 15. April 2026

  The central goal of active learning is to gather data that maximises downstream predictive performance, but popular approaches have limited flexibility in customising this data acquisition to different downstream problems and losses. We propose a rigorous loss-driven approach to Bayesian active lear…

• SpecMoE: A Fast and Efficient Mixture-of-Experts Inference via Self-Assisted Speculative Decoding

  Jehyeon Bang, Eunyeong Cho, Ranggi Hwang, Jinha Chung, Minsoo Rhu · 14. April 2026

  The Mixture-of-Experts (MoE) architecture has emerged as a promising approach to mitigate the rising computational costs of large language models (LLMs) by selectively activating parameters. However, its high memory requirements and sub-optimal parameter efficiency pose significant challenges for ef…

• Gaussian Approximation for Asynchronous Q-learning

  Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov, Alexey Naumov · 9. April 2026

  In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak-Ruppert averaged iterates generated by the asynchronous Q-learning algorithm with a polynomial stepsize $k^{-\omega},\, \omega \in (1/2, 1]$. Assuming that the sequence of state-action-next-state t…

• Approximate Replicability in Learning

  Max Hopkins, Russell Impagliazzo, Christopher Ye · 9. April 2026

  Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness). While a strong and interesting notion of stability, the cost of replicability can be prohibitive: there is no replica…

• Thompson Sampling for Infinite-Horizon Discounted Decision Processes

  Daniel Adelman, Cagla Keceli, Alba V. Olivares-Nadal · 9. April 2026

  This paper develops a viable notion of learning for sampling-based algorithms that applies in broader settings than previously considered. More specifically, we model a discounted infinite-horizon MDPs with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter. …