Online selection rules: the first set

struct BuyAndHold{T1<:EuclideanProjection} <: AbstractOnlinePortfolioSelectionAlgorithm

Lets the allocation drift with the market and never trades it, the buy-and-hold benchmark of the online selection papers (BAH).

From the uniform Start Allocation it is the uniform buy-and-hold portfolio, which the papers use as the market index. The rule keeps no state and reads no rows.

Mathematical definition

\[\begin{align} \boldsymbol{w}_{t+1} &= \mathrm{Proj}_{\mathcal{W}}\left( \hat{\boldsymbol{w}}_t \right)\,. \end{align}\]

Where:

• $\hat{\boldsymbol{w}}_t = \boldsymbol{w}_t \odot \boldsymbol{x}_t / \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle$: Price-Adjusted Allocation, the wealth held in each asset at the end of period $t$.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
• $\mathcal{W}$: Allocation Set.
• $\boldsymbol{w}_1$: Start Allocation, the allocation that the recursion starts from.
• $t$: Period index, counted from one.
• $\boldsymbol{r}_t$: Expert-return vector of period $t$, with entries $r_{t,k} = \langle \boldsymbol{h}_k(t), \boldsymbol{x}_t \rangle$.
• $\boldsymbol{p}_t$: Weight vector over the experts at period $t$, with entries $p_{t,k}$ that sum to one.

The entries of $\hat{\boldsymbol{w}}_t$ are non-negative and sum to one. So on the simplex the projection returns $\hat{\boldsymbol{w}}_t$ unchanged, and the rule never trades. The weight of asset $i$ after period $t$ is then $w_{1,i} \prod_{s \leq t} x_{s,i}$, divided by the sum of that product over the assets.

As the weighting of an ExpertMixture, the rule reads the expert-return vector $\boldsymbol{r}_t$ in place of $\boldsymbol{x}_t$. Its step is then $\boldsymbol{p}_{t+1} \propto \boldsymbol{p}_t \odot \boldsymbol{r}_t$, the wealth-weighted mixture that the papers write as BAH_W. It is the default weighting of the mixture.

Algorithm

1. Compute wh, the Price-Adjusted Allocation of w over x.
2. Project wh onto the Allocation Set set with alg.proj, from wh. Return the carrier st unchanged, and the projection.

Fields

• proj: The Projection Geometry the rule projects its raw step onto the Allocation Set in; the slot's type bound names the geometries the rule's theorem covers.

Constructors

BuyAndHold(; proj::EuclideanProjection = EuclideanProjection()) -> BuyAndHold

Keywords correspond to the struct's fields.

Examples

julia> BuyAndHold()BuyAndHold  proj ┴ EuclideanProjection()

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• ExpertMixture: the mixture whose default weighting this rule is.
• price_adjusted_allocation

References

• [151] B. Li and S. C. H. Hoi. Online portfolio selection: A survey. ACM Computing Surveys 46(3), 1–36 (2014).

struct ConstantRebalancedPortfolio{T1<:(Union{Nothing, var"#s7442"} where var"#s7442"<:(AbstractVector)), T2<:EuclideanProjection} <: AbstractOnlinePortfolioSelectionAlgorithm

Rebalances to the same allocation w after every price move, the constant rebalanced portfolio (CRP).

With the uniform w, the default, it is the uniform constant rebalanced portfolio (UCRP). The rule reads nothing of the market. The head holds a given Start Allocation for the first period, and the first update replaces it with w. The constant rebalanced portfolios sampled from the simplex are the experts of UniversalPortfolio, and the single-asset ones are the experts of SwitchingPortfolio.

Mathematical definition

\[\begin{align} \boldsymbol{w}_{t+1} &= \mathrm{Proj}_{\mathcal{W}}\left( \boldsymbol{b} \right)\,. \end{align}\]

Where:

• $\boldsymbol{b}$: Target of a constant rebalanced portfolio, the allocation that it rebalances to every period.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
• $\mathcal{W}$: Allocation Set.
• $t$: Period index, counted from one.
• $S_t(\boldsymbol{b}) = \prod_{s \leq t} \langle \boldsymbol{b}, \boldsymbol{x}_s \rangle$: Wealth of the constant rebalanced portfolio $\boldsymbol{b}$ after period $t$, from a wealth of one.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.

On the simplex the projection returns $\boldsymbol{b}$, so the rule holds $\boldsymbol{b}$ in every period after the first. Over periods $2$ to $t$ its wealth is then $S_t(\boldsymbol{b}) / S_1(\boldsymbol{b})$.

Algorithm

1. Set q to alg.w, or to the uniform allocation over the assets of w when alg.w is nothing.
2. Project q onto set with alg.proj, from the Price-Adjusted Allocation of w over x. Return the carrier st unchanged, and the projection.

Fields

• w: The target $\boldsymbol{b}$, the allocation that the rule rebalances to every period, over the pinned universe. A nothing value is the uniform allocation.

• proj: The Projection Geometry the rule projects its raw step onto the Allocation Set in; the slot's type bound names the geometries the rule's theorem covers.

Constructors

ConstantRebalancedPortfolio(;    w::Option{<:AbstractVector} = nothing,    proj::EuclideanProjection = EuclideanProjection()) -> ConstantRebalancedPortfolio

Keywords correspond to the struct's fields. A nothing w is the uniform allocation over the pinned universe.

Validation

