Master algorithm design and upper bound proof

[akerman]

Hello,

I am currently preparing myself for exams and I have a past exam question which I can't solve. This question concerns online learning and the following picture illustrates it: View attachment 5486
Is anyone able to help me out and propose a solution to this question?

 

[Greg]

Hello, akerman! :D

We ask that our users show their progress (work thus far or thoughts on how to begin) when posting questions. This way our helpers can see where you are stuck or may be going astray and will be able to post the best help possible without potentially making a suggestion which you have already tried, which would waste your time and that of the helper.

Can you post what you have done so far?

 

[akerman]

All I have right now is the initial setting where we do not have k classes but we just use {0,1}. For this setting I have that the mistakes or loss for S (online sequence of data) is:
$Loss(S) = \sum_{t=1}^{m} |y_{t} - \hat{y_{t}} |$

From there I don't know how to progress or solve this question...