Haotian Jiang: Minimizing Convex Functions with Integral/Rational Minimizers
This event is free and open to the publicAdd to Google Calendar
(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.