Research map / Bandits and online learning / Online convex optimization and games
Gradient-Variation Bound for Online Convex Optimization with 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 online primal-dual mirror-prox update with gradient-variation-dependent tuning | OCO with complex constraints in a general normed space · OCO with complex constraints | regret: T^{2/3} -> \mathcal{O}( \max\{ \sqrt{V_*(T)}, L_f \} ) | Helped |
| Use the online primal-dual mirror-prox update with fixed-constraint dual queues | OCO with complex constraints in a general normed space · OCO with complex constraints | constraint violation: \cO(\sqrt{T}) -> \cO(1) | Helped |
| Use the proposed method rather than the best-known Slater-condition method | OCO with complex constraints · OCO with complex constraints | regret: \sqrt{T} -> \sqrt{V_*(T)} | Helped |
| Use the proposed probability-simplex method with mixed iterates | OCO with complex constraints on the probability simplex · Probability simplex | constraint violation: \tilde{\cO}(\sqrt{T}) -> \tilde{\cO}(1) | Helped |
| Add iterate mixing with the uniform vector to keep iterates away from the simplex boundary | Online Primal-Dual Mirror-Prox on Probability Simplex · Probability simplex | regret: extra logarithmic factor $\log T$ | Hurt |
Closest papers by meaning
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.91)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.91)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
- Constrained Online Convex Optimization with Polyak Feasibility Steps (ICML 2025 · similarity 0.91)
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization (NeurIPS 2025 · similarity 0.91)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 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.