CRPS-Learning

# CRPS-Learning
## Jonathan Berrisch, Florian Ziel
### University of Duisburg-Essen
### 2021-06-28

---

class:middle

# Outline

- [Motivation](#motivation)
- [The Framework of Prediction under Expert Advice](#pred_under_exp_advice)
- [The Continious Ranked Probability Score](#crps)
- [Optimality of (Pointwise) CRPS-Learning](#crps_optim)
- [A Simple Probabilistic Example](#simple_example)
- [The Proposed CRPS-Learning Algorithm](#proposed_algorithm)
- [Simulation Results](#simulation)
- [Possible Extensions](#extensions)
- [Application Study](#application)
- [Wrap-Up](#conclusion)
- [References](#references)

---

# Motivation

The Idea:
- Combine multiple forecasts instead of choosing one

- Combination weights may vary over **time**, over the **distribution** or **both**

2 Popular options for combining distributions:
- Combining across quantiles (this paper)
  - Horizontal aggregation, vincentization
- Combining across probabilities
  - Vertical aggregation

]

![](data:image/png;base64,#index_files/figure-html/unnamed-chunk-1-1.svg)

]

.panel[.panel-name[Distribution]
![](data:image/png;base64,#index_files/figure-html/unnamed-chunk-2-1.svg)

]]
]

---

# The Framework of Prediction under Expert Advice

### The sequential framework

Each day, `$t = 1, 2, ... T$`
- The **forecaster** receives predictions `$\widehat{X}_{t,k}$` from `$K$` **experts**
- The **forecaster** assings weights `$w_{t,k}$` to each **expert**
- The **forecaster** calculates her prediction:
`\begin{equation}
    \widetilde{X}_{t} = \sum_{k=1}^K w_{t,k} \widehat{X}_{t,k}.
    \label{eq_forecast_def}
\end{equation}`
- The realization for `$t$` is observed
]

### The Regret

Weights are updated sequentially according to the past performance of the `$K$` experts.

That is, a loss function `$\ell$` is needed. This is used to compute the **cumulative regret** `$R_{t,k}$`

`\begin{equation}
    R_{t,k}  = \widetilde{L}_{t} - \widehat{L}_{t,k} =  \sum_{i = 1}^t \ell(\widetilde{X}_{i},Y_i) - \ell(\widehat{X}_{i,k},Y_i)
    \label{eq_regret}
\end{equation}`

- <a id='cite-cesa2006prediction'></a><a href='#bib-cesa2006prediction'>Cesa-Bianchi and Lugosi (2006)</a>

]

---

# Popular Algorithms and the Risk

### Popular Aggregation Algorithms

#### The naive combination

`\begin{equation}
    w_{t,k}^{\text{Naive}} = \frac{1}{K}
\end{equation}`

#### The exponentially weighted average forecaster (EWA)

`\begin{align}
    w_{t,k}^{\text{EWA}} & = \frac{e^{\eta R_{t,k}} }{\sum_{k = 1}^K e^{\eta R_{t,k}}}
    =
    \frac{e^{-\eta \ell(\widehat{X}_{t,k},Y_t)} w^{\text{EWA}}_{t-1,k} }{\sum_{k = 1}^K e^{-\eta \ell(\widehat{X}_{t,k},Y_t)} w^{\text{EWA}}_{t-1,k} }
    \label{eq_ewa_general}
\end{align}`

]

### Optimality

In stochastic settings, the cumulative Risk should be analyzed <a id='cite-wintenberger2017optimal'></a><a href='#bib-wintenberger2017optimal'>Wintenberger (2017)</a>:
`\begin{align}
    &\underbrace{\widetilde{\mathcal{R}}_t = \sum_{i=1}^t \mathbb{E}[\ell(\widetilde{X}_{i},Y_i)|\mathcal{F}_{i-1}]}_{\text{Cumulative Risk of Forecaster}} \\
    &\underbrace{\widehat{\mathcal{R}}_{t,k} = \sum_{i=1}^t \mathbb{E}[\ell(\widehat{X}_{i,k},Y_i)|\mathcal{F}_{i-1}]}_{\text{Cumulative Risk of Experts}}
    \label{eq_def_cumrisk}
\end{align}`

]

---

# Optimal Convergence

### The selection problem
`\begin{equation}
    \frac{1}{t}\left(\widetilde{\mathcal{R}}_t - \widehat{\mathcal{R}}_{t,\min} \right) \stackrel{t\to \infty}{\rightarrow} a \quad \text{with} \quad a \leq 0.
    \label{eq_opt_select}
\end{equation}`
The forecaster is asymptotically not worse than the best expert `$\widehat{\mathcal{R}}_{t,\min}$`.

### The convex aggregation problem

`\begin{equation}
    \frac{1}{t}\left(\widetilde{\mathcal{R}}_t - \widehat{\mathcal{R}}_{t,\pi} \right) \stackrel{t\to \infty}{\rightarrow} b \quad \text{with} \quad b \leq 0 .
    \label{eq_opt_conv}
\end{equation}`
The forecaster is asymptotically not worse than the best convex combination `$\widehat{X}_{t,\pi}$` in hindsight (**oracle**).
]

Optimal rates with respect to selection \eqref{eq_opt_select} and convex aggregation \eqref{eq_opt_conv}  <a href='#bib-wintenberger2017optimal'>Wintenberger (2017)</a>:

`\begin{align}
    \frac{1}{t}\left(\widetilde{\mathcal{R}}_t - \widehat{\mathcal{R}}_{t,\min} \right) & =
    \mathcal{O}\left(\frac{\log(K)}{t}\right)\label{eq_optp_select}
\end{align}`
`\begin{align}
    \frac{1}{t}\left(\widetilde{\mathcal{R}}_t - \widehat{\mathcal{R}}_{t,\pi} \right)  & =
    \mathcal{O}\left(\sqrt{\frac{\log(K)}{t}}\right)
    \label{eq_optp_conv}
\end{align}`

Algorithms can statisfy both \eqref{eq_optp_select} and \eqref{eq_optp_conv} depending on:

- The loss function
- Regularity conditions on `$Y_t$` and `$\widehat{X}_{t,k}$`
- The weighting scheme

]

---

name:crps

## Optimality

EWA satisfies the optimal selection convergence \eqref{eq_optp_select} in a deterministic setting if:
- Loss `$\ell$` is exp-concave
- Learning-rate `$\eta$` is chosen correctly

Those results can be converted to stochastic iid settings <a id='cite-kakade2008generalization'></a><a href='#bib-kakade2008generalization'>Kakade and Tewari (2008)</a> <a id='cite-gaillard2014second'></a><a href='#bib-gaillard2014second'>Gaillard, Stoltz, and Van Erven (2014)</a>.

The optimal convex aggregation convergence \eqref{eq_optp_conv} can be satisfied by applying the kernel-trick:
`\begin{align}
\ell^{\nabla}(x,y) = \ell'(\widetilde{X},y) x
\end{align}`
`$\ell'$` is the subgradient of `$\ell$` at forecast combination `$\widetilde{X}$`.

]

## The CRPS

`\begin{align*}
    \text{CRPS}(F, y) & = \int_{\mathbb{R}} {(F(x) - \mathbb{1}\{ x > y \})}^2 dx
    \label{eq_crps}
\end{align*}`

It's strictly proper <a id='cite-gneiting2007strictly'></a><a href='#bib-gneiting2007strictly'>Gneiting and Raftery (2007)</a>.

Using the CRPS, we can calculate time-adaptive weights `$w_{t,k}$`. However, what if the experts' performance is not uniform over all parts of the distribution?

The idea: utilize this relation:

`\begin{align*}
    \text{CRPS}(F, y) = 2 \int_0^{1}  \text{QL}_p(F^{-1}(p), y) \, d p.
    \label{eq_crps_qs}
\end{align*}`

To combine quantiles of the probabilistic forecasts individually using the quantile-loss QL.

]

---

# CRPS-Learning Optimality

QL is convex, but not exp-concave <svg aria-hidden="true" role="img" viewBox="0 0 192 512" style="height:1em;width:0.38em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:#ffa600;overflow:visible;position:relative;"><path d="M176 432c0 44.112-35.888 80-80 80s-80-35.888-80-80 35.888-80 80-80 80 35.888 80 80zM25.26 25.199l13.6 272C39.499 309.972 50.041 320 62.83 320h66.34c12.789 0 23.331-10.028 23.97-22.801l13.6-272C167.425 11.49 156.496 0 142.77 0H49.23C35.504 0 24.575 11.49 25.26 25.199z"/></svg> <svg aria-hidden="true" role="img" viewBox="0 0 448 512" style="height:1em;width:0.88em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:#000000;overflow:visible;position:relative;"><path d="M190.5 66.9l22.2-22.2c9.4-9.4 24.6-9.4 33.9 0L441 239c9.4 9.4 9.4 24.6 0 33.9L246.6 467.3c-9.4 9.4-24.6 9.4-33.9 0l-22.2-22.2c-9.5-9.5-9.3-25 .4-34.3L311.4 296H24c-13.3 0-24-10.7-24-24v-32c0-13.3 10.7-24 24-24h287.4L190.9 101.2c-9.8-9.3-10-24.8-.4-34.3z"/></svg> Bernstein Online Aggregation (BOA) lets us weaken the exp-concavity condition. It satisfies that there exist a `$C>0$` such that for `$x>0$` it holds that
`\begin{equation}
    P\left( \frac{1}{t}\left(\widetilde{\mathcal{R}}_t - \widehat{\mathcal{R}}_{t,\pi} \right)  \leq C \log(\log(t)) \left(\sqrt{\frac{\log(K)}{t}} + \frac{\log(K)+x}{t}\right)  \right) \geq
    1-e^{x}
    \label{eq_boa_opt_conv}
\end{equation}`

The same algorithm satisfies that there exist a `$C>0$` such that for `$x>0$` it holds that
`\begin{equation}
    P\left( \frac{1}{t}\left(\widetilde{\mathcal{R}}_t - \widehat{\mathcal{R}}_{t,\min} \right) \leq
    C\left(\frac{\log(K)+\log(\log(Gt))+ x}{\alpha t}\right)^{\frac{1}{2-\beta}} \right) \geq
    1-e^{x}
    \label{eq_boa_opt_select}
\end{equation}`

if `$Y_t$` is bounded, the considered loss `$\ell$` is convex `$G$`-Lipschitz and weak exp-concave in its first coordinate.

---

# A Probabilistic Example

Simple Example:

`\begin{align}
    Y_t               & \sim \mathcal{N}(0,\,1)                     \\
    \widehat{X}_{t,1} & \sim \widehat{F}_{1}  = \mathcal{N}(-1,\,1) \\
    \widehat{X}_{t,2} & \sim \widehat{F}_{2}  = \mathcal{N}(3,\,4)
    \label{eq:dgp_sim1}
\end{align}`

- True weights vary over `$p$`
- Figures show the ECDF and calculated weights using `$T=25$` realizations
- Pointwise solution creates rough estimates
- Pointwise is better than constant
- Smooth solution is better than pointwise

]

]

]]
]

