Online selection rules: the meta-learning rows

struct SwitchingWeighting{T1<:Real, T2<:EuclideanProjection} <: AbstractOnlinePortfolioSelectionAlgorithm

Moves each weight to the other entries with probability $\gamma$ after the wealth step, the switching weighting of Singer (1997) (SP).

As the weighting of an ExpertMixture it acts on the expert-return vector. There the wealth step is the buy-and-hold weighting, and the share is the switch from one expert to another. Over the single-asset constant rebalanced portfolios it is the paper's switching portfolio, SwitchingPortfolio. On the head over the assets it gives the same numbers, because the blend of the unit experts is the weight vector itself. The rule keeps no state and reads no rows. The package does not build the paper's second version, whose rate falls the longer the process holds one asset.

Mathematical definition

\[\begin{align} w_{t+1, k} &= (1 - \gamma)\, \hat{w}_{t, k} + \frac{\gamma}{K - 1} \sum_{j \neq k} \hat{w}_{t, j} \\ &= \left(1 - \frac{\gamma K}{K - 1}\right) \hat{w}_{t, k} + \frac{\gamma}{K - 1}\,. \end{align}\]

Where:

• $w_{t+1, k}$: Weight of entry $k$ during period $t + 1$.
• $\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$.
• $\hat{w}_{t, k}$: Entry $k$ of the Price-Adjusted Allocation.
• $\gamma$: Switching rate, in $[0, 1]$.
• $K$: Length of the weight vector. It is the asset count on the head and the expert count in a mixture.
• $\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.
• $t$: Period index, counted from one.

The first line is the paper's equation 4 written in weights. The second line is its equation 6, because the entries of $\hat{\boldsymbol{w}}_t$ sum to one. The paper notes that the update resembles the fixed share of Herbster and Warmuth. The share is a stochastic matrix, so $\boldsymbol{w}_{t+1}$ lies on the simplex, and the Euclidean projection onto the simplex returns it unchanged. At $\gamma = 0$ the share is the identity. At $\gamma = (K - 1) / K$ every entry of $\boldsymbol{w}_{t+1}$ is $1 / K$.

Algorithm

1. Compute q, the Price-Adjusted Allocation of w over x.
2. Set K to the length of q.
3. When K is one, set p to q, because one entry has no other entry to switch to. Otherwise, set p to the fixed share of q at the rate gamma.
4. Project p onto the Allocation Set with alg.proj, from q. Return the carrier st unchanged, and the projection.

Fields

• gamma: The switching rate, the share of each weight that moves to the other entries every period.

• 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

SwitchingWeighting(; gamma::Real = 1/3, proj::EuclideanProjection = EuclideanProjection()) -> SwitchingWeighting

Keywords correspond to the struct's fields. The default rate is $1/3$, the rate of the paper's experiments without transaction costs.

Validation

• 0 <= gamma <= 1. A DomainError is thrown otherwise.

Examples

julia> SwitchingWeighting()SwitchingWeighting  gamma ┼ Float64: 0.3333333333333333   proj ┴ EuclideanProjection()

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• ExpertMixture
• SwitchingPortfolio: the mixture that this weighting builds over the unit experts.
• BuyAndHold: the weighting at $\gamma = 0$.
• ConstantRebalancedPortfolio: over the unit experts, the uniform one is the weighting at $\gamma = (K - 1) / K$.

References

• [216] Y. Singer. Switching portfolios. International Journal of Neural Systems 8(4), 445–455 (1997).

SwitchingPortfolio(; N::Integer, gamma::Real = 1/3, eset::Option{<:BoundedAllocationSet} = nothing, proj::EuclideanProjection = EuclideanProjection())

Builds Singer's (1997) switching portfolio, the ExpertMixture under SwitchingWeighting over the N single-asset ConstantRebalancedPortfolios of the pinned universe (SP).

The paper's portfolio is the Bayesian mixture over the paths of a hidden process. The process holds one asset, and each period it switches to one of the others with probability $\gamma$. The weight of the mixture on a unit expert is the posterior probability that the process holds that asset in the next period.

A view of the head onto a subset of the assets drops no expert. The unit expert of an excluded asset has no mass on the kept assets, so its constant rebalanced portfolio becomes the uniform allocation over them. The view then runs with one uniform expert for each excluded asset, and it is not the switching portfolio over the kept assets. Construct the portfolio over the assets that it will run on.

Mathematical definition

