Sponsored by
[ Events ]

Activity Search
Sort out
Korea-Taiwan-Vietnam Joint Seminar in Combinatorics and Analysis
15:00 - 16:00, March 3, 2023 (Friday)
Zoom, Online seminar
(線上演講 Zoom)
Non-smooth, Holder-smooth, and Robust Submodular Maximization
Dabeen Lee (Korea Advanced Institute of Science and Technology)


We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an guarantee when the function is monotone and Hölder-smooth, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least . For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is Hölder-smooth, for which we may apply both the continuous greedy method and the mirror-prox method. 

Link Information: https://us02web.zoom.us/j/87167950828?pwd=UFpHTkcwaDZWTndsRGloRE5yN2tIdz09

Zoom Meeting ID: 871 6795 0828
Passcode: 352266


back to list  
(C) 2021 National Center for Theoretical Sciences