---

# The Smoothing Procedure

Let `$\varphi=(\varphi_1,\ldots, \varphi_L)$` be bounded basis functions on `$(0,1)$` Then we approximate `$w_{t,k}$` by

`\begin{align}
w_{t,k}^{\text{smooth}} = \sum_{l=1}^L \beta_l \varphi_l = \beta'\varphi
\end{align}`

with parameter vector `$\beta$`. The latter is estimated penalized `$L_2$`-smoothing which minimizes

`\begin{equation}
    \| w_{t,k} - \beta' \varphi  \|^2_2 + \lambda \| \mathcal{D}^{d}  (\beta' \varphi)  \|^2_2
    \label{eq_function_smooth}
\end{equation}`

with differential operator `$\mathcal{D}$`

Smoothing can be applied ex-post or inside of the algorithm ( <svg aria-hidden="true" role="img" viewBox="0 0 448 512" style="height:1em;width:0.88em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:#000000;overflow:visible;position:relative;"><path d="M190.5 66.9l22.2-22.2c9.4-9.4 24.6-9.4 33.9 0L441 239c9.4 9.4 9.4 24.6 0 33.9L246.6 467.3c-9.4 9.4-24.6 9.4-33.9 0l-22.2-22.2c-9.5-9.5-9.3-25 .4-34.3L311.4 296H24c-13.3 0-24-10.7-24-24v-32c0-13.3 10.7-24 24-24h287.4L190.9 101.2c-9.8-9.3-10-24.8-.4-34.3z"/></svg> [Simulation](#simulation)).

]

We receive the constant solution for high values of `$\lambda$` when setting `$d=1$`

]

