For a matrix $W \in \mathbb{ Z}^{ m \times n}$, $m \leq n$, and a convex function $g: \mathbb{ R}^m \rightarrow \mathbb{ R}$, we are interested in minimizing $f(x) = g(Wx)$ over the set $\{ 0,1\}^n$. We will study separable convex functions and sharp convex functions $g$. Moreover, the matrix $W$ is unknown to us. Only the number of rows $m \leq n$ and $\|W\|_{ \infty}$ is revealed. The composite function $f(x)$ is presented by a zeroth and first order oracle only. Our main result is a proximity theorem that ensures that an integral minimum and a continuous minimum for separable convex and sharp convex functions are always "close" by. This will be a key ingredient to develop an algorithm for detecting an integer minimum that achieves a running time of roughly $(m \| W \|_{ \infty})^{ \mathcal{ O}(m^3)} \cdot \text{ poly}(n)$. In the special case when $(i)$ $W$ is given explicitly and $(ii)$ $g$ is separable convex one can also adapt an algorithm of Hochbaum and Shanthikumar. The running time of this adapted algorithm matches with the running time of our general algorithm.
Categories: math.OC cs.DM