\[\begin{align} \boldsymbol{h}_k(t) &= \boldsymbol{e}_k\,, \\ \boldsymbol{r}_t &= \boldsymbol{x}_t\,, \\ \boldsymbol{w}_t &= \sum_{k=1}^{N} p_{t, k}\, \boldsymbol{e}_k = \boldsymbol{p}_t\,. \end{align}\]

Where:

• $\boldsymbol{h}_k(t)$: Allocation that expert $k$ holds during period $t$.
• $\boldsymbol{e}_k$: Unit vector of asset $k$.
• $\boldsymbol{r}_t$: Expert-return vector of period $t$, with entries $r_{t,k} = \langle \boldsymbol{h}_k(t), \boldsymbol{x}_t \rangle$.
• $\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.
• $\boldsymbol{p}_t$: Weight vector over the experts at period $t$, with entries $p_{t,k}$ that sum to one.
• $N$: Number of assets.
• $t$: Period index, counted from one.

So $\boldsymbol{p}_t$ takes the switching step over $\boldsymbol{x}_t$, and the portfolio holds the path that the switching step holds on the head over the assets.

Arguments

• N: The number of assets of the pinned universe, one unit expert each.
• gamma: The switching rate.
• eset: The Expert Set the weighting projects onto, or nothing for the bare simplex.
• proj: The geometry of the projection of the blend onto the head's Allocation Set.

Validation

• N >= 1. A DomainError is thrown otherwise.
• 0 <= gamma <= 1. A DomainError is thrown otherwise.

Examples

julia> sp = SwitchingPortfolio(; N = 3);julia> length(sp.experts), sp.alg.gamma(3, 0.3333333333333333)

Related

• ExpertMixture
• SwitchingWeighting: the weighting, which holds the same path on the head over the assets.
• ConstantRebalancedPortfolio: the uniform one is this portfolio at gamma = (N - 1) / N.
• BuyAndHold: this portfolio at gamma = 0.

References

• [216] Y. Singer. Switching portfolios. International Journal of Neural Systems 8(4), 445–455 (1997).

Ader(; eta_min::Real, K::Integer, eps::Real, obj::AbstractOnlineObjective = LogWealth(), eset::Option{<:BoundedAllocationSet} = nothing, proj::EuclideanProjection = EuclideanProjection())

Builds the improved Ader of Zhang, Lu and Zhou (2018, Algorithms 3 and 4), an ExpertMixture of K GradientProjection experts on a geometric grid of rates.

Every expert takes one Euclidean step from its own iterate, on the gradient at the allocation that the mixture played, the BlendPoint. The weighting is ExponentiatedGradient at the rate eps, from the paper's start over the experts. That start gives the largest weight to the smallest rate.

The weighting sets the weights of the experts from their log wealth under every objective obj. So the mixture is the paper's algorithm only under the default LogWealth objective. Under another objective, such as RiskLoss, the experts step on that objective, but the weights follow the log wealth of the experts. The paper tunes the grid and the rate for a known horizon. An online rule does not know the horizon, so the three values are the caller's.

Mathematical definition

\[\begin{align} \eta_k &= 2^{k - 1} \eta_{\min}\,, \\ p_{1, k} &= \frac{C}{k (k + 1)}\,, \\ C &= 1 + \frac{1}{K}\,, \\ \boldsymbol{w}_t &= \sum_{k=1}^{K} p_{t, k}\, \boldsymbol{h}_k(t)\,, \\ \boldsymbol{h}_k(t + 1) &= \mathrm{Proj}_{\mathcal{W}}\left( \boldsymbol{h}_k(t) - \eta_k \nabla f_t(\boldsymbol{w}_t) \right)\,, \\ p_{t+1, k} &= \frac{p_{t, k} \exp\left(-\alpha\, \ell_t(\boldsymbol{h}_k(t))\right)}{\sum_{j=1}^{K} p_{t, j} \exp\left(-\alpha\, \ell_t(\boldsymbol{h}_j(t))\right)}\,. \end{align}\]

Where:

• $\eta_k$: Grid rate of expert $k$, the learning rate of its gradient step.
• $\eta_{\min}$: Smallest grid rate, the rate of the first expert.
• $\boldsymbol{p}_t$: Weight vector over the experts at period $t$, with entries $p_{t,k}$ that sum to one.
• $C$: Normaliser of the start over the experts.
• $K$: Expert count of an expert mixture.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\boldsymbol{h}_k(t)$: Allocation that expert $k$ holds during period $t$.
• $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
• $f_t$: Online loss of period $t$, the objective that the experts step on.
• $\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.
• $\alpha$: Learning rate of the weighting.
• $t$: Period index, counted from one.