---

name:proposed_algorithm

# The Proposed CRPS-Learning Algorithm

**Initialization:**

Array of expert predicitons: `$\widehat{X}_{t,k,p}$`

Vector of Prediction targets: `$Y_t$`

Starting Weights: `$w_0=(w_{0,1},\ldots, w_{0,K})$`,

Penalization parameter: `$\lambda\geq 0$`

B-spline and penalty matrices `$B$` and `$D$` on `$\mathcal{P}= (p_1,\ldots,p_M)$`

Hat matrix: `$$\mathcal{H} = B(B'B+ \lambda D'D)^{-1} B'$$`

Cumulative Regret: `$R_{0,k} = 0$`

Range parameter: `$E_{0,k}=0$`

]]

**Core**:

for(t in 1:T) { for(p in `$\mathcal{P}$`) {

&nbsp;&nbsp;&nbsp;&nbsp; `$\widetilde{X}_{t,k}(p) = \sum_{k=1}^K w_{t-1,k,p} \widehat{X}_{t,k}(p)$` .grey[\# Prediction]
        
&nbsp;&nbsp;&nbsp;&nbsp; for(k in 1:K){

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `$r_{t,k,p} = \text{QL}_p^{\nabla}(\widehat{X}_{t,k}(p),Y_t) - \text{QL}_p^{\nabla}(\widetilde{X}_{t}(p),Y_t)$`

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `$E_{t,k,p} = \max(E_{t-1,k,p}, |r_{t,k,p}|)$`

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `$\eta_{t,k,p}=\min\left(1/2E_{t,k,p}, \sqrt{\log(K)/ \sum_{i=1}^t (r^2_{i, k,p})}\right)$`

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `$R_{t,k,p} = R_{t-1,k,p} + \frac{1}{2} \left( r_{t,k,p}  \left( 1+ \eta_{t,k,p}  r_{t,k,p} \right) + 2E_{t,k,p}  \mathbb{1}(\eta_{t,k,p}r_{t,k,p} > \frac{1}{2}) \right)$`

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `$w_{t,k,p} =  \eta_{t,k,p} \exp \left(-  \eta_{t,k,p}  R_{t,k,p} \right) w_{0,k,p} / \left( \frac{1}{K}  \sum_{k = 1}^K  \eta_{t,k,p} \exp \left( - \eta_{t,k,p}  R_{t,k,p}\right) \right)$`

&nbsp;&nbsp; }.grey[\#k]}.grey[\#p]

&nbsp;&nbsp; for(k in 1:K){

&nbsp;&nbsp;&nbsp;&nbsp; `$w_{t,k} = \mathcal{H} w_{t,k}(\mathcal{P})$` .grey[\# Smoothing]

} .grey[\#k]} .grey[\#t]

]
]

---

# Simulation Study

Data Generating Process of the [simple probabilistic example](#simple_example)

- Constant solution `$\lambda \rightarrow \infty$`
- Pointwise Solution of the proposed BOAG
- Smoothed Solution of the proposed BOAG
  - Weights are smoothed during learning
  - Smooth weights are used to calculate Regret, adjust weights, etc. 
- Smooth ex-post solution
  - Weights are smoothed after the learning
  - Algorithm always uses non-smoothed weights

]

Deviation from best attainable `$\text{QL}_p$` (1000 runs).

![](data:image/png;base64,#pre_vs_post.gif)

]

CRPS Values for different `$\lambda$` (1000 runs)

![](data:image/png;base64,#pre_vs_post_lambda.gif)

]]

]
---

# Simulation Study

The same simulation carried out for different algorithms (1000 runs):

---

# Simulation Study

**New DGP:**

`\begin{align}
    Y_t               & \sim \mathcal{N}\left(\frac{\sin(0.005 \pi t )}{2},\,1\right) \\
    \widehat{X}_{t,1} & \sim      \widehat{F}_{1}  = \mathcal{N}(-1,\,1)              \\
    \widehat{X}_{t,2} & \sim       \widehat{F}_{2}  = \mathcal{N}(3,\,4) \label{eq_dgp_sim2}
\end{align}`

]

**Weights of expert 2**

]

