Skip to Main content Skip to Navigation
Conference papers

Non-monotone DR-submodular Maximization over General Convex Sets

Abstract : Many real-world problems can often be cast as the optimization of DR-submodular functions defined over a convex domain. These functions play an important role with applications in many areas of applied mathematics, such as machine learning, computer vision, operation research, communication systems or economics. In addition, they capture a subclass of non-convex optimization that provides both practical and theoretical guarantees. In this paper, we show that for maximizing non-monotone DR-submodular functions over a general convex set (such as up-closed convex sets, conic convex set, etc) the Frank-Wolfe algorithm achieves an approximation guarantee which depends on the convex set. To the best of our knowledge, this is the first approximation guarantee. Finally we benchmark our algorithm on problems arising in machine learning domain with the real-world datasets.
Document type :
Conference papers
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02980471
Contributor : Christoph Dürr <>
Submitted on : Tuesday, October 27, 2020 - 2:56:48 PM
Last modification on : Wednesday, November 18, 2020 - 5:23:09 PM

Links full text

Identifiers

Citation

Christoph Dürr, Kim Thang Nguyen, Abhinav Srivastav, Léo Tible. Non-monotone DR-submodular Maximization over General Convex Sets. Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence , Jan 2021, Yokohama, Japan. pp.2148--2154, ⟨10.24963/ijcai.2020/297⟩. ⟨hal-02980471⟩

Share

Metrics

Record views

23


Données de recherche