Online Learning with an Almost Perfect Expert
This work addresses theoretical bounds in online learning for scenarios with nearly perfect experts, which is incremental to existing expert advice frameworks.
The paper tackles the multiclass online learning problem with expert advice, focusing on the scenario where the best expert makes at most b mistakes, and shows that when b = o(log₄n), the optimal forecaster's expected mistakes are at most log₄n + o(log₄n), with a tight bound proven via an adversary strategy for binary prediction.
We study the multiclass online learning problem where a forecaster makes a sequence of predictions using the advice of $n$ experts. Our main contribution is to analyze the regime where the best expert makes at most $b$ mistakes and to show that when $b = o(\log_4{n})$, the expected number of mistakes made by the optimal forecaster is at most $\log_4{n} + o(\log_4{n})$. We also describe an adversary strategy showing that this bound is tight and that the worst case is attained for binary prediction.