• w, when given, is non-empty. An IsEmptyError is thrown otherwise.
• Every element of w is finite and non-negative, when w is given. A DomainError is thrown otherwise.
• sum(w) ≈ 1 when w is given, because every Allocation Set has a budget of one. A DomainError is thrown otherwise.

View parameters

ConstantRebalancedPortfolio defines its own port_opt_view method rather than deriving one from field tags.

• The method slices w to the selected assets and divides it by the sum of the slice, so it sums to one again. A slice that sums to zero becomes the uniform allocation over the selected assets.
• A nothing w stays nothing, so the view is uniform over the selected assets.

Examples

julia> ConstantRebalancedPortfolio()ConstantRebalancedPortfolio     w ┼ nothing  proj ┴ EuclideanProjection()

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• UniversalPortfolio: the mixture over sampled constant rebalanced portfolios.
• SwitchingPortfolio: the mixture over the single-asset constant rebalanced portfolios.
• BestConstantRebalancedPortfolio: the best target in hindsight.
• port_opt_view

References

• [180] T. M. Cover. Universal portfolios. Mathematical Finance 1, 1–29 (1991).

struct NewtonStep{T1<:Real, T2<:Real, T3<:Real, T4<:(Union{var"#s7440", var"#s7439"} where {var"#s7440"<:EuclideanProjection, var"#s7439"<:GramProjection})} <: AbstractOnlinePortfolioSelectionAlgorithm

Steps to the Newton point of the log wealth of the past periods, the online Newton step (ONS) of Agarwal, Hazan, Kale and Schapire (2006).

The rule is a second-order method on the exp-concave log-wealth objective. Each step solves one dense $N \times N$ linear system, and the carrier holds an $N \times N$ matrix. Under a GramProjection each step also solves a programme. The head projects the Start Allocation before the first gradient, where $A_0 = I$ and the Gram norm is the Euclidean norm, so it projects the start in the Euclidean geometry. As the weighting of an ExpertMixture, the rule steps on the expert-return vector, and its Gram matrix is $K \times K$ for $K$ experts.

Mathematical definition

\[\begin{align} \boldsymbol{g}_s &= \frac{\boldsymbol{x}_s}{\langle \boldsymbol{w}_s, \boldsymbol{x}_s \rangle}\,, \\ A_t &= I + \sum_{s \leq t} \boldsymbol{g}_s \boldsymbol{g}_s^\intercal\,, \\ \boldsymbol{b}_t &= \left(1 + \frac{1}{\beta}\right) \sum_{s \leq t} \boldsymbol{g}_s\,, \\ \boldsymbol{q} &= (1 - \eta)\, \delta A_t^{-1} \boldsymbol{b}_t + \frac{\eta}{N} \boldsymbol{1}\,, \\ \boldsymbol{w}_{t+1} &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min}\; (\boldsymbol{w} - \boldsymbol{q})^\intercal M (\boldsymbol{w} - \boldsymbol{q})\,. \end{align}\]

Where:

• $\boldsymbol{g}_s$: Gradient of the log wealth $\log \langle \boldsymbol{w}, \boldsymbol{x}_s \rangle$ of period $s$, taken at the iterate.
• $A_t$: Gram matrix after period $t$, $N \times N$.
• $I$: Identity matrix, $N \times N$.
• $\boldsymbol{b}_t$: Weighted gradient sum after period $t$.
• $\beta$: Trade-off parameter, positive. It scales the gradient sum.
• $\delta$: Scale of the Newton direction, positive.
• $\eta$: Shrinkage towards the uniform allocation, in $[0, 1)$.
• $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
• $M$: Matrix of the projection norm. It is $A_t$ under a GramProjection and $I$ under the EuclideanProjection.
• $\mathcal{W}$: Allocation Set.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $N$: Number of assets.
• $t$: Period index, counted from one.
• $T$: Regret horizon, the number of periods that a regret bound covers.
• $\alpha$: Market variability, the smallest entry of any price relative after each price relative is scaled so that its largest entry is one.

At $M = A_t$ and $\eta = 0$ this is the update of the paper's Figure 1. The paper mixes the uniform allocation into the projected point, $(1 - \eta) \boldsymbol{p}_t + \eta \boldsymbol{1} / N$. The rule mixes before the projection instead, so the answer stays in an Allocation Set whose bounds the uniform allocation breaks. On the simplex at $\eta = 0$ the two norms give one answer whenever $\delta A_t^{-1} \boldsymbol{b}_t$ lies in the simplex.

The paper's Theorem 1 bounds the regret against the best constant rebalanced portfolio in hindsight. If the market variability is $\alpha > 0$, then $\eta = 0$, $\beta = \alpha / (8 \sqrt{N})$ and $\delta = 1$ give a regret of at most $(10 N^{1.5} / \alpha) \log(N T / \alpha^2)$. The rule at these values under the Gram norm is the paper's algorithm, so the bound holds for it. With no assumption on the market, the paper chooses $\eta$ and $\beta$ from $T$ and bounds the regret by $22 N^{1.25} \sqrt{T \log(N T)}$. That bound needs the paper's mix after the projection, so the rule does not carry it. The package claims neither bound under the Euclidean default.

Algorithm

1. Compute g, the gradient x ./ dot(w, x).
2. Add g * transpose(g) to st.A in place.
3. Add (1 + 1/beta) .* g to st.b in place.
4. Solve the symmetric system st.A \ st.b, and scale the solution by delta, giving q.
5. When eta is not zero, shrink q towards the uniform allocation in place.
6. Bind st.A onto alg.proj with gram_geometry. Project q onto set in that geometry, from the Price-Adjusted Allocation of w over x, giving wn.
7. Return a carrier with the count raised by one, which holds the same A and b, and wn.

