Mirror descent

MirrorDescent is the first-order rule. At each period it takes one mirror descent step on the gradient, in the divergence of its projection geometry. Each constructor is named after one published method, and its docstring cites the work that defines it. ExponentiatedGradient uses the entropic geometry, and GradientProjection uses the Euclidean one. EGE, EGR and EGA are the exponentiated gradient with momentum, with root-mean-square scaling and with adaptive moments.

In place of a fixed step size eta, a rule can hold a learning-rate schedule. InverseSquareRootRate and SelfConfidentRate set the step size at each period. DoublingTrickRate restarts the rule at each stage. WindowedBestRate runs the exponentiated gradient at each rate of a set, and takes the rate with the most wealth over a window. MAEG and AEG are the two adaptive strategies of Zhang et al. [268], which also defines WindowedBestRate.

A gradient transform, such as GradientMomentum, rescales the gradient before the step. The default grad = nothing applies none. The debias field of each transform selects whether it divides its moving averages by their bias at a zero start, as Adam does, and the default divides nothing. The rule steps on log wealth, LogWealth, by default, or on a risk measure over the last rows, RiskLoss. A gradient predictor in the predictor field makes the rule optimistic mirror descent. The rule then takes two half-steps each period, the second along a guess of the next gradient. The page Adaptive optimistic has the predictors.

PortfolioOptimisers.AbstractGradientTransform — Type
abstract type AbstractGradientTransform <: AbstractAlgorithm

Abstract supertype for the Gradient Transforms, which change the gradient of a first-order rule before its mirror step.

A MirrorDescent rule applies its transform to the gradient of every period. Its default grad = nothing applies no transform, so the mirror step reads the gradient of the period as it is. The momentum transforms of Section 4.2 of [77] change the exponent of the multiplicative update, and do not change the form of the update.

Each moving average of the three momentum transforms starts at zero, and the debias field of the transform selects how the transform reads it. The default debias = nothing reads the average as it is, which is the form of Equations 7, 8 and 9 of [77]. ZeroStartDebias divides each average by $1 - \gamma^k$, so each average is the weighted mean of the gradients that it read, which is the correction of Algorithm 1 of [78]. The count $k$ is shared by all assets, and a restart of the Learning-Rate Schedule reseeds it with the averages. So, up to $\epsilon$, the correction multiplies the step of the $k$-th period since the seed by one scalar:

TransformFactor of the corrected step over the uncorrected step
GradientMomentum$1 / (1 - \gamma_1^k)$
RootMeanSquareGradient$\sqrt{1 - \gamma_2^k}$
AdaptiveMomentGradient$\sqrt{1 - \gamma_2^k} / (1 - \gamma_1^k)$

The undivided form starts slowly. At $\gamma_1 = 0.99$ and $\gamma_2 = 0$, the defaults of [77], the first uncorrected step is $1 - \gamma_1 = 0.01$ of the corrected step. It stays below one half of the corrected step for the first 68 periods, and it is $0.63$ of it after $1 / (1 - \gamma_1) = 100$ periods. This shrinks the early steps, when the averages read few gradients. The divided form takes each step at its full size from the first period. At $\gamma_2 = 0$ the factor $\sqrt{1 - \gamma_2^k}$ is one, so the correction does not change RootMeanSquareGradient at its default. At the rates $\gamma_1 = 0.9$ and $\gamma_2 = 0.999$ of [78], the uncorrected first step is about three times the corrected one, because the second average is small, and [78] corrects both averages for this reason. No Learning-Rate Schedule of the library gives these factors, so the field is the way to reach the divided form.

Interfaces

In order to implement a new transform, subtype AbstractGradientTransform and implement:

  • gradient_state_seed(grad::AbstractGradientTransform, w::AbstractVector): The state the transform keeps on the Rule State before the first row, such as a moving average of the gradient, or nothing, the default. w is the Start Allocation, and the state takes its length and its element type.
  • transform_gradient!(grad::AbstractGradientTransform, gs, g::AbstractVector) -> Tuple: Returns the state of the transform after the period, and the transformed gradient of the period, computed from the raw gradient g. It can write the arrays of the state gs in place. The rule keeps the returned state, so a state that holds a count returns a new value of it.

A transform whose state is not nothing, a vector, a pair of vectors or a GradientAverageState also implements:

  • gradient_state_view(gs::MyGradientState, i) -> MyGradientState: The state of the transform, sliced to the assets i, as a copy.
  • copy_gradient_state(gs::MyGradientState) -> MyGradientState: A copy of the state of the transform that shares no array with it.

The head's state already slices and copies a transform state of the other four shapes.

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.
  • [78] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations (2015). Algorithm 1.
source
PortfolioOptimisers.InverseSquareRootRate — Type
struct InverseSquareRootRate{__T_c} <: AbstractLearningRateSchedule

Shrinks the learning rate with the square root of the period count, and needs no horizon.

The schedule reads the period count and nothing else. It is the schedule of Theorem 1 of [229] for online gradient descent, which gives an $O(\sqrt{T})$ regret under the Euclidean map. At $c = \sqrt{\log N / (2 N)}$ it is the anytime Soft-Bayes rate of Theorem 10 of [257]. That theorem states the rate for the Soft-Bayes step with the online correction of Equation 14 of [257].

Under the entropic map, Theorem 4.1 of [249] tunes a fixed rate, $\eta = 2 r \sqrt{2 \log N / T}$. That rate needs the horizon $T$ and a lower bound $r$ on each price relative as a fraction of the largest one of its period. An online rule knows neither, so the library states that rate here and does not implement it as a schedule.

Mathematical definition

\[\begin{align} \eta_t &= \frac{c}{\sqrt{t}}\,. \end{align}\]

Where:

  • $\eta_t$: Learning rate of the update at period $t$.
  • $c > 0$: Scale of the rate.
  • $t$: Period index, counted from one.

Fields

  • c: The scale of the rate, the numerator of $c / \sqrt{t}$.

Constructors

InverseSquareRootRate(; c::Real = 1) -> InverseSquareRootRate

Keywords correspond to the struct's fields.

Validation

  • c > 0. A DomainError is thrown otherwise.

Examples

julia> InverseSquareRootRate()InverseSquareRootRate  c ┴ Int64: 1

Related

References

  • [229] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, 928–936 (2003). Algorithm 1, Theorem 1.
  • [257] L. Orseau, T. Lattimore and S. Legg. Soft-Bayes: Prod for mixtures of experts with log-loss. In: Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76, 372–399 (2017). Section 6, Equation 14, Theorem 10.
  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Theorem 4.1.
source
PortfolioOptimisers.DoublingTrickRate — Type
struct DoublingTrickRate{__T_N} <: AbstractLearningRateSchedule

Runs the rule in stages of growing length, and restarts it at the Start Allocation after the last period of each stage.

This is the staged exponentiated gradient of Corollary 4.3 of [249], with the uniform mix. It applies the doubling trick of Section 4.6 of [269], which restarts the rule at a growing guess of the horizon. Each stage sets its uniform-mix share and its rate from its own length, as Theorem 4.2 of [249] sets them from the horizon. The schedule sets both, so a MirrorDescent that holds it does not read its own alpha.

From the uniform Start Allocation, the staged rule is universal. For every sequence of non-negative price relatives, with no lower bound on them, its regret against every constant rebalanced portfolio over $T$ periods is at most $6 N^2 \log N (1 + (T / (2 N^2 \log N))^{3/4})$, which the proof of Corollary 4.3 of [249] derives. The bound holds under the entropic map. Under another map the schedule restarts the rule and sets its rate, and no bound is known.

Mathematical definition

\[\begin{align} T_0 &= \lceil 2 N^2 \log N \rceil\,, \\ T_i &= \lceil 2^i N^2 \log N \rceil\,, \quad i > 0\,, \\ \alpha_i &= \left( \frac{N^2 \log N}{8 T_i} \right)^{1/4}\,, \\ \eta_i &= \sqrt{\frac{8 \alpha_i^2 \log N}{N^2 T_i}}\,. \end{align}\]

Where:

  • $N$: Number of assets.
  • $i$: Stage index, counted from zero.
  • $T_i$: Length of stage $i$, in periods.
  • $\alpha_i$: Uniform-mix share of every period of stage $i$.
  • $\eta_i$: Learning rate of every period of stage $i$.

Stages $0$ and $1$ have the same length. At $T_i \geq 2 N^2 \log N$ the share is at most $1/2$, the range that Theorem 4.2 of [249] needs.

Algorithm

At period t the schedule runs these steps.

  1. Find the stage that holds t with doubling_stage, giving its length len and its last period fin.
  2. Compute the stage's share $\alpha_i$ from len. The rule reads it in place of its own alpha.
  3. Compute the stage's rate $\eta_i$ from the share and len.
  4. When t == fin, name a restart. The rule's update of period t then returns the Start Allocation, and puts the state of the rule back at its seed. The period count stays, because the stages are cumulative.

Fields

  • N: The number of assets. The stage lengths, the shares and the rates depend on it.

Constructors

