BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//132.216.98.100//NONSGML kigkonsult.se iCalcreator 2.20.4//
BEGIN:VEVENT
UID:20250916T022555EDT-8190a2jZjC@132.216.98.100
DTSTAMP:20250916T062555Z
DESCRIPTION:Title: Optimal approximation for unconstrained non-submodular m
 inimizationOptimal approximation for unconstrained non-submodular minimiza
 tion\n\nAbstract:Submodular function minimization is well studied\, and ex
 isting algorithms solve it exactly or up to arbitrary accuracy. However\, 
 in many applications\, such as structured sparse learning or batch Bayesia
 n optimization\, the objective function is not exactly submodular\, but cl
 ose. In this case\, no theoretical guarantees exist. Indeed\, submodular m
 inimization algorithms rely on intricate connections between submodularity
  and convexity. We show how these relations can be extended to obtain appr
 oximation guarantees for minimizing non-submodular functions\, characteriz
 ed by how close the function is to submodular. We also extend this result 
 to noisy function evaluations. Our approximation results are the first for
  minimizing non-submodular functions\, and are optimal\, as established by
  our matching lower bound.\n\n \n\nFor Zoom meeting information please con
 tact tim.hoheisel [at] mcgill.ca\n
DTSTART:20210208T210000Z
DTEND:20210208T220000Z
SUMMARY:Marwa El Halabi\, MILA
URL:/mathstat/channels/event/marwa-el-halabi-mila-3279
 57
END:VEVENT
END:VCALENDAR