---

# Simulation Results

The simulation using the new DGP carried out for different algorithms (1000 runs):

---

name:extensions

# Possible Extensions

**Forgetting**

- Only taking part of the old cumulative regret into account
- Exponential forgetting of past regret

`\begin{align*}
    R_{t,k} & =  R_{t-1,k}(1-\xi) + \ell(\widetilde{F}_{t},Y_i) - \ell(\widehat{F}_{t,k},Y_i) \label{eq_regret_forget}
\end{align*}`

**Fixed Shares** <a id='cite-herbster1998tracking'></a><a href='#bib-herbster1998tracking'>Herbster and Warmuth (1998)</a>

- Adding fixed shares to the weights
  - Shrinkage towards a constant solution

`\begin{align*}
    \widetilde{w}_{t,k} = \rho \frac{1}{K} + (1-\rho) w_{t,k}
    \label{fixed_share_simple}.
\end{align*}`

]

**Non-Equidistant Knots**
- Non-equidistant spline-basis could be used
- Potentially improves the tail-behavior
- Destroys shrinkage towards constant

]

---

# Application Study: Overview

Data:

- Forecasting European emission allowances (EUA)
- Daily month-ahead prices 
- Jan 13 - Dec 20 (Phase III, 2092 Obs)

Combination methods:

