Online selection rules: the adaptive subgradient and the optimistic step

struct AdaptiveSubgradient{T1<:Real, T2<:Real, T3<:AbstractOnlineObjective} <: 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 Duchi, Hazan and Singer (2011, Algorithm 1) 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 whose every price relative so far is zero has no gradient mass. The diagonal of the norm then has a zero entry, and DiagonalProjection refuses it with a DomainError. The paper takes a pseudo-inverse there, but the projection in a seminorm has no unique answer, so the rule refuses instead.

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^{-1} \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$.
• $\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 of a vector $\boldsymbol{z}$ in a positive 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$.

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 the paper 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. The paper shows 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 of the paper (Algorithm 2) 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

The seven-argument online_update! runs these steps at the period's row x. The six-argument form calls it with the book w as the Gradient Point point.

1. Take the gradient g of obj at point, from x and the head's rows, with loss_gradient.
2. Form the Price-Adjusted Allocation wh of the book w after the row.
3. When every entry of g is zero, project w onto the set from wh in the Euclidean geometry. Count the period, keep the gradient mass, and return that allocation. Stop.
4. Add g to the gradient mass st.s in place, as the root of the sum of squares of each asset.
5. Form the diagonal h = delta .+ st.s.
6. Form the raw step q = w .- eta .* g ./ h.
7. Project q onto the set from wh in the geometry DiagonalProjection(h), which gives the new allocation.
8. Return the state, with the period count raised by one, and the new allocation.

A zero gradient accrues no mass, and the norm of step 7 has no meaning there. So step 3 takes the zero step of every first-order rule. A RiskLoss gives a zero gradient while the head holds fewer than two rows.

Fields

• eta: The learning rate of the step. A larger rate reacts faster and is less stable.

• delta: The paper's $\delta$, which the rule adds to the gradient mass of every asset.

• 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. The paper fixes no default. eta = 1 / sqrt(2) is the rate of its Corollary 6 on the simplex, and the paper states 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

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• AdaptiveSubgradientState
• DiagonalProjection
• MirrorDescent
• NewtonStep

References

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

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.

An OptimisticStep 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 carrier 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 carrier takes.
• predict_gradient!(pred::AbstractGradientPredictor, ps, obj::AbstractOnlineObjective, g::AbstractVector, v::AbstractVector, x::AbstractVector, xm::AbstractVector, rows, t::Integer) -> Tuple: Returns the carrier after the period and the hint. The arguments are the objective obj of the wrapped 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 wrapped rule, the rows that the head holds through the period, and the period count t. g reads xm, and xm is x where the wrapped rule does not mix. A predictor that reads the relative as a price folds x. A predictor that evaluates the loss of the wrapped 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.

The head's state already slices and copies a carrier that is nothing, a vector or a Partial Fit State. A carrier of another shape needs its own methods of predictor_state_view and copy_predictor_state.

Related

• LastGradient
• MeanGradient
• ForecastGradient
• OptimisticStep

struct LastGradient <: AbstractGradientPredictor

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

This is the default predictor of OptimisticStep. Under it the optimistic step is the two-projection algorithm of Chiang, Yang, Lee, Mahdavi, Lu, Jin and Zhu (2012), 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 (2004). Rakhlin and Sridharan [212] 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 wrapped 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

• AbstractGradientPredictor
• OptimisticStep
• MeanGradient

References

• [213] 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).
• [212] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In: Advances in Neural Information Processing Systems 26, 3066–3074 (2013).
• [214] 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).

struct MeanGradient <: AbstractGradientPredictor

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

Rakhlin and Sridharan [215] call the regret bound under this hint a variance bound. The carrier 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

• AbstractGradientPredictor
• OptimisticStep
• LastGradient

References

• [215] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In: Proceedings of the 26th Annual Conference on Learning Theory, 993–1019 (2013).

struct ForecastGradient{T1<:AbstractExpectedReturnsEstimator} <: 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 carrier folds it 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 papers take their hints from the past gradients, and this hint is not in them. 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 wrapper needs as many rows as the larger of the predictor and the wrapped rule.

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

• AbstractGradientPredictor
• OptimisticStep
• PriceLevelExpectedReturns
• PriorExpectedReturns
• forecast_relative

predictor_state_seed(pred::AbstractGradientPredictor, w::AbstractVector)
predictor_state_seed(pred::MeanGradient, w::AbstractVector)
predictor_state_seed(pred::ForecastGradient, w::AbstractVector)

