I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap [-10,10]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose coordinates are in the range $-10..10$, inclusive).

I'm interested in computing a non-trivial lower bound on the value of

$$\min_{\substack{x_1 \neq x_2 \\ x_1,x_2 \in X}} \big|~f(x_1) - f(x_2)~\big|$$

One possible approach is exhaustive search. Say there are $N = |X|$ distinct elements in the domain. Then I would compute $f(x)$ for each $x \in X$, and then calculate the difference between the $f(x_1)-f(x_2)$ for each pair of distinct values $(x_1,x_2) \in X$. This would require $N$ evaluations of $f$ and $N(N-1)$ operations between the values.

My questions are:

  1. Has someone has seen this type of problem before. I'd like to find out more about related problems, but I just don't know what are the right terms to look for in the literature.

  2. Is it possible to do better by exploiting properties of $f$? I'm looking to compute the "minimum difference in function values" for a functions such as $\log(1+\exp(-s^Tx))$ (i.e., convex, continuous, monotonically decreasing in $s^Tx$ where $s \in \mathbb{R}^d$; this is the logistic loss function that is optimized in machine learning applications).

  • 1
    $\begingroup$ I suspect that little or nothing can be done without any knowledge of $f$. I don't see off the top of my head if your properties yield something interesting. $\endgroup$
    – Raphael
    Mar 11 '15 at 20:17
  • 1
    $\begingroup$ Can you clarify what you mean by your second question? You give an example of the function $f(x)=\log(1+\exp(x))$, but this doesn't have the right type signature (or it is restricted to the special case $d=1$). What does monotonically non-decreasing mean when $X$ is not totally ordered, such as your example of $X$? What does continuous mean when $X$ is a discrete set? These terms are not well-defined. Perhaps you mean that you have a function $f:\mathbb{R}^d \to Y$ that is convex, continuous, and (something), and then you want to do optimization on $f$ restricted to the domain $X$? $\endgroup$
    – D.W.
    Mar 11 '15 at 21:58

You can certainly do better than $N(N-1)$: you can achieve $O(N \lg N)$ running time. Evaluate $f$ on every possible element of $x$, then sort the resulting values, and look at the gap between consecutive values. The smallest such gap is exactly the value of $\min |f(x_1)-f(x_2)|$.

As Raphael says, without any information about $f$, it seems unlikely that you can do any better than to evaluate $f$ on every possible input. Indeed, it seems possible to prove this using an adversarial argument, in a black-box setting: if there is a single value $x^*$ where you haven't evaluated $f(x^*)$, then any answer your algorithm outputs can be made to be wrong by choosing the value of $f(x^*)$ appropriately.

Since the notion of "monotonically non-decreasing" is not defined when the domain is not totally ordered (as in your example for $X$), and the notion of continuous is not defined when the domain is discrete (i.e., not continuous, as in your example for $X$), your second question isn't well-formed and can't be answered in its current state.

  • $\begingroup$ Thank you for this! You are right, the monotonically non-decreasing in $x$ did not make sense. I didn't remove it so that you wouldn't have to edit the answer. $\endgroup$
    – Berk U.
    Mar 13 '15 at 22:54
  • $\begingroup$ @BerkU., thank you for thinking of that, but please feel free to edit your question to make the question make more sense or match what you want more closely; don't worry about my answer. If you edit your question, I'll edit my answer accordingly -- it's more important that your question be useful to you. $\endgroup$
    – D.W.
    Mar 13 '15 at 23:52

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.