Haotian Jiang: Minimizing Convex Functions with Integral/Rational Minimizers

Given a separation oracle $SO$ for a convex function $f$ defined on $\mathbb{R}^n$ that has an integral minimizer inside a box with radius $R$, we show how to find an exact minimizer of $f$ using at most

(1) $O(n (n \log \log (n)/\log (n) + \log(R)))$ calls to $SO$ and $\poly(n, \log(R))$ arithmetic operations, or
(2) $O(n \log(nR))$ calls to $SO$ and $\exp(O(n)) \cdot \poly(\log(R))$ arithmetic operations.

When the set of minimizers of $f$ has integral extreme points, our algorithm outputs an integral minimizer of $f$. This improves upon the previously best oracle complexity of $O(n^2 (n + \log(R)))$ for polynomial time algorithms and $O(n^2\log(nR))$ for exponential time algorithms obtained by [Gr\”otschel, Lov\’asz and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. Our improvement on Gr\”otschel, Lov\’asz and Schrijver’s result generalizes to the setting where the set of minimizers of $f$ is a rational polyhedron with bounded vertex complexity.

For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most $O(n^3 \log \log (n)/\log (n))$ calls to an evaluation oracle, and an exponential time algorithm that makes at most $O(n^2 \log(n))$ calls to an evaluation oracle. These improve upon the previously best $O(n^3 \log^2(n))$ oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, V\’egh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity $O(n^3 \log(n))$ given in the former work.

From the perspectives of first-order optimization or parallel depth complexity, our algorithm for SFM is the best possible (up to polylog) due to the recent lower bounds of [Chakrabarty, Lee, Sidford and Wong, STOC 2017] and [Chakrabarty, Graur, Jiang and Sidford, Manuscript 2022]. The question of proving a matching evaluation oracle complexity lower bound, however, remains open.