DoublingTrickRate(; N::Integer) -> DoublingTrickRate

Keywords correspond to the struct's fields. N is the number of assets the rule moves over, or the number of experts when the rule weights a mixture. It has no default, because the stage lengths depend on it.

Validation

  • N >= 2. A DomainError is thrown otherwise, because $\log 1 = 0$ gives a stage of no periods.

Examples

julia> DoublingTrickRate(; N = 4)DoublingTrickRate  N ┴ Int64: 4

Related

References

  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Section 4, Theorem 4.2, Corollary 4.3.
  • [269] N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire and M. K. Warmuth. How to use expert advice. Journal of the ACM 44(3), 427–485 (1997). Section 4.6, Algorithm P*.
source
PortfolioOptimisers.SelfConfidentRate — Type
struct SelfConfidentRate{__T_eta_max} <: AbstractLearningRateSchedule

Reads the learning rate from the running excess of each period's best asset over the played allocation.

This is the self-confident rate of Theorem 6 of [257]. The state of the rule keeps the excess for the schedule, beside $\log N$. The excess is measured at the allocation the rule played, so under a MirrorDescent with a positive alpha it reads the mix.

Theorem 6 of [257] bounds the regret of the Soft-Bayes step, ExpectationMaximisation, against every constant rebalanced portfolio. At the fixed rate $\sqrt{2 \log N / C_1}$, with $C_1$ the excess of the whole run, the bound is $\min\{C_1, \sqrt{2 C_1 \log N} + 2 T \log N / C_1\}$. It is small when one asset is the best predictor for long stretches. Orseau et al. [257] note that the excess never falls, so the rate can be read online from the running excess. Remark 8 of [257] states no formal result for that online rate. Under a MirrorDescent the rate is read online in the same way, and no bound is known either.

Under the online form of the Soft-Bayes step, this rate caps the pull towards the Start Allocation at $\sqrt{t / (t + 1)}$, as Remark 8 of [257] advises (correction_ratio_cap). Without the cap, the rate stays almost constant while the mixture predicts well, and a weight can then decay exponentially.

The rate is capped at eta_max, because the excess is zero before the first row. The theorem needs a rate in $(0, 1)$, and [257] states no cap, so the default cap is the end of that interval.

Mathematical definition

\[\begin{align} C_{1, t} &= \sum_{s = 1}^{t} \left( \max_i \frac{x_{s, i}}{\langle \boldsymbol{w}_s, \boldsymbol{x}_s \rangle} - 1 \right)\,, \\ \eta_t &= \min\left( \sqrt{\frac{2 \log N}{C_{1, t-1}}}, \eta_{\max} \right)\,. \end{align}\]

Where:

  • $C_{1, t}$: First-order excess through period $t$, zero at $t = 0$.
  • $x_{s, i}$: Price relative of asset $i$ in period $s$.
  • $\boldsymbol{x}_s$: Price relative vector of period $s$.
  • $\boldsymbol{w}_s$: Allocation the rule played in period $s$.
  • $\eta_t$: Learning rate of the update at period $t$.
  • $\eta_{\max} > 0$: Cap on the rate.
  • $N$: Number of assets.

Each term of $C_{1, t}$ is non-negative, because the largest price relative is at least their mean under $\boldsymbol{w}_s$. So the excess never falls, and the rate never rises. While the excess is zero, the rate is $\eta_{\max}$.

Algorithm

  1. Before the first row, seed the statistic s = [0, log(N)].
  2. Read the rate of period t from s: eta_max while s[1] is not positive, and $\eta_t$ otherwise.
  3. After the rule's step of period t, add maximum(x ./ dot(w, x)) - 1 to s[1], with w the allocation the rule played in period t and x its price relative.

Fields

  • eta_max: The cap on the rate, answered while the running excess is zero and whenever the formula exceeds it.

Constructors

SelfConfidentRate(; eta_max::Real = 1) -> SelfConfidentRate

Keywords correspond to the struct's fields.

Validation

  • eta_max > 0. A DomainError is thrown otherwise.

Examples

julia> SelfConfidentRate()SelfConfidentRate  eta_max ┴ Int64: 1

Related

References

  • [257] L. Orseau, T. Lattimore and S. Legg. Soft-Bayes: Prod for mixtures of experts with log-loss. In: Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76, 372–399 (2017). Section 5, Theorem 6. Section 6, Remark 8.
source
PortfolioOptimisers.WindowedBestRate — Type
struct WindowedBestRate{__T_etas, __T_window} <: AbstractLearningRateSchedule

Chooses the learning rate of each period from a set of rates, by the recent wealth of one exponentiated-gradient run per rate.

This is the moving-window adaptive rate of Equations 7 to 9 of [268]. Each rate in etas names an expert, the exponentiated gradient run at that rate from the Start Allocation. The rate of the period is the rate of the expert with the largest wealth over the last window periods. When window is nothing, the schedule compares the wealth over the whole history. Zhang et al. [268] call the first rule MAEG and the second AEG, which is Equation 11 of that work.

The experts are a statistic of the run, and the rule never plays them. Each expert takes the plain entropic step of Equation 10 of [268] over the simplex, from the rule's Start Allocation, whatever the rule's own geometry, Allocation Set, uniform mix, Gradient Transform and objective. The rule applies the chosen rate to its own step. So on another geometry the schedule chooses the rate by a replay of the exponentiated gradient.

Section 5.2 of [268] takes the rate set 0.001:0.001:0.2 from the practice of Helmbold et al. [249], and chooses the window 30 over 7 on its data. Over windows from 2 to 50, Section 5.4.2 of [268] reports that the final wealth stays within a small range, and that the window must stay within a reasonable range. A period costs one entropic step per rate and one sum over the ring, which is O((N + w) K) at K rates. The online form of ExpectationMaximisation refuses this schedule by name, because that form also reads the rate of the next period.

Mathematical definition

\[\begin{align} t' &= \max(1, t - w + 1)\,, \\ S_t(\eta) &= \prod_{\tau = t'}^{t} \langle \boldsymbol{b}_\tau(\eta), \boldsymbol{x}_\tau \rangle\,, \\ \eta_t &= \underset{\eta \in H}{\arg\max} \; S_t(\eta)\,. \end{align}\]

Where:

  • $H$: Set of rates, the field etas.
  • $w$: Window, in periods. Under the whole history $t' = 1$.
  • $\boldsymbol{b}_\tau(\eta)$: Allocation of the expert at rate $\eta$ in period $\tau$.
  • $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
  • $S_t(\eta)$: Wealth of the expert at rate $\eta$ over the window that ends at period $t$.
  • $\eta_t$: Learning rate of the update at period $t$.
  • $t$: Period index, counted from one.

The rate of the update at period $t$ reads $\boldsymbol{x}_t$. It is $\eta_{t+1}$ in [268], which forms $\boldsymbol{b}_{t+1}$ from $\boldsymbol{b}_t$ and $\boldsymbol{x}_t$. At a tie the first rate of etas wins.

Algorithm

  1. Before the first row, seed the state: every column of B is the Start Allocation, and L is zero, with window rows, or one row under the whole history.
  2. The schedule answers true to reads_period_row, so the rule writes the state before it reads the rate. At period n, find the row row of L with ring_row.
  3. For the expert b at each rate eta, compute its period return r = dot(b, x). Write log(r) into L[row, k]: overwrite it under a window, and add it to the running sum under the whole history.
  4. Step b to b .* exp.(eta .* x ./ r), and divide it by its sum.
  5. Sum each column of L, and take the rate of the column with the largest sum. The sum is in logs, so the comparison never overflows.

Fields

  • etas: The rates the experts run at, one exponentiated-gradient run each.
  • window: The number of periods over which the schedule compares the experts' wealth. nothing compares the whole history.

Constructors

WindowedBestRate(; etas::AbstractVector{<:Real} = 0.001:0.001:0.2, window::Option{<:Integer} = 30) -> WindowedBestRate

Keywords correspond to the struct's fields.

Validation

  • etas: non-empty, and every element is positive and finite.
  • window >= 1 when it is a number. A DomainError is thrown otherwise.

Examples

julia> WindowedBestRate()WindowedBestRate    etas ┼ 200-element StepRangeLen{Float64, Base.TwicePrecision{Float64}, Base.TwicePrecision{Float64}, Int64}  window ┴ Int64: 30

Related

References

  • [268] Y. Zhang, H. Lin, L. Zheng and X. Yang. Adaptive online portfolio strategy based on exponential gradient updates. Journal of Combinatorial Optimization 43(3), 672–696 (2022). Section 4, Equations 7 to 11, Algorithm 2. Section 5.2. Section 5.4.2.
  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Section 5.2, Table 5.3.
source
PortfolioOptimisers.GradientMomentum — Type
struct GradientMomentum{__T_gamma1, __T_debias} <: AbstractGradientTransform

Replaces the gradient with its exponential moving average, which gives the step a momentum.

This is Equation 7 of [77]. Under the entropic map it is the EGE of Li et al. [77]. Equation 13 of Theorem 1 of [77] bounds the regret by $O(\sqrt{T \log N})$, as for the exponentiated gradient, with constants that depend on the ratio of the transformed gradient to the raw one.

