Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback

Yeongjong KimarXiv 2023 · DOI · arXiv

TL;DR

This paper introduces a novel algorithm for online convex optimization with stochastic constraints that achieves zero constraint violation in expectation while maintaining sublinear regret. It also extends this approach to a bandit feedback setting, offering improved performance over prior work.

What Problem Does This Paper Address?

Online Convex Optimization (OCO) is a powerful framework for sequential decision-making under uncertainty, widely used in areas like portfolio management and recommendation systems. A key challenge in OCO is dealing with constraints that must be satisfied over time, especially when these constraints are "stochastic" (i.e., they depend on random factors). Traditional methods often struggle to guarantee both minimal regret (performing close to an optimal static solution) and zero constraint violation simultaneously, especially when feedback is limited (like in bandit settings). This paper tackles the problem of achieving zero constraint violation in expectation while bounding regret, and importantly, doing so in a way that is oblivious to the total time horizon, which is a significant improvement over existing methods.

Methods

The core of the paper's contribution lies in a modified "drift-plus-penalty" (DPP) algorithm, which they call Conservative Drift-Plus-Penalty (CDPP). The key innovations are:

  • Time-Varying Parameters: Unlike previous DPP algorithms that used fixed parameters, CDPP employs time-varying step-size and penalty parameters. This allows for more adaptive behavior and is crucial for achieving zero constraint violation.
  • Conservatism Parameter ($\gamma_t$): A novel "conservatism" parameter is introduced in the dual update. This parameter effectively adds an extra layer of caution to satisfy constraints, leading to improved constraint violation bounds.
  • Novel Drift Lemma: The theoretical underpinnings rely on a new "drift lemma" that provides time-varying bounds on the virtual queue drift. This is essential for analyzing the algorithm's performance with time-varying parameters.
  • Bandit Feedback Extension: The CDPP framework is adapted to a two-point bandit feedback setting. This means the algorithm can learn and perform well even when it only observes function values at a few points per iteration, rather than full gradients. This adaptation involves using gradient estimates derived from these limited observations.

Datasets

  • Electricity Market Price Data: The authors use electricity cost data from the New York ISO, collected over 15 zones every 5 minutes for a period of about 1.5 months. This data is used to simulate an online scheduling problem.
  • Synthetically Generated Cost Vectors: For a second set of experiments, they generate 100,000 cost vectors sampled from a normal distribution, which are then projected onto a specific range. This setup is used to test the algorithms under a stochastic loss function scenario.

Key Insights and Ideas

  • Time-Varying Parameters are Key: The paper demonstrates that making algorithm parameters (like step size and penalty) dependent on time is not just an academic exercise but a critical component for achieving theoretical guarantees like zero constraint violation.
  • Conservatism Pays Off: Introducing a "conservatism" parameter in the dual update is a clever way to directly influence constraint satisfaction, showing that a more cautious approach to constraints can lead to better outcomes without sacrificing too much performance.
  • Bandit Adaptation is Feasible: The successful extension to the bandit setting highlights the robustness of the DPP framework and its adaptability to scenarios with limited information feedback. This is crucial for real-world applications where obtaining full gradients might be expensive or impossible.
  • Obliviousness to Horizon is a Practical Advantage: An algorithm that doesn't need to know the total number of iterations beforehand is more flexible for practical deployment, as the duration of the problem might not be known in advance.

Key Results

  • Zero Constraint Violation: The proposed CDPP algorithm achieves zero constraint violation in expectation for both the full information and bandit feedback settings.
  • Sublinear Regret: The algorithm guarantees an expected regret of $O(\sqrt{T})$, which is a standard and desirable bound in online learning.
  • Improved Bandit Performance: For the two-point bandit feedback setting, the CDPP adaptation offers better bounds on regret and constraint violation compared to prior work (specifically, Cao and Liu [7]).
  • Numerical Validation: Experiments on both real-world electricity market data and synthetic data confirm the theoretical findings, showing that increasing the conservatism parameter reduces constraint violation while keeping regret at acceptable levels.

Limitations and Future Work

  • Dependence on Dimension (Bandit Setting): The analysis for the bandit setting shows some dependence on the dimension of the decision space, which is a common challenge in high-dimensional bandit problems.
  • Theoretical vs. Practical Parameter Tuning: While the algorithm is oblivious to the total horizon $T$, the theoretical analysis relies on specific choices of parameters (like $C$) that might require careful tuning in practice.
  • Future Work: The paper suggests extending the framework to multiple constraints and exploring more general bandit feedback models. The numerical experiments also hint at the impact of irregular changes in cost vectors, which could be a direction for further investigation.

Summary updated

Abstract

This paper studies online convex optimization with stochastic constraints. We propose a variant of the drift-plus-penalty algorithm that guarantees $O(\sqrt{T})$ expected regret and zero constraint violation, after a fixed number of iterations, which improves the vanilla drift-plus-penalty method with $O(\sqrt{T})$ constraint violation. Our algorithm is oblivious to the length of the time horizon $T$, in contrast to the vanilla drift-plus-penalty method. This is based on our novel drift lemma that provides time-varying bounds on the virtual queue drift and, as a result, leads to time-varying bounds on the expected virtual queue length. Moreover, we extend our framework to stochastic-constrained online convex optimization under two-point bandit feedback. We show that by adapting our algorithmic framework to the bandit feedback setting, we may still achieve $O(\sqrt{T})$ expected regret and zero constraint violation, improving upon the previous work for the case of identical constraint functions. Numerical results demonstrate our theoretical results.
BibTeX
@misc{kim2023online,
  author = {Yeongjong Kim},
  title = {{Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback}},
  year = {2023},
  eprint = {2301.11267},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.11267},
}
Figure