Online Convex Optimization with Stochastic Constraints

By Hao Yu, Michael J. Neely, Xiaohan Wei. 2017

269 citations recorded by the source corpus.

This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special cases, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves $O(\sqrt{T})$ expected regret and constraint violations and $O(\sqrt{T}\log(T))$ high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

The Ideal Continual Learner: An Agent That Never Forgets (2023, methodology): “Inspired by classic works on adaptive filtering (Haykin, 2002) and recursive least-squares (Singhal & Wu, 1989) in signal processing, Zeng et al. (2019) proposed to set the projection matrix to be I − (X 1 )> ( X (j) 1 (X (j) 1 ) > + λI )−1 X (j) 1 for the task 1 and update it for later tasks as in ”
A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints (2019, methodology): “in [25], Xu in [24], and Nedic and Ozdaglar in [23].”
Conservative Stochastic Optimization With Expectation Constraints (2020, methodology): “The parameters for the G-OCO algorithm [cf. Algorithm 1 [25]] were tuned in a similar manner, resulting in α = 2 .”