Why are log and exp considered 'expensive' computations in ML?

Question

In many resources/videos I see comments being made along the lines of "and we can see here that we have a logarithm/exponential so this will be an expensive computation to make." (such as with the sigmoid activation function for a NN). What is behind these statements?

A more specific example would be: what makes $e^{-x}$ so much different than something like $x^4$ or $4^x$ in a computer calculation?

Answer 1

To add to Lutz Lehmann's answer, you can look up the latency for the CPU instructions in this comprehensive table by Agner Fog. For example, on the Intel Ivy Bridge processors:

• FADD / FSUB (floating point add and subtract) both take 3 cycles
• FMUL (multiply) takes 5 cycles
• FDIV (divide) takes 10-24 cycles
• FYL2X ($y \cdot \log_2(x)$) takes 90-106 cycles
• F2XM1 ($2^x - 1$) takes about 68 cycles

To calculate the exponential with a base other than 2, you have to use a combination of the FYL2X and F2XM1 instructions. In addition to the reasons that Lutz stated, the IEEE-754 standard has pretty stringent requirements for how accurately transcendental functions have to be evaluated -- correct to the last bit and correct rounding. For many applications, this level of accuracy is completely unnecessary, and people will use approximations in software that take far fewer cycles than the built-in hardware instructions take. For example, this blog post shows how to quickly calculate an approximation to the exponential function if you're willing to trade off some accuracy. I gather than in ML it's also quite common to use lower precision floating point numbers -- just 32, 16, or even 8 bits -- instead of the full 64.

Answer 2

$\exp$, $\sin$, $\tan$ and their inverse and otherwise related functions are transcendental, defined by an infinite power series. Meaning it takes some effort to evaluate uniformly good approximations. This is done via argument simplification using the properties of these functions, and polynomial approximations, or using quotients of polynomials à la Padé approximation (but again shifted toward some kind of uniform convergence).

So indeed a sigmoid $\frac1{1+e^{-x}}$ should take some more cycles than for instance $\frac{0.5+\max(0,x)}{1+|x|}$.

Power functions are evaluated via $x^y=\exp(y\log(x))$ or some wrapper that removes parts that are simpler to compute, thus especially for non-integer $y$ more expensive than the exponential function.