Mathematical definition

\[\begin{align} \boldsymbol{v}_{t+1} &= \gamma_1 \boldsymbol{v}_t + (1 - \gamma_1) \boldsymbol{g}_t\,, \\ \hat{\boldsymbol{g}}_t &= \begin{cases} \boldsymbol{v}_{t+1} & \text{under } \texttt{debias = nothing} \\ \dfrac{\boldsymbol{v}_{t+1}}{1 - \gamma_1^{k}} & \text{under } \texttt{debias = ZeroStartDebias()} \end{cases}\,. \end{align}\]

Where:

  • $\boldsymbol{v}_t$: Gradient average before period $t$, zero at $t = 1$.
  • $\gamma_1$: Momentum decay, the weight the gradient average keeps on its past, in $[0, 1)$.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate.
  • $\hat{\boldsymbol{g}}_t$: Transformed gradient of period $t$, the vector the mirror step reads.
  • $k$: Steps taken since the seed of the averages, one at the first step and again at the first step after a restart of the schedule.

The average starts at zero, so under the default debias = nothing the first transformed gradient is $(1 - \gamma_1) \boldsymbol{g}_1$. Li et al. [77] apply no bias correction, and the default follows them. ZeroStartDebias gives the corrected average, whose first value is $\boldsymbol{g}_1$. AbstractGradientTransform compares the two forms.

Fields

  • gamma1: The decay of the moving average of the gradient, in [0, 1).
  • debias: How the transform reads each moving average out of its state, which starts at zero. nothing, the default, reads the average as it is, the undivided form of Equations 7, 8 and 9 of [77]. ZeroStartDebias divides each average by 1 - gamma^k, where k counts the steps since the seed of the state, the corrected form of Algorithm 1 of [78].

Constructors

GradientMomentum(; gamma1::Real = 0.99, debias::Option{<:AbstractZeroStartDebias} = nothing) -> GradientMomentum

Keywords correspond to the struct's fields. The default gamma1 comes from Section 5.5.1 of [77], and the default debias is the undivided form of Equation 7.

Validation

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

Examples

julia> GradientMomentum()GradientMomentum  gamma1 ┼ Float64: 0.99  debias ┴ nothing

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.1, Equation 7. Section 4.3, Theorem 1. Section 5.5.1.
  • [78] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations (2015). Algorithm 1.
source
PortfolioOptimisers.RootMeanSquareGradient — Type
struct RootMeanSquareGradient{__T_gamma2, __T_eps, __T_debias} <: AbstractGradientTransform

Divides the gradient by the root of a moving average of its square, per asset.

This is Equation 8 of [77]. Under the entropic map it is the EGR of Li et al. [77].

At the default $\gamma_2 = 0$, which Section 5.5.1 of [77] recommends, the rule under LogWealth stays at its Start Allocation, up to the offset $\epsilon$. At $\gamma_2 = 0$ the transformed gradient is the sign of the gradient, up to $\epsilon$. Every entry of the log-wealth gradient is negative, so the step moves every asset by the same amount, and the normalisation undoes it. The rule is then the constant rebalanced portfolio at its Start Allocation, not buy-and-hold. A positive $\gamma_2$ gives the average a memory, and the rule then moves.

Mathematical definition

\[\begin{align} \boldsymbol{m}_{t+1} &= \gamma_2 \boldsymbol{m}_t + (1 - \gamma_2) \boldsymbol{g}_t^2\,, \\ \hat{\boldsymbol{m}}_{t+1} &= \begin{cases} \boldsymbol{m}_{t+1} & \text{under } \texttt{debias = nothing} \\ \dfrac{\boldsymbol{m}_{t+1}}{1 - \gamma_2^{k}} & \text{under } \texttt{debias = ZeroStartDebias()} \end{cases}\,, \\ \hat{\boldsymbol{g}}_t &= \frac{\boldsymbol{g}_t}{\sqrt{\hat{\boldsymbol{m}}_{t+1}} + \epsilon}\,. \end{align}\]

Where:

  • $\boldsymbol{m}_t$: Squared-gradient average before period $t$, the square taken per asset, zero at $t = 1$.
  • $\hat{\boldsymbol{m}}_{t+1}$: Squared-gradient average that the division reads, divided by $1 - \gamma_2^k$ under ZeroStartDebias.
  • $\gamma_2$: Squared-gradient decay, the weight the squared-gradient average keeps on its past, in $[0, 1)$.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate.
  • $\hat{\boldsymbol{g}}_t$: Transformed gradient of period $t$, the vector the mirror step reads.
  • $\epsilon$: Positive offset added to the root of the squared-gradient average before the division.
  • $k$: Steps taken since the seed of the averages, one at the first step and again at the first step after a restart of the schedule.

The square, the root and the division are per asset. At $\gamma_2 = 0$, $\hat{\boldsymbol{g}}_t = \boldsymbol{g}_t / (\lvert \boldsymbol{g}_t \rvert + \epsilon)$ under both values of debias. Li et al. [77] apply no bias correction, and the default debias = nothing follows them. AbstractGradientTransform compares the two forms.

Fields

  • gamma2: The decay of the moving average of the squared gradient, in [0, 1).
  • eps: The constant added to the root of the average before the division.
  • debias: How the transform reads each moving average out of its state, which starts at zero. nothing, the default, reads the average as it is, the undivided form of Equations 7, 8 and 9 of [77]. ZeroStartDebias divides each average by 1 - gamma^k, where k counts the steps since the seed of the state, the corrected form of Algorithm 1 of [78].

Constructors

RootMeanSquareGradient(; gamma2::Real = 0, eps::Real = 1e-8, debias::Option{<:AbstractZeroStartDebias} = nothing) -> RootMeanSquareGradient

Keywords correspond to the struct's fields. The default gamma2 comes from Section 5.5.1 of [77], the default eps from Section 4.2.2, and the default debias is the undivided form of Equation 8.

Validation

  • 0 <= gamma2 < 1, eps > 0. A DomainError is thrown otherwise.

Examples

julia> RootMeanSquareGradient()RootMeanSquareGradient  gamma2 ┼ Int64: 0     eps ┼ Float64: 1.0e-8  debias ┴ nothing

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.2, Equation 8. Section 5.5.1.
  • [78] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations (2015). Algorithm 1.
source
PortfolioOptimisers.AdaptiveMomentGradient — Type
struct AdaptiveMomentGradient{__T_gamma1, __T_gamma2, __T_eps, __T_debias} <: AbstractGradientTransform

Divides the moving average of the gradient by the root of the moving average of its square, per asset.

This is Equation 9 of [77], with both averages of GradientMomentum and RootMeanSquareGradient. Under the entropic map it is the EGA of Li et al. [77], which applies no bias correction, and the default debias = nothing follows it. Algorithm 1 of [78] divides both averages by their bias, with the decay rates $\beta_1 = 0.9$ and $\beta_2 = 0.999$ and the offset $\epsilon = 10^{-8}$ as defaults. AdaptiveMomentGradient(; gamma1 = 0.9, gamma2 = 0.999, debias = ZeroStartDebias()) is that algorithm. The decay rates default to those of [77]. AbstractGradientTransform compares the two forms.

Mathematical definition

\[\begin{align} \boldsymbol{v}_{t+1} &= \gamma_1 \boldsymbol{v}_t + (1 - \gamma_1) \boldsymbol{g}_t\,, \\ \boldsymbol{m}_{t+1} &= \gamma_2 \boldsymbol{m}_t + (1 - \gamma_2) \boldsymbol{g}_t^2\,, \\ (\hat{\boldsymbol{v}}_{t+1}, \hat{\boldsymbol{m}}_{t+1}) &= \begin{cases} (\boldsymbol{v}_{t+1}, \boldsymbol{m}_{t+1}) & \text{under } \texttt{debias = nothing} \\ \left(\dfrac{\boldsymbol{v}_{t+1}}{1 - \gamma_1^{k}}, \dfrac{\boldsymbol{m}_{t+1}}{1 - \gamma_2^{k}}\right) & \text{under } \texttt{debias = ZeroStartDebias()} \end{cases}\,, \\ \hat{\boldsymbol{g}}_t &= \frac{\hat{\boldsymbol{v}}_{t+1}}{\sqrt{\hat{\boldsymbol{m}}_{t+1}} + \epsilon}\,. \end{align}\]

Where:

  • $\boldsymbol{v}_t$: Gradient average before period $t$, zero at $t = 1$.
  • $\boldsymbol{m}_t$: Squared-gradient average before period $t$, the square taken per asset, zero at $t = 1$.
  • $\hat{\boldsymbol{v}}_{t+1}$: Gradient average that the step reads, divided by $1 - \gamma_1^k$ under ZeroStartDebias.
  • $\hat{\boldsymbol{m}}_{t+1}$: Squared-gradient average that the division reads, divided by $1 - \gamma_2^k$ under ZeroStartDebias.
  • $\gamma_1$: Momentum decay, the weight the gradient average keeps on its past, in $[0, 1)$.
  • $\gamma_2$: Squared-gradient decay, the weight the squared-gradient average keeps on its past, in $[0, 1)$.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate.
  • $\hat{\boldsymbol{g}}_t$: Transformed gradient of period $t$, the vector the mirror step reads.
  • $\epsilon$: Positive offset added to the root of the squared-gradient average before the division.
  • $k$: Steps taken since the seed of the averages, one at the first step and again at the first step after a restart of the schedule.

