2
$\begingroup$

I am new to this subject so this question might seem a bit trivial

Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for example Online gradient descent guarantees a sub-linear regret (Assuming that our loss functions are convex). However does it guarantees a convergence $x_t \rightarrow x_*$ where $x_*$ is the best choice in hindsight? and in which rate?

If the answer is yes I will be greatful if you will provide me some reference

Thanks

$\endgroup$
  • $\begingroup$ Formalizing this isn't immediately obvious to me. One approach is to assume the loss functions are drawn i.i.d. and ask about convergence to the hypothesis with lowest expected loss on the underlying distribution. But I think you want a statement like: $x_t \to x_{*}(t)$ as $t \to \infty$ for any (infinite) sequence of loss functions, where $x_{*}(t)$ is the optimal hypothesis in hindsight at time $t$. Is that right? $\endgroup$ – usul Aug 30 '15 at 2:42
  • $\begingroup$ Intuitively it seems like you need a uniqueness condition on $x_{*}$ (think of a case where there are many optimal hypotheses). Or something like $d(x_t,X_{*}(t)) \to 0$ as $t \to \infty$ where $X_{*}(t)$ is the set of all optimal hypotheses in hindsight at time $t$ and $d(a,B) = \min_{b \in B} d(a,b)$. $\endgroup$ – usul Aug 30 '15 at 2:44
  • $\begingroup$ (Sorry for the comment chain.) Consider $K = [0,1]$ and each loss function is of the form $\ell(x,y) = |x-y|$ for some $y \in [0,1]$, and consider the sequence $y=0,1,1,0,0,1,1,0,0,1,1,\dots$. Then the sequence of optimal $x_{*}$ is $0,?,1,?,0,?,1,\dots$ where $?$ denotes that any value in $[0,1]$ is optimal. I think no online learning algorithm is going to converge to $x_*$ here ... some sort of strict convexity assumption seems necessary. $\endgroup$ – usul Aug 30 '15 at 2:53
  • 1
    $\begingroup$ I agree with Usul -- it doesn't guarantee x_t -> x*. E.g., with multiplicative-weights algorithms, each x_t may be a vertex of the underlying polytope, whereas x* is the average of the x_t's, which may be fractional. For another example, consider fictitious play, where, say, each player always plays the optimal pure strategy against the average of the opponent's historical plays. Each x_t will be a pure strategy, but OPT will not be. $\endgroup$ – Neal Young Sep 1 '15 at 14:38

Your Answer

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

Browse other questions tagged or ask your own question.