Machine Learning and Algorithms

Neueste Paper

• The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets

  Yujun Kim, Chaewon Moon, Chulhee Yun · 29. Oktober 2025

  We study the parameter complexity of robust memorization for $\mathrm{ReLU}$ networks: the number of parameters required to interpolate any given dataset with $\epsilon$-separation between differently labeled points, while ensuring predictions remain consistent within a $\mu$-ball around each traini…

• Revisiting Agnostic Boosting

  Arthur da Cunha, Mikael M{\o}ller H{\o}gsgaard, Andrea Paudice, Yuxin Sun · 28. Oktober 2025

  Boosting is a key method in statistical learning, allowing for converting weak learners into strong ones. While well studied in the realizable case, the statistical properties of weak-to-strong learning remain less understood in the agnostic setting, where there are no assumptions on the distributio…

• Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization

  Milad Sefidgaran, Kimia Nadjahi, Abdellatif Zaidi · 28. Oktober 2025

  In this paper, we leverage stochastic projection and lossy compression to establish new conditional mutual information (CMI) bounds on the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than the existing ones. In particular, we prove that…

• On the Hardness of Approximating Distributions with Tractable Probabilistic Models

  John Leland, YooJung Choi · 28. Oktober 2025

  A fundamental challenge in probabilistic modeling is to balance expressivity and inference efficiency. Tractable probabilistic models (TPMs) aim to directly address this tradeoff by imposing constraints that guarantee efficient inference of certain queries while maintaining expressivity. In particul…

• Learning to Better Search with Language Models via Guided Reinforced Self-Training

  Seungyong Moon, Bumsoo Park, Hyun Oh Song · 28. Oktober 2025

  While language models have shown remarkable performance across diverse tasks, they still encounter challenges in complex reasoning scenarios. Recent research suggests that language models trained on linearized search traces toward solutions, rather than solely on the final solutions, exhibit improve…

• Online POMDP Planning with Anytime Deterministic Optimality Guarantees

  Moran Barenboim, Vadim Indelman · 28. Oktober 2025

  Decision-making under uncertainty is a critical aspect of many practical autonomous systems due to incomplete information. Partially Observable Markov Decision Processes (POMDPs) offer a mathematically principled framework for formulating decision-making problems under such conditions. However, find…

• How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension

  Cynthia Dwork, Lunjia Hu, Han Shao · 27. Oktober 2025

• Uniform Convergence Beyond Glivenko-Cantelli

  Tanmay Devale, Pramith Devulapalli, Steve Hanneke · 27. Oktober 2025

• Learning from Interval Targets

  Rattana Pukdee, Ziqi Ke, Chirag Gupta · 27. Oktober 2025

• SAMOSA: Sharpness Aware Minimization for Open Set Active learning

  Young In Kim, Andrea Agiollo, Rajiv Khanna · 27. Oktober 2025