At the default $\gamma_2 = 0$, which Section 5.5.1 of [77] recommends, the divisor is $\lvert \boldsymbol{g}_t \rvert + \epsilon$. The step then reads the momentum in units of the size of the current gradient.

Fields

  • gamma1: The decay of the moving average of the gradient, in [0, 1).
  • gamma2: The decay of the moving average of the squared gradient, in [0, 1).
  • eps: The constant added to the root of the second average before the division.
  • debias: How the transform reads each moving average out of its state, which starts at zero. nothing, the default, reads the average as it is, the undivided form of Equations 7, 8 and 9 of [77]. ZeroStartDebias divides each average by 1 - gamma^k, where k counts the steps since the seed of the state, the corrected form of Algorithm 1 of [78].

Constructors

AdaptiveMomentGradient(; gamma1::Real = 0.99, gamma2::Real = 0, eps::Real = 1e-8, debias::Option{<:AbstractZeroStartDebias} = nothing) -> AdaptiveMomentGradient

Keywords correspond to the struct's fields. The defaults of gamma1, gamma2 and eps come from Sections 4.2.2 and 5.5.1 of [77], and the default debias is the undivided form of Equation 9.

Validation

  • 0 <= gamma1 < 1, 0 <= gamma2 < 1, eps > 0. A DomainError is thrown otherwise.

Examples

julia> AdaptiveMomentGradient()AdaptiveMomentGradient  gamma1 ┼ Float64: 0.99  gamma2 ┼ Int64: 0     eps ┼ Float64: 1.0e-8  debias ┴ nothing

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.3, Equation 9. Section 5.5.1.
  • [78] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations (2015). Algorithm 1.
source
PortfolioOptimisers.AbstractOnlineObjective — Type
abstract type AbstractOnlineObjective <: AbstractAlgorithm

Abstract supertype for the objectives of a first-order Online Selection Rule.

The objective is the loss of each period. The mirror step reads the gradient of that loss at the iterate.

Interfaces

In order to implement a new objective, subtype AbstractOnlineObjective and implement:

  • loss_gradient(obj::AbstractOnlineObjective, u::AbstractVector, x::AbstractVector, rows) -> AbstractVector: The gradient of the period's loss at the iterate u. It reads the period's price relative x and the rows the head holds, which are nothing when the objective reads no rows.
  • rows_needed(obj::AbstractOnlineObjective) -> Union{Nothing, Integer}: The number of rows the objective reads at a step, 0 when it reads none. The rule that holds the objective answers this number as its own.

Related

source
PortfolioOptimisers.LogWealth — Type
struct LogWealth <: AbstractOnlineObjective

Takes the negative log of the period's wealth as the loss of a first-order Online Selection Rule.

It reads the period's price relative and no rows. It is the default objective of MirrorDescent, and the objective of every rule that the docstring of MirrorDescent cites.

Mathematical definition

\[\begin{align} \ell_t(\boldsymbol{w}) &= -\log \langle \boldsymbol{w}, \boldsymbol{x}_t \rangle\,, \\ \boldsymbol{g}_t &= \nabla \ell_t(\boldsymbol{w}_t) = -\frac{\boldsymbol{x}_t}{\langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle}\,. \end{align}\]

Where:

  • $\ell_t$: Loss of period $t$.
  • $\boldsymbol{w}$: Allocation at which the loss is evaluated.
  • $\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{g}_t$: Gradient of the loss of period $t$, taken at the iterate.

Examples

julia> LogWealth()LogWealth()

Related

source
PortfolioOptimisers.RiskLoss — Type
struct RiskLoss{__T_r, __T_window, __T_sca, __T_pe} <: AbstractOnlineObjective

Takes a risk measure over the last window rows the head holds as the loss of a first-order Online Selection Rule.

The Risk Loss replaces log wealth as the objective. r is one risk measure or a vector of them. The Risk Loss reads returns and not price relatives, because a risk measure reads returns. At every step the prior pe is fitted on the window, and the measure is resolved against that prior. So a Variance reads the covariance of the window, and a measure that holds its own matrix keeps it. The rule takes one step per period towards the minimiser of the measure, which it estimates again each period.

sca scalarises a vector of measures at the settings.scale of each measure. So [MeanReturn(), Variance()], with a negative scale on the mean, gives one step on the mean-variance utility.

When its prior states x_src = ExcessSource(), the loss reads the returns in excess of the benchmark. The loss holds no source of its own. It gives the window to pe, and the prior fits it on X - B, which benchmark_relative_returns gives. So a Variance becomes the tracking variance against the benchmark B that the rows carry. The head's rows keep the raw returns and the benchmark, so the prior reads its own source, whatever the source of the head's step is. The prior joins the group of the head, see group_frames. A DataBenchmarkTracking in r refuses a prior that states ExcessSource(), because it would subtract the benchmark twice.

A prior fitted on one row has no covariance. So the loss starts when the head holds two rows, and the step before that leaves the iterate unchanged. The loss reads the last window rows that the head holds, so the first window - 1 steps read a shorter window. The head can hold more rows, because its Allocation Set or another rule can need more, and the loss does not read them.

A risk gradient is small, so a rule on a Risk Loss needs a much larger rate than a log-wealth rule. A variance gradient $2 \boldsymbol{\Sigma} \boldsymbol{w}$ has the size of one period's variance. Take 1000 periods of returns randn(StableRNG(7), 1000, 4) .* [0.01 0.02 0.03 0.04], a window of 20 and the uniform allocation. Over every window, the log-wealth gradient is then between 1100 and 6400 times larger than the variance gradient. The entropic rule on Variance at the log-wealth default eta = 0.05 ends 0.005 from its uniform start, and the minimum-variance allocation is 0.45 away. At eta = 100 the rule ends within 0.06 of that allocation.

The prior is fitted on the window, a view of the rows that the head holds as a ReturnsResult, as a batch prior is fitted on any returns data. The rows hold NaN where there was no return, and the active mask beside them. So under a time-varying panel the prior reduces to the Coverage Universe of the window, and answers NaN at an asset that the window does not cover. The loss reads its gradient on the Investable Mask of that result, and writes zero at every other leg. The window holds no data about such a leg, so the loss does not move it, and the projection alone places it. A plain pe therefore never meets a constant column. A leg unlisted for a part of the window is outside the Coverage Universe of a plain prior until the window clears that part. A mask-aware prior takes the leg in after its own warm-up.

The regret theorems of the first-order rules need a convex loss. So they hold here for the measures that are convex in the weights: Variance, StandardDeviation, ConditionalValueatRisk, EntropicValueatRisk, WorstRealisation, Range, MaximumDrawdown, AverageDrawdown, ConditionalDrawdownatRisk, EntropicDrawdownatRisk, the low-order moment measures, and MeanReturn, which is linear. A quantile measure such as ValueatRisk or DrawdownatRisk, a kurtosis, a skewness and a ratio are not convex, and on them the step is a heuristic with no bound. At a kink of a convex measure, a finite-difference gradient is the chord across the kink, near a subgradient, as risk_gradient states.

Mathematical definition

\[\begin{align} \ell_t(\boldsymbol{w}) &= \rho(\boldsymbol{w}; \mathbf{X}_t)\,, \\ \boldsymbol{g}_t &= \nabla_{\boldsymbol{w}} \rho(\boldsymbol{w}_t; \mathbf{X}_t)\,. \end{align}\]

Where:

  • $\ell_t$: Loss of period $t$.
  • $\rho$: Risk measure, resolved against the prior fitted on $\mathbf{X}_t$. A vector of measures is their scalarisation.
  • $\mathbf{X}_t$: Returns of the last $\min(t, W)$ periods through period $t$, with $W$ the field window. When pe states x_src = ExcessSource() they are the returns in excess of the benchmark.
  • $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate.

risk_gradient computes $\boldsymbol{g}_t$, in closed form where the library states one and by a finite difference otherwise. loss_gradient states the steps.

Fields

  • r: Risk measure or vector of risk measures.
  • window: The number of rows of the head's returns buffer that the loss reads.
  • sca: Scalariser for combining multiple risk measures. nothing gives the sum of SumScalariser.
  • pe: Prior estimator.

Constructors

RiskLoss(;    r::BaseRM_VecBaseRM = Variance(),    window::Integer = 20,    sca::Option{<:Scalariser} = nothing,    pe::AbstractPriorEstimator = EmpiricalPrior()) -> RiskLoss

Keywords correspond to the struct's fields.

