Machine Learning and Algorithms

Últimos artículos

• Enhanced Structured Lasso Pruning with Class-wise Information

  Xiang Liu, Mingchen Li, Xia Li, Leigang Qu, Guansu Wang, Zifan Peng, Yijun Song, Zemin Liu, Linshan Jiang, Jialin Li · 24 de marzo de 2026

  Modern applications require lightweight neural network models. Most existing neural network pruning methods focus on removing unimportant filters; however, these may result in the loss of statistical information after pruning due to failing to consider the class-wise information. In this paper, we e…

• The Cost of Replicability in Active Learning

  Rupkatha Hira, Dominik Kau, Jessica Sorrell · 24 de marzo de 2026

  Active learning aims to reduce the number of labeled data points required by machine learning algorithms by selectively querying labels from initially unlabeled data. Ensuring replicability, where an algorithm produces consistent outcomes across different runs, is essential for the reliability of ma…

• Learning-Augmented Algorithms for $k$-median via Online Learning

  Anish Hebbar, Rong Ge, Amit Kumar, Debmalya Panigrahi · 20 de marzo de 2026

  The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence …

• Learning Over Dirty Data with Minimal Repairs

  Cheng Zhen, Prayoga, Nischal Aryal, Arash Termehchy, Garrett Biwer, Lubna Alzamil · 19 de marzo de 2026

  Missing data often exists in real-world datasets, requiring significant time and effort for data repair to learn accurate models. In this paper, we show that imputing all missing values is not always necessary to achieve an accurate ML model. We introduce concepts of minimal and almost minimal repai…

• Identifying Latent Actions and Dynamics from Offline Data via Demonstrator Diversity

  Felix Schur · 19 de marzo de 2026

  Can latent actions and environment dynamics be recovered from offline trajectories when actions are never observed? We study this question in a setting where trajectories are action-free but tagged with demonstrator identity. We assume that each demonstrator follows a distinct policy, while the envi…

• CASHomon Sets: Efficient Rashomon Sets Across Multiple Model Classes and their Hyperparameters

  Fiona Katharina Ewald, Martin Binder, Matthias Feurer, Bernd Bischl, Giuseppe Casalicchio · 17 de marzo de 2026

  Rashomon sets are model sets within one model class that perform nearly as well as a reference model from the same model class. They reveal the existence of alternative well-performing models, which may support different interpretations. This enables selecting models that match domain knowledge, hid…

• Active Seriation: Efficient Ordering Recovery with Statistical Guarantees

  James Cheshire, Yann Issartel · 17 de marzo de 2026

  Active seriation aims at recovering an unknown ordering of $n$ items by adaptively querying pairwise similarities. The observations are noisy measurements of entries of an underlying $n$ x $n$ permuted Robinson matrix, whose permutation encodes the latent ordering. The framework allows the algorithm…

• From Specification to Architecture: A Theory Compiler for Knowledge-Guided Machine Learning

  Asela Hevapathige, Yu Xia, Sachith Seneviratne, Saman Halgamuge · 17 de marzo de 2026

  Theory-guided machine learning has demonstrated that including authentic domain knowledge directly into model design improves performance, sample efficiency and out-of-distribution generalisation. Yet the process by which a formal domain theory is translated into architectural constraints remains en…

• Mamba-3: Improved Sequence Modeling using State Space Principles

  Aakash Lahoti, Kevin Y. Li, Berlin Chen, Caitlin Wang, Aviv Bick, J. Zico Kolter, Tri Dao, Albert Gu · 17 de marzo de 2026

  Scaling inference-time compute has emerged as an important driver of LLM performance, making inference efficiency a central focus of model design alongside model quality. While the current Transformer-based models deliver strong model quality, their quadratic compute and linear memory make inference…

• Structural Incompatibility of Differentiable Sorting and Within-Vector Rank Normalization

  Taeyun Kim · 16 de marzo de 2026

  We show that differentiable sorting and ranking operators are structurally incompatible with within-vector rank normalization. We formalize admissibility through monotone invariance (C1), batch independence (C2), and a rank-space stability condition (C3). Gap-sensitive relaxations such as SoftSort v…

• From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages

  Katsuhiko Hayashi, Hidetaka Kamigaito · 16 de marzo de 2026

  We prove that all standard subregular language classes are linearly separable when represented by their deciding predicates. This establishes finite observability and guarantees learnability with simple linear models. Synthetic experiments confirm perfect separability under noise-free conditions, wh…

• Active Causal Structure Learning with Latent Variables: Towards Learning to Detour in Autonomous Robots

  Pablo de los Riscos, Fernando J. Corbacho · 16 de marzo de 2026

  Artificial General Intelligence (AGI) Agents and Robots must be able to cope with everchanging environments and tasks. They must be able to actively construct new internal causal models of their interactions with the environment when new structural changes take place in the environment. Thus, we cla…

