Online Portfolio Selection - Online Newton Step

I presented the Smooth Selection(SS) algorithm in my previous blog. Assuming the stock returns are lower bounded by \(r\), the regret of SS is \(O(\frac{n}{r}\log(T))\), and the run time is \(O(n^{2.5} T)\) per iteration. In this blog, I present the Online Newton Step Algorithm that improves the runtime to \(n^{3.5}\).

Quadratic Lower Bound

Define \(f_t(x) = -\log(r_t^\top x)\). Then the regret of a strategy \(Alg\) against a fixed portfolio vector \(x\) is:

\[\mathcal{R}_T(Alg,[r]_1^T,x) = \sum_{t=1}^T \log(r_t^\top x) - \log(r_t^\top x_t) = \sum_{t=1}^T f_t(x_t)-f_t(x)\]

Assume \(f_t\) has a “local”-quadratic lower-bound, i.e., for all \(x,y \in \Delta_n\), we have:

\[f_t(y) \geq f_t(x)+\nabla f_t(x)^\top (y-x) + \frac{1}{2} (y-x)^\top A_t(x) (y-x)\]

Here \(A_t(x)\) is a symmetric PSD matrix. We have the regret upper bound by applying the above inequality:

\[f_t(x_t)-f_t(x) \leq \nabla f_t(x_t)^\top (x_t-x) - \frac{1}{2} (x_t-x)^\top A_t(x_t) (x_t-x)\]

So, we have the regret bound:

\[\sum_{t=1}^T f_t(x_t)-f_t(x) \leq \sum_{t=1}^T \left[\nabla f_t(x_t)^\top (x_t-x) - \frac{1}{2} (x_t-x)^\top A_t(x_t) (x_t-x)\right]\]

The above inequality is always smaller than \(\sum_{t=1}^T \nabla f_t(x_t)^\top (x_t-x)\). So, we can get tighter regret bounds by using a quadratic lower bound instead of a linear lower bound.

For the portfolio selection problem, we can show that \(A_t(x) = \frac{r_t r_t^\top}{r_t^\top x}\).

Quadratized Follow-The-Regularized-Leader

In my previous blogs, I discussed the Exponentiated Gradient, which is a form of linearized FTRL, and Smooth Selection, which is a form of full FTRL. Here we define the Quadratized version of FTL and FTRL.

Define the quadratic surrogate function:

\[\begin{align*} \tilde{f}_t(x) &= f_t(x_t)+\nabla f_t(x_t)^\top(x-x_t) + \frac{1}{2}(x-x_t)^\top A_t(x_t)(x-x_t)\\ &=\frac{1}{2}x^\top A_t(x_t)x + (\nabla f_t(x_t) - A_t(x_t)x_t)^\top x \\ &\quad \quad + (f_t(x_t)-\nabla f_t(x_t)^\top x_t + \frac{1}{2} x_t^\top A_t(x_t)x_t) \end{align*}\]

Quadratized FTL is:

\[x_{t+1} = \arg\min_{x\in \Delta_n} \sum_{t=1}^T \tilde{f}_t(x)\]

Quadratized FTRL is:

\[x_{t+1} = \arg\min_{x\in \Delta_n} \sum_{t=1}^T \tilde{f}_t(x) + \epsilon R(x)\]

Since the constant terms in \(\tilde{f}_t\) are not required for optimization, we can rewrite the above updates. Let \(A_t = \sum_{s=1}^t A_s(x_s)\) and \(b_t = \sum_{s=1}^t (\nabla f_s(x_s) - A_s(x_s)x_s)\). Then, the Quadratized FTL is:

\[x_{t+1} = \arg\min_{x\in \Delta_n} \frac{1}{2} x^\top A_tx + b_t^\top x\]

Note that this can be solved using a Quadratic Program solver. Quadratized FTL is also called Follow the Approximate Leader(FTAL).

Quadratized FTRL is:

\[x_{t+1} = \arg\min_{x\in \Delta_n} \frac{1}{2} x^\top A_tx + b_t^\top x + \epsilon R(x)\]

At each step, we only need to update \(A_t\), \(b_t\) and compute \(x_{t+1}\), which can be done in \(O(n^{3.5})\) time. Notice that the update computation time does not depend on \(T\). In Quadratized FTRL, if we pick \(R(x) = \frac{1}{2}\|x\|_2^2\), we get the Online Newton Step (ONS) algorithm. We can use a Quadratic Program solver to find the iterates.

Regret

With a new analysis, the regret of Quadratized FTL can be bounded as:

\[O\left(\frac{n}{\min_{t,i} r_t[i]} \log(T)\right)\]

This bound is obtained without any tuning.

The regret of ONS with \(\epsilon=1\) can be bounded as:

\[\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 lowerbound \(r\) is known aprior, we can tune \(\epsilon = 1/r\) and get the bound:

\[O\left(\frac{n}{r} \log(T)\right)\]

Using the standard universalization trick, we can get an \(O(n\sqrt{T \log(T)})\) universal algorithm.

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^3 T$$
Modified Smooth Prediction $$\frac{1}{r} n \log(T)$$ $$n \sqrt{T\log(T)}$$ - $$n^3 T$$
Follow the Approximate Leader - - $$\frac{n}{\min_{t,i} r_t[i]} \log(T)$$ $$n^{3.5}$$
Online Newton Step $$\frac{1}{r} n \log(T)$$ $$n \sqrt{T\log(T)}$$ - $$n^{3.5}$$

References

Written on March 4, 2023