For minimizing a general convex function with access to a separation oracle, it is generally impossible to design a strongly polynomial-time algorithm. However, the situation improves when the convex function has an integer minimizer. This paper assumes that we are given a separation oracle for a convex function defined on ℝⁿ with an integral minimizer inside a box with radius R, and then presents an algorithm to find an exact minimizer thereof with either O(n(n log log(n)/log(n) + log(R))) calls to the oracle requiring poly(n,log(R)) arithmetic operations or O(nlog(nR)) calls and exp(O(n)) ⋅ poly(log(R)) arithmetic operations. The authors overcome the previous bottleneck by formulating a direct reduction to the shortest vector problem in lattices, thereby reducing the dimension.

This is a significant advancement particularly because the assumption of the presence of an integer minimizer is a natural assumption satisfied by many optimization problems, including submodular function minimization (SFM). Furthermore, for SFM, the above result readily “implies a strongly polynomial algorithm that makes at most O(n³ log log (n)/log(n)) calls to an evaluation oracle, and an exponential time algorithm that makes at most (O(n² log(n))) calls to an evaluation oracle.”

A final note: despite its favorable “oracle complexity,” the running time of this algorithm is quite high as it uses costly methods/algorithms as sub-routines. In a follow up work (currently available in arXiv), the author (along with some other collaborators) claims to have made a significant improvement thereon.