Research map / Optimization / Nonconvex and smooth optimization
Constrained Online Convex Optimization with Polyak Feasibility Steps
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 OGD with Polyak feasibility steps for OCO with a fixed convex functional constraint, achieving O(sqrt(T)) regret and anytime constraint satisfaction using only first-order constraint feedback at played actions.
Problem
Online convex optimization with a fixed non-smooth convex functional constraint, where only the constraint value and subgradient at played actions are observed; prior methods give cumulative (not anytime) constraint satisfaction and need primal-dual updates.
Approach
After each OGD step, apply a subgradient step on the constraint using the Polyak step-size computed from a first-order approximation of the tightened constraint at the intermediate iterate, using a single sequence of iterates and one oracle call per round, with constraint tightening to create a buffer zone.
Key results
- Theory: Corollary gives O(sqrt(T)) regret and g(x_t) <= 0 for all t when a strictly feasible initial point is known (step size eta and tightening rho = alpha/sqrt(T)).
- Numerical toy experiment: PFS has no constraint violation while DPP (primal-dual baseline) incurs violation; DPP attains smaller regret than PFS.
- Corollary without strictly feasible start gives anytime satisfaction after O(log T) rounds and cumulative satisfaction for sufficiently large T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PFS instead of DPP | DPP · 2D toy setting | regret | Hurt |
| Use PFS instead of DPP | DPP · 2D toy setting | constraint violation | Helped |
| Tighten the constraint | DPP · 2D toy setting | constraint violation | Helped |
| Tighten the constraint | DPP · 2D toy setting | regret | Hurt |
Surprising findings
- The baseline DPP achieves smaller regret than the proposed PFS in the experiments, a trade-off for guaranteed feasibility.
Limitations
- Anytime constraint satisfaction requires a known strictly feasible initial point; otherwise only after O(log T) rounds.
- Larger dependence on problem parameters (e.g., subgradient bound G_g) and empirically higher regret than primal-dual DPP.
- Experiments limited to a 2-dimensional toy setting.
Experimental setup
Benchmarks: 2-dimensional toy quadratic OCO with linear constraints
Metrics: regret cumulative constraint violation instantaneous violation
Baselines: DPP (drift-plus-penalty primal-dual algorithm) DPP-T (tightened DPP)
Builds on: online gradient descent Polyak step-size primal-dual OCO with long-term constraints
Closest papers by meaning
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results (NeurIPS 2025 · similarity 0.89)
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.88)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.88)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.87)
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.