From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

Shinsaku Sakaue, Yuichi Yoshida

We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. By extending the batch-to…