- Naive, BOAG, EWAG, ML-PolyG, BMA

Tuning paramter grids:

- Smoothing Penalty: `$\Lambda= \{0\}\cup \{2^x|x\in \{-4,-3.5,\ldots,12\}\}$`
- Learning Rates: `$\mathcal{E}= \{2^x|x\in \{-1,-0.5,\ldots,9\}\}$`

]
]

]

---

# Application Study: Experts

Simple exponential smoothing with additive errors (**ETS-ANN**):

`\begin{align*}
Y_{t} = l_{t-1} + \varepsilon_t \quad \text{with} \quad l_t = l_{t-1} + \alpha \varepsilon_t \quad \text{and} \quad \varepsilon_t \sim \mathcal{N}(0,\sigma^2)
\end{align*}`

Quantile regression (**QuantReg**): For each `$p \in \mathcal{P}$` we assume:

`\begin{align*}
F^{-1}_{Y_t}(p) = \beta_{p,0} + \beta_{p,1} Y_{t-1} + \beta_{p,2} |Y_{t-1}-Y_{t-2}|
\end{align*}`

ARIMA(1,0,1)-GARCH(1,1) with Gaussian errors (**ARMA-GARCH**):

`\begin{align*}
Y_{t} = \mu + \phi(Y_{t-1}-\mu) + \theta \varepsilon_{t-1} + \varepsilon_t \quad \text{with} \quad \varepsilon_t = \sigma_t Z, \quad \sigma_t^2 = \omega + \alpha \varepsilon_{t-1}^2 + \beta \sigma_{t-1}^2 \quad \text{and} \quad Z_t \sim \mathcal{N}(0,1)
\end{align*}`

ARIMA(0,1,0)-I-EGARCH(1,1) with Gaussian errors (**I-EGARCH**):

`\begin{align*}
Y_{t} = \mu + Y_{t-1}  + \varepsilon_t \quad \text{with} \quad \varepsilon_t = \sigma_t Z, \quad \log(\sigma_t^2) = \omega + \alpha Z_{t-1}+ \gamma (|Z_{t-1}|-\mathbb{E}|Z_{t-1}|) + \beta \log(\sigma_{t-1}^2) \quad \text{and} \quad Z_t \sim \mathcal{N}(0,1)
\end{align*}`

ARIMA(0,1,0)-GARCH(1,1) with student-t errors (**I-GARCHt**}):

`\begin{align*}
Y_{t} = \mu + Y_{t-1}  + \varepsilon_t \quad \text{with} \quad \varepsilon_t = \sigma_t Z, \quad \sigma_t^2 = \omega + \alpha \varepsilon_{t-1}^2 + \beta \sigma_{t-1}^2 \quad \text{and} \quad Z_t \sim t(0,1, \nu)
\end{align*}`

]

---

# Application Study: Results

<table class=" lightable-material" style='font-family: "Source Sans Pro", helvetica, sans-serif; margin-left: auto; margin-right: auto;'>
 <thead>
  <tr>
   <th style="text-align:left;">   </th>
   <th style="text-align:center;"> BOAG </th>
   <th style="text-align:center;"> EWAG </th>
   <th style="text-align:center;"> ML-PolyG </th>
   <th style="text-align:center;"> BMA </th>
  </tr>
 </thead>
