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: 


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