Validation

  • window >= 2. A DomainError is thrown otherwise, because a prior fitted on one row has no covariance, and the loss never reads a window of one row.
  • No field of r holds a ReturnsTracking. An ArgumentError that names the field is thrown otherwise, because the loss reads rows that change at every step, and a fixed series cannot follow them. A WeightsTracking benchmark reads the rows themselves and passes.
  • If r holds a DataBenchmarkTracking: pe must not state x_src = ExcessSource(), see assert_data_benchmark_prior.

Examples

julia> RiskLoss()RiskLoss       r ┼ Variance         │    settings ┼ RiskMeasureSettings         │             │   scale ┼ Float64: 1.0         │             │      ub ┼ nothing         │             │     rke ┴ Bool: true         │       sigma ┼ nothing         │        chol ┼ nothing         │          rc ┼ nothing         │         alg ┼ SquaredSOCRiskExpr()         │    mtx_sqrt ┼ EigenFallbackSquareRoot()         │   ratio_alg ┼ SquareRootRatio()         │      corner ┴ nothing  window ┼ Int64: 20     sca ┼ nothing      pe ┼ EmpiricalPrior         │           ce ┼ PortfolioOptimisersCovariance         │              │   ce ┼ Covariance         │              │      │    me ┼ SimpleExpectedReturns         │              │      │       │   w ┴ nothing         │              │      │    ce ┼ GeneralCovariance         │              │      │       │   ce ┼ StatsBase.SimpleCovariance: StatsBase.SimpleCovariance(true)         │              │      │       │    w ┴ nothing         │              │      │   alg ┼ FullMoment()         │              │      │     w ┴ nothing         │              │   mp ┼ MatrixProcessing         │              │      │     pdm ┼ Posdef         │              │      │         │      alg ┼ UnionAll: NearestCorrelationMatrix.Newton         │              │      │         │   kwargs ┴ @NamedTuple{}: NamedTuple()         │              │      │      dn ┼ nothing         │              │      │      dt ┼ nothing         │              │      │     alg ┼ nothing         │              │      │   order ┴ NTuple{4, Symbol}: (:pdm, :dn, :dt, :alg)         │           me ┼ SimpleExpectedReturns         │              │   w ┴ nothing         │      horizon ┼ nothing         │   fill_limit ┼ nothing         │        x_src ┴ nothing

Related

source
PortfolioOptimisers.factory — Method
factory(
    obj::RiskLoss,
    w::AbstractVector{<:Union{Number, AbstractJuMPScalar}}
) -> RiskLoss

Return a RiskLoss whose measure takes the Price-Adjusted Allocation w of the step.

factory(obj.r, w) advances the measure. A WeightsTracking benchmark or a TurnoverRiskMeasure reference that is not fixed takes w, and every other measure stays as it is. A rule calls this method before it reads the gradient, so the loss reads the step's book, as the turnover and the tracking error of a ProgrammeAllocationSet do. window, sca and pe pass through unchanged.

Related

source
PortfolioOptimisers.AbstractGradientPredictor — Type
abstract type AbstractGradientPredictor <: AbstractAlgorithm

Abstract supertype for the Gradient Predictors, which give the hint of an optimistic step for the gradient of the next period.

A MirrorDescent rule with a predictor takes its second half-step along the hint $M_{t+1}$.

Interfaces

To implement a new predictor, subtype AbstractGradientPredictor and implement:

  • predictor_state_seed(pred::AbstractGradientPredictor, w::AbstractVector): Returns the state that the predictor keeps on the Rule State before the first row, nothing by default. w is the Start Allocation, whose length and element type the state takes.
  • predict_gradient!(pred::AbstractGradientPredictor, ps, obj::AbstractOnlineObjective, g::AbstractVector, v::AbstractVector, x::AbstractVector, xm::AbstractVector, rows, t::Integer) -> Tuple: Returns the state of the predictor after the period, and the hint. The arguments are the objective obj of the rule, the gradient g of the period at the played allocation, the secondary iterate v that the second half-step starts from, the price relative x of the period as traded, the same relative xm after the uniform mix of the rule, the rows that the head holds through the period, and the period count t. g reads xm, and xm is x where the rule does not mix. A predictor that reads the relative as a price folds x. A predictor that evaluates the loss of the rule again reads xm, so the hint sees the loss that g saw.
  • rows_needed(pred::AbstractGradientPredictor): The rows the predictor reads at a step, 0 by default.

A predictor whose state is not nothing, a vector or a Partial Fit State also implements:

  • predictor_state_view(ps::MyPredictorState, i) -> MyPredictorState: The state of the predictor, sliced to the assets i, as a copy.
  • copy_predictor_state(ps::MyPredictorState) -> MyPredictorState: A copy of the state of the predictor that shares no array with it.

The head's state already slices and copies a predictor state of the other three shapes.

Related

source
PortfolioOptimisers.MirrorDescent — Type
struct MirrorDescent{__T_eta, __T_proj, __T_alpha, __T_obj, __T_grad, __T_predictor} <: AbstractOnlinePortfolioSelectionAlgorithm

Takes one mirror-descent step on the period's gradient, then projects the result back onto the Allocation Set.

This is the first-order Online Selection Rule of the family. The step and the projection both use the divergence of the rule's Projection Geometry.

Each geometry gives a published rule.

  • Under EntropicProjection the step is the multiplicative update of Equation 3.3 of [249], the exponentiated gradient. Its regret is $O(\sqrt{T \log N})$ at $\eta = 2 r \sqrt{2 \log N / T}$, when every price relative is at least $r$ times the largest one of its period (Theorem 4.1 of [249]).
  • Under EuclideanProjection the step is additive, and the projection onto the simplex follows it. This is the greedy projection of Algorithm 1 of [229], with regret $O(\sqrt{T})$ at $\eta_t = 1 / \sqrt{t}$ (Theorem 1). It is also the gradient projection of Equation 5 of [262], except that Helmbold et al. [262] assume the projection and do not enforce it.
  • Under TsallisProjection and LogBarrierProjection the step is the barrier step of Section 3 of [255], of Section 3.2 of [256] and of Section 7 of [257]. On the default set each projection is a scalar root.

The Euclidean map admits every Allocation Set the head admits. The other three maps are defined on the positive orthant, so they refuse a set with a negative lower bound. The tuned rates of the theorems need the horizon, which an online rule does not know, so the library states them as formulas only. The anytime rates are InverseSquareRootRate, SelfConfidentRate and DoublingTrickRate, on eta.

alpha is the uniform mix of Theorem 4.2 of [249]. The update reads the mixed price relatives at the unmixed iterate, and the head plays the mix of the new iterate. mixed_relatives states how the mix scales to the price relatives of [249], which have a period maximum of one. The state of the rule holds the unmixed iterate, so the rule never inverts the mix. At alpha = 0 the played allocation is the iterate, and the rule is the plain step. The mix is a convex shift and not a projection, so every geometry admits it. The theorem, $O(T^{3/4})$ regret at $\alpha = (N^2 \log N / (8 T))^{1/4}$ with no lower bound on the price relatives, holds under the entropic map. The doubling trick of Corollary 4.3 of [249] sets $\alpha$ and $\eta$ per stage, and its share takes precedence over alpha. The rule plays the Start Allocation unmixed in the first period, as every rule does.

The mix lies in the Allocation Set when the uniform allocation does. Otherwise reprojection projects it onto the set again, in the rule's geometry. A bounded set that excludes the uniform allocation, a turnover ceiling and a MIP kind are such sets. On the default set the reprojection costs nothing.

A schedule can name a restart. The update of that period then returns the Start Allocation, re-entered onto the set from the book the fund holds by reprojection. The update puts the statistic of the schedule back at its seed, and the averages of the Gradient Transform restart with it. The period count stays, because the stages are cumulative.

The rule can also serve inside a mixture. As the weighting of an ExpertMixture, it moves the weight over the experts on their period returns. As an expert of a mixture under BlendPoint, the rule reads its gradient at the blend that the mixture played, and steps from its own iterate. The last slot of online_update! hands it that Gradient Point. This is the shared gradient of Algorithm 4 of [252]. The meta-algorithm of [253] also reads the gradient at the blend, as the linearised loss of its Equation 13. Each of its experts reads the gradient at its own iterate. On the head, and under OwnPoint, the point is the iterate.

obj is the loss. LogWealth is the loss of every rule above. A RiskLoss is a risk measure over the last window rows the head holds. The rule reads as many rows as its objective. Only the log-wealth gradient reads the mixed price relatives, because a risk measure reads returns and not price relatives. The mix of the played allocation applies under both.

predictor makes the step optimistic. With a Gradient Predictor, the rule is the optimistic mirror descent (OMD) of [270] and [271]. With a fixed rate and the last gradient as the hint, it is the algorithm of Chiang et al. [272]. Each period then takes two half-steps in the rule's geometry, and the second one follows the predictor's hint for the gradient of the next period. The state of the rule is then an OptimisticMirrorDescentState, which holds two iterates. The secondary iterate is where the step of the next period starts, and the played allocation is one hint step ahead of it. At predictor = nothing the rule takes the plain step, and its state is a MirrorDescentState.