Fields

• beta: The trade-off parameter $\beta$, which scales the gradient sum.

• delta: The scale $\delta$ of the Newton direction.

• eta: The shrinkage $\eta$ of the Newton point towards the uniform allocation before the projection, in [0, 1). At 0 the rule is the paper's algorithm.

• proj: The Projection Geometry the rule projects its raw step onto the Allocation Set in; the slot's type bound names the geometries the rule's theorem covers.

Constructors

NewtonStep(;    beta::Real = 1,    delta::Real = 0.125,    eta::Real = 0,    proj::Union{<:EuclideanProjection, <:GramProjection} = EuclideanProjection()) -> NewtonStep

Keywords correspond to the struct's fields. The defaults beta = 1, delta = 1/8 and eta = 0 are the values of the paper's experiments. The proj slot takes the Gram geometry of the paper's theorem or the Euclidean geometry.

Validation

• beta > 0, delta > 0. A DomainError is thrown otherwise.
• 0 <= eta < 1. A DomainError is thrown otherwise.

Examples

julia> NewtonStep()NewtonStep   beta ┼ Int64: 1  delta ┼ Float64: 0.125    eta ┼ Int64: 0   proj ┴ EuclideanProjection()

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• NewtonStepState
• GramProjection: the geometry of the paper's projection.
• UniversalPortfolio: the paper reports that the Newton step runs much faster than the sampled universal portfolio.

References

• [179] A. Agarwal, E. Hazan, S. Kale and R. E. Schapire. Algorithms for portfolio management based on the Newton method. In: Proceedings of the 23rd International Conference on Machine Learning, 9–16 (2006).

abstract type AbstractPassiveAggressiveSlack <: AbstractAlgorithm

Abstract supertype for the step-length rules of the passive aggressive mean reversion rule.

The paper's three variants, NoSlack, LinearSlack and QuadraticSlack, differ in one formula for the step length $\tau_t$. PassiveAggressiveMeanReversion holds one of them in its slack field.

Interfaces

To implement a new step-length rule, subtype AbstractPassiveAggressiveSlack and implement the method below.

passive_aggressive_step

• passive_aggressive_step(slack::AbstractPassiveAggressiveSlack, loss::Real, denom::Real) -> Real: The step length $\tau_t$ of the period, non-negative.

Arguments

• slack: The rule.
• loss: $\ell_t$, the hinge loss of the period, non-negative.
• denom: $\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2$, the squared norm of the centred price relative, positive.

Returns

• tau::Real: The step length.

Examples

A rule that takes half the step of NoSlack.

julia> struct HalfSlack <: PortfolioOptimisers.AbstractPassiveAggressiveSlack endjulia> function PortfolioOptimisers.passive_aggressive_step(::HalfSlack, loss::Real, denom::Real)           return loss / (2 * denom)       endjulia> PortfolioOptimisers.passive_aggressive_step(HalfSlack(), 0.2, 0.1)1.0julia> PassiveAggressiveMeanReversion(; slack = HalfSlack()).slackHalfSlack()

Related

• NoSlack
• LinearSlack
• QuadraticSlack
• PassiveAggressiveMeanReversion
• passive_aggressive_step

struct NoSlack <: AbstractPassiveAggressiveSlack

Takes the full step that brings the hinge loss of the period to zero, the step-length rule of PAMR.

Mathematical definition

\[\begin{align} \tau_t &= \frac{\ell_t}{\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2}\,. \end{align}\]

Where:

• $\tau_t$: Step length of the passive-aggressive update of period $t$, non-negative.
• $\ell_t = \max(0, \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle - \epsilon)$: Hinge loss of period $t$, the part of the gross return above the reversion threshold.
• $\bar{x}_t$: Cross-sectional mean of the price relative of period $t$, the average of its $N$ entries.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\epsilon$: Reversion threshold on the gross return of the period.
• $t$: Period index, counted from one.

It is the limit of the steps of LinearSlack and QuadraticSlack as $C \to \infty$.

Examples

julia> NoSlack()NoSlack()

Related

• AbstractPassiveAggressiveSlack
• PassiveAggressiveMeanReversion

References

• [181] B. Li, P. Zhao, S. C. H. Hoi and V. Gopalkrishnan. PAMR: Passive aggressive mean reversion strategy for portfolio selection. Machine Learning 87, 221–258 (2012).

struct LinearSlack{T1<:Real} <: AbstractPassiveAggressiveSlack

Caps the step of NoSlack at the aggressiveness C, the step-length rule of PAMR-1.

Mathematical definition

\[\begin{align} \tau_t &= \min\left( C, \frac{\ell_t}{\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2} \right)\,. \end{align}\]

Where:

• $\tau_t$: Step length of the passive-aggressive update of period $t$, non-negative.
• $C$: Aggressiveness of a passive-aggressive slack rule, positive.
• $\ell_t = \max(0, \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle - \epsilon)$: Hinge loss of period $t$, the part of the gross return above the reversion threshold.
• $\bar{x}_t$: Cross-sectional mean of the price relative of period $t$, the average of its $N$ entries.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\epsilon$: Reversion threshold on the gross return of the period.
• $t$: Period index, counted from one.

The paper derives this step from a linear penalty $C \xi$ on a slack $\xi \geq 0$ of the loss constraint, without the non-negativity constraint on the allocation.

