Definition of Runtime Profiles without targets

[nikohansen]

As @TGlas pointed out, we don't need to define target values for plotting runtime profiles (formerly known as empirical runtime distributions, ERD, RTD, ECDF). Specifically, this can be done as follows.

Input:

• the observations $(t, f^{i,j}_t)$ for strictly increasing sequences of times $t \in \mathbb R$ for some functions $i=1,\dots,n$ and repetitions $j=1,\dots,m_i$, where also the recorded values of $t$ may depend on $(i,j)$ and $f_t$ tends to be decreasing with increasing $t$;
• a strictly increasing $f$-values transformation $T:$ $]0, \infty[$ $\to \mathbb R$, like $x\mapsto x$ or $x\mapsto \lg(x)$. More specifically, the domains for the values $f^{i,.}_{.}$ will be $T: [\varepsilon^i, f^i_0 - f^i_\infty + \delta^i + \varepsilon^i] \to [T(\varepsilon^i), T^i_0]$, see below.

We define or set

• $f^i_0 = \mathrm{max}_{j}(f^{i,j}_0)$ or some given reference base value.
• $\delta^i\ge 0$, e.g., as zero when the initial search point was evaluated, or as the largest of the first $f$-improvements over all repetitions. The $\delta^i$ determine the size of the first vertical step.
• $f^i_\infty = \mathrm{min}_{t, j}(f^{i,j}_t)$. The $f^i_\infty$ can also be set to the desired best $f^i$-value if known, like in COCO usually $f^i_\infty=f^i_{* } + 10^{-8}$ where $f^i_{* }$ is the known optimal $f$-value, or to a desired relative improvement over $f^i_0$ or $f^i_0 + \delta^i$ like $10^{-5}\times(f^i_0 + \delta^i)$.
• $\varepsilon^i\ge 0$ determine a shift away from zero before applying $T$ to $f-f^i_\infty$ and have no effect when $T$ is affine linear. The COCO-bbob-default is $\varepsilon^i = f^i_\infty - f^i_{* } = 10^{-8}$ where $f^i_{* }$ is the best possible $f$-value. Another possibility could be half of the smallest nonzero $f$-improvement over all repetitions (or all repetitions and all functions).

The nonmonotonous runtime profile function is defined as

$$ P^i: f\mapsto \left\{\begin{array}{cl}0 & \text{if~} f \ge f^i_0 + \delta^i \\ 1 & \text{if~} f \le f^i_\infty\\ \displaystyle\frac{T^i_0 - T(f - f^i_\infty + \varepsilon^i)}{T^i_0 - T(\varepsilon^i)} & \in [0, 1] \text{~otherwise} \end{array}\right. $$

where $T^i_0 = T(f^i_0 - f^i_\infty + \delta^i + \varepsilon^i)$. In the image domain $]0, 1[$, the $P^i$ is affine linear w.r.t. $T(f - f^i_\infty + \varepsilon^i)$ and hence affine linear w.r.t. $f$ when $T$ is affine linear.

For a single repetition (i.e., when only $t$ varies for some given $i, j$), the (monotonous) runtime profile of the observations ${f_t^{i,j}}$ is

$$t\mapsto \max_{s\le t}(P^i(f_s^{i, j}))\enspace.$$

For aggregating any observations, we can generalize to

$$t\mapsto \frac1n \sum_{i, j}\frac{\max_{s\le t}(P^i(f_s^{i, j}))}{m_i}\enspace,$$

where the $m_i$ in the denominator ensure equal vertical weight for all $n$ functions, and the $1/n$ ensures that the profile value does not exceed 1.

The (monotonous) runtime profile graph $P$ versus $t$ can be constructed like

• start at $(t, P) = (\mathrm{argmin}_t{f_t^{i,j} \mid i=1,\dots,n, j=1,\dots,m_i}, 0)$
• while any $f^{i,j}_t$ is left:
  • pick any $f^{i,j}_t$ with the smallest $t$ from all $f^{i,j}_t$ not yet consumed
  • draw horizontally up to $t$
  • if $P^i(f^{i,j}_{t}) > P_{t-1} := \mathrm{max}_{s<t}P^i(f^{i,j}_{s})$, i.e. the proviously drawn $f^{i,j}$-value,
    • draw vertically by $\frac{P^i(f^{i,j}_{t}) - P_{t-1}}{m_i \times n}$

When the $t$ are positive and can be reasonably interpreted on a ratio scale, we can plot the $x$-axis in log-scale.

[nikohansen]

FTR, using target values seems equivalent with defining the above increasing transformation $T$ as a step function.

[nikohansen]

For budget-based target values and for data profiles (which have a single budget-based target value), the targets for each function depend on the data. It is not likely that the user will provide such targets though.