Online Convex Optimization with Stochastic Constraints

Abstract

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.

This paper extends our own ArXiv reports arXiv:1604.02218 (by considering more general stochastic functional constraints) and arXiv:1702.04783 (by relaxing a deterministic Slater-type assumption to a weaker stochastic Slater assumption; refining proofs; and providing high probability performance guarantees). See Introduction section (especially footnotes 1 and 2) for more details of distinctions

References in corpus (4)

• Random matrices: Universality of local spectral statistics of non-Hermitian matrices
• Online Convex Optimization with Time-Varying Constraints
• Algorithms for stochastic optimization with functional or expectation constraints
• A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints

Cited by in corpus (9)

• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Almost surely constrained convex optimization
• Online Stochastic Optimization with Wasserstein Based Non-stationarity
• Optimal Convergence for Stochastic Optimization with Multiple Expectation Constraints
• Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectives
• Personalized Treatment Selection using Causal Heterogeneity
• Learning and Management for Internet-of-Things: Accounting for Adaptivity and Scalability
• Optimization-based Calibration of Simulation Input Models
• Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study