Research map / Bandits and online learning / Online convex optimization and games
Online Convex Optimization with Stochastic Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use virtual queues and drift-plus-penalty updates, with V = \sqrt{T} and \alpha = T | OCO with stochastic constraints · OCO with stochastic constraints | expected regret: O(\sqrt{T}) | Helped |
| Use virtual queues and drift-plus-penalty updates, with V = \sqrt{T} and \alpha = T | OCO with stochastic constraints · OCO with stochastic constraints | expected constraint violations: O(\sqrt{T}) | Helped |
| Use the proposed algorithm instead of existing long-term-constraint algorithms | OCO with long term constraints · OCO with long term constraints | constraint violations: O(T^{1-\beta/2}) -> O(\sqrt{T}) | Helped |
| Use the proposed algorithm instead of existing long-term-constraint algorithms | OCO with long term constraints · OCO with long term constraints | regret: O(T^{\max\{\beta, 1-\beta\}}) -> O(\sqrt{T}) | Mixed |
| Use the proposed algorithm for online rather than batch-only stochastic constrained optimization | Stochastic constrained convex optimization · Stochastic constrained convex optimization | convergence rate: O(1/\sqrt{T}) | Helped |
| Use virtual queues with a multi-step drift analysis | Proposed algorithm · OCO with stochastic constraints | high probability constraint violations: O\big(\sqrt{T}\log(T)\log(\frac{1}{\lambda})\big) | Helped |
| Apply the proposed algorithm with truncation-based concentration for unbounded queue differences | Proposed algorithm · OCO with stochastic constraints | high probability regret: O(\sqrt{T}\log(T)\log^{1.5}(\frac{1}{\lambda})) | Helped |
Closest papers by meaning
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization (NeurIPS 2025 · similarity 0.87)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.87)
- Safe Online Convex Optimization with Heavy-Tailed Observation Noises (AAAI 2025 · similarity 0.87)
- Constrained Online Convex Optimization with Polyak Feasibility Steps (ICML 2025 · similarity 0.87)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.