The optimistic step reads two gradients a period, so it applies no Gradient Transform, grad = nothing. A transform keeps a state that one gradient writes each period. The optimistic rule needs as many rows as the larger of the objective and the predictor. A schedule on eta counts the periods of the rule and reads its state, and HintResidualRate is the schedule that reads the hint residuals there.

Mathematical definition

\[\begin{align} \tilde{\boldsymbol{x}}_t &= \left(1 - \frac{\alpha}{N}\right) \boldsymbol{x}_t + \frac{\alpha}{N} \max_i x_{t, i} \boldsymbol{1}\,, \\ \boldsymbol{w}_{t+1} &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; \eta_t \langle \hat{\boldsymbol{g}}_t, \boldsymbol{w} \rangle + D_\Psi(\boldsymbol{w}, \boldsymbol{w}_t) = \mathrm{Proj}_\Psi\left( \nabla \Psi^* \left( \nabla \Psi(\boldsymbol{w}_t) - \eta_t \hat{\boldsymbol{g}}_t \right) \right)\,, \\ \tilde{\boldsymbol{w}}_{t+1} &= (1 - \alpha) \boldsymbol{w}_{t+1} + \frac{\alpha}{N} \boldsymbol{1}\,. \end{align}\]

Where:

  • $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
  • $x_{t, i}$: Price relative of asset $i$ in period $t$.
  • $\tilde{\boldsymbol{x}}_t$: Mixed price relative vector of period $t$. The log-wealth gradient reads it in place of $\boldsymbol{x}_t$.
  • $\alpha$: Uniform-mix share, in $[0, 1)$.
  • $N$: Number of assets.
  • $\boldsymbol{1}$: Vector of ones.
  • $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
  • $\hat{\boldsymbol{g}}_t$: Transformed gradient of period $t$, the vector the mirror step reads. It is the Gradient Transform of $\boldsymbol{g}_t$, the gradient of the loss.
  • $\eta_t$: Learning rate of the update at period $t$.
  • $\mathcal{W}$: Allocation Set.
  • $\Psi$: Potential of the Projection Geometry.
  • $D_\Psi$: Bregman divergence of $\Psi$.
  • $\Psi^*$: Convex conjugate of $\Psi$.
  • $\mathrm{Proj}_\Psi$: Projection onto $\mathcal{W}$ in the divergence $D_\Psi$.
  • $\tilde{\boldsymbol{w}}_{t+1}$: Allocation the head plays in period $t + 1$.

Under the entropic map the step is $w_{t+1, i} \propto w_{t, i} \exp(-\eta_t \hat{g}_{t, i})$. Under the Euclidean map it is $\mathrm{Proj}_{\mathcal{W}}(\boldsymbol{w}_t - \eta_t \hat{\boldsymbol{g}}_t)$. At $\alpha = 0$, $\tilde{\boldsymbol{x}}_t = \boldsymbol{x}_t$ and $\tilde{\boldsymbol{w}}_{t+1} = \boldsymbol{w}_{t+1}$.

With a predictor, the rule takes two half-steps each period.

\[\begin{align} \boldsymbol{v}_{t+1} &= \underset{\boldsymbol{v} \in \mathcal{W}}{\arg\min} \; \eta_t \langle \boldsymbol{g}_t, \boldsymbol{v} \rangle + D_\Psi(\boldsymbol{v}, \boldsymbol{v}_t)\,, \\ \boldsymbol{w}_{t+1} &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; \eta_{t+1} \langle M_{t+1}, \boldsymbol{w} \rangle + D_\Psi(\boldsymbol{w}, \boldsymbol{v}_{t+1})\,. \end{align}\]

Where:

  • $\boldsymbol{v}_t$: Secondary iterate of the optimistic step at period $t$, the allocation that the first half-step of period $t$ starts from.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate. The rule takes it at $\boldsymbol{w}_t$. Under LogWealth it is $-\tilde{\boldsymbol{x}}_t / \langle \boldsymbol{w}_t, \tilde{\boldsymbol{x}}_t \rangle$.
  • $M_t$: Hint of period $t$, the forecast of the gradient $\boldsymbol{g}_t$ that the Gradient Predictor makes one period earlier.
  • $t$: Period index, counted from one.
  • $\lVert \cdot \rVert_*$: Dual norm of the norm that the potential of the Projection Geometry is strongly convex against.

Here $\boldsymbol{w}_{t+1}$ is the played allocation before the uniform mix. The rates follow equation (1) of [271], which forms $\boldsymbol{w}_{t+1}$ at $\eta_{t+1}$. A fixed rate is one rate for both half-steps. Under the zero hint the second half-step returns $\boldsymbol{v}_{t+1}$, so the rule is the plain step.

For a fixed rate $\eta$ and a comparator $\boldsymbol{w}^*$ with $D_\Psi(\boldsymbol{w}^*, \boldsymbol{v}_1) \leq R^2$, Lemma 1 of [271], with its equation (3) at $\rho = \eta$, bounds the regret by $\eta^{-1} R^2 + \tfrac{\eta}{2} \sum_t \lVert \boldsymbol{g}_t - M_t \rVert_*^2$. At the rate tuned to the residual sum, the bound is $O(\sqrt{\sum_t \lVert \boldsymbol{g}_t - M_t \rVert_*^2})$. The residual sum is the path length of the gradients under LastGradient, and the spread of the gradients about their mean bounds it under MeanGradient. Rakhlin and Sridharan [270] state that a hint that misses keeps the bound of mirror descent up to a constant, for hints no larger than the gradients in the dual norm. HintResidualRate on eta is the adaptive rate of [271].

Algorithm

online_update! runs these steps at the period's row x. The Gradient Point point is the iterate when it is nothing, the default. st is the state of the rule, the MirrorDescentState that the rule keeps from one update to the next.

  1. Set the period t = st.n + 1, and the Price-Adjusted Allocation wh of the book w after the row.
  2. When the schedule names a restart at t, re-enter the Start Allocation st.w0 onto the set from wh with reprojection. Put the statistic of the schedule and the state of the Gradient Transform back at their seeds, keep t, and return that allocation. Stop.
  3. When the schedule reads the period's row, write its statistic from w and x.
  4. Read the rate eta and the share alpha of period t. A schedule's share takes precedence over the field alpha.
  5. Mix the price relatives into xm with mixed_relatives.
  6. Resolve the loss against wh with factory, so that a benchmark or a turnover reference of a RiskLoss that is not fixed takes wh. Take the gradient g of that loss at point, from xm and the head's rows.
  7. Transform g with the Gradient Transform, which updates its state.
  8. Take the mirror step q from the iterate st.u, on eta times the transformed gradient.
  9. Project q onto the set from wh, which gives the new iterate u.
  10. When the schedule reads the past alone, write its statistic from w and x.
  11. Form the played allocation from u with played_allocation. When alpha is positive, project it with reprojection.
  12. Return the new state and the played allocation.

With a predictor, the update runs these steps instead. The Gradient Point point is the unmixed played iterate st.u when it is nothing, the default. st is then an OptimisticMirrorDescentState.

  1. Set the period t = st.n + 1, and form the Price-Adjusted Allocation wh of the book w after the row.
  2. When the schedule of eta names a restart at t, re-enter the Start Allocation st.w0 onto the set from wh with reprojection. Put both iterates at that allocation, and the states of the schedule and the predictor at their seeds, keep t, and return that allocation. Stop.
  3. When the schedule reads the period's row before the rate, write its statistic from w and x.
  4. Read the rate eta and the share alpha of period t.
  5. Mix the price relatives into xm with mixed_relatives.
  6. Resolve obj against wh with factory. Take the gradient g of that objective at point, from xm and the head's rows, with loss_gradient.
  7. Take the first half-step from the secondary iterate st.v on eta .* g with half_step, which gives the new secondary iterate v.
  8. Form the hint m and the state ps of the predictor with predict_gradient!, from the resolved objective, g, v, x and xm.
  9. Measure the residual r of g against the last hint st.m with hint_residual, and shift the residual sums into res.
  10. When the schedule reads the past alone, write its statistic s from w and x.
  11. Read the rate of period t + 1 from a state of the rule that holds the period's row. Take the second half-step from v on that rate times m, which gives the unmixed played iterate u.
  12. Form the played allocation from u with played_allocation. When alpha is positive, project it with reprojection.
  13. Return the new state and the played allocation.

Fields

  • eta: The learning rate, a number or a Learning-Rate Schedule. A larger rate reacts faster and is less stable.
  • 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.
  • alpha: The uniform-mix share, in [0, 1). At 0 the rule takes the plain step.
  • obj: The objective whose gradient the rule reads, log wealth or a Risk Loss over the head's rows.
  • grad: The Gradient Transform applied before the mirror step, or nothing to apply none.
  • predictor: The Gradient Predictor whose hint the second half-step of the optimistic step follows, or nothing for the plain step.

Constructors

