Adaptive optimistic

This page has the first-order rule AdaptiveSubgradient and the gradient predictors of optimistic mirror descent. AdaptiveSubgradient is the diagonal adaptive subgradient method. The step size of each asset follows the gradients that asset has had so far, and the projection uses a norm weighted by those gradients. A MirrorDescent rule with a gradient predictor is optimistic mirror descent. It takes two half-steps each period, the second along a guess of the next gradient. The predictor makes the guess: LastGradient, MeanGradient or ForecastGradient. HintResidualRate is the adaptive step size that reads how far the guesses were from the real gradients.

PortfolioOptimisers.AdaptiveSubgradient — Type
struct AdaptiveSubgradient{__T_eta, __T_delta, __T_obj} <: AbstractOnlinePortfolioSelectionAlgorithm

Steps each asset at its own rate, set by the gradient mass that the asset has accrued (AdaGrad).

This is the diagonal adaptive subgradient method of Algorithm 1 of [284], with its composite mirror descent update. The rule projects in the norm of its gradient mass, through a DiagonalProjection that it builds at every step, so it holds no proj slot.

At delta = 0 an asset with no gradient so far has no gradient mass, and the diagonal of the norm has a zero entry there. This happens to an asset whose every price relative so far is zero, and under a RiskLoss to an asset that the window does not price. Duchi et al. [284] take the pseudo-inverse of $H_t$ in the raw step there, and so does the rule. The gradient of such an asset is zero, so its raw step is its weight. The projection in the seminorm of $H_t$ fixes the weights of the other assets, and DiagonalProjection gives the asset its limit as $\delta \to 0^{+}$. So the rule at delta = 0 is the limit of the rule at a positive delta, and its answer is a minimiser of the projection of Duchi et al. [284], on which the bound below holds.

Mathematical definition

\[\begin{align} s_{t, i} &= \sqrt{\textstyle\sum_{s \leq t} g_{s, i}^2}\,, \\ H_t &= \delta I + \mathrm{diag}(\boldsymbol{s}_t)\,, \\ \boldsymbol{w}_{t+1} &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; \eta \langle \boldsymbol{g}_t, \boldsymbol{w} \rangle + \tfrac{1}{2} \lVert \boldsymbol{w} - \boldsymbol{w}_t \rVert^2_{H_t} = \mathrm{Proj}^{H_t}_{\mathcal{W}} \left( \boldsymbol{w}_t - \eta H_t^{\dagger} \boldsymbol{g}_t \right)\,. \end{align}\]

Where:

  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate. Under LogWealth it is $-\boldsymbol{x}_t / \langle \boldsymbol{w}_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.
  • $t$: Period index, counted from one.
  • $\boldsymbol{s}_t$: Gradient mass after period $t$, with one entry for each asset.
  • $\delta$: Offset that the rule adds to the gradient mass of every asset.
  • $H_t$: Diagonal matrix of the norm of the step at period $t$.
  • $H_t^{\dagger}$: Pseudo-inverse of $H_t$, the diagonal matrix with $1 / H_{t, ii}$ at a positive entry and zero at a zero entry.
  • $\eta$: Fixed learning rate of the rule.
  • $\mathcal{W}$: Allocation Set.
  • $\lVert \boldsymbol{z} \rVert^2_{H} = \boldsymbol{z}^\intercal H \boldsymbol{z}$: Squared norm, or seminorm, of a vector $\boldsymbol{z}$ in a non-negative diagonal matrix $H$.
  • $\mathrm{Proj}^{H}_{\mathcal{W}}$: Projection onto $\mathcal{W}$ in the norm of $H$, which is DiagonalProjection with the diagonal of $H$. At a zero entry of $H$ it is the limit that DiagonalProjection states.

