31 lines
1.3 KiB
TeX
31 lines
1.3 KiB
TeX
We describe the bisection procedure used to compute $\tau = \hat{F}_0^{-1}(1-\alpha;\mathcal{B}_0)$
|
|
in the KDE-ROLL forward pass (\Cref{sec:roll-kde-forward}).
|
|
|
|
\paragraph{Bracket initialisation.}
|
|
Because $\sigma(u;\,v) \to 0$ exponentially as $u \to -\infty$ and $\sigma(u;\,v) \to 1$
|
|
as $u \to +\infty$, with tails decaying within roughly $10/v_0$ of the data range, the
|
|
interval
|
|
\[
|
|
\mathrm{lo} = \min(\mathbf{s}^{(0)}) - \tfrac{10}{v_0},
|
|
\qquad
|
|
\mathrm{hi} = \max(\mathbf{s}^{(0)}) + \tfrac{10}{v_0}
|
|
\]
|
|
is guaranteed to satisfy $\hat{F}_0(\mathrm{lo}) < 1-\alpha < \hat{F}_0(\mathrm{hi})$.
|
|
|
|
\paragraph{Bisection iterations.}
|
|
At each step we evaluate the midpoint,
|
|
\[
|
|
\tau_{\mathrm{mid}} = \tfrac{1}{2}(\mathrm{lo} + \mathrm{hi}),
|
|
\]
|
|
and update the bracket:
|
|
\[
|
|
\begin{cases}
|
|
\mathrm{lo} \leftarrow \tau_{\mathrm{mid}} & \text{if } \hat{F}_0(\tau_{\mathrm{mid}};\,\mathcal{B}_0) < 1-\alpha, \\
|
|
\mathrm{hi} \leftarrow \tau_{\mathrm{mid}} & \text{otherwise.}
|
|
\end{cases}
|
|
\]
|
|
Iteration continues until $\lvert\hat{F}_0(\tau_{\mathrm{mid}};\,\mathcal{B}_0)-(1-\alpha)\rvert < \varepsilon$
|
|
(with $\varepsilon = 10^{-4}$), or until a maximum iteration count is reached.
|
|
The method converges unconditionally and requires no derivative evaluation, in contrast
|
|
to the Newton--Raphson alternative documented in Appendix~\ref{appendix:kde-nr}.
|