Research map / Bandits and online learning / Online convex optimization and games
Projection-Free Online Convex Optimization with Time-Varying Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Projection-free online convex optimization with adversarial time-varying soft constraints, using only T linear optimization oracle calls, achieving interval-wise (adaptive) regret and constraint-violation bounds, with bandit extension.
Problem
Online convex optimization with a hard fixed constraint set that is expensive to project onto and additional time-varying soft constraints satisfied on average; prior methods require projections onto the hard set.
Approach
Combine approximately-feasible projections built from linear optimization oracle calls (Frank-Wolfe-based) with drift-plus-penalty and Lagrangian primal-dual updates over blocks of size K, so that the played points stay in the hard set while the soft constraints are handled via penalties on the infeasible iterates.
Key results
- Drift-plus-penalty LOO-based algorithm with T LOO calls achieves O(T^{3/4} sqrt(log T)) interval regret and O(T^{7/8}) constraint violation on any interval.
- Lagrangian primal-dual variant needs only first-order access and achieves O(T^{3/4}) regret and O(T^{7/8}) violation over the full sequence.
- Bandit extension achieves expected regret O(sqrt(n) T^{3/4} sqrt(log T)) and expected violation O(n^{1/4} T^{7/8} log^{1/4} T).
Limitations
- Regret and violation rates are worse than the O(sqrt(T)) and O(T^{3/4}) achievable with projections.
- Interval-adaptive guarantees only for the drift-plus-penalty algorithm; the more efficient primal-dual method gives only full-sequence guarantees.
- Bandit results hold only in expectation and require the hard set to contain a ball and oblivious adversary.
Experimental setup
Metrics: regret constraint violation
Baselines: projection-based OCO with time-varying constraints (full-information)
Builds on: online convex optimization with long-term constraints approximately-feasible projection via linear optimization drift-plus-penalty Frank-Wolfe
Closest papers by meaning
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.93)
- Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints (ICML 2026 · similarity 0.93)
- Gradient-Variation Bound for Online Convex Optimization with Constraints (AAAI 2023 · similarity 0.91)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.90)
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.89)
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.