MirrorDescent(;    eta::Union{Real, AbstractLearningRateSchedule} = 0.05,    proj::Union{EuclideanProjection, EntropicProjection, TsallisProjection, LogBarrierProjection} = EntropicProjection(),    alpha::Real = 0,    obj::AbstractOnlineObjective = LogWealth(),    grad::Option{<:AbstractGradientTransform} = nothing,    predictor::Option{<:AbstractGradientPredictor} = nothing) -> MirrorDescent

Keywords correspond to the struct's fields. The proj slot takes only the geometries whose projection onto the default set is a scalar root. ExponentiatedGradient fills it with the entropic map, and GradientProjection with the Euclidean map.

Validation

  • If eta is a number: eta > 0. A DomainError is thrown otherwise.
  • 0 <= alpha < 1. A DomainError is thrown otherwise.
  • If predictor is not nothing: grad is nothing. An ArgumentError is thrown otherwise.

View parameters

port_opt_view takes the view of predictor at the selected assets and carries the rest unchanged.

Examples

julia> MirrorDescent()MirrorDescent        eta ┼ Float64: 0.05       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ nothing  predictor ┴ nothing

Related

References

  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Section 3, Equation 3.3. Section 4, Theorems 4.1 and 4.2, Corollary 4.3.
  • [262] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. A comparison of new and old algorithms for a mixture estimation problem. Machine Learning 27(1), 97–119 (1997). Section 3, Equation 5.
  • [229] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, 928–936 (2003). Algorithm 1, Theorem 1.
  • [255] J. D. Abernethy, C. Lee and A. Tewari. Fighting bandits with a new kind of smoothness. In: Advances in Neural Information Processing Systems 28 (2015). Section 3.
  • [256] J. Zimmert and Y. Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research 22(28), 1–49 (2021). Section 3.2.
  • [257] L. Orseau, T. Lattimore and S. Legg. Soft-Bayes: Prod for mixtures of experts with log-loss. In: Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76, 372–399 (2017). Section 7.
  • [252] 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). Section 3.4, Equation 12, Algorithms 3 and 4.
  • [253] 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). Section 2.3, Equation 13.
  • [270] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In: Proceedings of the 26th Annual Conference on Learning Theory, 993–1019 (2013). Section 2.2, Lemma 3.
  • [271] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In: Advances in Neural Information Processing Systems 26, 3066–3074 (2013). Section 2, Equation 1, Lemma 1 and Corollary 2.
  • [272] C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin and S. Zhu. Online optimization with gradual variations. In: Proceedings of the 25th Annual Conference on Learning Theory, 6.1–6.20 (2012). Algorithm 1 in Section 3.
source
PortfolioOptimisers.GradientAverageState — Type
struct GradientAverageState{__T_k, __T_v, __T_m}

Holds the moving averages of a momentum Gradient Transform, and the count of the steps since their seed.

GradientMomentum keeps the gradient average v alone, RootMeanSquareGradient keeps the squared-gradient average m alone, and AdaptiveMomentGradient keeps both. The transform writes each average in place, and returns a new state with the next count. A restart of the Learning-Rate Schedule seeds the state again, so the count restarts with the averages. The period count of the Rule State does not restart, so it cannot give the count. The debias field of the transform reads the count, and under debias = nothing no step reads it.

Fields

  • k: The count of the steps since the seed, zero at the seed.
  • v: The gradient average, or nothing for a transform that keeps none.
  • m: The squared-gradient average, or nothing for a transform that keeps none.

Related

source
PortfolioOptimisers.gradient_state_seed — Function
gradient_state_seed(grad::Option{<:AbstractGradientTransform}, w::AbstractVector)
gradient_state_seed(grad::GradientMomentum, w::AbstractVector)
gradient_state_seed(grad::RootMeanSquareGradient, w::AbstractVector)
gradient_state_seed(grad::AdaptiveMomentGradient, w::AbstractVector)

Seeds the state that a Gradient Transform keeps on the Rule State before the first row.

The seed is nothing for no transform, grad = nothing, and for a transform that has no method of its own. For each momentum transform it is a GradientAverageState at the count zero, with a zero vector for each average that the transform keeps.

Related

source
PortfolioOptimisers.transform_gradient! — Function
transform_gradient!(::Nothing, ::Nothing, g::AbstractVector)
transform_gradient!(grad::GradientMomentum, gs::GradientAverageState, g::AbstractVector)
transform_gradient!(grad::RootMeanSquareGradient, gs::GradientAverageState, g::AbstractVector)
transform_gradient!(grad::AdaptiveMomentGradient, gs::GradientAverageState, g::AbstractVector)

Returns the state of the transform after the period, and the transformed gradient of the period.

grad = nothing applies no transform, and returns nothing and g itself. Each momentum transform writes its averages in place, and returns a GradientAverageState with the next count. It multiplies each average by the mean that zero_start_mean reads out of a unit state under its debias field. The count is shared by all assets, so this is one scalar per average, and it is exactly one under nothing. GradientMomentum returns that gradient average as a new vector. RootMeanSquareGradient returns g over the root of that squared average, plus eps. AdaptiveMomentGradient returns that gradient average over the same root plus eps. The type docstrings state the formulas.

Related

source
PortfolioOptimisers.loss_gradient — Function
loss_gradient(obj::LogWealth, u::AbstractVector, x::AbstractVector, rows)
loss_gradient(obj::RiskLoss, u::AbstractVector, x::AbstractVector, rows)

Computes the gradient of the period's loss at the iterate u.

For LogWealth the gradient reads the price relative x alone. For a RiskLoss it reads rows, the rows that the head holds as a ReturnsResult. The type docstrings state the two losses and their gradients.

Algorithm

The LogWealth method returns -x ./ dot(u, x). The RiskLoss method runs these steps.

  1. When rows is nothing, or holds fewer than two rows, return the zero vector.
  2. View the last min(window, n) of the n rows of rows. The head can hold more rows than the loss reads, because another part of the head can need more.
  3. Fit the prior pr of the loss on that view, as a batch prior is fitted, on its returns and its Asset Panel. The prior reads its own source, so under x_src = ExcessSource() it reads X - B. The prior answers NaN at an asset outside its Coverage Universe.
  4. Read the Investable Mask of pr.
  5. Compute the gradient of the measure on that mask with investable_risk_gradient, against the rows of the view. It is zero at every other leg.

Related

source
PortfolioOptimisers.ExponentiatedGradient — Function
ExponentiatedGradient(; eta::Union{Real, AbstractLearningRateSchedule} = 0.05, alpha::Real = 0, obj::AbstractOnlineObjective = LogWealth(), grad::Option{<:AbstractGradientTransform} = nothing, predictor::Option{<:AbstractGradientPredictor} = nothing)

Builds the exponentiated gradient, a MirrorDescent rule under EntropicProjection (EG). It is the rule of Equation 3.3 of [249]. Helmbold et al. [262] derive the same update for mixture estimation, as Equation 6 of that work.

The rule moves weight towards the assets that just did well. Its regret is $O(\sqrt{T \log N})$ at a rate tuned to the horizon (Theorem 4.1 of [249]), and under the uniform mix alpha with the doubling trick it is universal (Corollary 4.3). The default rate is the rate $0.05$ of [249]. In Section 5.2 of [249], rates from $0.01$ to $0.15$ all do well, and a rate above one loses money on the two-stock example. As the weighting of an ExpertMixture, the rule takes the online gradient step over the vector of expert returns.

With a predictor, the rule takes the optimistic step of MirrorDescent. Under LastGradient it is the entropic form of the algorithm of Chiang et al. [272].

Mathematical definition

Under LogWealth, at alpha = 0 and with no Gradient Transform,

\[\begin{align} w_{t+1, i} &= \frac{w_{t, i} \exp(\eta_t x_{t, i} / \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle)}{\sum_j w_{t, j} \exp(\eta_t x_{t, j} / \langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle)}\,. \end{align}\]

Where:

  • $w_{t, i}$: Weight of asset $i$ in the iterate of period $t$.
  • $x_{t, i}$: Price relative of asset $i$ in 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.
  • $\eta_t$: Learning rate of the update at period $t$.

The normalisation is the entropic projection onto the simplex.

Examples

julia> ExponentiatedGradient()MirrorDescent        eta ┼ Float64: 0.05       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ nothing  predictor ┴ nothing

Related

References

  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Section 3, Equation 3.3. Section 4, Theorem 4.1, Corollary 4.3. Section 5.2.
  • [262] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. A comparison of new and old algorithms for a mixture estimation problem. Machine Learning 27(1), 97–119 (1997). Section 3, Equation 6.
  • [272] C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin and S. Zhu. Online optimization with gradual variations. In: Proceedings of the 25th Annual Conference on Learning Theory, 6.1–6.20 (2012). Algorithm 1 in Section 3, Section 4.2.
source
PortfolioOptimisers.GradientProjection — Function
GradientProjection(; eta::Union{Real, AbstractLearningRateSchedule} = 0.05, alpha::Real = 0, obj::AbstractOnlineObjective = LogWealth(), grad::Option{<:AbstractGradientTransform} = nothing, predictor::Option{<:AbstractGradientPredictor} = nothing)

