Online Portfolio Selection - Smooth Prediction
I presented the Exponentiated Gradient(EG) algorithm in my previous blog. Assuming the stock returns are lower bounded by \(r\), the regret of EG is \(O(\frac{1}{r}\sqrt{T\log(n)})\) and the run time is \(O(n)\) per iteration. Using a standard trick for “universalizing”, we can remove the lower bound assumption and get a regret of \(O(n^{1/2}\log(n)^{1/4} T^{3/4})\). In this blog, I present the Smooth Prediction Algorithm that improves the dependence on \(T\) to \(O(\log T)\).
Smooth Selection
In my first blog, I discussed the Follow-the-Leader(FTL) algorithm, which can be stated as:
\[x_{t} = \arg\max_{x \in \Delta_n} \sum_{i=1}^{t-1} \log(r_i^\top x)\]Smooth Selection is a Follow-the-Regularized-Leader(FTRL) algorithm with the log-barrier regularization, stated as:
\[x_{t} = \arg\max_{x \in \Delta_n} \sum_{i=1}^{t-1} \log(r_i^\top x)+ \sum_{j=1}^n \log(e_j^\top x)\]Here \(e_j\) is the \(j\)th standard basis vector. It can be thought of as an FTL algorithm that has been primed on the pseudo-return sequence \(e_1,\dots,e_n\) before seeing the actual returns \(r_1,\dots,r_T\).
Regret and Improvements
In the original paper, Smooth Prediction’s regret bound is stated as \(O(\frac{n}{(\min_{i,t} r_{t}[i])^2} \log(Tn))\). With a slightly better analysis, it is possible to show \(O(\frac{n}{(\min_{i,t} r_{t}[i])^2} \log(T))\). Here we used the fact that \(\text{det}(A) \leq (\text{Trace}(A)/n)^n\) instead of \(\text{det}(A) \leq \lambda_{\max} (A)^n\) that is used in the paper.
We can modify the algorithm by introducing the parameter \(\epsilon\):
\[x_{t} = \arg\max_{x \in \Delta_n} \sum_{i=1}^{t-1} \log(r_i^\top x)+ \epsilon \sum_{j=1}^n \log(e_j^\top x)\]\(\epsilon = 1\), corresponding to Smooth Prediction, has a regret
\[\begin{align*} &O\left(\frac{n}{(\min_{i,t} r_{t}[i])} \log\left(\sum_{t=1}^T\frac{1}{(\min_{i} r_{t}[i])}\right)\right) \\ &\leq O\left(\frac{n}{(\min_{i,t} r_{t}[i])} \log\left(\frac{T}{(\min_{i,t} r_{t}[i])}\right)\right) \end{align*}\]If a lower bound \(r\) is known apriori, then, we can pick \(\epsilon = 1/r\), giving the bound
\[O\left(\frac{n}{r} \log(T)\right)\]The run time is \(O(T n^{2.5})\) per iteration.
Universalization
Use the standard trick for universalization, ie, perturbing returns and portfolio vector:
\[\tilde{r}_t = (1-\alpha/n)r_t + \alpha/n\] \[\tilde{x}_t = (1-\alpha)x_t + \alpha/n\]Picking \(\alpha = n\sqrt{\log(T)/T}\), we get the regret bound \(O(n\sqrt{T \log (T)})\)
Experiments
Summary of Algorithms
| Known Bounded Returns Regret | Universalized Regret | Return Dependent Regret | Iteration Run Time | |
|---|---|---|---|---|
| Cover's UP | - | $$n\log(T)$$ | - | $$n^4 T^{14}$$ |
| Exponentiated Gradient | $$\frac{1}{r}\sqrt{T \log(n)}$$ | $$n^{1/2}\log(n)^{1/4} T^{3/4}$$ | - | $$n$$ |
| AdaHedge | - | - | $$\sqrt{\log(n)\left(\sum_{t=1}^T \frac{1}{(\min_i r_t[i])^2}\right)}$$ | $$n$$ |
| Smooth Prediction | - | - | $$\frac{n}{(\min_{i,t} r_{t}[i])} \log\left(\sum_{t=1}^T\frac{1}{(\min_{i} r_{t}[i])}\right)$$ | $$n^{2.5} T$$ |
| Modified Smooth Prediction | $$\frac{1}{r} n \log(T)$$ | $$n \sqrt{T\log(T)}$$ | - | $$n^{2.5} T$$ |