02/02/2021

Online DR-Submodular Maximization: Minimizing Regret and Constraint Violation

Prasanna Raut, Omid Sadeghi, Maryam Fazel

Keywords:

Abstract Paper Similar Papers

Abstract: In this paper, we consider online continuous DR-submodular maximization with linear stochastic long-term constraints. Compared to the prior work on online submodular maximization, our setting introduces the extra complication of stochastic linear constraint functions that are i.i.d. generated at each round. In particular, at each time step a DR-submodular utility function and a constraint vector, i.i.d. generated from an unknown distribution, are revealed after committing to an action and we aim to maximize the overall utility while the expected cumulative resource consumption is below a fixed budget. Stochastic long-term constraints arise naturally in applications where there is a limited budget or resource available and resource consumption at each step is governed by stochastically time-varying environments. We propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm to solve this class of online problems. We analyze the performance of the OLFW algorithm and we obtain sub-linear regret bounds as well as sub-linear cumulative constraint violation bounds, both in expectation and with high probability.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949132
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 19:35 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 13:32 
 0
 0
 0
 0
 11:59 
 0
 0
 0
 0
 18:32 
 0
 0
 0
 0
 4:35 
 0
 0
 0
 0
 2:10 
 0
 0
 0
 0
 16:23 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 15:18 
 1
 0
 0
 0
 12:46 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 14:18 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 5:37 
 0
 0
 0
 0
 17:31 
 0
 0
 0
 0
 12:38 
 0
 0
 0
 0
 11:59 
 0
 0
 0
 0
 8:57 
 0
 0
 0
 0
 11:21 
 0
 0
 0
 1
 5:54 
 1
 1
 1
 1
 3:09 
 0
 0
 0
 0
 20:54 
 0
 0
 0
 0
 15:53 
 0
 0
 0
 0
 13:50 
 0
 0
 0
 0
 13:40 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 15:09 
 0
 0
 0
 0
 15:23 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 13:54 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 7:36 
 0
 0
 0
 0
 3:48 
 0
 0
 0
 0
 24:43 
 0
 0
 0
 0
 3:20