5
$\begingroup$

For $c, d > 0$, suppose I want to solve for $t$ in \begin{align*} t = \sigma(c - dt) \end{align*} where $\sigma(x) = (1 + \exp(-x))^{-1}$ is the logistic sigmoid function, also known as the expit function in statistics. I want an incredibly fast algorithm to find this, something that delivers $10^{-6}$ precision with one iteration or so.

Background and Motivation

In statistics & machine learning, there are many kinds of so-called (inverse) link functions which map a linear combination of covariates/features into a subset of $\mathbb{R}$. For example $\exp: \mathbb{R}\rightarrow \mathbb{R}_+$ and $\sigma: \mathbb{R} \rightarrow (0, 1)$, common inverse link functions for positive data and binary probabilities, respectively. I'm working on a class of numerical methods which, at some step in the process, need to find the fixed point of the inverse link function extremely quickly. Let's first look at the easier problem \begin{align*} t = \exp(c - dt) \end{align*} Replacing $z = dt$, \begin{align*} ze^{z} = de^{c} \end{align*} This functional equation is what defines the Lambert $W$ function, and therefore $z = W(de^c) \implies t = W(de^c)/d$. The Lambert $W$ function appears quite often in physics and complex analysis, and therefore has been studied very well and many methods have been implemented for this. (See, for example, apparently the fastest implementation for the Lambert $W$ function by Darko Veberic.)

I tried to mimic the derivation of the above implementation by Veberic, but encountered the following problems, mostly simply due to the fact that $\sigma$ does not have as nice of properties as $\exp$:

  1. To derive an initial approximation, Veberic performed a series expansion around $W^{-1}(z) = z e^z$ at its extrema, and then inverted. Unfortunately, such extrema do not exist with $\sigma$.
  2. Unlike the $\exp$, I cannot isolate my unknown variable to one side like $z e^z = de^c$.

Any help on this would be greatly appreciated!

$\endgroup$
  • 1
    $\begingroup$ Have you tried just applying one Newton step starting at $f(0)/(1-f(1)+f(0))$ (where the equation is $t=f(t)$)? $\endgroup$ – Ian Sep 11 at 17:10
  • $\begingroup$ Thanks @Ian, I have not, but how did you determine that initial position? $\endgroup$ – Tom Chen Sep 11 at 17:33
  • 1
    $\begingroup$ Note that the fixed point is in $(0,1)$ and thus take the approximation $f(t) \approx f(0)+(f(1)-f(0))t$ and set that approximation equal to $t$. (This is basically a secant method step with initial guesses 0 and 1; it should perform better than simply starting at $1/2$ all the time.) $\endgroup$ – Ian Sep 11 at 17:45
  • $\begingroup$ I tried this with $c=0,d=1$ and I got an answer with an error of about $3.5 \cdot 10^{-6}$. So maybe one iteration from this guess isn't quite enough for your needs, but perhaps two will suffice? $\endgroup$ – Ian Sep 11 at 18:15
  • $\begingroup$ Awesome, this sounds good. I'll try this out and maybe use a Halley iteration to see how much better the approximation is! $\endgroup$ – Tom Chen Sep 11 at 18:26
3
$\begingroup$

As in the comments I write $f(t)=\sigma(c-dt)$.

You can get a pretty fast method by just doing one Newton step starting from a relatively good guess. Since we know any fixed point must be in $\mathrm{range}(f)=(0,1)$, it is reasonable to start with a fixed point of some simple global approximation of $f$ on $(0,1)$. One is $g(t)=f(0)+(f(1)-f(0))t$. The fixed point of $g$ is $\frac{f(0)}{1-f(1)+f(0)}$. You can use that as an initial guess for Newton or Halley iteration and it should work pretty well because $f$ is reasonably nice, particularly if $d$ is not much larger than $c$.

Better guesses exist, using the information given about $f$ in more detail.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.