A derivative-free method for continuous submodular optimization

Abstract: Submodular functions are a classical concept of discrete optimization, that can also be extended to the continuous setting. In particular, the class of continuous submodular functions encompasses some nonconvex functions arising in natural language processing, which partly explains renewed interest for this topic in recent years.

In this talk, I will describe a derivative-free algorithm for continuous submodular optimization over compact sets, adapted from a classical framework for bound-constrained derivative-free optimization. The first part will focus on theoretical (complexity) guarantees for the proposed method, which departs from the general nonconvex setting. The second part will illustrate the practical performance of our algorithm on continuous submodular tasks. Time permitting, I will also discuss the discrete submodular case.

Mathematics

Audience: researchers in the topic

PIMS-CORDS SFU Operations Research Seminar