3 papers
cs.LG2025
Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
Dhruv Rohatgi, Abhishek Shetty, Donya Saless +4
Test-time algorithms that combine the generative power of language models with process verifiers that assess the quality of partial generations offer a promising lever for elicitin…
cs.LG2025
Proofs as Explanations: Short Certificates for Reliable Predictions
Avrim Blum, Steve Hanneke, Chirag Pabbaraju +1
We consider a model for explainable AI in which an explanation for a prediction consists of a subset of the training data (if it exists) such that all classifiers $h'…
stat.ML2025
PAC Learning with Improvements
Idan Attias, Avrim Blum, Keziah Naggita +3
One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes samples to learn to error (and more, if the…