Adaptive optimistic: private API

PortfolioOptimisers.DiagonalProjection — Type
struct DiagonalProjection{__T_h} <: AbstractProjectionGeometry

Projects the raw step onto the Allocation Set in the norm of a non-negative diagonal matrix.

This is the geometry of the diagonal adaptive subgradient method of Duchi et al. [284]. 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.

A zero entry of $\boldsymbol{h}$ makes the norm a seminorm. The projection then has many minimisers, and all of them have the same weights at the positive entries of $\boldsymbol{h}$. The geometry returns the limit of the projection in $\mathrm{diag}(\boldsymbol{h} + \delta \boldsymbol{1})$ as $\delta \to 0^{+}$, which is the minimiser nearest $\boldsymbol{q}$ in the Euclidean norm. So the projection is continuous in $\boldsymbol{h}$ at a zero entry. On a ProgrammeAllocationSet a failed solve of the limit keeps a minimiser that need not be the limit, as solve_projection_programme! states. A diagonal of equal entries, zero included, is a multiple of the identity, and on a BoundedAllocationSet its projection is the Euclidean one.

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}$: Non-negative 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 with a positive $\boldsymbol{h}$ the projection is $\boldsymbol{w}(\theta)$ at that root, and bounded_quadratic_projection states the limit at a zero entry. At $\boldsymbol{h} = \boldsymbol{1}$ it is the Euclidean projection.

Fields

  • h: The diagonal of the norm of the projection, non-negative. 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

  • [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). Equation 1 and Algorithm 1.
source
PortfolioOptimisers.OptimisticMirrorDescentState — Type
struct OptimisticMirrorDescentState{__T_n, __T_v, __T_u, __T_w0, __T_s, __T_res, __T_m, __T_ps} <: AbstractPartialFitState

Holds the two iterates of the optimistic step of a MirrorDescent rule with a predictor, its hint residuals and the states 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 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 state 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 the optimistic step 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

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