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 <>
Submitted on : Monday, March 15, 2021 - 11:08:52 PM
Last modification on : Thursday, July 1, 2021 - 11:04:07 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

38

Files downloads

46