HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Online Non-Monotone DR-Submodular Maximization

Abstract : In this paper, we study fundamental problems of maximizing DR-submodular continuous functions that have real-world applications in the domain of machine learning, economics, operations research and communication systems. It captures a subclass of non-convex optimization that provides both theoretical and practical guarantees. Here, we focus on minimizing regret for online arriving non-monotone DRsubmodular functions over down-closed and general convex sets. First, we present an online algorithm that achieves a 1/e-approximation ratio with the regret of O(T3/4) for maximizing DR-submodular functions over any down-closed convex set. Note that, the approximation ratio of 1/e matches the best-known offline guarantee. Next, we give an online algorithm that achieves an approximation guarantee (depending on the search space) for the problem of maximizing non-monotone continuous DR-submodular functions over a general convex set (not necessarily downclosed). Finally we run experiments to verify the performance of our algorithms on problems arising in machine learning domain with the real-world datasets.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03170034
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Monday, March 15, 2021 - 11:08:52 PM
Last modification on : Monday, December 13, 2021 - 9:17:20 AM
Long-term archiving on: : Wednesday, June 16, 2021 - 7:34:02 PM

File

AAAI2021_NKT_AS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03170034, version 1

Citation

Kim Thang Nguyen, Abhinav Srivastav. Online Non-Monotone DR-Submodular Maximization. 35th AAAI Conference on Artificial Intelligence (AAAI-2021), Feb 2021, Vancouver (virtual), Canada. ⟨hal-03170034⟩

Share

Metrics

Record views

47

Files downloads

41