Adaptive optimistic: private API
PortfolioOptimisers.DiagonalProjection — Type
struct DiagonalProjection{__T_h} <: AbstractProjectionGeometryProjects 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 todeltaplus its gradient mass at the step.
Constructors
DiagonalProjection(h::AbstractVector) -> DiagonalProjectionThe 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). ADomainErroris thrown otherwise.
Examples
julia> PortfolioOptimisers.DiagonalProjection([1.0, 2.0])PortfolioOptimisers.DiagonalProjection h ┴ Vector{Float64}: [1.0, 2.0]Related
AbstractProjectionGeometryEuclideanProjectionGramProjection: the full-matrix geometry, whose programme arm this geometry shares.AdaptiveSubgradientprojectset_projection_objective!
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.
PortfolioOptimisers.AdaptiveSubgradientState — Type
struct AdaptiveSubgradientState{__T_n, __T_s} <: AbstractPartialFitStateHolds the gradient mass of each asset, the state of the adaptive subgradient rule.
Fields
n: Number of observations folded into the state.
s: The gradient mass $\boldsymbol{s}_t$, with $s_{t, i}^2 = \sum_{s \leq t} g_{s, i}^2$,assets × 1. The rule writes it in place.
Related
PortfolioOptimisers.OptimisticMirrorDescentState — Type
struct OptimisticMirrorDescentState{__T_n, __T_v, __T_u, __T_w0, __T_s, __T_res, __T_m, __T_ps} <: AbstractPartialFitStateHolds 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, ornothing.
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$.HintResidualRatereads 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, ornothing.
Related
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,TsallisProjectionandLogBarrierProjection. - $\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
PortfolioOptimisers.half_step — Function
half_step(
alg::MirrorDescent,
set::AbstractAllocationSet,
u::AbstractVector,
s::AbstractVector,
w::AbstractVector
) -> Any
Takes one half-step of the optimistic step of a MirrorDescent rule. This is the mirror step of the rule from u on the scaled gradient s, projected onto the set in the rule's geometry from the Price-Adjusted Allocation w.
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).