Search Mailing List Archives
[theory-seminar] Fwd: Haotian Jiang Presenting Tomorrow 4:00PM
Aaron Sidford
sidford at stanford.edu
Tue May 31 21:08:16 PDT 2022
Hi all,
I thought this talk might be of interest to many of you.
All the best,
Aaron
---------- Forwarded message ---------
From: Aaron Sidford <sidford at stanford.edu>
Date: Tue, May 31, 2022 at 9:03 PM
Subject: Haotian Jiang Presenting Tomorrow 4:00PM
To: <algorithms-and-optimization at lists.stanford.edu>
Cc: Haotian Jiang <jhtdavid96 at gmail.com>
Hi all,
Tomorrow we will have the last group meeting of the quarter at 4:00PM in
Huang 305. Haotian Jiang <https://jhtdavid96.wixsite.com/jianghaotian> is
visiting from the University of Washington and will be presenting some
exciting work on "Minimizing Convex Functions with Integral/Rational
Minimizers" (abstract at the end of the email).
I hope the quarter is wrapping up well for all of you and I look forward to
seeing you tomorrow!
All the best,
Aaron
*Title: Minimizing Convex Functions with Integral/Rational Minimizers*
*Abstract: **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, 2022]. The question of
proving a matching evaluation oracle complexity lower bound, however,
remains open. *
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220531/c4bf1b61/attachment.html>
More information about the theory-seminar
mailing list