Under log wealth the raw step is $\boldsymbol{w}_t + \eta \boldsymbol{x}_t / (\langle \boldsymbol{w}_t, \boldsymbol{x}_t \rangle (\delta + \boldsymbol{s}_t))$, with the division taken asset by asset. At $\delta = 0$ the first raw step is $\boldsymbol{w}_1 + \eta \boldsymbol{1}$, a uniform shift, because $s_{1, i} = \lvert g_{1, i} \rvert$. The projection in the norm of $H_1$ then takes more of the shift back from the assets with the smaller gradient, so the first step moves weight toward the assets that rose the most. It leaves the allocation unchanged only when every price relative is equal.

Let $D_\infty = \sup_{\boldsymbol{w} \in \mathcal{W}} \lVert \boldsymbol{w} - \boldsymbol{w}^* \rVert_\infty$ for a fixed comparator $\boldsymbol{w}^*$. At $\delta = 0$ and $\eta = D_\infty / \sqrt{2}$, Corollary 6 of [284] bounds the regret against $\boldsymbol{w}^*$ by $\sqrt{2} D_\infty \sum_i \lVert \boldsymbol{g}_{1:T, i} \rVert_2$, with $\boldsymbol{g}_{1:T, i}$ the gradients of asset $i$ over $T$ periods. On the simplex $D_\infty \leq 1$, and the default $\eta = 1 / \sqrt{2}$ is that rate. The bound is small when a few assets carry most of the gradient mass. Duchi et al. [284] show that the bound is below the bound of online gradient descent on a box. On the simplex, with dense gradients, it can be larger by a factor of up to $\sqrt{N / 2}$, and log-wealth gradients are dense.

The full-matrix variant, Algorithm 2 of [284], uses $H_t = \delta I + (\sum_{s \leq t} \boldsymbol{g}_s \boldsymbol{g}_s^\intercal)^{1/2}$, the root of the sum that NewtonStep accrues. This rule keeps the diagonal alone, and the diagonal keeps the step at $O(N)$.

Algorithm

online_update! runs these steps at the period's row x. The Gradient Point point is the book w when it is nothing, the default.

  1. Form the Price-Adjusted Allocation wh of the book w after the row.
  2. Resolve obj 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 objective at point, from x and the head's rows, with loss_gradient.
  3. Add g to the gradient mass st.s in place, as the root of the sum of squares of each asset.
  4. Form the diagonal h = delta .+ st.s.
  5. Form the raw step q = w .- eta .* g ./ h, with the pseudo-inverse at a zero entry of h: there g is zero, and the entry of q is the entry of w.
  6. Project q onto the set from wh in the geometry DiagonalProjection(h), which gives the new allocation.
  7. Return the state, with the period count raised by one, and the new allocation.

A RiskLoss gives a zero gradient while the head holds fewer than two rows. At delta = 0 the first such step has h = 0. On a set with no Objective Penalty it is then the Euclidean projection of w, the zero step of every first-order rule.

Fields

  • eta: The learning rate of the step. A larger rate reacts faster and is less stable.
  • delta: The offset $\delta$ that the rule adds to the gradient mass of every asset. It is $\delta$ in [284].
  • obj: The objective whose gradient the rule takes, log wealth or a Risk Loss over the head's rows.

Constructors

AdaptiveSubgradient(;    eta::Real = 1 / sqrt(2),    delta::Real = 0,    obj::AbstractOnlineObjective = LogWealth()) -> AdaptiveSubgradient

Keywords correspond to the struct's fields. Duchi et al. [284] fix no default. eta = 1 / sqrt(2) is the rate of Corollary 6 of [284] on the simplex. Duchi et al. [284] state that delta = 0 works in practice. obj is the slot of MirrorDescent. It takes log wealth, or a RiskLoss over the head's rows, whose gradient loss_gradient gives at the Gradient Point. The rule needs as many rows as its objective.

Validation

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

Examples

julia> AdaptiveSubgradient()AdaptiveSubgradient    eta ┼ Float64: 0.7071067811865475  delta ┼ Int64: 0    obj ┴ LogWealth()

