Research map / Bandits and online learning / Online convex optimization and games
Revisiting Projection-Free Online Learning 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.
Proposes a Lyapunov-based composite surrogate loss plus a parameter-free online Frank-Wolfe variant to get improved projection-free constrained online convex optimization bounds for general and strongly convex losses, in full-information and bandit settings.
Problem
Constrained online convex optimization where decisions must lie in a complex domain that is expensive or intractable to project onto, while satisfying time-varying constraints long term; existing projection-free methods give O(T^{3/4} sqrt(log T)) regret and O(T^{7/8}) cumulative constraint violatio
Approach
Build a composite surrogate loss combining the original loss and the constraint via a Lyapunov drift bound, then run a parameter-free online Frank-Wolfe (doubling trick on the gradient-norm estimate) on it, so regret and CCV are both controlled by surrogate regret.
Key results
- For general convex losses, the full-information method achieves O(T^{3/4}) regret and O(T^{3/4} log T) CCV, improving on the prior O(T^{3/4} sqrt(log T)) and O(T^{7/8}).
- For strongly convex losses, the paper reports O(T^{2/3}) regret and O(T^{5/6}) CCV, the first such guarantees for projection-free COCO.
- Experiments on MovieLens (full-information) and Film Trust (bandit) show the proposed OFW-TVC and SCOFW-TVC methods outperform OPDP, LPM and LBPM in cumulative cost loss and CCV.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OFW-TVC with a Lyapunov-based surrogate loss instead of LOO-BOGD | Projection-free COCO with full-information feedback and general convex losses · Adversarial time-varying constraints | regret bound: \O(T^{3/4} \sqrt{\log T}) -> \O(T^{3/4}) | Helped |
| Use OFW-TVC with a Lyapunov-based surrogate loss instead of LOO-BOGD | Projection-free COCO with full-information feedback and general convex losses · Adversarial time-varying constraints | CCV bound: \O(T^{7/8}) -> \O(T^{3/4} \log T) | Helped |
| Use BFW-TVC with a one-point gradient estimator and blocking instead of the prior bandit method | Projection-free COCO with bandit feedback and general convex losses · Adversarial time-varying constraints | regret bound: \O(T^{3/4} \sqrt{\log T}) -> \O(T^{3/4}) | Helped |
| Use BFW-TVC with a one-point gradient estimator and blocking instead of the prior bandit method | Projection-free COCO with bandit feedback and general convex losses · Adversarial time-varying constraints | CCV bound: \O(T^{7/8} \log T ) -> \O(T^{3/4} \log T) | Helped |
| Use the strongly convex OFW variant and quadratic Lyapunov function | Projection-free COCO with full-information feedback · Adversarial time-varying constraints with strongly convex losses | regret bound: \O(T^{3/4}) -> \O(T^{2/3}) | Helped |
| Use the strongly convex OFW variant and quadratic Lyapunov function | Projection-free COCO with full-information feedback · Adversarial time-varying constraints with strongly convex losses | CCV bound: \O(T^{3/4} \log T) -> \O(T^{5/6}) | Hurt |
| Use the strongly convex bandit variant | Projection-free COCO with bandit feedback · Adversarial time-varying constraints with strongly convex losses | regret bound: General convex losses: \O(T^{3/4}); strongly convex losses: \O(T^{2/3} \log T) | Mixed |
| Use the strongly convex bandit variant | Projection-free COCO with bandit feedback · Adversarial time-varying constraints with strongly convex losses | CCV bound: \O(T^{3/4} \log T) -> \O(T^{5/6} \log T) | Hurt |
| Apply the proposed methods to online matrix completion | OFW-TVC and SCOFW-TVC · MovieLens, full-information | cumulative cost loss | Helped |
| Use SCOFW-TVC rather than OFW-TVC | Online matrix completion · MovieLens, full-information | cumulative cost loss | Helped |
| Use SCOFW-TVC rather than OFW-TVC | Online matrix completion · MovieLens, full-information | CCV | Hurt |
| Use the proposed methods instead of the baseline | Online matrix completion · Film Trust, bandit | cumulative cost loss and CCV | Helped |
Surprising findings
- The strongly convex variant trades off CCV: it improves regret to O(T^{2/3}) but its CCV bound O(T^{5/6}) is looser than the general convex CCV bound, which the authors attribute to the quadratic Lyapunov function.
Limitations
- Strongly convex CCV bound O(T^{5/6}) is looser than the general convex CCV bound, likely due to the quadratic Lyapunov function.
- Bandit-setting bounds for strongly convex losses include extra log factors and rely on blocking and a one-point gradient estimator.
Experimental setup
Datasets: MovieLens Film Trust
Benchmarks: MovieLens Film Trust
Metrics: cumulative cost loss cumulative constraint violation
Baselines: OPDP LPM LBPM
Builds on: online Frank-Wolfe drift-plus-penalty framework SCOFW one-point gradient estimator
Closest papers by meaning
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.93)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.92)
- Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.91)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.91)
- Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.91)
- Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint (AAAI 2025 · similarity 0.91)
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.