<p>I am new to this subject so this question might seem a bit trivial</p>

<p>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?</p>

<p>If the answer is yes I will be greatful if you will provide me some reference</p>

<p>Thanks</p>

CC BY-SA 3.0
2015-08-30T02:42:14.233Z
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?
usul
CC BY-SA 3.0
2015-08-30T02:44:21.663Z
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)$.
usul
CC BY-SA 3.0
2015-08-30T02:53:41.200Z
(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.
usul
CC BY-SA 3.0
2015-09-01T14:38:53.587Z
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.
Neal Young
<machine-learning><convex-optimization><online-algorithms>
Convergence of online convex optimization methods
rabe
# Convergence of online convex optimization methods

(Asked by: username_0 on 2015-08-29)

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

**Tags:** machine-learning, convex-optimization, online-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_1**: 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)$.  
> **username_1**: (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.  
> **username_2**: 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.  

---

## 0 answers

