Return to Question

edited body

Source Link

edited Sep 2, 2015 at 23:49

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 S}{\text{argmin}} ~f(x).$$$$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$

Let us denote a minimizer of $f$ over $L$ as $$x^*_{\text{int}} \in \underset{x \in S}{\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$

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$

Source Link

asked Sep 2, 2015 at 19:03

Berk U.

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

$$ \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$