The start sums to one, because $\sum_{k=1}^{K} 1 / (k (k + 1)) = K / (K + 1)$. Under the log-wealth loss $f_t(\boldsymbol{w}) = -\log \langle \boldsymbol{w}, \boldsymbol{x}_t \rangle$, the blend gives $\langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle = \langle \boldsymbol{p}_t, \boldsymbol{r}_t \rangle$. The weight update is then the exponentiated-gradient step over the expert-return vector,

\[\begin{align} p_{t+1, k} &= \frac{p_{t, k} \exp\left(\alpha\, r_{t, k} / \langle \boldsymbol{p}_t, \boldsymbol{r}_t \rangle\right)}{\sum_{j=1}^{K} p_{t, j} \exp\left(\alpha\, r_{t, j} / \langle \boldsymbol{p}_t, \boldsymbol{r}_t \rangle\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{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.

Theorem 4 of the paper sets

\[\begin{align} \eta_{\min} &= \frac{D}{G} \sqrt{\frac{7}{2 T}}\,, \\ K &= \left\lceil \tfrac{1}{2} \log_2 \left(1 + \frac{4 T}{7}\right) \right\rceil + 1\,, \\ \alpha &= \sqrt{\frac{2}{T G^2 D^2}}\,. \end{align}\]

Where:

• $D$: Diameter of the feasible set in the Euclidean norm.
• $G$: Bound on the Euclidean norm of the gradient of every online loss over the feasible set.
• $T$: Regret horizon, the number of periods that a regret bound covers.
• $P_T = \sum_{t=2}^{T} \lVert \boldsymbol{u}_t - \boldsymbol{u}_{t-1} \rVert_2$: Path length of a comparator sequence $\boldsymbol{u}_1, \ldots, \boldsymbol{u}_T$ in the feasible set.

Under these values the dynamic regret against every comparator sequence is $O(\sqrt{T (1 + P_T)})$. On the simplex $D = \sqrt{2}$. Under the log-wealth loss the smallest $G$ is $\max_t \lVert \boldsymbol{x}_t \rVert_2 / \min_i x_{t, i}$, which the vertex of the smallest price relative attains.

Arguments

• eta_min: The smallest rate of the grid.
• K: The number of experts.
• eps: The weighting's rate, the paper's $\alpha$.
• obj: The objective every expert steps on.
• eset: The Expert Set the weighting projects onto, or nothing for the bare simplex.
• proj: The geometry of the projection of the blend onto the head's Allocation Set.

Validation

• eta_min > 0, K >= 1, eps > 0. A DomainError is thrown otherwise.

Examples

julia> mix = Ader(; eta_min = 0.05, K = 3, eps = 0.1);julia> [e.eta for e in mix.experts], mix.p0([0.05, 0.1, 0.2], [0.6666666666666666, 0.2222222222222222, 0.1111111111111111])

Related

• ExpertMixture
• BlendPoint
• GradientProjection
• ExponentiatedGradient
• Sword

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).

Sword(; eta_min::Real, K::Integer, eps::Real, obj::AbstractOnlineObjective = LogWealth(), eset::Option{<:BoundedAllocationSet} = nothing, proj::EuclideanProjection = EuclideanProjection())

Builds the small-loss Sword of Zhao, Zhang, Zhang and Zhou (2020, Theorem 5), an ExpertMixture of K GradientProjection experts on a geometric grid of rates, from the uniform start.

The experts, the BlendPoint and the ExponentiatedGradient weighting are those of Ader. The two differ in the start over the experts, which is uniform here, and in the grid that the paper tunes. The paper's meta-algorithm is the exponentially weighted forecaster on the linearised loss, with no optimism.

As for Ader, the weighting sets the weights of the experts from their log wealth under every objective obj. So the mixture is the paper's algorithm only under the default LogWealth objective. The paper tunes the grid and the rate for a known horizon and a known cumulative loss. An online rule knows neither, so the three values are the caller's.

The package builds neither of the paper's two other forms. In the gradient-variation form, the experts take the extra-gradient step and the weighting carries an optimistic hint. The best-of-both-worlds form runs a second meta-algorithm that learns the hint.

Mathematical definition

\[\begin{align} \eta_k &= 2^{k - 1} \eta_{\min}\,, \\ p_{1, k} &= \frac{1}{K}\,, \\ \boldsymbol{w}_t &= \sum_{k=1}^{K} p_{t, k}\, \boldsymbol{h}_k(t)\,, \\ \boldsymbol{h}_k(t + 1) &= \mathrm{Proj}_{\mathcal{W}}\left( \boldsymbol{h}_k(t) - \eta_k \nabla f_t(\boldsymbol{w}_t) \right)\,, \\ p_{t+1, k} &= \frac{p_{t, k} \exp\left(-\varepsilon\, \ell_t(\boldsymbol{h}_k(t))\right)}{\sum_{j=1}^{K} p_{t, j} \exp\left(-\varepsilon\, \ell_t(\boldsymbol{h}_j(t))\right)}\,. \end{align}\]

Where:

• $\eta_k$: Grid rate of expert $k$, the learning rate of its gradient step.
• $\eta_{\min}$: Smallest grid rate, the rate of the first expert.
• $\boldsymbol{p}_t$: Weight vector over the experts at period $t$, with entries $p_{t,k}$ that sum to one.
• $K$: Expert count of an expert mixture.
• $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
• $\boldsymbol{h}_k(t)$: Allocation that expert $k$ holds during period $t$.
• $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
• $f_t$: Online loss of period $t$, the objective that the experts step on.
• $\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.
• $\varepsilon$: Learning rate of the weighting.
• $t$: Period index, counted from one.

The paper writes the forecaster on $\langle \nabla f_t(\boldsymbol{w}_t), \boldsymbol{h}_k(t) \rangle$. That term differs from $\ell_t(\boldsymbol{h}_k(t))$ by a term that is the same for every expert, so the two give the same weights. Under the log-wealth loss $f_t(\boldsymbol{w}) = -\log \langle \boldsymbol{w}, \boldsymbol{x}_t \rangle$, the weight update is the exponentiated-gradient step over the expert-return vector,

\[\begin{align} p_{t+1, k} &= \frac{p_{t, k} \exp\left(\varepsilon\, r_{t, k} / \langle \boldsymbol{p}_t, \boldsymbol{r}_t \rangle\right)}{\sum_{j=1}^{K} p_{t, j} \exp\left(\varepsilon\, r_{t, j} / \langle \boldsymbol{p}_t, \boldsymbol{r}_t \rangle\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{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.

Theorem 5 of the paper sets

\[\begin{align} \eta_{\min} &= \sqrt{\frac{D}{16 L G T}}\,, \\ K &= \left\lceil \tfrac{1}{2} \log_2 \frac{G T}{D L} \right\rceil + 1\,, \\ \varepsilon &= \sqrt{\frac{2 + \ln K}{D^2 F_T^{\boldsymbol{w}}}}\,. \end{align}\]

Where:

• $D$: Diameter of the feasible set in the Euclidean norm.
• $G$: Bound on the Euclidean norm of the gradient of every online loss over the feasible set.
• $L$: Smoothness constant of every online loss.
• $T$: Regret horizon, the number of periods that a regret bound covers.
• $F_T^{\boldsymbol{w}} = \sum_{t=1}^{T} f_t(\boldsymbol{w}_t)$: Cumulative loss of the played allocations.
• $F_T = \sum_{t=1}^{T} f_t(\boldsymbol{u}_t)$: Cumulative loss of the comparator sequence.
• $P_T = \sum_{t=2}^{T} \lVert \boldsymbol{u}_t - \boldsymbol{u}_{t-1} \rVert_2$: Path length of a comparator sequence $\boldsymbol{u}_1, \ldots, \boldsymbol{u}_T$ in the feasible set.

Under these values the dynamic regret against every comparator sequence is $O(\sqrt{(1 + P_T + F_T)(1 + P_T)})$. The theorem needs online losses that are non-negative and $L$-smooth on the whole space. The log-wealth loss has a value only where $\langle \boldsymbol{w}, \boldsymbol{x}_t \rangle > 0$, so the bound does not apply to it.

Arguments

• eta_min: The smallest rate of the grid.
• K: The number of experts.
• eps: The weighting's rate, the paper's $\varepsilon$.
• obj: The objective every expert steps on.
• eset: The Expert Set the weighting projects onto, or nothing for the bare simplex.
• proj: The geometry of the projection of the blend onto the head's Allocation Set.

Validation

• eta_min > 0, K >= 1, eps > 0. A DomainError is thrown otherwise.

Examples

julia> mix = Sword(; eta_min = 0.05, K = 3, eps = 0.1);julia> [e.eta for e in mix.experts], mix.p0([0.05, 0.1, 0.2], nothing)

Related

• ExpertMixture
• BlendPoint
• GradientProjection
• ExponentiatedGradient
• Ader

References

• [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).