# Online Primal-Dual Mirror Descent under Stochastic Constraints

arXiv: https://arxiv.org/abs/1908.00305 · HTML: https://mlsanity.com/paper/1908.00305/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2019.

## Built on by (most cited first, 30 of 31)

- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions](https://mlsanity.com/paper/2207.12463/) (2022)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)
- [Tuning Particle Accelerators with Safety Constraints using Bayesian Optimization](https://mlsanity.com/paper/2203.13968/) (2022)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints](https://mlsanity.com/paper/2505.21841/) (2025)
- [Monotone Individual Fairness](https://mlsanity.com/paper/2403.06812/) (2024)
- [A New Benchmark for Online Learning with Budget-Balancing Constraints](https://mlsanity.com/paper/2503.14796/) (2025)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint](https://mlsanity.com/paper/2412.10703/) (2024)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints](https://mlsanity.com/paper/2212.01689/) (2022)
- [Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback](https://mlsanity.com/paper/2301.11267/) (2023)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Near-Optimal Sample Complexity for Online Constrained MDPs](https://mlsanity.com/paper/2602.15076/) (2026)
- [Online Non-convex Optimization with Long-term Non-convex Constraints](https://mlsanity.com/paper/2311.02426/) (2023)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)

## Abstract (arXiv)

We consider online convex optimization with stochastic constraints where the objective functions are arbitrarily time-varying and the constraint functions are independent and identically distributed (i.i.d.) over time. Both the objective and constraint functions are revealed after the decision is made at each time slot. The best known expected regret for solving such a problem is O(√T), with a coefficient that is polynomial in the dimension of the decision variable and relies on the Slater condition (i.e. the existence of interior point assumption), which is restrictive and in particular precludes treating equality constraints. In this paper, we show that such Slater condition is in fact not needed. We propose a new primal-dual mirror descent algorithm and show that one can attain O(√T) regret and constraint violation under a much weaker Lagrange multiplier assumption, allowing general equality constraints and significantly relaxing the previous Slater conditions. Along the way, for the case where decisions are contained in a probability simplex, we reduce the coefficient to have only a logarithmic dependence on the decision variable dimension. Such a dependence has long been known in the literature on mirror descent but seems new in this new constrained online learning scenario.