Fields

• C: The aggressiveness $C$, the cap on the step.

Constructors

LinearSlack(; C::Real = 500) -> LinearSlack

Keywords correspond to the struct's fields. The default is the value of the paper's experiments.

Validation

• C > 0. A DomainError is thrown otherwise.

Examples

julia> LinearSlack()LinearSlack  C ┴ Int64: 500

Related

• AbstractPassiveAggressiveSlack
• PassiveAggressiveMeanReversion
• NoSlack: the limit as $C \to \infty$.

References

• [181] B. Li, P. Zhao, S. C. H. Hoi and V. Gopalkrishnan. PAMR: Passive aggressive mean reversion strategy for portfolio selection. Machine Learning 87, 221–258 (2012).

struct QuadraticSlack{T1<:Real} <: AbstractPassiveAggressiveSlack

Softens the step of NoSlack by adding 1 / (2C) to its denominator, the step-length rule of PAMR-2.

Mathematical definition

\[\begin{align} \tau_t &= \frac{\ell_t}{\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2 + \frac{1}{2C}}\,. \end{align}\]

Where:

• $\tau_t$: Step length of the passive-aggressive update of period $t$, non-negative.
• $C$: Aggressiveness of a passive-aggressive slack rule, positive.
• $\ell_t = \max(0, \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle - \epsilon)$: Hinge loss of period $t$, the part of the gross return above the reversion threshold.
• $\bar{x}_t$: Cross-sectional mean of the price relative of period $t$, the average of its $N$ entries.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\epsilon$: Reversion threshold on the gross return of the period.
• $t$: Period index, counted from one.

The paper derives this step from a quadratic penalty $C \xi^2$ on a slack $\xi$ of the loss constraint, without the non-negativity constraint on the allocation.

Fields

• C: The aggressiveness $C$, which softens the denominator.

Constructors

QuadraticSlack(; C::Real = 500) -> QuadraticSlack

Keywords correspond to the struct's fields. The default is the value of the paper's experiments.

Validation

• C > 0. A DomainError is thrown otherwise.

Examples

julia> QuadraticSlack()QuadraticSlack  C ┴ Int64: 500

Related

• AbstractPassiveAggressiveSlack
• PassiveAggressiveMeanReversion
• NoSlack: the limit as $C \to \infty$.

References

• [181] B. Li, P. Zhao, S. C. H. Hoi and V. Gopalkrishnan. PAMR: Passive aggressive mean reversion strategy for portfolio selection. Machine Learning 87, 221–258 (2012).

passive_aggressive_step(::NoSlack, loss::Real, denom::Real)
passive_aggressive_step(slack::LinearSlack, loss::Real, denom::Real)
passive_aggressive_step(slack::QuadraticSlack, loss::Real, denom::Real)

Returns the step length of a passive-aggressive update under each step-length rule.

Mathematical definition

\[\begin{align} \tau_t &= \frac{\ell_t}{\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2} && \text{under } \mathrm{NoSlack}\,, \\ \tau_t &= \min\left( C, \frac{\ell_t}{\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2} \right) && \text{under } \mathrm{LinearSlack}\,, \\ \tau_t &= \frac{\ell_t}{\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2 + \frac{1}{2C}} && \text{under } \mathrm{QuadraticSlack}\,. \end{align}\]

Where:

• $\tau_t$: Step length of the passive-aggressive update of period $t$, non-negative.
• $C$: Aggressiveness of a passive-aggressive slack rule, positive.
• $\ell_t = \max(0, \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle - \epsilon)$: Hinge loss of period $t$, the part of the gross return above the reversion threshold.
• $\bar{x}_t$: Cross-sectional mean of the price relative of period $t$, the average of its $N$ entries.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\epsilon$: Reversion threshold on the gross return of the period.
• $t$: Period index, counted from one.

Arguments

• slack: The step-length rule.
• loss: $\ell_t$, the hinge loss of the period, non-negative.
• denom: $\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert^2$, the squared norm of the centred price relative, positive.

Returns

• tau::Real: The step length $\tau_t$.

Related

• AbstractPassiveAggressiveSlack
• PassiveAggressiveMeanReversion

References

• [181] B. Li, P. Zhao, S. C. H. Hoi and V. Gopalkrishnan. PAMR: Passive aggressive mean reversion strategy for portfolio selection. Machine Learning 87, 221–258 (2012).

struct PassiveAggressiveMeanReversion{T1<:Real, T2<:AbstractPassiveAggressiveSlack, T3<:EuclideanProjection} <: AbstractOnlinePortfolioSelectionAlgorithm

Moves the allocation the least distance that brings the last period's gross return down to eps, the passive aggressive mean reversion (PAMR) of Li, Zhao, Hoi and Gopalkrishnan (2012).

The rule sells what rose in the last period, a bet on mean reversion over one period. Its threshold bounds the return on the realised price relative from above. The threshold of ForecastReversion bounds the return on a forecast from below. The rule keeps no state and reads no rows.

Mathematical definition

\[\begin{align} \ell_t &= \max\left(0, \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle - \epsilon\right)\,, \\ \boldsymbol{q} &= \boldsymbol{w}_t - \tau_t \left( \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \right)\,, \\ \boldsymbol{w}_{t+1} &= \mathrm{Proj}_{\mathcal{W}}\left( \boldsymbol{q} \right)\,. \end{align}\]

Where:

