Ganghua Wang: Power of Queries: From Binary Search to Active Learning

Active learning improves learning efficiency by strategically selecting informative queries. Classical binary search illustrates its remarkable potential, achieving exponential convergence by repeatedly halving the search space. But how much of this efficiency survives in the presence of noisy responses, or extends to more general learning problems? In this talk, I will present two recent advances: establishing the exponential convergence of probabilistic bisection under noisy responses, and investigating how enriched queries can fundamentally change learning complexity. We further conjecture that halving may serve as a fundamental structural property that permits exponential convergence for membership queries. Together, these results advance a broader research agenda of understanding learning through interaction, where observations are adaptive and dependencies can be complex, with potential implications for modern AI systems.