15
$\begingroup$

Suppose we have a function $f : \mathbb{R}^N \rightarrow \mathbb{R}$ which, given a vector, returns the value of its smallest element. How can I approximate $f$ with a differentiable function(s)?

$\endgroup$
3
  • $\begingroup$ The tag of the question is probably wrong. Sorry for that. $\endgroup$
    – eakbas
    Aug 11, 2010 at 5:45
  • $\begingroup$ Are these the real numbers $\mathbb{R}$? $\endgroup$
    – Amir Sagiv
    Aug 11, 2016 at 21:43
  • $\begingroup$ @AmirSagiv yes, they are. $\endgroup$
    – eakbas
    Aug 12, 2016 at 3:29

5 Answers 5

12
$\begingroup$

If signs aren't a big deal, use the generalized mean formula

$$ \left(\frac{1}{n}\sum x_i^k\right)^{1/k} $$

for $k\to -\infty$.

$\endgroup$
5
  • $\begingroup$ Nice, but you probably want to get rid of 1/n so that the result is as close to the smallest x_i as possible? $\endgroup$
    – Neil
    Aug 11, 2010 at 7:42
  • $\begingroup$ @Neil: The $1/n$ normalization is the standard one since it gives exactly what you want when all the $x_i$ are equal. But in fact if $n$ is fixed and $k$ approaches negative infinity, it doesn't matter asymptotically what constant you put inside the parentheses. $\endgroup$
    – Tracy Hall
    Aug 11, 2010 at 8:28
  • 4
    $\begingroup$ Since the function is piecewise linear, probably the most efficient smooth approximation is just by convolution with standard mollifiers $\epsilon^-n \rho(x/\epsilon)$, this simply 'rounds the corners' and leaves the function unchanged at most points. But the OP should really clarify what he needs. $\endgroup$ Aug 11, 2010 at 11:10
  • $\begingroup$ is this function concave? $\endgroup$ Sep 2, 2018 at 2:51
  • $\begingroup$ Is there a proper way to patch this so it doesn't fail with zero valued inputs? $\endgroup$
    – Mastiff
    Nov 1, 2021 at 20:36
14
$\begingroup$

A smooth approximation is $f(x) = -\frac{1}{\rho}\log \sum_i e^{-\rho x_i} $. The larger $\rho>0$, the closer the approximation is to the minimum.

$\endgroup$
7
  • $\begingroup$ To get the proper normalization I think you actually want to replace sum_i with (1/n)sum_i, similar to Aaron Bergman's answer. I just tried it with sum vs mean inside the logarithm, and mean gave me much closer to the minimum, quantitatively. $\endgroup$
    – Kevin Holt
    Feb 1, 2017 at 18:36
  • $\begingroup$ I'm not sure. If there are many values $x_i$ which are large, their exponentials will be small, and the mean will increase beyond the minimum. I think the discussion in the other answer is similar. $\endgroup$
    – Pait
    Feb 2, 2017 at 17:52
  • $\begingroup$ Yes, but if there are many values $x_i$ that are close to the minimum, then the unnormalized version gives $f(x) < \min(x)$ which really has no useful interpretation, whereas in the normalized version when the mean increases beyond the minimum that can be interpreted as a compromise between the true minimum and the other values that are above the minimum. $\endgroup$
    – Kevin Holt
    Feb 13, 2017 at 21:09
  • $\begingroup$ I added this as a separate answer with a more in-depth argument. $\endgroup$
    – Kevin Holt
    Feb 13, 2017 at 21:10
  • $\begingroup$ The expression without the $1/n$ factor is always larger than the minimum. This is a problem if there are many points near the minimum - the approximation becomes too conservative. On the other hand the expression with the $1/n$ factor will become smaller than the minimum if there are many points larger than the minimum, which may make it less desirable. $\endgroup$
    – Pait
    Feb 14, 2017 at 22:50
6
$\begingroup$

I would use $$f(x) = -\frac{1}{\rho}\log \frac{1}{N} \sum_{i=1}^N e^{-\rho x_i},$$ which approaches $f(x) \rightarrow \min_i |x_i|$ as $\rho \rightarrow +\infty$.

There has been some debate about normalization, so let's compare these four: $$f_{A}(x) = -\frac{1}{\rho}\log \frac{1}{N}\sum_{i=1}^N e^{-\rho x_i} $$ $$f_{B}(x) = -\frac{1}{\rho}\log \sum_{i=1}^N e^{-\rho x_i} $$ $$f_C(x) = \left(\frac{1}{N}\sum x_i^{-\rho}\right)^{-1/\rho}$$ $$f_D(x) = \left(\sum x_i^{-\rho}\right)^{-1/\rho}$$

For $x$=[1,2,3,4,5] and $\rho=10$, $f_A=1.16$, $f_B=1.0$, $f_C=1.1745$, $f_D=1.0$.

For $x$=[1,2,3,4,5] and $\rho=100$, $f_A=1.016$, $f_B=1.0$, $f_C=1.0162$, $f_D=1.0$.

For $x$=[1,1,1,1,1] and $\rho=10$, $f_A=1$, $f_B=0.8391$, $f_C=1$, $f_D=0.8513$.

For $x$=[1,1,1,1,1] and $\rho=100$, $f_A=1$, $f_B=0.9839$, $f_C=1$, $f_D=0.9840$.

For $x$=[0,1,10,100,1000] and $\rho=10$, $f_A=0.1609$, $f_B=0$, $f_C=0$, $f_D=0$.

For $x$=[0,1,10,100,1000] and $\rho=100$, $f_A=0.0161$, $f_B=0$, $f_C=0$, $f_D=0$.