Related

References

  • [284] J. Duchi, E. Hazan and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research 12, 2121–2159 (2011). Section 3, Algorithm 1, Equation 4, Theorem 5 and Corollary 6.
source
PortfolioOptimisers.LastGradient — Type
struct LastGradient <: AbstractGradientPredictor

Takes the last gradient as the hint of the optimistic step.

Under it the optimistic step of a MirrorDescent rule is the two-projection algorithm of Chiang et al. [272], and the residual sum $\sum_t \lVert \boldsymbol{g}_t - \boldsymbol{g}_{t-1} \rVert_*^2$ is the path length of the gradients.

With at_played = false the predictor reads the loss of the period again at the new secondary iterate, through loss_gradient. This is the online form of the Mirror-Prox method of Nemirovski [285]. Rakhlin and Sridharan [271] recover Mirror Prox from the optimistic step with the hint at the secondary point, for one fixed objective, so the two agree when every period has the same loss. The secondary iterate $\boldsymbol{v}_{t+1}$ is not the played allocation $\boldsymbol{w}_t$, so the two hints of this type differ in general from the first period on.

Mathematical definition

\[\begin{align} M_{t+1} &= \boldsymbol{g}_t\,, \\ M_{t+1}^{\mathrm{MP}} &= -\boldsymbol{x}_t / \langle \boldsymbol{v}_{t+1}, \boldsymbol{x}_t \rangle\,. \end{align}\]

Where:

  • $M_t$: Hint of period $t$, the forecast of the gradient $\boldsymbol{g}_t$ that the Gradient Predictor makes one period earlier. $M_{t+1}$ is the hint at at_played = true.
  • $M_{t+1}^{\mathrm{MP}}$: Hint at at_played = false under LogWealth.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate. The optimistic step takes it at the played allocation $\boldsymbol{w}_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. Where the rule mixes, it is the mixed price relative that $\boldsymbol{g}_t$ reads.
  • $\boldsymbol{v}_t$: Secondary iterate of the optimistic step at period $t$, the allocation that the first half-step of period $t$ starts from.
  • $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.

Fields

  • at_played: Whether the hint is the gradient at the played allocation. When it is false, the hint is the gradient of the loss of the period at the new secondary iterate.

Constructors

LastGradient(; at_played::Bool = true) -> LastGradient

Keywords correspond to the struct's fields.

Examples

julia> LastGradient()LastGradient  at_played ┴ Bool: true

Related

