Non-monotone DR-submodular Maximization over General Convex Sets - Université d'Évry Access content directly
Conference Papers Year : 2021

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.

Dates and versions

hal-02980471 , version 1 (27-10-2020)

Identifiers

Cite

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 {IJCAI-PRICAI-20}, Jan 2021, Yokohama, Japan. pp.2148--2154, ⟨10.24963/ijcai.2020/297⟩. ⟨hal-02980471⟩
117 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More