BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221027T161500
DTEND;TZID=Asia/Seoul:20221027T171500
DTSTAMP:20260418T084453
CREATED:20221012T134118Z
LAST-MODIFIED:20240705T171136Z
UID:6311-1666887300-1666890900@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Non-smooth and Hölder-smooth submodular optimization
DESCRIPTION: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 [(1−1/e)OPT−ϵ] 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 [(1/2)OPT−ϵ] 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 (1/2)OPT−ϵ. 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.\nJoint work with Duksang Lee and Nam Ho-Ngyuen.
URL:https://dimag.ibs.re.kr/event/2022-10-27/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
END:VCALENDAR