Dear referees and chairs, 1 We would like to thank all referees for their close reading of the manuscript

We would like to thank all referees for their close reading of the manuscript. The second reason to include the multiclass setting is the bandit setting. For an overview of the different bounds we provided Table 1. The parameters can be found in Section 2. Importantly, Gaptron often is on par with, if not better than slower algorithms such as ONS. This lower bound does not apply to our setting, where the learner suffers the zero-one loss.