Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points

Question

I am currently working on a problem where I have to minimize a $m$-strongly convex function $$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$ over a bounded integer lattice, $$L = \mathbb{Z}^n \cap [-10,10]^n \\$$

Let us denote a minimizer of $f$ over $L$ as $$x^*_{\text{int}} \in \underset{x \in L}{\text{argmin}} ~f(x).$$ I am wondering: is it possible to exploit the strong convexity to produce a lower bound on the difference between $f(x^*_{\text{int}})$ and the value of $f$ at any other (suboptimal) point $x \in L$. That is, can we produce a lower bound on the value of:

$$ \min_{x \in V} ~f(x) - f(x^*_{\text{int}})$$

where, $$V = L \setminus \underset{x\in L}{\text{argmin}} ~f(x)$$

I suspect that that answer is yes, but I am having difficulty deriving the bound. Aside from strong convexity, some other facts that may help are that:

• $\|x-x^*_{\text{int}}\| \geq 1 $ for all for all points $x \in V$
• $f$ is infinitely differentiable over $\mathbb{R}^d$
• $f$ has Lipschitz continuous gradient over $L$

Answer 1

Unfortunately, no. Here is an example for $n=1$ (1-dimension). For parameters $m>0$, $b\in\mathbb{R}$ define:
$$f(x) = (m/2)(x-b)^2 $$ For any $b \in \mathbb{R}$, this function $f$ is strongly convex with modulus $m$.

Now fix $\epsilon \in (0, 1/2)$ and define $b = 1/2 - \epsilon$. Then the minimizer of $f(x)$ over the integers is $x^*_{int} = 0$, and: $$ f(1) - f(0) = (m/2)(1/2+\epsilon)^2 - (m/2)(1/2-\epsilon)^2 = m \epsilon$$ and this value can be arbitrarily small (for fixed $m$) by choosing $\epsilon$ arbitrarily small.

---

You can generalize to $n$ dimensions by defining: $$f(x_1, \ldots, x_n) = \sum_{i=1}^n (m/2)(x_i-b)^2 $$