<tbody>
  <tr>
   <td style="text-align:left;font-weight: bold;"> pointwise </td>
   <td style="text-align:center;background-color: #99EE80 !important;"> -0.161 (0.067) </td>
   <td style="text-align:center;background-color: #D6FF80 !important;"> -0.085 (0.177) </td>
   <td style="text-align:center;background-color: #AFF580 !important;"> -0.136 (0.126) </td>
   <td style="text-align:center;background-color: #FFF980 !important;"> 0.030 (0.753) </td>
  </tr>
  <tr>
   <td style="text-align:left;font-weight: bold;"> smooth </td>
   <td style="text-align:center;background-color: #85E780 !important;"> -0.185 (0.037) </td>
   <td style="text-align:center;background-color: #D1FF80 !important;"> -0.094 (0.150) </td>
   <td style="text-align:center;background-color: #99EE80 !important;"> -0.161 (0.066) </td>
   <td style="text-align:center;background-color: #FFF980 !important;"> 0.027 (0.722) </td>
  </tr>
  <tr>
   <td style="text-align:left;font-weight: bold;"> constant </td>
   <td style="text-align:center;background-color: #AEF580 !important;"> -0.137 (0.020) </td>
   <td style="text-align:center;background-color: #E0FF80 !important;"> -0.067 (0.144) </td>
   <td style="text-align:center;background-color: #B3F780 !important;"> -0.132 (0.027) </td>
   <td style="text-align:center;background-color: #FFF880 !important;"> 0.035 (0.826) </td>
  </tr>
  <tr>
   <td style="text-align:left;font-weight: bold;"> smooth* </td>
   <td style="text-align:center;background-color: #80E680 !important;"> -0.191 (0.023) </td>
   <td style="text-align:center;background-color: #9CEF80 !important;"> -0.158 (0.025) </td>
   <td style="text-align:center;background-color: #80E680 !important;"> -0.190 (0.021) </td>
   <td style="text-align:center;background-color: #FFFE80 !important;"> -0.009 (0.333) </td>
  </tr>
</tbody>
</table>

CRPS difference to **Naive** (scaled by `$10^4$`) of single experts and four combination methods with four options.
Additionally, we show the p-value of the DM-test, testing against **Naive**. The smallest value is bold. We also report the optimal ex-post selection by **smooth***

]

]

.panel[.panel-name[Weights]
<img src="data:image/png;base64,#index_files/figure-html/unnamed-chunk-11-1.svg" style="display: block; margin: auto;" />
]

]]

---

# Wrap-Up

Potential Downsides:
- Pointwise optimization can induce quantile crossing
  - Can be solved by sorting the predictions

Upsides:
- Pointwise learning outperforms the Naive solution significantly
- Online learning is much faster than batch methods
- Smoothing further improves the predictive performance
- Asymptotically not worse than the best convex combination

]

Important:
- The choice of the learning rate is crucial
- The loss function has to meet certain criteria

The [<svg aria-hidden="true" role="img" viewBox="0 0 496 512" style="height:1em;width:0.97em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:currentColor;overflow:visible;position:relative;"><path d="M165.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6zm-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3zm44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9zM244.8 8C106.1 8 0 113.3 0 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C428.2 457.8 496 362.9 496 252 496 113.3 383.5 8 244.8 8zM97.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1zm-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7zm32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1zm-11.4-14.7c-1.6 1-1.6 3.6 0 5.9 1.6 2.3 4.3 3.3 5.6 2.3 1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2z"/></svg> profoc](https://profoc.berrisch.biz/) R Package:

- Implements all algorithms discussed above
- Is written using RcppArmadillo <svg aria-hidden="true" role="img" viewBox="0 0 448 512" style="height:1em;width:0.88em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:#000000;overflow:visible;position:relative;"><path d="M190.5 66.9l22.2-22.2c9.4-9.4 24.6-9.4 33.9 0L441 239c9.4 9.4 9.4 24.6 0 33.9L246.6 467.3c-9.4 9.4-24.6 9.4-33.9 0l-22.2-22.2c-9.5-9.5-9.3-25 .4-34.3L311.4 296H24c-13.3 0-24-10.7-24-24v-32c0-13.3 10.7-24 24-24h287.4L190.9 101.2c-9.8-9.3-10-24.8-.4-34.3z"/></svg> its fast
- Accepts vectors for most parameters
  - The best parameter combination is chosen online
- Implements 
  - Forgetting, Fixed Share
  - Different loss functions + gradients

]
]

<a href="https://github.com/BerriJ" class="github-corner" aria-label="View source on Github"><svg width="80" height="80" viewBox="0 0 250 250" style="fill:#f2f2f2; color:#212121; position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a><style>.github-corner:hover .octo-arm{animation:octocat-wave 560ms ease-in-out}@keyframes octocat-wave{0%,100%{transform:rotate(0)}20%,60%{transform:rotate(-25deg)}40%,80%{transform:rotate(10deg)}}@media (max-width:500px){.github-corner:hover .octo-arm{animation:none}.github-corner .octo-arm{animation:octocat-wave 560ms ease-in-out}}</style>