(For the last two cases, $f_C$ and $f_D$ can be evaluated by using $\log(0)=\infty$ and $\infty^{-1/\rho}=0$).

So as we would hope, when $\rho$ is large, all versions give reasonably good approximations to the minimum.

The question then is which is best when $\rho$ is not that big -- this is an important question since large $\rho$ can give practical difficulties with finite precision arithmetic. Comparing the four versions above, we can see that the mean versions (A and C) overestimate the minimum when $x$ has a lot of values above the minimum. Conversely, the sum versions (B and D) underestimate the minimum when $x$ has a lot of values that are all equal to the minimum. Which is better is ultimately a question of your application. But to me, the mean version gives an answer that makes much more sense. The approximate minimum should be similar to the minimum but the approximation should get pulled in the direction of all of the individual values in $x$. This is what happens in the mean version (A and C), which also keep the approximate minimum inside the range of the data, i.e. $$\min(x) \le f_A(x) , f_C(x) \le \max(x)$$ On the other hand, the sum versions (B and D) can give a minimum value that is actually lower than any value contained in the data (see the third and fourth examples above). In other words, it is possible that $$f_B(x), f_D(x) < \min(x),$$ which is a property I want to avoid in an approximate minimum since it makes it very hard to interpret that approximate-minimum value. So I find A,C to be more useful than B,D.

The last question is A vs C. Version A is fairly stable as $x_i \rightarrow 0$, but version C however runs out of precision. For example $x^{-100}$ overflows double precision below $x \approx 8.27e^{-4}$ and overflows single precision below $x \approx 0.412$.

Therefore, at least in my own uses, $f_A$ gives the most useful approximation and is the most numerically stable.

Edit: For practical implementation, note that instead of directly aggregating the raw values $x$, you can also instead do the aggregation relative to some arbitrary value $\mu$, without analytically changing the result: $$\mu + f_A\left(x-\mu\right) = f_A$$ $$\mu + f_B\left(x-\mu\right) = f_B$$ $$\mu f_C\left(x / \mu\right) = f_C$$ $$\mu f_D\left(x / \mu\right) = f_D$$ The end result is unchanged (aside from numerical issues), but a clever choice of $\mu$ can help improve numerical stability. Specifically, if possible I would recommend using the true minimum, $\mu = \min(x)$, which gives $$\begin{aligned} \hat{f}_A\left(x\right) &= f_A\left(x-\min(x)\right) + \min(x) \\ &= \min(x) -\frac{1}{\rho}\log \frac{1}{N}\sum_{i=1}^N e^{-\rho \left(x_i - \min(x)\right)} \end{aligned}$$ The other versions can also be modified similarly. You can probably do similar tricks when calculating the derivative.

$\endgroup$
3
  • $\begingroup$ Is there a trick to normalize this to avoid underflow? With even a modest sized p, exp(-p*x) can go to zero in a computer. In your example will be an entry exp(-100*1000). $\endgroup$
    – Mastiff
    Nov 1, 2021 at 20:58
  • $\begingroup$ Yep! Good question, I just edited the answer with that detail. Note that as long as values near the minimum don't underflow, then it's OK if values far from the minimum do underflow - because they aren't really contributing to the sum anyway. E.g. in my specific example, exp(-100*1000) is dwarfed by exp(-0), so the underflow for x=100 isn't really a problem. But if the minimum value is 100 then yeah underflow would kill you with the naive equations. Anyway check out my edit and hopefully that helps. $\endgroup$
    – Kevin Holt
    Nov 3, 2021 at 2:56
  • $\begingroup$ Thanks. I did think of that, but I'm using this for a machine learning application, and I'm not sure if I've solved my differentiable function problem if the overall solution still requires a non-differentiable component. It seems likely that the double use of the min() would fall out in the overall autodiff, but I'm not certain. $\endgroup$
    – Mastiff
    Nov 5, 2021 at 15:20
5
$\begingroup$

For two dimensions, we have $\min(x,y) = \tfrac{1}{2}(x+y-|x-y|)$, so you just need a differentiable approximation to $x \mapsto |x|$. Then for higher dimensions we have $\min(x,y,z) = \min(x, \min(y,z))$, etc.

$\endgroup$
3
  • $\begingroup$ and is there a good analytical approximation to $|x|$? $\endgroup$
    – Amir Sagiv
    Aug 12, 2016 at 12:15
  • 4
    $\begingroup$ Bernstein, S. N. "Sur la meilleure approximation de |x| par les polynomes de degrés donnés." Acta Math. 37, 1-57, 1913. $\endgroup$ Aug 12, 2016 at 14:39
  • 2
    $\begingroup$ For instance $\sqrt{\epsilon +x^2}$ $\endgroup$ Feb 13, 2017 at 21:08
1
$\begingroup$

What about $f: [x_1 \dots\ x_n] \mapsto \frac{1}{\sum_i x_i^{-1}}$?

$\endgroup$
3
  • $\begingroup$ I see a small problem if any of the $x_i$ is nonpositive. $\endgroup$
    – Pait
    Jun 27, 2013 at 22:07
  • $\begingroup$ @pait: +1, you may want to add this comment to the accepted answer as well? $\endgroup$
    – Neil
    Jun 28, 2013 at 1:33
  • $\begingroup$ Well the accepted answer states that it's only applicable to absolute values, and 0 is not a problem in the formula with squares. It seems that to achieve smoothness it is more practical to work with exponentials. $\endgroup$
    – Pait
    Jun 28, 2013 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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