Debate as a training protocol gets its first learning analysis: cooperating debaters can cut mistakes to a constant in some cases
When debate is used as a training protocol, a human judges which of two debaters is right instead of supplying labels. Earlier work analyzed only the game between debaters under a known judge, leaving open how debaters learn the correct function. This work formulates debate as an online learning problem and shows there are cases where adversarial debate cannot learn but cooperative debate needs only a constant number of mistakes, with a new combinatorial dimension characterizing the optimal mistake bound for cooperative debaters in the realizable setting.