29 lines
1.3 KiB
TeX
29 lines
1.3 KiB
TeX
An earlier version of the implementation used Newton--Raphson to invert the KDE CDF
|
|
instead of bisection (\Cref{sec:roll-kde-forward}). We document it here as a reference
|
|
alternative.
|
|
|
|
\paragraph{Method.}
|
|
To find $\tau = \hat{F}_0^{-1}(1-\alpha;\mathcal{B}_0)$, choose an initial guess $\tau_0$
|
|
and iterate:
|
|
\begin{equation}
|
|
\tau_{n+1} = \tau_n
|
|
- \frac{\hat{F}_0(\tau_n;\,\mathcal{B}_0) - (1-\alpha)}
|
|
{\dfrac{\partial\hat{F}_0(\tau_n;\,\mathcal{B}_0)}{\partial\tau}},
|
|
\label{eq:kde-nr-step}
|
|
\end{equation}
|
|
where the denominator is the KDE density evaluated at $\tau_n$:
|
|
\[
|
|
\frac{\partial\hat{F}_0(\tau_n;\,\mathcal{B}_0)}{\partial\tau}
|
|
= \frac{1}{|\mathcal{B}_0|}\sum_{\mathbf{x}_j\in\mathcal{B}_0}
|
|
\sigma_0'(\tau_n - f_\theta(\mathbf{x}_j)).
|
|
\]
|
|
Iteration continues until
|
|
$\lvert\hat{F}_0(\tau_n;\,\mathcal{B}_0)-(1-\alpha)\rvert < \varepsilon$.
|
|
|
|
\paragraph{Limitations.}
|
|
Newton--Raphson requires evaluating $\sigma_0'$ at every step and can diverge if
|
|
$\tau_0$ is far from the root or if the KDE density is very small near the target
|
|
quantile (e.g.\ early in training when scores cluster tightly and $v_0$ is large).
|
|
These failure modes motivated the switch to bisection, which requires no derivative
|
|
evaluation in the forward pass and is guaranteed to converge given a valid bracket.
|