Given vectors $x_1,\dots,x_T \in R^d$ satisfying $\|x_i\|_2 = 1$, define $A_0 = I$ and $A_t = I + \sum_{i=1}^tx_ix_i^\top$ for $t \geq 1$. We are interested in the following quantity: \begin{align} S_{d,T} = \sum_{i=1}^T\|A_{i-1}^{-1}x_i\|_2. \end{align} If $d = 1$, it is easy to bound $S_{1,T}$ by $\log T$ as follows: \begin{align} S_{1,T} = \sum_{i=1}^T\frac{1}{i} = O(\log T). \end{align} Is it true that for $d\geq 2$, we still have the similar bound $S_{d,T} \leq O(poly(d)\log T)$, where $poly(d)$ represents some polynomial of $d$?
Add a comment
|