[Theory] UC Theory Seminar

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, February 27, 3:30pm
Location: Ryerson 251

SPEAKER: Haotian Jiang  (Microsoft Research/UChicago)

TITLE: Sparse Submodular Function Minimization

ABSTRACT: We discuss the problem of minimizing a submodular function (defined on an n-element ground set) that is guaranteed to have a k-sparse minimizer. I will present a weakly polynomial time parallel algorithm with \poly(k)-depth and a strongly polynomial time algorithm that makes n \poly(k) queries to an evaluation oracle. When k is small, our algorithms have sub-linear parallel depth or sub-quadratic evaluation oracle query complexities. All previous algorithms for this problem have at least linear parallel depth and make at least a quadratic number of queries. 

In contrast to state-of-the-art weakly- and strongly-polynomial time algorithms for SFM that all apply cutting plane methods, our algorithms use first-order methods. We introduce what we call sparse dual certificates, which encode information on the sparse minimizers, and our algorithms provide new algorithmic tools for allowing first-order optimization methods to efficiently compute them. 

This talk is based on joint work with Andrei Graur and Aaron Sidford, both from Stanford University. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240220/f84d947c/attachment.html>