Builds the gradient projection, a MirrorDescent rule under EuclideanProjection (GP, OGD). It is the rule of Equation 5 of [262].

On the simplex this is the greedy projection of Algorithm 1 of [229]. Helmbold et al. [262] subtract the mean of the gradient to keep the budget, and assume that the weights stay non-negative (Section 4.2). The projection keeps the budget and enforces the sign. The regret is $O(\sqrt{T})$ at $\eta_t = 1 / \sqrt{t}$ (Theorem 1 of [229]), and InverseSquareRootRate is the anytime rate. Neither [262] nor [229] states a rate for the portfolio problem, so the default is the rate of ExponentiatedGradient.

With a predictor, the rule takes the optimistic step of MirrorDescent. Under LastGradient it is the Euclidean form of the algorithm of Chiang et al. [272].

Mathematical definition

Under LogWealth, at alpha = 0 and with no Gradient Transform,

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

Where:

  • $\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.
  • $\eta_t$: Learning rate of the update at period $t$.
  • $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.

On the simplex, the projection sets to zero every entry that the step leaves below the projection's threshold.

Examples

julia> GradientProjection()MirrorDescent        eta ┼ Float64: 0.05       proj ┼ EuclideanProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ nothing  predictor ┴ nothing

Related

References

  • [262] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. A comparison of new and old algorithms for a mixture estimation problem. Machine Learning 27(1), 97–119 (1997). Section 3, Equation 5. Section 4.2, Theorem 3.
  • [229] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, 928–936 (2003). Algorithm 1, Theorem 1.
  • [272] C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin and S. Zhu. Online optimization with gradual variations. In: Proceedings of the 25th Annual Conference on Learning Theory, 6.1–6.20 (2012). Algorithm 1 in Section 3, Section 4.1.
source
PortfolioOptimisers.EGE — Function
EGE(; eta::Union{Real, AbstractLearningRateSchedule} = 0.05, gamma1::Real = 0.99, debias::Option{<:AbstractZeroStartDebias} = nothing, alpha::Real = 0)

Builds the exponentiated gradient with the momentum of an exponential moving average, ExponentiatedGradient under GradientMomentum (EGE).

This is the EGE of Equation 7 of [77]. Section 5.5.1 of [77] takes the rate $2 r \sqrt{2 \log N / T}$ of Theorem 4.1 of [249], with the doubling trick when the horizon is unknown. DoublingTrickRate on eta gives that trick. The default rate is the rate of ExponentiatedGradient.

Examples

julia> EGE()MirrorDescent        eta ┼ Float64: 0.05       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ GradientMomentum            │   gamma1 ┼ Float64: 0.99            │   debias ┴ nothing  predictor ┴ nothing

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.1, Equation 7. Section 5.5.1.
  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Section 4, Theorem 4.1.
source
PortfolioOptimisers.EGR — Function
EGR(; eta::Union{Real, AbstractLearningRateSchedule} = 0.05, gamma2::Real = 0, eps::Real = 1e-8, debias::Option{<:AbstractZeroStartDebias} = nothing, alpha::Real = 0)

Builds the exponentiated gradient with a root-mean-square scale on the gradient, ExponentiatedGradient under RootMeanSquareGradient (EGR).

This is the EGR of Equation 8 of [77]. At the default gamma2 = 0, which Section 5.5.1 of [77] recommends, the rule stays at its Start Allocation, up to eps. The transformed gradient is then the sign of the gradient, the same at every asset, so the update moves nothing, and the rule is the constant rebalanced portfolio at its Start Allocation. RootMeanSquareGradient states why.

Examples

julia> EGR()MirrorDescent        eta ┼ Float64: 0.05       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ RootMeanSquareGradient            │   gamma2 ┼ Int64: 0            │      eps ┼ Float64: 1.0e-8            │   debias ┴ nothing  predictor ┴ nothing

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.2, Equation 8. Section 5.5.1.
source
PortfolioOptimisers.EGA — Function
EGA(; eta::Union{Real, AbstractLearningRateSchedule} = 0.05, gamma1::Real = 0.99, gamma2::Real = 0, eps::Real = 1e-8, debias::Option{<:AbstractZeroStartDebias} = nothing, alpha::Real = 0)

Builds the exponentiated gradient with an adaptive-moment scale on the gradient, ExponentiatedGradient under AdaptiveMomentGradient (EGA).

This is the EGA of Equation 9 of [77]. EGA(; gamma1 = 0.9, gamma2 = 0.999, debias = ZeroStartDebias()) is the exponentiated gradient under the bias-corrected averages of Algorithm 1 of [78], as AdaptiveMomentGradient states.

Examples

julia> EGA()MirrorDescent        eta ┼ Float64: 0.05       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ AdaptiveMomentGradient            │   gamma1 ┼ Float64: 0.99            │   gamma2 ┼ Int64: 0            │      eps ┼ Float64: 1.0e-8            │   debias ┴ nothing  predictor ┴ nothing

Related

References

  • [77] Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022). Section 4.2.3, Equation 9. Section 5.5.1.
source
PortfolioOptimisers.MAEG — Function
MAEG(; etas::AbstractVector{<:Real} = 0.001:0.001:0.2, window::Integer = 30, alpha::Real = 0)

Builds the moving-window adaptive exponential gradient, ExponentiatedGradient under a WindowedBestRate over window periods (MAEG).

This is the MAEG of Algorithm 2 of [268]. The defaults come from Section 5.2 of [268]. They are the rate set of Helmbold et al. [249] and the window 30, which that section chooses over 7.

Examples

julia> MAEG(; etas = [0.05, 0.1], window = 5)MirrorDescent        eta ┼ WindowedBestRate            │     etas ┼ Vector{Float64}: [0.05, 0.1]            │   window ┴ Int64: 5       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ nothing  predictor ┴ nothing

Related

References

  • [268] Y. Zhang, H. Lin, L. Zheng and X. Yang. Adaptive online portfolio strategy based on exponential gradient updates. Journal of Combinatorial Optimization 43(3), 672–696 (2022). Section 4, Equations 7 to 10, Algorithm 2. Section 5.2.
  • [249] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998). Section 5.2, Table 5.3.
source
PortfolioOptimisers.AEG — Function
AEG(; etas::AbstractVector{<:Real} = 0.001:0.001:0.2, alpha::Real = 0)

Builds the adaptive exponential gradient, ExponentiatedGradient under a WindowedBestRate over the whole history (AEG).

This is the AEG of Equation 11 of [268], the special case of MAEG whose window is the horizon.

Examples

julia> AEG(; etas = [0.05, 0.1])MirrorDescent        eta ┼ WindowedBestRate            │     etas ┼ Vector{Float64}: [0.05, 0.1]            │   window ┴ nothing       proj ┼ EntropicProjection()      alpha ┼ Int64: 0        obj ┼ LogWealth()       grad ┼ nothing  predictor ┴ nothing

Related

References

  • [268] Y. Zhang, H. Lin, L. Zheng and X. Yang. Adaptive online portfolio strategy based on exponential gradient updates. Journal of Combinatorial Optimization 43(3), 672–696 (2022). Section 4, Equation 11.
source

References

[77]
Y. Li, X. Zheng, C. Chen, J. Wang and S. Xu. Exponential gradient with momentum for online portfolio selection. Expert Systems with Applications 187, 115889 (2022).
[78]
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In: 3rd International Conference on Learning Representations (2015), arXiv:1412.6980.
[229]
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning (2003); pp. 928–936.
[249]
D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998).
[252]
L. Zhang, S. Lu and Z.-H. Zhou. Adaptive online learning in dynamic environments. In: Advances in Neural Information Processing Systems 31 (2018); pp. 1323–1333.
[253]
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 (2020); pp. 12510–12520.
[255]
J. D. Abernethy, C. Lee and A. Tewari. Fighting bandits with a new kind of smoothness. In: Advances in Neural Information Processing Systems, Vol. 28 (2015).
[256]
J. Zimmert and Y. Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research 22, 1–49 (2021).
[257]
L. Orseau, T. Lattimore and S. Legg. Soft-Bayes: Prod for mixtures of experts with log-loss. In: Proceedings of the 28th International Conference on Algorithmic Learning Theory, Vol. 76 of Proceedings of Machine Learning Research (2017); pp. 372–399.
[262]
D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. A comparison of new and old algorithms for a mixture estimation problem. Machine Learning 27, 97–119 (1997).
[268]
Y. Zhang, H. Lin, L. Zheng and X. Yang. Adaptive online portfolio strategy based on exponential gradient updates. Journal of Combinatorial Optimization 43, 672–696 (2022).
[269]
N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire and M. K. Warmuth. How to use expert advice. Journal of the ACM 44, 427–485 (1997).
[270]
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In: Proceedings of the 26th Annual Conference on Learning Theory (2013); pp. 993–1019.
[271]
A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In: Advances in Neural Information Processing Systems 26 (2013); pp. 3066–3074.
[272]
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin and S. Zhu. Online optimization with gradual variations. In: Proceedings of the 25th Annual Conference on Learning Theory (2012); p. 6.1–6.20.