• $\ell_t = \max(0, \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle - \epsilon)$: Hinge loss of period $t$, the part of the gross return above the reversion threshold.
• $\tau_t$: Step length of the passive-aggressive update of period $t$, non-negative.
• $\bar{x}_t$: Cross-sectional mean of the price relative of period $t$, the average of its $N$ entries.
• $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
• $\epsilon$: Reversion threshold on the gross return of the period.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
• $\mathcal{W}$: Allocation Set.
• $N$: Number of assets.
• $t$: Period index, counted from one.

The step length $\tau_t$ is the step of the step-length rule. It is zero when every entry of $\boldsymbol{x}_t$ is equal, because then $\lVert \boldsymbol{x}_t - \bar{x}_t \boldsymbol{1} \rVert = 0$. The paper sets it to zero in that case too.

The entries of $\boldsymbol{x}_t - \bar{x}_t \boldsymbol{1}$ sum to zero, so $\boldsymbol{q}$ keeps the budget of one. Under NoSlack with $\ell_t > 0$, the gross return of $\boldsymbol{q}$ over period $t$ is exactly $\epsilon$. So, by the paper's Proposition 1, $\boldsymbol{q}$ solves the paper's first problem without the non-negativity constraint. The projection onto the simplex is the normalisation step of the paper's Algorithm 1.

The paper takes $\epsilon \geq 0$, and its experiments choose $\epsilon \leq 1$ because the gross return of a period is near one. With a threshold above one, the rule moves only after a period whose gross return is above the threshold.

Algorithm

1. Compute dev, the price relative x minus its mean.
2. Compute denom, the sum of the squares of dev.
3. Compute loss, the hinge loss max(0, dot(w, x) - eps).
4. Set tau to zero when denom is zero. Otherwise, set tau to the step of alg.slack from loss and denom.
5. Compute q = w .- tau .* dev.
6. Project q onto set with alg.proj, from the Price-Adjusted Allocation of w over x. Return the carrier st unchanged, and the projection.

Fields

• eps: The reversion threshold $\epsilon$. The rule moves only when the gross return of the last period is above it.

• slack: The step-length rule, one of the paper's three variants.

• proj: The Projection Geometry the rule projects its raw step onto the Allocation Set in; the slot's type bound names the geometries the rule's theorem covers.

Constructors

PassiveAggressiveMeanReversion(;    eps::Real = 0.5,    slack::AbstractPassiveAggressiveSlack = NoSlack(),    proj::EuclideanProjection = EuclideanProjection()) -> PassiveAggressiveMeanReversion

Keywords correspond to the struct's fields. NoSlack(), LinearSlack(; C) and QuadraticSlack(; C) are the paper's PAMR, PAMR-1 and PAMR-2. The default eps = 0.5 is the value of the paper's experiments.

Validation

• eps >= 0, the range that the paper states. A DomainError is thrown otherwise.

Examples

julia> PassiveAggressiveMeanReversion()PassiveAggressiveMeanReversion    eps ┼ Float64: 0.5  slack ┼ NoSlack()   proj ┴ EuclideanProjection()

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• AbstractPassiveAggressiveSlack
• ForecastReversion: the reversion rule whose threshold acts on a forecast.
• ConfidenceWeightedMeanReversion: the reversion rule that moves a belief over the allocation.

References

• [181] B. Li, P. Zhao, S. C. H. Hoi and V. Gopalkrishnan. PAMR: Passive aggressive mean reversion strategy for portfolio selection. Machine Learning 87, 221–258 (2012).

struct OwnPoint <: AbstractAlgorithm

Makes every expert of a mixture read its gradient at its own iterate, the default Gradient Point.

Every expert then runs as it runs alone. ExpertMixture holds this point in its grad field by default.

Mathematical definition

\[\begin{align} \boldsymbol{h}_k(t + 1) &= U_k\left( \boldsymbol{h}_k(t), \nabla f_t(\boldsymbol{h}_k(t)) \right)\,. \end{align}\]

Where:

• $\boldsymbol{h}_k(t)$: Allocation that expert $k$ holds during period $t$.
• $U_k$: Online Update of expert $k$, from its iterate, with the gradient that it reads.
• $f_t$: Online loss of period $t$, the objective that the experts step on.
• $t$: Period index, counted from one.

Examples

julia> OwnPoint()OwnPoint()

Related

• ExpertMixture
• BlendPoint

struct BlendPoint <: AbstractAlgorithm

Makes every first-order expert of a mixture read its gradient at the blend that the mixture played, while it steps from its own iterate.

This is the shared gradient of Zhang, Lu and Zhou (2018, Algorithm 4) and of Zhao, Zhang, Zhang and Zhou (2020, Algorithm 2). The papers state their dynamic-regret bounds on it, and Ader and Sword build the mixture on it. The mixture passes the blend through the seven-argument online_update!. MirrorDescent, OptimisticStep and AdaptiveSubgradient read it, and the hint of OptimisticStep stays the hint of its predictor. A rule with no gradient takes its six-argument update and ignores the point.

Mathematical definition

\[\begin{align} \boldsymbol{h}_k(t + 1) &= U_k\left( \boldsymbol{h}_k(t), \nabla f_t(\boldsymbol{w}_t) \right)\,. \end{align}\]

Where:

• $\boldsymbol{h}_k(t)$: Allocation that expert $k$ holds during period $t$.
• $U_k$: Online Update of expert $k$, from its iterate, with the gradient that it reads.
• $f_t$: Online loss of period $t$, the objective that the experts step on.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $t$: Period index, counted from one.

