4 papers
Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem
Avrim Blum, Marten Garicano, Kavya Ravichandran +1
The improving multi-armed bandits problem is a formal model for allocating effort under uncertainty, motivated by scenarios such as investing research effort into new technologies,…
Online Learnability of Chain-of-Thought Verifiers: Soundness and Completeness Trade-offs
Maria-Florina Balcan, Avrim Blum, Kiriaki Fragkia +2
Large Language Models (LLMs) using chain-of-thought reasoning have demonstrated great potential for solving complex reasoning and planning tasks. However, their outputs remain unre…
Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees
Ally Yalei Du, Eric Huang, Dravyansh Sharma
Graph-based semi-supervised learning is a powerful paradigm in machine learning for modeling and exploiting the underlying graph structure that captures the relationship between la…
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 th…