Returns the carrier 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 carrier of the forecaster from forecaster_seed under ForecastGradient.

Related

• AbstractGradientPredictor
• predict_gradient!

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 carrier after the period and the hint of the period, and writes the carrier 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 carrier after the period, and the hint, a new vector.

Related

• AbstractGradientPredictor
• predictor_state_seed
• OptimisticStep

struct HintResidualRate{T1<:Real} <: 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 [212]. It needs no horizon and no bound on the residual sum ahead of time. The schedule reads the residuals that an OptimisticStep keeps on its carrier, and it refuses the carrier 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. The paper sets $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, the paper bounds 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 wrapped 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 paper's $R_{\max}$, which scales the rate and caps it.

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

• AbstractLearningRateSchedule
• OptimisticStep
• InverseSquareRootRate

References

• [212] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In: Advances in Neural Information Processing Systems 26, 3066–3074 (2013).

struct OptimisticStep{T1<:MirrorDescent, T2<:AbstractGradientPredictor} <: AbstractOnlinePortfolioSelectionAlgorithm

Plays two half-steps of a first-order rule each period, the second along a hint for the gradient of the next period (OMD).

This is the optimistic mirror descent of Rakhlin and Sridharan (2013), as a wrapper over a MirrorDescent rule. The carrier 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.

eta, proj, alpha and obj are those of the wrapped rule. Both half-steps are its mirror step in its geometry, and the gradient is that of its objective, through loss_gradient. A RiskLoss reads the head's rows, and the wrapper needs as many rows as the larger of the objective and the predictor. A schedule on eta counts the periods of the wrapper and reads its carrier. The wrapper reads the uniform mix alpha as the wrapped rule does.

Mathematical definition

\[\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{w}_t$: Iterate of the rule at period $t$, the allocation its update reads. Here it is the played allocation before the uniform mix.
• $\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 $-\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.
• $M_t$: Hint of period $t$, the forecast of the gradient $\boldsymbol{g}_t$ that the Gradient Predictor makes one period earlier.
• $\eta_t$: Learning rate of the update at period $t$.
• $t$: Period index, counted from one.
• $\mathcal{W}$: Allocation Set.
• $\Psi$: Potential of the Projection Geometry.
• $D_\Psi$: Bregman divergence of $\Psi$.
• $\lVert \cdot \rVert_*$: Dual norm of the norm that the potential of the Projection Geometry is strongly convex against.

The rates follow equation (1) of [212], 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 wrapped rule.

For a fixed rate $\eta$ and a comparator $\boldsymbol{w}^*$ with $D_\Psi(\boldsymbol{w}^*, \boldsymbol{v}_1) \leq R^2$, Lemma 1 of [212], 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. [215] states 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 the eta of the wrapped rule is the adaptive rate of [212].

Algorithm

The seven-argument online_update! runs these steps at the period's row x. The six-argument form calls it with the unmixed played iterate st.u as the Gradient Point point.

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 every carrier at its seed, 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. Take the gradient g of obj 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 carrier ps of the predictor with predict_gradient!, from 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 carrier 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

• alg: The first-order rule that takes both half-steps.

• predictor: The Gradient Predictor whose hint the second half-step follows.

Constructors

OptimisticStep(;    alg::MirrorDescent = MirrorDescent(),    predictor::AbstractGradientPredictor = LastGradient()) -> OptimisticStep

Keywords correspond to the struct's fields. The Gradient Transform of the wrapped rule must be the identity. A transform keeps a carrier that one gradient writes each period, and the optimistic step reads two gradients a period.

Validation

• alg.grad is a PlainGradient. An ArgumentError is thrown otherwise.

Examples

julia> OptimisticStep()OptimisticStep        alg ┼ MirrorDescent            │     eta ┼ Float64: 0.05            │    proj ┼ EntropicProjection()            │   alpha ┼ Int64: 0            │     obj ┼ LogWealth()            │    grad ┴ PlainGradient()  predictor ┼ LastGradient            │   at_played ┴ Bool: true

Related

• AbstractOnlinePortfolioSelectionAlgorithm
• OnlinePortfolioSelection
• MirrorDescent
• OptimisticStepState
• AbstractGradientPredictor
• HintResidualRate

References

• [215] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In: Proceedings of the 26th Annual Conference on Learning Theory, 993–1019 (2013).
• [212] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In: Advances in Neural Information Processing Systems 26, 3066–3074 (2013).
• [213] 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).