Examples

julia> BlendPoint()BlendPoint()

Related

• ExpertMixture
• OwnPoint
• MirrorDescent
• OptimisticStep
• AdaptiveSubgradient

References

• [182] L. Zhang, S. Lu and Z.-H. Zhou. Adaptive online learning in dynamic environments. In: Advances in Neural Information Processing Systems 31, 1323–1333 (2018).
• [183] P. Zhao, Y.-J. Zhang, L. Zhang and Z.-H. Zhou. Dynamic regret of convex and smooth functions. In: Advances in Neural Information Processing Systems 33, 12510–12520 (2020).

struct ExpertMixture{T1<:(AbstractVector{<:AbstractOnlinePortfolioSelectionAlgorithm}), T2<:AbstractOnlinePortfolioSelectionAlgorithm, T3<:(Union{Nothing, var"#s7436"} where var"#s7436"<:BoundedAllocationSet), T4<:EuclideanProjection, T5<:Union{BlendPoint, OwnPoint}, T6<:(Union{Nothing, var"#s7435"} where var"#s7435"<:(AbstractVector))} <: AbstractOnlinePortfolioSelectionAlgorithm

Mixes the allocations of several expert rules, with weights that a second rule moves on the experts' returns.

Every expert takes its own Online Update. The weighting is itself an Online Selection Rule, and it reads the expert-return vector in place of the price relative. Under BuyAndHold, the default, the mixture is the wealth-weighted mixture that the papers write as BAH_W. Over sampled constant rebalanced portfolios it is Cover's universal portfolio, UniversalPortfolio.

The weighting projects its step onto the Expert Set eset, in the weighting's own Projection Geometry. A nothing set is the bare simplex over the experts. A given BoundedAllocationSet broadcasts a scalar bound over the experts and reads one entry per expert from a vector bound, so a cap on eset caps the weight of any one expert.

The mixture then projects the blend onto the head's Allocation Set once more, in its own Euclidean geometry proj, from its Price-Adjusted Allocation. On a BoundedAllocationSet a blend of feasible allocations is feasible, so blend_projection skips the projection and the default configuration solves nothing. On a ProgrammeAllocationSet the projection is the repair that a MIP kind needs, or a turnover ceiling under a weighting other than buy-and-hold. Then the mixture solves $K + 1$ programmes a period, one for each expert and one of its own. A Newton weighting holds a $K \times K$ Gram matrix, so two thousand experts cost a $2000 \times 2000$ solve a period.

The mixture reads nothing of a given Start Allocation. The head holds it for the first period, and the experts' mix replaces it. Each expert starts where its rule starts. A constant rebalanced portfolio starts at its own w, and any other rule starts at the Start Allocation. The seed projects each start onto the head's Allocation Set in the expert's geometry, as project_start projects the head's w0. So a sampled expert's wealth is Cover's $S_t(\boldsymbol{b})$ of its feasible allocation from the first period. The weights start at p0, uniform by default, and the seed projects them onto the Expert Set in the weighting's geometry. The seed makes a start outside a set feasible, and never refuses it.

grad is the Gradient Point. Under OwnPoint, the default, every expert reads its gradient at its own iterate. Under BlendPoint, every first-order expert reads its gradient at the blend $\boldsymbol{w}_t$ that the mixture played, and steps from its own iterate.

Mathematical definition

\[\begin{align} r_{t,k} &= \langle \boldsymbol{h}_k(t), \boldsymbol{x}_t \rangle\,, \\ \boldsymbol{h}_k(t + 1) &= U_k\left( \boldsymbol{h}_k(t), \boldsymbol{x}_t \right)\,, \\ \boldsymbol{p}_{t+1} &= V_{\mathcal{E}}\left( \boldsymbol{p}_t, \boldsymbol{r}_t \right)\,, \\ \boldsymbol{w}_{t+1} &= \mathrm{Proj}_{\mathcal{W}}\left( \sum_{k=1}^{K} p_{t+1,k}\, \boldsymbol{h}_k(t + 1) \right)\,. \end{align}\]

Where:

• $\boldsymbol{r}_t$: Expert-return vector of period $t$, with entries $r_{t,k} = \langle \boldsymbol{h}_k(t), \boldsymbol{x}_t \rangle$.
• $\boldsymbol{h}_k(t)$: Allocation that expert $k$ holds during period $t$.
• $U_k$: Online Update of expert $k$, from its iterate, on the price relative.
• $\boldsymbol{p}_t$: Weight vector over the experts at period $t$, with entries $p_{t,k}$ that sum to one.
• $V_{\mathcal{E}}$: Online Update of the weighting, on the expert-return vector, projected onto the Expert Set in the weighting's geometry.
• $\mathcal{E}$: Expert Set, the Allocation Set over the experts that the weighting of an expert mixture projects onto.
• $K$: Expert count of an expert mixture.
• $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
• $\mathcal{W}$: Allocation Set.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $t$: Period index, counted from one.
• $S_{T,k}$: Wealth of expert $k$ after period $T$, from a wealth of one.
• $\hat{S}_T$: Wealth of the mixture after period $T$, from a wealth of one.
• $T$: Regret horizon, the number of periods that a regret bound covers.
• $\ell_t(\boldsymbol{w}) = \langle \nabla f_t(\boldsymbol{w}_t), \boldsymbol{w} - \boldsymbol{w}_t \rangle$: Surrogate loss of period $t$, the online loss linearised at the played allocation.

