Timezone: »
Poster
A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints
Omid Sadeghi · Prasanna Raut · Maryam Fazel
In this paper, we consider an online optimization problem in which the reward functions are DRsubmodular, and in addition to maximizing the total reward, the sequence of decisions must satisfy some convex constraints on average. Specifically, at each round $t\in\{1,\dots,T\}$, upon committing to an action $x_t$, a DRsubmodular utility function $f_t(\cdot)$ and a convex constraint function $g_t(\cdot)$ are revealed, and the goal is to maximize the overall utility while ensuring the average of the constraint functions $\frac{1}{T}\sum_{t=1}^T g_t(x_t)$ is nonpositive. Such cumulative constraints arise naturally in applications where the average resource consumption is required to remain below a prespecified threshold. We study this problem under an adversarial model and a stochastic model for the convex constraints, where the functions $g_t$ can vary arbitrarily or according to an i.i.d. process over time slots $t\in\{1,\dots,T\}$, respectively. We propose a single algorithm which achieves sublinear (with respect to $T$) regret as well as sublinear constraint violation bounds in both settings, without prior knowledge of the regime. Prior works have studied this problem in the special case of linear constraint functions. Our results not only improve upon the existing bounds under linear cumulative constraints, but also give the first sublinear bounds for general convex longterm constraints.
Author Information
Omid Sadeghi (University of Washington)
Prasanna Raut (University of Washington)
Maryam Fazel (University of Washington)
Related Events (a corresponding poster, oral, or spotlight)

2020 Spotlight: A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints »
Fri. Dec 11th 03:20  03:30 AM Room Orals & Spotlights: Optimization
More from the Same Authors

2022 : On the Global Convergence of the Regularized Generalized GaussNewton Algorithm »
Vincent Roulet · Maryam Fazel · Siddhartha Srinivasa · Zaid Harchaoui 
2022 Poster: Learning in Congestion Games with Bandit Feedback »
Qiwen Cui · Zhihan Xiong · Maryam Fazel · Simon Du 
2022 Poster: NearOptimal Randomized Exploration for Tabular Markov Decision Processes »
Zhihan Xiong · Ruoqi Shen · Qiwen Cui · Maryam Fazel · Simon Du 
2021 Poster: Selective Sampling for Online Bestarm Identification »
Romain Camilleri · Zhihan Xiong · Maryam Fazel · Lalit Jain · Kevin Jamieson 
2021 Poster: Towards Sampleefficient Overparameterized Metalearning »
Yue Sun · Adhyyan Narang · Ibrahim Gulluk · Samet Oymak · Maryam Fazel 
2019 Poster: Escaping from saddle points on Riemannian manifolds »
Yue Sun · Nicolas Flammarion · Maryam Fazel 
2016 Poster: Designing smoothing functions for improved worstcase competitive ratio in online optimization »
Reza Eghbali · Maryam Fazel 
2016 Poster: Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models »
Amin Jalali · Qiyang Han · Ioana Dumitriu · Maryam Fazel 
2012 Poster: Structured learning of Gaussian graphical models »
Karthik Mohan · Michael J Chung · Seungyeop Han · Daniela Witten · SuIn Lee · Maryam Fazel