???

Execution Times:

T = 5000

Opera:

Ml-Poly > 157 ms
Boa     > 212 ms

Profoc:

Ml-Poly > 17
BOA     > 16

---

[<svg aria-hidden="true" role="img" viewBox="0 0 576 512" style="height:1em;width:1.12em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:currentColor;overflow:visible;position:relative;"><path d="M552 64H88c-13.255 0-24 10.745-24 24v8H24c-13.255 0-24 10.745-24 24v272c0 30.928 25.072 56 56 56h472c26.51 0 48-21.49 48-48V88c0-13.255-10.745-24-24-24zM56 400a8 8 0 0 1-8-8V144h16v248a8 8 0 0 1-8 8zm236-16H140c-6.627 0-12-5.373-12-12v-8c0-6.627 5.373-12 12-12h152c6.627 0 12 5.373 12 12v8c0 6.627-5.373 12-12 12zm208 0H348c-6.627 0-12-5.373-12-12v-8c0-6.627 5.373-12 12-12h152c6.627 0 12 5.373 12 12v8c0 6.627-5.373 12-12 12zm-208-96H140c-6.627 0-12-5.373-12-12v-8c0-6.627 5.373-12 12-12h152c6.627 0 12 5.373 12 12v8c0 6.627-5.373 12-12 12zm208 0H348c-6.627 0-12-5.373-12-12v-8c0-6.627 5.373-12 12-12h152c6.627 0 12 5.373 12 12v8c0 6.627-5.373 12-12 12zm0-96H140c-6.627 0-12-5.373-12-12v-40c0-6.627 5.373-12 12-12h360c6.627 0 12 5.373 12 12v40c0 6.627-5.373 12-12 12z"/></svg> CRPS-Learning](https://arxiv.org/abs/2102.00968)

---
name:references

# References 1

Cesa-Bianchi, N. and G. Lugosi (2006). _Prediction, learning, and games_. Cambridge
university press.

Gaillard, P., G. Stoltz, and T. Van Erven (2014). "A second-order bound with excess
losses". In: _Conference on Learning Theory_. PMLR. , pp. 176-196.

Gaillard, P. and O. Wintenberger (2018). "Efficient online algorithms for fast-rate
regret bounds under sparsity". In: _Advances in Neural Information Processing
Systems_. , pp. 7026-7036.

Gneiting, T. and A. E. Raftery (2007). "Strictly proper scoring rules, prediction, and
estimation". In: _Journal of the American statistical Association_ 102.477, pp.
359-378.

Herbster, M. and M. K. Warmuth (1998). "Tracking the best expert". In: _Machine
learning_ 32.2, pp. 151-178.

Kakade, S. M. and A. Tewari (2008). "On the Generalization Ability of Online Strongly
Convex Programming Algorithms." In: _NIPS_. , pp. 801-808.

Wintenberger, O. (2017). "Optimal learning with Bernstein online aggregation". In:
_Machine Learning_ 106.1, pp. 119-141.

---

# References 2

```
## Warning in `[[.BibEntry`(x, ind): subscript out of bounds
```

Wintenberger, O. (2017). "Optimal learning with Bernstein online aggregation". In:
_Machine Learning_ 106.1, pp. 119-141.

---

[<svg aria-hidden="true" role="img" viewBox="0 0 512 512" style="height:1em;width:1em;vertical-align:-0.125em;margin-left:auto;margin-right:auto;font-size:inherit;fill:currentColor;overflow:visible;position:relative;"><path d="M500.33 0h-47.41a12 12 0 0 0-12 12.57l4 82.76A247.42 247.42 0 0 0 256 8C119.34 8 7.9 119.53 8 256.19 8.1 393.07 119.1 504 256 504a247.1 247.1 0 0 0 166.18-63.91 12 12 0 0 0 .48-17.43l-34-34a12 12 0 0 0-16.38-.55A176 176 0 1 1 402.1 157.8l-101.53-4.87a12 12 0 0 0-12.57 12v47.41a12 12 0 0 0 12 12h200.33a12 12 0 0 0 12-12V12a12 12 0 0 0-12-12z"/></svg>](#content)