Under BuyAndHold on the bare Expert Set, $\boldsymbol{p}_{t+1} \propto \boldsymbol{p}_t \odot \boldsymbol{r}_t$. Wherever the projection onto $\mathcal{W}$ returns the blend, the wealth of the mixture is then the $\boldsymbol{p}_1$-weighted average of the experts' wealths. So for every sequence of price relatives, $\max_k \log S_{T,k} - \log \hat{S}_T \leq -\log p_{1,k^\star}$, with $k^\star$ the best expert. At the uniform start the bound is $\log K$, the bound of Cover and Ordentlich (1996) for an equal split over expert strategies. The package does not claim the bound where the Expert Set binds or the second projection changes the blend.

Under BlendPoint with ExponentiatedGradient as the weighting, $\langle \boldsymbol{p}_t, \boldsymbol{r}_t \rangle = \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle$ wherever the projection onto $\mathcal{W}$ returns the blend. The weight update is then exactly the exponentially weighted forecaster on the surrogate losses $\ell_t(\boldsymbol{h}_k(t))$. Ader and Sword build that mixture over a geometric grid of first-order experts.

Algorithm

1. Compute r, the expert-return vector, from the held allocations st.h.
2. Compute point, the Gradient Point, with gradient_point.
3. Take the Online Update of every expert from its own carrier and allocation, with point. Store the new carrier and allocation in st.st and st.h.
4. Resolve the Expert Set with expert_allocation_set. Take the Online Update of the weighting from st.pst and st.p, on r, over that set, giving pst and p.
5. Compute the blend q, the sum of p[k] .* h over the experts.
6. Project q onto set with blend_projection in alg.proj, from the Price-Adjusted Allocation of w over x, giving wn.
7. Return a carrier with the count raised by one, which holds the new pst and p, and wn.

Fields

• experts: The expert rules, one Rule State each.

• alg: The weighting, a rule of the family that reads the expert-return vector in place of the price relative.

• eset: The Expert Set that the weighting projects onto, over the experts, or nothing for the bare simplex over them.

• proj: The geometry of the second projection, which projects the blend onto the head's Allocation Set.

• grad: The Gradient Point, where every first-order expert reads its gradient.

• p0: The Start Allocation over the experts, projected onto the Expert Set at the seed, or nothing for the uniform one.

Constructors

ExpertMixture(;    experts::AbstractVector{<:AbstractOnlinePortfolioSelectionAlgorithm},    alg::AbstractOnlinePortfolioSelectionAlgorithm = BuyAndHold(),    eset::Option{<:BoundedAllocationSet} = nothing,    proj::EuclideanProjection = EuclideanProjection(),    grad::Union{OwnPoint, BlendPoint} = OwnPoint(),    p0::Option{<:AbstractVector} = nothing) -> ExpertMixture

Keywords correspond to the struct's fields. A nothing p0 starts the weighting uniform over the experts, and a nothing eset is the bare simplex over them.

Validation

• experts is non-empty. An IsEmptyError is thrown otherwise.
• rows_needed(alg) == 0, because the weighting reads the expert-return vector, and the head holds no rows of it. An ArgumentError is thrown otherwise.
• p0, when given, is non-empty. An IsEmptyError is thrown otherwise.
• Every element of p0 is finite, when p0 is given. A DomainError is thrown otherwise.
• p0, when given, has one entry per expert. A DimensionMismatch is thrown otherwise. The seed projects the start onto the Expert Set, so the start need not lie in it.
• eset, when given, holds a WeightBounds and no sets, because an expert has no name for a WeightBoundsEstimator to resolve. An ArgumentError is thrown otherwise.

View parameters

ExpertMixture defines its own port_opt_view method rather than deriving one from field tags.

• Every expert recurses through port_opt_view with the same arguments.
• The weighting, eset, proj, grad and p0 pass unchanged, because they are stated over the experts, not over the assets.

Examples

julia> ExpertMixture(; experts = [ExponentiatedGradient(), NewtonStep()])ExpertMixture  experts ┼ 2-element Vector{PortfolioOptimisers.AbstractOnlinePortfolioSelectionAlgorithm}          │ MirrorDescent ⋯          │ NewtonStep ⋯      alg ┼ BuyAndHold          │   proj ┴ EuclideanProjection()     eset ┼ nothing     proj ┼ EuclideanProjection()     grad ┼ OwnPoint()       p0 ┴ nothing

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• UniversalPortfolio: the mixture over sampled constant rebalanced portfolios.
• SwitchingPortfolio: the mixture over the single-asset constant rebalanced portfolios.
• ExpertMixtureState
• BuyAndHold: the default weighting.
• OwnPoint
• BlendPoint
• Ader
• Sword
• port_opt_view

References

• [151] B. Li and S. C. H. Hoi. Online portfolio selection: A survey. ACM Computing Surveys 46(3), 1–36 (2014).
• [184] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory 42, 348–363 (1996).
• [182] L. Zhang, S. Lu and Z.-H. Zhou. Adaptive online learning in dynamic environments. In: Advances in Neural Information Processing Systems 31, 1323–1333 (2018).
• [183] P. Zhao, Y.-J. Zhang, L. Zhang and Z.-H. Zhou. Dynamic regret of convex and smooth functions. In: Advances in Neural Information Processing Systems 33, 12510–12520 (2020).

