# Lower bound the difference between distinct values of a function over a discrete domain?

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).

• 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. – Raphael Mar 11 '15 at 20:17
• 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$? – 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.
• 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. – Berk U. Mar 13 '15 at 22:54