• Minimax learning rates for estimating binary classifiers under margin conditions

  Jonathan Garc\'ia, Philipp Petersen · 16 de marzo de 2026

  We study classification problems using binary estimators where the decision boundary is described by horizon functions and where the data distribution satisfies a geometric margin condition. A key novelty of our work is the derivation of lower bounds for the worst-case learning rates over broad clas…

• BoSS: A Best-of-Strategies Selector as an Oracle for Deep Active Learning

  Denis Huseljic, Paul Hahn, Marek Herde, Christoph Sandrock, Bernhard Sick · 16 de marzo de 2026

  Active learning (AL) aims to reduce annotation costs while maximizing model performance by iteratively selecting valuable instances. While foundation models have made it easier to identify these instances, existing selection strategies still lack robustness across different models, annotation budget…

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

  Orit Davidovich, Zohar Ringel · 13 de marzo de 2026

  We formally define Algorithmic Capture (i.e., ``grokking'' an algorithm) as the ability of a neural network to generalize to arbitrary problem sizes ($T$) with controllable error and minimal sample adaptation, distinguishing true algorithmic learning from statistical interpolation. By analyzing infi…

• Federated Active Learning Under Extreme Non-IID and Global Class Imbalance

  Chen-Chen Zong, Sheng-Jun Huang · 12 de marzo de 2026

  Federated active learning (FAL) seeks to reduce annotation cost under privacy constraints, yet its effectiveness degrades in realistic settings with severe global class imbalance and highly heterogeneous clients. We conduct a systematic study of query-model selection in FAL and uncover a central ins…

• Adaptive Active Learning for Regression via Reinforcement Learning

  Simon D. Nguyen, Troy Russo, Kentaro Hoffman, Tyler H. McCormick · 12 de marzo de 2026

  Active learning for regression reduces labeling costs by selecting the most informative samples. Improved Greedy Sampling is a prominent method that balances feature-space diversity and output-space uncertainty using a static, multiplicative rule. We propose Weighted improved Greedy Sampling (WiGS),…

• A Gaussian Comparison Theorem for Training Dynamics in Machine Learning

  Ashkan Panahi · 11 de marzo de 2026

  We study training algorithms with data following a Gaussian mixture model. For a specific family of such algorithms, we present a non-asymptotic result, connecting the evolution of the model to a surrogate dynamical system, which can be easier to analyze. The proof of our result is based on the cele…

• Adaptive and Stratified Subsampling for High-Dimensional Robust Estimation

  Prateek Mittal, Joohi Chauhan · 11 de marzo de 2026

  We study robust high-dimensional sparse regression under finite-variance heavy-tailed noise, epsilon-contamination, and alpha-mixing dependence via two subsampling estimators: Adaptive Importance Sampling (AIS) and Stratified Sub-sampling (SS). Under sub-Gaussian design whose scopeis precisely delim…

• ActiveUltraFeedback: Efficient Preference Data Generation using Active Learning

  Davit Melikidze, Marian Schneider, Jessica Lam, Martin Wertich, Ido Hakimi, Barna P\'asztor, Andreas Krause · 11 de marzo de 2026

  Reinforcement Learning from Human Feedback (RLHF) has become the standard for aligning Large Language Models (LLMs), yet its efficacy is bottlenecked by the high cost of acquiring preference data, especially in low-resource and expert domains. To address this, we introduce ACTIVEULTRAFEEDBACK, a mod…

• Margin in Abstract Spaces

  Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine · 10 de marzo de 2026

  Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. This makes it a central case study in modern highly over-parameterized learning. We ask what minimal mathematical structu…

• ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning

  Roger Creus Castanyer, Faisal Mohamed, Pablo Samuel Castro, Cyrus Neary, Glen Berseth · 10 de marzo de 2026

  Reinforcement learning (RL) algorithms are highly sensitive to reward function specification, which remains a central challenge limiting their broad applicability. We present ARM-FM: Automated Reward Machines via Foundation Models, a framework for automated, compositional reward design in RL that le…

• Sparsity and Out-of-Distribution Generalization

  Scott Aaronson, Lin Lin Lee, Jiawei Li · 10 de marzo de 2026

  Explaining out-of-distribution generalization has been a central problem in epistemology since Goodman's "grue" puzzle in 1946. Today it's a central problem in machine learning, including AI alignment. Here we propose a principled account of OOD generalization with three main ingredients. First, t…

• Revisiting Unknowns: Towards Effective and Efficient Open-Set Active Learning

  Chen-Chen Zong, Yu-Qi Chi, Xie-Yang Wang, Yan Cui, Sheng-Jun Huang · 10 de marzo de 2026

  Open-set active learning (OSAL) aims to identify informative samples for annotation when unlabeled data may contain previously unseen classes-a common challenge in safety-critical and open-world scenarios. Existing approaches typically rely on separately trained open-set detectors, introducing subst…

• Agnostic learning in (almost) optimal time via Gaussian surface area

  Lucas Pesenti, Lucas Slot, Manuel Wiedmer · 9 de marzo de 2026

  The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its $L_1$-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most $\Gamma$, Klivans et al. (2008) show that degree $d = O(\Gamma^2 / \…