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} <: AbstractOnlinePortfolioSelectionAlgorithmSteps 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
LogWealthit 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
DiagonalProjectionwith the diagonal of $H$. At a zero entry of $H$ it is the limit thatDiagonalProjectionstates.
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.
- Form the Price-Adjusted Allocation
whof the bookwafter the row. - Resolve
objagainstwhwithfactory, so that a benchmark or a turnover reference of aRiskLossthat is not fixed takeswh. Take the gradientgof that objective atpoint, fromxand the head'srows, withloss_gradient. - Add
gto the gradient massst.sin place, as the root of the sum of squares of each asset. - Form the diagonal
h = delta .+ st.s. - Form the raw step
q = w .- eta .* g ./ h, with the pseudo-inverse at a zero entry ofh: theregis zero, and the entry ofqis the entry ofw. - Project
qonto the set fromwhin the geometryDiagonalProjection(h), which gives the new allocation. - 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()) -> AdaptiveSubgradientKeywords 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. ADomainErroris thrown otherwise.
Examples
julia> AdaptiveSubgradient()AdaptiveSubgradient eta ┼ Float64: 0.7071067811865475 delta ┼ Int64: 0 obj ┴ LogWealth()Related
AbstractOnlinePortfolioSelectionAlgorithmOnlinePortfolioSelectionAdaptiveSubgradientStateDiagonalProjectionMirrorDescentNewtonStep
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.
PortfolioOptimisers.LastGradient — Type
struct LastGradient <: AbstractGradientPredictorTakes 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 = falseunderLogWealth. - $\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 isfalse, the hint is the gradient of the loss of the period at the new secondary iterate.
Constructors
LastGradient(; at_played::Bool = true) -> LastGradientKeywords correspond to the struct's fields.
Examples
julia> LastGradient()LastGradient at_played ┴ Bool: trueRelated
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.
PortfolioOptimisers.MeanGradient — Type
struct MeanGradient <: AbstractGradientPredictorTakes 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.
PortfolioOptimisers.ForecastGradient — Type
struct ForecastGradient{__T_me} <: AbstractGradientPredictorForms 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) -> ForecastGradientKeywords 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
meis not anOnlinewrapper, and holds none. AnArgumentErroris thrown otherwise.
Examples
julia> ForecastGradient(; me = PriceLevelExpectedReturns(; alg = MovingAverage(; window = 3)))ForecastGradient me ┼ PriceLevelExpectedReturns │ alg ┼ MovingAverage │ │ window ┴ Int64: 3Related
AbstractGradientPredictorMirrorDescentPriceLevelExpectedReturnsPriorExpectedReturnsforecast_relative
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.
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
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
LastGradientthe hint is a copy ofg. Atat_played = falseit is the gradient ofobjat the secondary iteratev, on the mixed relativexmthatgreads. - Under
MeanGradientthe method updates the running meanm, and the hint is a copy of it. - Under
ForecastGradientthe method folds or fits the forecaster on the traded relativexthroughforecast_relative, and the hint is the log-wealth gradient of the forecast atv. 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
PortfolioOptimisers.predictor_state_view — Function
predictor_state_view(ps::Nothing, i)
predictor_state_view(ps::AbstractVector, i)
predictor_state_view(ps::AbstractPartialFitState, i)Returns the state of a Gradient Predictor sliced to the assets i, as a copy.
Related
PortfolioOptimisers.copy_predictor_state — Function
copy_predictor_state(ps::Nothing)
copy_predictor_state(ps::AbstractVector)
copy_predictor_state(ps::AbstractPartialFitState)Returns a copy of the state of a Gradient Predictor that shares no array with it.
Related
PortfolioOptimisers.HintResidualRate — Type
struct HintResidualRate{__T_rmax} <: AbstractLearningRateScheduleSets 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) -> HintResidualRateKeywords correspond to the struct's fields.
Validation
rmax > 0. ADomainErroris thrown otherwise.
Examples
julia> HintResidualRate()HintResidualRate rmax ┴ Int64: 1Related
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.
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).