References

  • [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, with Section 4.1 for the Euclidean geometry and Section 4.2 for the entropic one.
  • [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.
  • [285] A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization 15, 229–251 (2004). Section 3, Equations 3.2 and 3.3.
source
PortfolioOptimisers.MeanGradient — Type
struct MeanGradient <: AbstractGradientPredictor

Takes the running mean of the past gradients as the hint of the optimistic step.

Rakhlin and Sridharan [270] call the regret bound under this hint a variance bound. The state of the predictor holds the mean, and the predictor updates it in one pass.

Mathematical definition

\[\begin{align} M_{t+1} &= \frac{1}{t} \sum_{s \leq t} \boldsymbol{g}_s\,. \end{align}\]

Where:

  • $M_t$: Hint of period $t$, the forecast of the gradient $\boldsymbol{g}_t$ that the Gradient Predictor makes one period earlier.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate.
  • $t$: Period index, counted from one.

With $M_1 = \boldsymbol{0}$, the residual sum is at most the squared first gradient plus twice the spread of the gradients about their mean, $\sum_{t \leq T} \lVert \boldsymbol{g}_t - M_t \rVert_2^2 \leq \lVert \boldsymbol{g}_1 \rVert_2^2 + 2 \sum_{t \leq T} \lVert \boldsymbol{g}_t - \bar{\boldsymbol{g}}_T \rVert_2^2$, with $\bar{\boldsymbol{g}}_T$ the mean of the first $T$ gradients. The maximum norm is at most the Euclidean norm, so the bound holds for the residuals in the maximum norm too.

Examples

julia> MeanGradient()MeanGradient()

Related

References

  • [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 1 after Equation 2, Section 2.2 and Section 5.2.
source
PortfolioOptimisers.ForecastGradient — Type
struct ForecastGradient{__T_me} <: AbstractGradientPredictor

Forms the hint of the optimistic step from a Price Relative Forecast.

The hint is the gradient that the log-wealth loss of the next period would have at the secondary iterate, if the forecast were the outcome. The forecaster is any expected-returns estimator. The state of the predictor folds the forecaster where it has an exact fold, and the predictor fits it again from the head's rows otherwise, as the me slot of ForecastReversion does. A flat forecast gives a hint with equal entries, and the projection onto the budget undoes the uniform shift of such a hint.

The optimistic step of [272] takes the last gradient as its hint. Rakhlin and Sridharan [270] and Rakhlin and Sridharan [271] allow any hint that the learner computes from the past or from side information, so the forecast is a hint of their framework. Neither work proposes it, and it is an addition of the library. It is the natural hint of the portfolio problem, where every reversion rule and every tracking rule already holds a forecast.

Mathematical definition

\[\begin{align} M_{t+1} &= -\hat{\boldsymbol{x}}_{t+1} / \langle \boldsymbol{v}_{t+1}, \hat{\boldsymbol{x}}_{t+1} \rangle\,. \end{align}\]

Where:

  • $M_t$: Hint of period $t$, the forecast of the gradient $\boldsymbol{g}_t$ that the Gradient Predictor makes one period earlier.
  • $\hat{\boldsymbol{x}}_{t+1}$: Price Relative Forecast for period $t + 1$, made after the row of period $t$.
  • $\boldsymbol{v}_t$: Secondary iterate of the optimistic step at period $t$, the allocation that the first half-step of period $t$ starts from.
  • $t$: Period index, counted from one.

Fields

  • me: The forecaster whose Price Relative Forecast gives the hint.

Constructors

ForecastGradient(; me::AbstractExpectedReturnsEstimator) -> ForecastGradient

Keywords correspond to the struct's fields. The predictor needs as many rows as me, and the rule needs as many rows as the larger of the predictor and its objective.

Validation

  • me is not an Online wrapper, and holds none. An ArgumentError is thrown otherwise.

Examples

julia> ForecastGradient(; me = PriceLevelExpectedReturns(; alg = MovingAverage(; window = 3)))ForecastGradient  me ┼ PriceLevelExpectedReturns     │   alg ┼ MovingAverage     │       │   window ┴ Int64: 3

Related

References

  • [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.
  • [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 1, Equation 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.
source
PortfolioOptimisers.predictor_state_seed — Function
predictor_state_seed(pred::AbstractGradientPredictor, w::AbstractVector)
predictor_state_seed(pred::MeanGradient, w::AbstractVector)
predictor_state_seed(pred::ForecastGradient, w::AbstractVector)

Returns the state that a Gradient Predictor keeps on the Rule State before the first row. It is nothing by default, the zero mean under MeanGradient, and the state of the forecaster from forecaster_seed under ForecastGradient.

Related

source
PortfolioOptimisers.predict_gradient! — Function
predict_gradient!(pred::LastGradient, ps::Nothing, obj::AbstractOnlineObjective, g::AbstractVector, v::AbstractVector, x::AbstractVector, xm::AbstractVector, rows, t::Integer)
predict_gradient!(pred::MeanGradient, m::AbstractVector, obj::AbstractOnlineObjective, g::AbstractVector, v::AbstractVector, x::AbstractVector, xm::AbstractVector, rows, t::Integer)
predict_gradient!(pred::ForecastGradient, ps, obj::AbstractOnlineObjective, g::AbstractVector, v::AbstractVector, x::AbstractVector, xm::AbstractVector, rows, t::Integer)

Returns the state of the predictor after the period and the hint of the period, and writes that state in place.

  • Under LastGradient the hint is a copy of g. At at_played = false it is the gradient of obj at the secondary iterate v, on the mixed relative xm that g reads.
  • Under MeanGradient the method updates the running mean m, and the hint is a copy of it.
  • Under ForecastGradient the method folds or fits the forecaster on the traded relative x through forecast_relative, and the hint is the log-wealth gradient of the forecast at v. It reads no objective, because a forecast is a price relative.

A forecaster folds the path that traded, not the mixed one, so the mix does not pull its statistic toward one. The rule applies no mix to the forecast.

Returns

  • (ps', M)::Tuple: The state of the predictor after the period, and the hint, a new vector.

Related

source
PortfolioOptimisers.HintResidualRate — Type
struct HintResidualRate{__T_rmax} <: AbstractLearningRateSchedule

Sets the learning rate of an optimistic step from the hint residuals that the step has accrued.

This is the adaptive rate of Corollary 2 of [271]. It needs no horizon and no bound on the residual sum ahead of time. The schedule reads the residuals that a MirrorDescent rule with a predictor keeps on its state, and it refuses the state of any other rule by name. hint_residual states the norm of the residuals in each geometry.

Mathematical definition

\[\begin{align} S_t &= \sum_{i \leq t} \lVert \boldsymbol{g}_i - M_i \rVert_*^2\,, \\ \eta_t &= R_{\max} \min \left\lbrace \left( \sqrt{S_{t-1}} + \sqrt{S_{t-2}} \right)^{-1},\, 1 \right\rbrace\,. \end{align}\]

Where:

  • $\eta_t$: Learning rate of the update at period $t$.
  • $t$: Period index, counted from one.
  • $S_t$: Sum of the squared hint residuals through period $t$, zero for $t \leq 0$.
  • $\boldsymbol{g}_t$: Gradient of the loss of period $t$, taken at the iterate.
  • $M_t$: Hint of period $t$, the forecast of the gradient $\boldsymbol{g}_t$ that the Gradient Predictor makes one period earlier.
  • $\lVert \cdot \rVert_*$: Dual norm of the norm that the potential of the Projection Geometry is strongly convex against.
  • $R_{\max}$: Scale and cap of the rate. Rakhlin and Sridharan [271] set $R_{\max}^2 = \sup_{\boldsymbol{w}, \boldsymbol{w}' \in \mathcal{W}} D_\Psi(\boldsymbol{w}, \boldsymbol{w}')$.
  • $\mathcal{W}$: Allocation Set.
  • $D_\Psi$: Bregman divergence of $\Psi$.

The rate is the cap $R_{\max}$ while $S_{t-1} = 0$. With $R_{\max}$ at that supremum, Rakhlin and Sridharan [271] bound the regret over $T$ periods by $3.5 R_{\max} (\sqrt{S_T} + 1)$. Under the Euclidean geometry on the simplex the supremum is one, the default rmax. Under the entropic geometry the supremum is infinite, and the uniform mix alpha of the rule does not bound it, because the mix applies to the played allocation and not to the secondary iterate. There rmax is a tuning constant, and the bound does not hold.

Fields

  • rmax: The cap $R_{\max}$, which scales the rate and caps it. It is $R_{\max}$ in [271].

Constructors

HintResidualRate(; rmax::Real = 1) -> HintResidualRate

Keywords correspond to the struct's fields.

Validation

  • rmax > 0. A DomainError is thrown otherwise.

Examples

julia> HintResidualRate()HintResidualRate  rmax ┴ Int64: 1

Related

References

  • [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, Corollary 2.
source

References

[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.
[284]
J. Duchi, E. Hazan and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research 12, 2121–2159 (2011).
[285]
A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization 15, 229–251 (2004).