GitHub

Online selection rules: the adaptive subgradient and the optimistic step: private API

PortfolioOptimisers.DiagonalProjection — Type
struct DiagonalProjection{T1<:(AbstractVector)} <: AbstractProjectionGeometry

Projects the raw step onto the Allocation Set in the norm of a positive diagonal matrix.

This is the geometry of the diagonal adaptive subgradient method of Duchi, Hazan and Singer (2011). AdaptiveSubgradient builds one at every step from the gradient mass it has accrued, as NewtonStep binds its Gram matrix onto GramProjection. The rule projects the Start Allocation before it sees a gradient, so projection_geometry returns EuclideanProjection for that projection. The geometry admits a negative lower bound, as the Euclidean geometry does.

Mathematical definition

\[\begin{align} \mathrm{Proj}^{\boldsymbol{h}}_{\mathcal{W}}(\boldsymbol{q}) &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; \tfrac{1}{2} (\boldsymbol{w} - \boldsymbol{q})^\intercal \mathrm{diag}(\boldsymbol{h}) (\boldsymbol{w} - \boldsymbol{q})\,, \\ w_i(\theta) &= \min\left(\max\left(q_i - \theta / h_i,\, l_i\right),\, u_i\right)\,. \end{align}\]

Where:

  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
  • $\mathcal{W}$: Allocation Set.
  • $\boldsymbol{h}$: Positive diagonal of the norm, one entry for each asset.
  • $l_i$, $u_i$: Lower and upper bounds of asset $i$ on a BoundedAllocationSet.
  • $\theta$: Budget multiplier, the root of $\sum_i w_i(\theta) = 1$.

On a BoundedAllocationSet the projection is $\boldsymbol{w}(\theta)$ at that root. At $\boldsymbol{h} = \boldsymbol{1}$ it is the Euclidean projection.

Fields

  • h: The diagonal of the norm of the projection. The rule sets it to delta plus its gradient mass at the step.

Constructors

DiagonalProjection(h::AbstractVector) -> DiagonalProjection

The positional argument is the struct's field. The rule builds the geometry at each step, and a caller never holds one.

Validation

  • all(> 0, h). A DomainError is thrown otherwise.

Examples

julia> PortfolioOptimisers.DiagonalProjection([1.0, 2.0])PortfolioOptimisers.DiagonalProjection  h ┴ Vector{Float64}: [1.0, 2.0]

Related

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).
source
PortfolioOptimisers.OptimisticStepState — Type
struct OptimisticStepState{__T_n, __T_v, __T_u, __T_w0, __T_s, __T_res, __T_m, __T_ps} <: AbstractPartialFitState

Holds the two iterates of an optimistic step, its hint residuals and the carriers of its schedule and its predictor.

Fields

  • n: Number of observations folded into the state.
  • v: The secondary iterate $\boldsymbol{v}_t$ over the full pinned universe, summing to one. The first half-step of the period starts from it.
  • u: The unmixed played iterate $\boldsymbol{w}_t$, at which the rule reads the gradient of the period.
  • w0: The Start Allocation projected onto the Allocation Set. A restart returns both iterates to it.
  • s: The schedule statistic of the wrapped rule, or nothing.
  • res: The sums of the squared hint residuals through the last period and the period before it, $[S_{t-1}, S_{t-2}]$ at period $t$. HintResidualRate reads them.
  • m: The hint $M_t$ along which the rule stepped the played iterate, assets × 1. The rule measures the gradient of the period against it.
  • ps: The carrier of the Gradient Predictor, or nothing.

Related

source
PortfolioOptimisers.hint_residual — Function
hint_residual(
    _::EuclideanProjection,
    d::AbstractVector
) -> Any

Returns the squared hint residual of a period in the dual norm of the geometry.

A MirrorDescent rule takes only the four geometries below, so an OptimisticStep never reads the residual under GramProjection or DiagonalProjection, and no method serves them.

Mathematical definition

\[\begin{align} r_{\mathrm{E}} &= \lVert \boldsymbol{g}_t - M_t \rVert_2^2\,, \\ r_{\infty} &= \lVert \boldsymbol{g}_t - M_t \rVert_\infty^2\,. \end{align}\]

Where:

  • $r_{\mathrm{E}}$: Squared residual under EuclideanProjection.
  • $r_{\infty}$: Squared residual under EntropicProjection, TsallisProjection and LogBarrierProjection.
  • $\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.
  • $t$: Period index, counted from one.

Each is the square of the dual norm $\lVert \boldsymbol{g}_t - M_t \rVert_*$. On the simplex the Euclidean potential is 1-strongly convex against the $\ell_2$ norm, whose dual is the $\ell_2$ norm. The entropic, Tsallis and log-barrier potentials are strongly convex against the $\ell_1$ norm with a modulus of at least one, and the dual of the $\ell_1$ norm is the $\ell_\infty$ norm.

Related

source

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