In the survey of Shai Shalev-Shwartz (see 1), the online convex optimization is presented as:


where one can see that the loss function is chosen. All proofs for regret bounds use (more or less) the loss difference $f_{t}(w_t) - f_{t+1}(w_t)$ and also $f_{t+1}(w_t) - f_{t+1}(w_{t+1})$.


enter image description here

as part of the proof, the author stets:

enter image description here

I can understand that $f_t(w_t)$ denotes the 'chosen' loss function at time $t$, where the solution vector $w_t$ was given. Yet, what does $f_{t+1}(w_t)$ mean? how can the loss function be chosen one step ahead and use the previous solution vector to the optimization? how can I compute the loss differences $f_t(w_t) - f_t(w_{t+1})$?


1 Answer 1


What does $f_{t+1}(w_t)$ mean? It means $f_{t+1}$ is evaluated at the argument value $w_t$.

As an illustrative example, let $t = 1, f_1(x) = x^2, w_1 = 1, w_2 = 2$. Then $f_t(w_t) - f_t(w_{t+1}) = 1 - 4 = -3$. At the time of the evaluation (at t+1), $f_t$ is still known, therefore it can be evaluated.

Anyhow, the point of the bounds is not that they would necessarily be computed during algorithm execution, but that they provide a guarantee as to progress, and therefore can facilitate such things as convergence proofs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.