In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines the regret $R_T = \sum_{i=1}^Tf_t(x_i) - \min_{x \in F} \sum_{i=1}^T f_t(x)$ Most typical analyses assume that the $f$s are convex.

Is this notion of "regret" lower bounded? Or under what conditions is it lower bounded?

I guess "minimizing the regret" does not make sense because one can always have an "Oracle" access to the sequence of points $x^*_i$ such that $x^*_i = \min_{x \in F} f_i(x)$. Then for this sequence for $x^*$ points the regret is only at most $0$.

  • $\begingroup$ There are lower bounds on regret that show that the classical algorithms cannot be improved. The lower bounds give an adversary which can force any algorithm to have a certain amount of regret. $\endgroup$ – Yuval Filmus Feb 17 '18 at 14:24
  • $\begingroup$ Thanks! Can you kindly link to the reference? And this lower bound is $0$? $\endgroup$ – gradstudent Feb 17 '18 at 18:59
  • $\begingroup$ The lower bound is certainly not 0. There are better lower bounds. $\endgroup$ – Yuval Filmus Feb 17 '18 at 23:06

There are many different models in which regret minimization makes sense. One particular model is Gaussian density estimation. Takimoto and Warmuth, in their paper The minimax strategy for Gaussian density estimation, give a tight analysis which includes both an upper bound achieved by a particular algorithm and an almost matching lower bound proved using the adversary method. There are probably many more such analyses out there.

  • $\begingroup$ Thanks! So in general I know of papers which in the context of such algorithms try to prove that the average regret i.e $\frac{R_T}{T}$is asymptotically $0$. What could be the motivation of trying to prove this particular limit? (...given that what the lower bound is seems to depend on the model and the distribution and other things as you say..) $\endgroup$ – gradstudent Feb 18 '18 at 5:28
  • $\begingroup$ This lower bound matches the performance of the proposed algorithm. Stated differently, the lower bound shows that the regret guaranteed by the algorithm is optimal. $\endgroup$ – Yuval Filmus Feb 18 '18 at 6:44
  • $\begingroup$ While it's true that the average regret goes to zero, we are still interested in how fast it decays. $\endgroup$ – Yuval Filmus Feb 18 '18 at 6:46
  • $\begingroup$ But what about my "oracle" based argument that $R_T$ can always be made at most $0$? If that is correct then why is average regret asymptotically going to $0$ (no matter how fats) even a good thing? Shouldnt one be targetting to get regret as negative? (because that is clearly possible for the oracle) $\endgroup$ – gradstudent Feb 18 '18 at 8:47
  • $\begingroup$ You cannot get negative regret. In the formula for regret, you're comparing the performance of your algorithm with the performance of the optimal after-the-fact algorithm. You cannot beat the optimal choice! $\endgroup$ – Yuval Filmus Feb 18 '18 at 8:50

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.