Research map / Bandits and online learning / Online convex optimization and games
A Unifying Framework for Online Optimization with Long-Term 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 the two-phase primal-dual Lagrangian framework with a strictly feasible solution | Online optimization with stochastic constraints and adversarial rewards · Stochastic constraints, constant ρ | regret and cumulative constraints violation: R^T \leq \frac{1}{\tilde \rho} \err_{T,\eta}+\left( 1+\frac{2}{\tilde \rho} \right)\cump_{T,\eta}+\frac{1}{\tilde \rho}\ | Helped |
| Set the dual feasibility floor to T^{-1/4} when the feasibility lower bound is too small | Online optimization with stochastic constraints and adversarial rewards · Stochastic constraints, arbitrary ρ | regret and cumulative constraints violation: R_T \leq T^{1/4}\err_{T,\eta}+\left( 1+2T^{1/4} \right)\cump_{T,\eta}+T^{1/4}\cumd_{T}; V_T \leq T^{3/4}+ M_{T^{-1/4}}+ | Helped |
| Use the two-phase primal-dual Lagrangian framework | Online optimization with adversarial rewards and constraints · Adversarial rewards and constraints, constant ρ | cumulative reward relative to the feasible-mixture baseline: \frac{\rho}{1+\rho} \sum_{t=1}^{T} \OPT_{\bar f, \bar g} -\mleft(1+\frac{2}{\tilde \rho}\mright)\cump_{T,\eta}- \frac{1} | Helped |
| Use the framework when rewards and constraints are both stochastic | Online optimization with long-term constraints · Stochastic rewards and constraints | recovery-phase entry: T_1 = T | Helped |
| Estimate a feasibility lower bound from an initial T^{1/2} rounds | Online optimization with stochastic constraints · Stochastic constraints with unknown ρ | regret and cumulative constraints violation: \tilde O(\sqrt{T}/ \rho) | Helped |
| Use the framework for budget and ROI constraints in repeated first-price auctions | Repeated-auction bidding · Repeated first-price auctions, budget and ROI constraints | cumulative constraint violation: \tilde O(T^{1/2}) | Helped |
| Replace packing-only budget pacing with the general long-term-constraint framework | Repeated-auction bidding · Adversarial inputs | fraction of optimal utility: \rho/(1+\rho) | Helped |
Closest papers by meaning
- Online Learning under Budget and ROI Constraints via Weak Adaptivity (ICML 2024 · similarity 0.91)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.91)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.90)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
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.