Order-Optimal Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Abstract

Projection-based algorithms for constrained Online Convex Optimization (COCO) face scalability challenges in high-dimensional settings due to the computational complexity of projecting iterates onto constraint sets. This paper introduces a projection-free algorithm for COCO that achieves state-of-the-art performance guarantees while eliminating the need for projections. By integrating a separation oracle with adaptive Online Gradient Descent (OGD) and employing a Lyapunov-driven surrogate function, while dynamically adjusting step sizes using gradient norms, our method jointly optimizes the regret and cumulative constraint violation (CCV). We also use a blocked version of OGD that helps achieve tradeoffs between the regret and CCV with the number of calls to the separation oracle. For convex cost functions, our algorithm attains an optimal regret of $\mathcal{O}(\sqrt{T})$ and a CCV of $\mathcal{O}(\sqrt{T} \log T)$, matching the best-known projection-based results, while only using $\tilde{\mathcal{O}}({T})$ calls to the separation oracle. The results also demonstrate a tradeoff where lower calls to the separation oracle increase the regret and the CCV. In the strongly convex setting, we further achieve a regret of $\mathcal{O}(\log T)$ and a CCV of $\mathcal{O}(\sqrt{T\log T} )$, while requiring ${\mathcal{O}}({T}^2)$ calls to the separation oracle. These results close the gap between projection-free and projection-based approaches, demonstrating that projection-free methods can achieve performance comparable to projection-based counterparts.

Introduction

In Online Convex Optimization (OCO), a learner repeatedly chooses actions to minimize a sequence of unknown, adversarial cost functions. In the Constrained (COCO) version, the learner must also satisfy a set of time-varying constraints, such as staying within a budget or safety limit.

Standard "projection-based" algorithms are theoretically optimal but practically slow. Every step requires a "projection"—essentially solving a quadratic optimization problem—to ensure the action stays within the feasible set. For complex geometries like the spectahedron or flow polytopes, this is a massive computational bottleneck. Existing "projection-free" methods typically use simpler tools like Linear Optimization Oracles (LOO), but they have historically suffered from slower convergence rates ($O(T^{3/4})$ instead of $O(T^{1/2})$). This work addresses whether optimal rates can be achieved without the heavy cost of full projections.

The BAGEL Algorithm

The authors introduce BAGEL (Blocked Adaptive online Gradient dEscent with infeasibLe projection). The algorithm's core innovations include:

  • Separation Oracle (SO): Instead of a full projection (finding the closest point in a set), BAGEL uses an SO. When a point is outside the feasible set, the SO provides a "separating hyperplane" that directs the algorithm back toward the set.
  • Infeasible Projection: Rather than forcing the iterate to be strictly feasible at every sub-step, the algorithm uses the SO to perform "infeasible projections," which are computationally much cheaper than standard Euclidean projections.
  • Adaptive Step-Sizes: A critical contribution is the use of a specific adaptive step-size ($\eta_m \propto 1/\sqrt{\epsilon + \sum \|\nabla\|^2}$). These adaptive steps are essential to keep the total number of oracle calls near-linear ($\tilde{O}(T)$) rather than quadratic ($O(T^2)$) by dampening gradients caused by accumulated constraint violations.
  • Surrogate Lyapunov Function: To handle constraints, BAGEL combines the cost function and the cumulative constraint violation into a single "surrogate" function. This forces the algorithm to prioritize safety when violations are high and cost minimization when they are low.

Theoretical Results

BAGEL proves that the "performance tax" previously associated with projection-free methods is not inevitable. By utilizing a Separation Oracle, the algorithm recovers the optimal $O(T^{1/2})$ time-horizon dependence for convex functions and $O(\log T)$ for strongly convex functions.

Comparison of BAGEL with existing projection-based and projection-free algorithms.

As shown in the comparison table above, BAGEL (referred to as "This paper") matches the $T$-dependence of the best projection-based methods while remaining projection-free. Specifically, it achieves $\tilde{O}(T^{1/2})$ cumulative constraint violation (CCV) and requires only $\tilde{O}(T)$ total calls to the Separation Oracle for general convex functions.

Discussion and Limitations

While BAGEL scales optimally with time ($T$), the number of oracle calls depends on the geometry of the action set ($D/r$). In very high dimensions where sets are "ill-conditioned" (extremely skinny or flat), the number of SO calls could still be significant.

Furthermore, the paper leaves open the question of whether these optimal $O(T^{1/2})$ rates can be achieved using the even simpler Linear Optimization Oracle (LOO), which is preferred for certain geometries like the nuclear norm ball. Future work could involve implementing BAGEL in real-world scenarios like portfolio optimization or dynamic resource allocation to empirically validate its practical speedup over projection-based solvers.

Summary updated

Abstract

Projection-based algorithms for constrained Online Convex Optimization (COCO) face scalability challenges in high-dimensional settings due to the computational complexity of projecting iterates onto constraint sets. This paper introduces a projection-free algorithm for COCO that achieves state-of-the-art performance guarantees while eliminating the need for projections. By integrating a separation oracle with adaptive Online Gradient Descent (OGD) and employing a Lyapunov-driven surrogate function, while dynamically adjusting step sizes using gradient norms, our method jointly optimizes the regret and cumulative constraint violation (CCV). We also use a blocked version of OGD that helps achieve tradeoffs betweeen the regret and CCV with the number of calls to the separation oracle. For convex cost functions, our algorithm attains an optimal regret of $\mathcal{O}(\sqrt{T})$ and a CCV of $\mathcal{O}(\sqrt{T} \log T)$, matching the best-known projection-based results, while only using $\tilde{\mathcal{O}}({T})$ calls to the separation oracle. The results also demonstrate a tradeoff where lower calls to the separation oracle increase the regret and the CCV. In the strongly convex setting, we further achieve a regret of $\mathcal{O}(\log T)$ and a CCV of $\mathcal{O}(\sqrt{T\log T} )$, while requiring ${\mathcal{O}}({T}^2)$ calls to the separation oracle. Further, tradeoff with the decreasing oracle calls is studied. These results close the gap between projection-free and projection-based approaches, demonstrating that projection-free methods can achieve performance comparable to projection-based counterparts.
BibTeX
@misc{lu2025order,
  author = {Yiyang Lu and Mohammad Pedramfar and Vaneet Aggarwal},
  title = {{Order-Optimal Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization}},
  year = {2025},
  eprint = {2502.16744},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.16744},
}
Figure