UniversalPortfolio(;
    N::Integer,
    n_experts::Integer = 2000,
    alpha::Num_VecNum = 1,
    rng::Random.AbstractRNG = Random.default_rng(),
    seed::Option{<:Integer} = nothing,
    alg::AbstractOnlinePortfolioSelectionAlgorithm = BuyAndHold(),
    eset::Option{<:BoundedAllocationSet} = nothing,
    proj::EuclideanProjection = EuclideanProjection()
) -> ExpertMixture

Builds Cover's (1991) universal portfolio as an expert mixture over n_experts constant rebalanced portfolios sampled from a Dirichlet prior on the simplex (UP).

Cover defines the portfolio as the wealth-weighted average of every constant rebalanced portfolio. The integral has no closed form beyond a few assets, so the mixture replaces it with an average over n_experts draws. alpha = 1 is Cover's uniform prior, and alpha = 1/2 is the Dirichlet(½) prior of Cover and Ordentlich (1996).

Each period costs $O(K N)$, and the carrier holds $K$ allocations of $N$ entries. The gap between the best sampled expert and the best constant rebalanced portfolio is sampling error. It shrinks as n_experts grows, it has no closed form, and it needs more draws as $N$ grows.

Mathematical definition

\[\begin{align} \boldsymbol{w}_{t+1} &= \frac{\int_{\Delta_N} \boldsymbol{b}\, S_t(\boldsymbol{b})\, d\mu(\boldsymbol{b})}{\int_{\Delta_N} S_t(\boldsymbol{b})\, d\mu(\boldsymbol{b})} \approx \frac{\sum_{k=1}^{K} \boldsymbol{b}_k\, S_t(\boldsymbol{b}_k)}{\sum_{k=1}^{K} S_t(\boldsymbol{b}_k)}\,, \quad \boldsymbol{b}_k \sim \mu = \mathrm{Dirichlet}(\boldsymbol{\alpha})\,. \end{align}\]

Where:

• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\Delta_N$: Probability simplex over the $N$ assets.
• $\boldsymbol{b}$: Target of a constant rebalanced portfolio, the allocation that it rebalances to every period.
• $S_t(\boldsymbol{b}) = \prod_{s \leq t} \langle \boldsymbol{b}, \boldsymbol{x}_s \rangle$: Wealth of the constant rebalanced portfolio $\boldsymbol{b}$ after period $t$, from a wealth of one.
• $\mu$: Dirichlet prior on the simplex.
• $\boldsymbol{\alpha}$: Dirichlet concentration, one entry per asset.
• $\boldsymbol{b}_k$: Target of sampled expert $k$.
• $K$: Expert count of an expert mixture.
• $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
• $N$: Number of assets.
• $t$: Period index, counted from one.
• $T$: Regret horizon, the number of periods that a regret bound covers.
• $S^\star_T$: Wealth of the best constant rebalanced portfolio in hindsight after period $T$, from a wealth of one.
• $\hat{S}_T$: Wealth of the universal portfolio after period $T$, from a wealth of one.

Under the default weighting on the bare Expert Set, the mixture's allocation is the sampled ratio on the right, with no error beyond the sampling. Two bounds hold for every sequence of price relatives.

• The exact integral, Theorems 1 and 2 of Cover and Ordentlich (1996). Under the uniform prior, $\log S^\star_T - \log \hat{S}_T \leq (N - 1) \log(T + 1)$. Under the Dirichlet(½) prior, the bound is $\log 2 + \frac{N - 1}{2} \log(T + 1)$. Neither bound needs an assumption on the price relatives. Cover (1991) proves that the growth rates of the two portfolios agree as $T \to \infty$, for every bounded sequence.
• The sampled mixture, exact for the object that the package builds. The best sampled expert beats the mixture by at most $\log K$ in log wealth, because the wealth of the mixture is the average of the experts' wealths, and an average is at least $1 / K$ of its largest term.

Algorithm

1. Check N and n_experts.
2. Check alpha. Build the symmetric Dirichlet distribution of dimension N from a scalar alpha. From a vector alpha, check its length and build the Dirichlet distribution with it.
3. Resolve the generator from rng and seed with resolve_rng.
4. Draw B, N × n_experts, one target per column.
5. Build one ConstantRebalancedPortfolio for each column of B, each with proj.
6. Return the ExpertMixture over them, with the weighting alg and the Expert Set eset.

Arguments

• N: The number of assets of the pinned universe that the experts are sampled over.
• n_experts: The number $K$ of constant rebalanced experts.
• alpha: The Dirichlet concentration, a scalar for the symmetric prior or one entry per asset.
• rng, seed: The generator that draws the experts, resolved through resolve_rng.
• alg: The weighting over the experts.
• eset: The Expert Set that the weighting projects onto, or nothing for the bare simplex.
• proj: The geometry of every expert.

Validation

• N >= 1, n_experts >= 1. A DomainError is thrown otherwise.
• alpha is non-empty. An IsEmptyError is thrown otherwise.
• Every element of alpha is positive and finite. A DomainError is thrown otherwise.
• A vector alpha has one entry per asset. A DimensionMismatch is thrown otherwise.

Examples

julia> up = UniversalPortfolio(; N = 3, n_experts = 2, seed = 1);julia> length(up.experts)2

Related

• ExpertMixture
• ConstantRebalancedPortfolio
• BuyAndHold: the default weighting.
• NewtonStep: its paper reports that it runs much faster than the sampled universal portfolio.
• RandomWeighted

References

• [180] T. M. Cover. Universal portfolios. Mathematical Finance 1, 1–29 (1991).
• [184] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory 42, 348–363 (1996).