1 Introduction↩︎

Online Convex Optimization (OCO) has emerged as a foundational framework for sequential decision-making under uncertainty, with applications spanning resource allocation, real-time control systems, and adversarial robustness in machine learning [1]. A critical variant of this framework, Constrained Online Convex Optimization (COCO), requires agents to minimize cumulative costs while adhering to time-varying constraints. In this problem, the learner interacts with an environment over \(T\) rounds, where at round \(t\), the learner selects a action \(\mathbf{x}_t \in \mathcal{K}\), where \(\mathcal{K}\in\mathbb{R}^n\) is the action set. The adversary then reveals a convex cost function \(f_t: \mathcal{K}\to \mathbb{R}\) and \(k\) convex constraint functions \(g_{t,i}: \mathcal{K}\to \mathbb{R},\;i \in [k]\). Let \(\mathcal{K}^\star \subseteq \mathcal{X}\) denote the set of feasible actions satisfying all constraints \(g_{t,i}(\mathbf{x}) \leq 0\) for \(t \in [T],\;i \in [k]\). We assume \(\mathcal{K}^\star \neq \emptyset\) to ensure that at least one feasible solution exists. Then, we use the following performance metrics: \[\begin{align} \mathtt{Regret}(T) &= \sum\limits_{t=1}^Tf_t(\mathbf{x}_t) - \min_{\mathbf{x}^\star \in \mathcal{K}} \sum_{t=1}^T f_t(\mathbf{x}^\star), \\ \mathtt{CCV}(T) &= \max_{i \in [k]} \sum\limits_{t=1}^T\left(g_{t,i}(\mathbf{x}_t)\right)^+. \end{align}\] The goal is to design an algorithm that achieves sublinear \(\mathtt{Regret}(T)\) and minimize \(\mathtt{CCV}(T)\) simultaneously. COCO’s applications span diverse domains, including portfolio optimization under dynamic risk constraints [2], dynamic resource allocation for time-varying workloads [3], real-time dynamic pricing with inventory constraints [4], and collision-free trajectory planning under safety constraints [5].

A central challenge in online optimization is the design of computationally efficient, projection-free algorithms for the adversarial Constrained Online Convex Optimization (COCO) setting. We summarize the key related works in Table ¿tbl:tbl:comparison?¹. We note that most works require solving a constrained convex optimization problem on each round (COO), or requires Euclidean projection operation on the convex set (PO). While projection-based algorithms, such as that of [6], establish the \(\tilde{O}(T^{1/2})\) bounds for both regret and CCV, this performance comes at the cost of a potentially intractable projection step in each round, limiting their applicability to domains like the spectahedron or flow polytopes. To circumvent this computational hurdle, current state-of-the-art projection-free methods relying on LOOs, such as [7] and [8], achieve regret rates of \(\mathcal{O}(T^{3/4})\) and CCV of \(\mathcal{O}(T^{7/8})\) or \(\tilde{\mathcal{O}}(T^{3/4})\). This gap with respect to horizon \(T\) raises a theoretical question: can projection-free methods match the horizon-dependent performance of projection-based methods in adversarial setting?

In this paper, we demonstrate that this gap with respect to \(T\) can be closed when a Separation Oracle (SO) is available. While LOOs are computationally advantageous for some geometries like the nuclear norm ball, Separation Oracles can be more efficient for some others (e.g., spectral norm balls) and offer a natural alternative for accessing the action set. A detailed discussion on LOO and SO is provided in Section 3. We present \(\mathtt{BAGEL}\) (Blocked Adaptive online Gradient descEnt with infeasibLe projection), which achieves \(\mathcal{O}(T^{1/2})\) regret and \(\tilde{\mathcal{O}}(T^{1/2})\) CCV bounds in the projection-free setting for adversarial COCO. Our total calls to SO depends on geometric constants (specifically the ratio of enclosing to enclosed balls), that may scale with the ambient dimension.

In Section 4, we develop a projection-free algorithm for OCO based on Online Gradient Descent with adaptive step sizes and establish its regret guarantees. While adaptive step sizes do not improve the regret bounds for OCO, they play a crucial role in proving the guarantees for the COCO problem. In Section 5, we introduce an approach that constructs a surrogate function and applies base algorithm for OCO to it. Inspired by [6], we adopt a Lyapunov-like function to include cumulative constraint violation in weights when combining cost and constraint via a surrogate function. Furthermore, we extend our analysis to strongly convex cost functions in Appendix 10 and 12. The key contributions of this work are summarized as follows.

1. We propose \(\mathtt{BAGEL}\), a projection-free algorithm for Adversarial Constrained Online Convex Optimization (COCO), that achieves \(\tilde{\mathcal{O}}(T^{1/2})\) regret and CCV for convex optimization while maintaining in total \(\tilde{\mathcal{O}}(T)\) calls to the separation oracle (Theorem 2). Our results match those of the projection-based counterparts on time horizon \(T\), improving upon the \(T\)-dependence of recent LOO-based works (which typically scale as \(T^{3/4}\)), albeit dependent on the action set geometry and the availability of Separation Oracle.

2. We are the first to analyze projection-free OGD for COCO with a specific adaptive step-size of the form \(\eta_m \propto 1/\sqrt{\epsilon+\sum_{\tau=1}^m\|\bar{\nabla}_\tau \|^2}\). We show this seemingly minor modification is critical for computational feasibility. As detailed in Remark 2, this step-size reduces the total number of calls to the separation oracle from a prohibitive \(\mathcal{O}(T^2)\) to a near-linear \(\tilde{\mathcal{O}}(T)\), making \(\tilde{\mathcal{O}}(T^{1/2})\) bounds of regret and CCV practically achievable.

3. We adopt blocking technique and use a trade-off parameter \(\beta\) to allow adjustment of algorithm to computational limitations. The tradeoff is given in Table ¿tbl:tbl:comparison?, where we see that with decreased \(\beta\), we would need less calls to the separation oracle at the cost of higher regret and CCV.

4. We extend \(\mathtt{BAGEL}\) to handle strongly convex cost functions, achieving \(\mathcal{O}(\log T)\) regret and \(\tilde{\mathcal{O}}(T^{1/2})\) CCV (Theorem 4), matching the performance of projection-based algorithms when allowed more separation oracle calls. This extension demonstrates that \(\mathtt{BAGEL}\) is effective in a wider range of optimization settings.

5. In order to obtain the above results, we also study projection-free Online Convex Optimization (OCO) with adaptive step sizes (Theorem 1 for convex and Theorem 3 for strongly-convex). We note that previous work considered constant step-sizes [11], while the results for COCO needed such an analysis with adaptive step-sizes.

2 Related Works↩︎

Adversarial COCO COCO problems have been widely studied, since they can handle complex action set [12]. Table ¿tbl:tbl:comparison? provides some of the key works for regret and CCV guarantees in the area. [9] proposed an algorithm that solves a constrained convex optimization problem in each round, and achieves \(\mathcal{O}(T^{1/2})\) regret with \(\mathcal{O}({T}^{3/4})\) CCV. This result is a special case of the result in [10]. Recently, [6] proposed a projection-based algorithm that achieves optimal regret and CCV of \(\tilde{\mathcal{O}}(T^{1/2})\). The results have been further extended to strongly convex cost functions, where all these works show a regret of \(\tilde{\mathcal{O}}(1)\) with a CCV of \(\tilde{\mathcal{O}}(T^{1/2})\). However, performing a constrained convex optimization or doing a orthogonal projection is computationally complex [11], [13], and thus we provide a projection-free algorithm in this paper.

Projection-free Algorithms for OCO Many projection-free algorithms have been proposed for classical OCO problems. However, regrets for Frank-Wolfe based approaches have been shown to achieve only \(\mathcal{O}(T^{3/4})\) for convex cost function [14], [15] and \(\mathcal{O}(T^{2/3})\) for strongly convex cost functions [16]. Even though [17] proves that on strongly convex set they can further improve the regrets to \(\mathcal{O}(T^{2/3})\) for convex cost function, these results are still not matching projection-based results. [18] proposes the concept of infeasible projection to replace the traditional orthogonal projection oracles, although it is only implemented for online linear optimization. In parallel with [19], [11] gives an approach to implement infeasible projection via separation oracle for OCO, which achieves an optimal regret of \(\mathcal{O}(T^{1/2})\) using online gradient descent based approach with constant step size. In their work, implementing infeasible projection via linear optimization oracle yields \(\mathcal{O}(T^{3/4})\) regret, which motivates the choice of separation oracle in our work. Our work builds upon the concept of infeasible projection, implemented via a separation oracle, pioneered by [11] for the unconstrained OCO setting. We specifically adopt the variant from [20] due to its favorable property of ensuring iterates remain within the constraint set \(\mathcal{K}\), which is crucial for our analysis. Our primary novelty lies in being the first to integrate this machinery with a carefully constructed adaptive step-size scheme and a surrogate framework inspired by [6] to solve the more complex constrained COCO problem, and in particular, to do so with near-optimal oracle complexity.

Projection-free Algorithms for Adversarial COCO Projection-free algorithms for online learning were proposed in response to the growing prevalence of high-dimensional data, which led to increased computational challenges for projection operators [11], [13], [15], [21], [22]. The primary challenge in projection-free COCO is to achieve strong guarantees using only computationally cheap oracles. As summarized in Table ¿tbl:tbl:comparison?, recent approaches based on Linear Optimization Oracles (LOOs) have made significant progress. [7] provides an algorithm with \(\mathcal{O}(T^{3/4})\) regret and \(\mathcal{O}(T^{7/8})\) CCV. Concurrently, [8] achieves \(\tilde{\mathcal{O}}(T^{3/4})\) for both metrics. While impressive, these results remain slower compared to projection-based methods. Our work differs by employing a Separation Oracle (SO), which is another natural projection-free setting in which the feasible action set \(\mathcal{K}\) can be given [11]. We demonstrate that this increase in oracle power is sufficient to close the performance gap entirely for convex functions.

3 Problem Setup↩︎

We formally describe the problem as follows. Consider an agent is playing a consecutive online game with an adversary. The time horizon is \(T\) if the game stops after \(T\) steps. At each step \(t\), the agent chooses an action \(\mathbf{x}_t\), and the adversary chooses a cost function \(f_t\) and \(k\) constraint functions \(g_{t,i}\), for \(i \in [k]\), and reveals them to the agent. Note that the objective of the game is to minimize the cost \(f_t(\mathbf{x}_t)\) while satisfying the constraints \(g_{t,i}(\mathbf{x}_t)\leq 0, \forall i\in[k]\).

Preliminaries and Notations We say a function \(f\) over the action set \(\mathcal{K}\) is convex if for all \(\mathbf{x},\mathbf{y}\in \mathcal{K}\), \(f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})\). We say a function \(f\) over the action set \(\mathcal{K}\) is \(\theta\)-strongly convex if for all \(\mathbf{x},\mathbf{y}\in \mathcal{K}\), \(f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})(\mathbf{y}-\mathbf{x})+\frac{\theta}{2}\Vert \mathbf{y}-\mathbf{x}\Vert^2\). For a set \(\mathcal{K}\subseteq \mathbb{R}^d\), we define the set of \(\alpha\mathbf{x}+(1-\alpha)\mathbf{y}\) for all \(\mathbf{x},\mathbf{y}\in\mathcal{K}\) and \(\alpha\in\mathbb{R}\) as the affine hull of \(\mathcal{K}\), \(\operatorname{aff}(\mathcal{K})\). The diameter of the action set is defined as \(D \triangleq \max_{\mathbf{x},\mathbf{y}\in \mathcal{K}}\Vert \mathbf{x}-\mathbf{y}\Vert\). The relative interior of \(\mathcal{K}\), denoted by \(\operatorname{relint}(\mathcal{K})\), is defined as the set \(\{\mathbf{x}\in\mathcal{K}| \exists r > 0, \mathbb{B}_r(\mathbf{x}) \cap \operatorname{aff}(\mathcal{K}) \subseteq \mathcal{K}\}\). By definition, for any point \(\mathbf{c} \in \operatorname{relint}(\mathcal{K})\), there exists a real number \(r > 0\) such that \(\operatorname{aff}(\mathcal{K})\cap \mathbb{B}_r(\mathbf{c}) \subseteq \mathcal{K}\), where \(\mathbb{B}_r(\mathbf{c})\) represent the ball of radius \(r\) centering at \(\mathbf{c}\). We use \(r_{\mathcal{K}, \mathbf{c}}\) to denote the largest \(r\) satisfying this property. Given \(\mathbf{c}\) and \(r\), for any \(\delta \in [0,1)\), referred to as the shrinking parameter, we define the shrunk constrained set \(\mathcal{K}_\delta\) as the set \((1-\delta)\mathcal{K}+ \delta\mathbf{c}\).

Oracle Type In classical projection-based algorithms, Projection Oracle (PO/\(\mathcal{O}_{P}\)) and Convex Optimization Oracle (COO/\(\mathcal{O}_{CO}\)) are standard feasibility mechanisms for actions chosen by the algorithm. Given a closed convex set \(\mathcal{K} \subseteq \mathbb{R}^n\) and a query point \(y \in \mathbb{R}^n\), a PO returns the unique point \(\mathbf{x}\in \mathcal{K}\) that minimizes the Euclidean distance to \(\mathbf{y}\), i.e., \(\mathcal{O}_{P}(\mathbf{y}, \mathcal{K}) = \arg\min_{\mathbf{x}\in \mathcal{K}} \| \mathbf{y}- \mathbf{x}\|_2^2\). Given a general convex objective function \(h: \mathbb{R}^n \rightarrow \mathbb{R}\) over \(\mathcal{K}\), a COO returns a global minimizer, i.e., \(\mathcal{O}_{CO}(h, \mathcal{K}) \in \arg\min_{\mathbf{x}\in \mathcal{K}} \;h(\mathbf{x})\). In the context of COCO, COOs are often invoked to handle time-varying soft constraints \(g_t(\mathbf{x}) \le 0\) without performing a direct projection. If \(h(\mathbf{x})\) is quadratic, a COO acts as a PO. If \(h(\mathbf{x})\) includes complex non-linear constraints, a COO represents a more computationally intensive subroutine than a simple projection.

The Linear Optimization Oracle (LOO/\(\mathcal{O}_{LO}\)) and Separation Oracle (SO/\(\mathcal{O}_{S}\)) are established approaches to move from projection-based algorithm to projection-free paradigms. The LOO exploits the fact that for many complex geometries, minimizing a linear function is vastly cheaper than minimizing a quadratic function (PO) or a general convex function (COO). Given a convex set \(\mathcal{K}\subseteq \mathbb{R}^n\) and a linear objective vector \(\mathbf{c} \in \mathbb{R}^n\) (typically a gradient or a direction vector), a LOO returns a vertex or point in \(\mathcal{K}\) that minimizes the linear function: \(\mathcal{O}_{LO}(\mathbf{c}, \mathcal{K}) \in \arg\min_{\mathbf{x}\in \mathcal{K}} \;\langle \mathbf{c}, \mathbf{x}\rangle\). The SO is a more recent development, and another natural projection-free setting to access the action set. Given a convex set \(\mathcal{K} \subseteq \mathbb{R}^n\) and a query point \(\mathbf{y}\in \mathbb{R}^n\), it either asserts that \(\mathbf{y}\in \mathcal{K}\), or it returns a separating hyperplane vector \(\mathbf{g} \in \mathbb{R}^n\) such that for all \(\mathbf{x}\in \mathcal{K}\), \(\langle \mathbf{g}, \mathbf{y}- \mathbf{x}\rangle > 0\). Although LOOs are more prevalent in the literature, it is worth noting the complementing nature between the two oracles in efficiency. [11] gave the example of two unit balls: a nuclear norm ball \(\mathcal{B}_* = \{ \mathbf{x} \in \mathbb{R}^{m \times n} \mid \|\mathbf{x}\|_* \leq 1 \}\), and a spectral norm ball \(\mathcal{B}_2 = \{ \mathbf{x} \in \mathbb{R}^{m \times n} \mid \|\mathbf{x}\|_2 \leq 1 \}\). While the requirement of a full Singular Value Decomposition (SVD) makes Euclidean projection computationally prohibitive onto either set, the efficiency of projection-free oracles differs. The LOO is efficient for \(\mathcal{B}_*\) (requiring only a rank-one SVD) but expensive for \(\mathcal{B}_2\) where a full SVD is needed [23]. In contrast, the SO is expensive for \(\mathcal{B}_*\) due to the subgradient for the nuclear norm (full SVD), but efficient for \(\mathcal{B}_2\) since computing a subgradient for \(g_2(\mathbf{X}) := \|\mathbf{X}\|_2 - 1\) requires only the top singular vector pair (rank-one SVD).

Regrets and CCV For an online algorithm that solves the constrained optimization, there are two key metrics, regret and cumulative constraint violation (CCV). The regret represents the distance in the cumulative cost from the actions chosen by the agent to the optimal action in hindsight. Mathematically, we define the regret to be \(\mathtt{Regret}(T) \triangleq \sum_{t=1}^T f_t(\mathbf{x}_t) - \sum_{t=1}^T f_t(\mathbf{x}^*)\), where \(\mathbf{x}^* \triangleq \operatorname{argmax}_{\mathbf{x}\in\mathcal{K}}\sum_{t=1}^T f_t(\mathbf{x})\). The cumulative constraint violation (CCV) represents the cumulative violation to the constraint, and when there are more than one constraints we choose the one that is violated the most cumulatively. We define CCV to be \(\mathtt{CCV}(T) \triangleq \max_{i\in[k]} \sum_{t=1}^T (g_{t,i})^+\), where \((z)^+ \triangleq \max\{z, 0\}\). In each step, we can simplify the constraint by letting \(g_t(x)=\max_{i\in [k]}g_{t,i}(x)\). Note that if each constraint condition is satisfied, constraint \(g_t\) naturally follows. Without loss of generality, we can assume that in each step, the adversary only reveals one constraint function, namely \(g_t\).

Assumptions Under the given problem setting, we introduce a few assumptions that are fundamental to our proposed algorithm. The first assumption is about the action set \(\mathcal{K}\) that we can choose actions from.

The second assumption concerns the cost and constraint functions at every time step.

Besides assumption on action set and cost and constraint functions, we highlight a feasibility assumption that ensures the problem is solvable in Assumption 3.

Infeasible Projection via Separation Oracle To replace costly projection steps, we use the Infeasible Projection via Separation Oracle (IP-SO) to ensure feasibility of actions generated by the algorithm. Unlike a standard Euclidean projection which finds the closest point in \(\mathcal{K}\), the IP-SO finds a point \(\mathbf{y}'\) (not necessarily in \(\mathcal{K}\)) that is closer to all points in a slightly shrunk set \(\mathcal{K}_\delta\) than the original point \(\mathbf{y}\) was. The key is that this can be implemented efficiently: if an iterate is outside \(\mathcal{K}\), the SO provides a separating hyperplane, and we take a small step in a direction normal to that plane. Lemma 3 guarantees that this iterative process terminates quickly and yields a point with the desired properties, effectively mimicking a projection without the high computational cost.

Next, we formally introduce the concept of infeasible projection oracle. We say \(\mathbf{y}' \in \mathbb{R}^n\) is an infeasible projection of \(\mathbf{y}\) onto \(\mathcal{K}\) if for all \(\mathbf{x}\in \mathcal{K}, \Vert \mathbf{y}'-\mathbf{x}\Vert \leq \Vert \mathbf{y}-\mathbf{x}\Vert\). Note that, unlike projection, \(\mathbf{y}'\) is not assumed to be in \(\mathcal{K}\). We say an algorithm returns an infeasible projection for set \(\mathcal{K}\) if it takes input point \(\mathbf{y}\) and return \(\mathbf{y}'\) that is an infeasible projection of \(\mathbf{y}\). An infeasible projection could be implemented using a separation oracle [11]. For a convex set \(\mathcal{K}\subseteq \mathbb{R}^n\), a Separation Oracle (\(SO_\mathcal{K}\)) is an oracle that, given a point \(\mathbf{x}\in \mathbb{R}^n\), either confirms that \(\mathbf{x}\in \mathcal{K}\) or else gives a hyperplane separating \(\mathbf{x}\) from \(\mathcal{K}\). Such a separating hyperplane could be represented as a vector \(\mathbf{g}\) where if \(\mathbf{y}\notin \mathcal{K}\), then \(\langle \mathbf{y}- \mathbf{x}, \mathbf{g}\rangle > 0\) for all \(\mathbf{x}\in \mathcal{K}\).

Here we use a variant of the IP-SO algorithm described in [20], and included in Appendix 8 as Algorithm 1 for completeness. We use \(\mathcal{P}_{\mathcal{K}, \mathbf{c}, r, \delta}\) to denote this algorithm. This variant slightly differs from the original version described in [11] in that it does not require the assumption that \(\mathcal{K}\) contains a \(d\)-dimensional ball, neither does it require \(\boldsymbol{0} \in \mathcal{K}\). The key idea of the algorithm is to provide an infeasible projection onto \(\mathcal{K}_\delta\) that is contained within \(\mathcal{K}\). This guarantees that the infeasible projection is not too far from the projection, since any point in \(\mathcal{K}\) is not too far from \(\mathcal{K}_\delta\). Lemma 3 (given in Appendix 8) ensures that the algorithm output is an infeasible projection within certain number of iterations (or queries of separation oracle). When there is no ambiguity, we simply use \(\mathcal{P}\) and drop the subscripts.

4 Base Algorithm: Projection-Free Algorithm for OCO↩︎

In order to extend OCO methods to the COCO framework inspired by [6], we use a surrogate function that combines the cost and constraint, leveraging the cumulative constraint violation as weights. A key challenge is that the gradients can have vastly different magnitudes across iterations, as shown in Section 5. When constraint violations accumulate, the weight can become very large, leading to explosive gradients. An adaptive step-size dampens these large gradients by incorporating gradient magnitudes into the denominator, providing the stability required for the surrogate-based analysis to hold. Therefore, we first formally analyze a projection-free OGD with such an adaptive step-size (Algorithm [alg:general]), a necessary building block for the algorithm under adversarial constraints.

The proposed base algorithm is based on Online Gradient Descent with adaptive step-size. Although [11] proposed a projection free OGD using an infeasible projection oracle (Algorithm 1, Lemma 4), it only considered constant step size and did not consider feasibility constraints on the action set \(\mathcal{K}\). However, the guarantees of results for COCO algorithm require adaptive step-sizes and feasible solutions returned by infeasible projection oracle, which is why we propose and analyze the Base Algorithm described in Algorithm [alg:general]. Note that we add a constraint constant \(\epsilon\) so that the regret are guaranteed with only \(\tilde{\mathcal{O}}(T)\) total calls to the separation oracle.

Algorithm [alg:general] takes as input: action set \(\mathcal{K}\), time horizon \(T\), \(\mathbf{c} \in \operatorname{relint}(\mathcal{K})\), \(r = r_{\mathcal{K}, \mathbf{c}}\), block size \(K\), shrinking parameter \(\delta\in[0,1)\), diameter of the action set \(D\), an instance of IP-SO algorithm \(\mathcal{P}\) implemented by Algorithm 1, a constraint constant \(\epsilon>0\) for convex cost functions or the strongly-convex parameter \(\theta\) for strongly-convex cost functions. We initiate the program by choosing \(\mathbf{x}_1\in\mathcal{K}\), and pass \(\mathcal{K}, \mathbf{c}, r, \delta\) to \(\mathcal{P}\) to initiate algorithm instances. Within each block \(m\), there are \(K\) iterations, represented by \(\mathcal{T}_m\). At each step \(t\), we play action \(\mathbf{x}_t\), and observe the cost function \(f_t\) adversarially selected and revealed by the adversary, which we use to compute \(\nabla_t\), the gradient of \(f_t\) at \(\mathbf{x}_t\). After \(K\) iterations, we compute the average gradient in the block \(m\), \(\bar{\nabla}_m=\frac{1}{K} \sum_{t\in\mathcal{T}_m} \nabla_t\), and perform a gradient descent update, \(\mathbf{x}_m - \eta_m\bar{\nabla}_m\), with adaptive step-size \(\eta_m = \frac{D}{\sqrt{\epsilon + \sum^m_{\tau=1}\Vert \bar{\nabla}_\tau \Vert^2}}\) in the convex case, or \(\eta_m = \frac{1}{m \theta}\) in the strongly convex case. The gradient descent update \(\mathbf{x}_m-\eta_m\bar{\nabla}_m\) is passed to the IP-SO instance \(\mathcal{P}\) to obtain next action, \(\mathbf{x}_{m+1}\).

We note that better regret bounds are achievable when the cost functions are chosen to be strongly convex. Thus, we give Theorem 3 to describe results for strongly convex functions. The proof details for Theorem 3 and Corollary 2 can be found in Appendix 10.

5 \(\mathtt{BAGEL}\): Projection-free algorithm for Adversarial COCO↩︎

In this section, to solve Online Convex Optimization with Adversarial Constraint (Adversarial COCO), we propose Algorithm [alg:constrained], Blocked Adaptive online Gradient dEscent with infeasibLe projection (\(\mathtt{BAGEL}\)), where “infeasible projection” refers to the use of IP-SO described in Section 3. For computational convenience, we introduce a processing parameter \(\gamma\) and we let \(\tilde{f}_t = \gamma f_t\), \(\tilde{g}_{t,i}=\gamma(g_{t,i})^+\). To track the cumulative constraint violation, we let \(Q_t=Q_{t-1}+\tilde{g}_t(\mathbf{x}_t)\), and \(Q_0=0\). Inspired by [6], \(\mathtt{BAGEL}\) (Algorithm 2) combines costs and constraints into a single surrogate cost function, \(\hat{f}_t\), and applies Base Algorithm to it. This surrogate consists of the original cost function and the current constraint violation weighted by dynamic term. If violations have been low, the weight is small, and the algorithm focuses on minimizing cost. If violations have been high, the weight becomes large, forcing the algorithm to aggressively prioritize satisfying the constraint. Since our objective is to make the weighted cumulative constraint violation small, similar to [6], we introduce a potential function \(\Phi: \mathbb{R}^+\mapsto\mathbb{R}^+\) that is non-decreasing, differentiable, convex, and satisfies \(\Phi(0)=0\). Thus, we create the surrogate cost function to be \(\hat{f}= \tilde{f}_t + \Phi'(Q_t)\tilde{g}_t\) where \(\Phi'(Q_t)\) is the gradient of the pre-defined function \(\Phi\) at \(Q_t\).

The algorithm use the inputs: action set \(\mathcal{K}\), time horizon \(T\), \(\mathbf{c} \in \operatorname{relint}(\mathcal{K})\), \(r = r_{\mathcal{K}, \mathbf{c}}\), shrinking parameter \(\delta \in [0,1)\), block size \(K\), action set diameter \(D\), an instance of the Base Algorithm (Algorithm [alg:general]) \(\mathcal{A}\), processing parameter \(\gamma\), function \(\Phi(\cdot)\), an instance of IP-SO \(\mathcal{P}\), and constant \(\epsilon > 0\) for convex costs or strongly-convex parameter \(\theta\). We initiate the algorithm by picking the initial action \(\mathbf{x}_1\in\mathcal{K}\), and set \(Q_0=0\), and passing the required input to \(\mathcal{A}\) to initiate the algorithm instance. We break the horizon \(T\) into blocks with size \(K\). For each step \(t\) within block \(m\), represented by \(\mathcal{T}_m\), we play action \(\mathbf{x}_m\) determined by the algorithm, and then observe cost \(f_t(\mathbf{x}_t)\) and constraint violation \((g_t(\mathbf{x}_t))^+\), where the cost function and the maximum constraint function are chosen and revealed by an adversary. We transform them into \(\tilde{f}_t = \gamma f, \tilde{g}_t =\gamma (g_t(x_t))^+\), and update the cumulative constraint violation with \(Q_t = Q_{t-1}+\tilde{g}_t\). We compute the gradient \(\nabla_t\) of the surrogate function \(\hat{f}_t(x_t):=\tilde{f}_t + \Phi'(Q_t)\tilde{g}_t\), i.e., \(\nabla_t=\nabla \hat{f}_t\), and pass the gradient information to \(\mathcal{A}\). At the end of the each block, \(\mathcal{A}\) returns the action for the next block \(\mathbf{x}_{m+1}\). The following Theorem provides the regret and the CCV for the proposed algorithm in the convex case.

6 Conclusion↩︎

In this paper, we investigated the gap regarding horizon \(T\) between projection-free and projection-based algorithms for for online convex optimization with adversarial constraints. We demonstrated that this gap can be closed for action sets with efficient Separation Oracle. Our algorithm, \(\mathtt{BAGEL}\), is the first projection-free algorithm to match the \(\tilde{\mathcal{O}}(T^{1/2})\) regret and CCV bounds of projection-based methods, using a number of separation oracle calls that is near-linear in the time horizon \(T\). We note that our algorithm assumes access to a separation oracle. The question remains open whether the bounds can be achieved with acess to LOO.

7 Useful lemmas↩︎

Here we introduce some technical lemmas that are used in our proofs.

8 Infeasible Projection via a Separation Oracle↩︎

As mentioned in Section 2, our work builds upon the concept of infeasible projection, implemented via a separation oracle, pioneered by [11] for the unconstrained OCO setting. We specifically adopt the variant from [20] due to its favorable property of ensuring iterates remain within the constraint set \(\mathcal{K}\), which is crucial for our analysis. Here we formally introduce the details of IP-SO algorithm in Algorithm 1 and an important Lemma 3.

9 Proof of Theorem 1↩︎

10 Analysis of Base Algorithm for Strongly convex cost↩︎

11 Proof of Theorem 2↩︎

The proof proceeds by connecting the performance of \(\mathtt{BAGEL}\) on the COCO problem to the performance of its base OCO algorithm (Theorem 1) on the sequence of surrogate costs. The first step is bounding surrogate regret. We apply Theorem 1 directly to the sequence of surrogate functions \(\{\hat{f}_t\}\) to obtain a bound on the surrogate regret, \(\mathtt{R}(\hat{f})\). This bound depends on the norms of the surrogate gradients. The second step is bounding surrogate gradients. We then bound the surrogate gradient norms in terms of the Lyapunov function’s derivative, \(\Phi'(Q_T)\), which effectively captures the worst-case cumulative violation. The third step is relating surrogate and true regret. We leverage the definition of \(\hat{f}_t\) and the convexity of \(\Phi\) to establish the key inequality: \(\mathtt{R}(\hat{f})\geq \mathtt{R}(\tilde{f})+\Phi(Q_T)\). This inequality forms a bridge, linking the (boundable) surrogate regret to the two quantities we ultimately wish to control: the true regret \(\mathtt{R}(\tilde{f})\) and the total violation (captured by \(\Phi(Q_T)\)). Step 4: Parameter Tuning. By combining these inequalities and carefully choosing our hyperparameters (\(\lambda,\gamma, \mathcal{K}, \delta\)) to balance the resulting terms, we can solve for the final bounds on \(\mathtt{Regret}(T)\) and \(\mathtt{CCV}(T)\).

We start with bounding \(\mathtt{R}(\hat{f})\):

Next, we aim to bound \(\mathtt{R}(\tilde{f})\), using the relationship between \(\hat{f}_t\) and \(\tilde{f}_t\), and replacing the \(\Vert \bar{\nabla}_m \Vert ^2\) term in Lemma 4. The results are provided below in Lemma 5 with proof.

Having necessary lemmas at hand, we now move towards parameter tuning. If we set \(\Phi(Q_T)=e^{\lambda Q_T}-1\) with some real number \(\lambda\), we have \(\Phi'(Q_T)=\lambda e^{\lambda Q_T}\). Letting \(S \triangleq \delta T + \frac{3}{\sqrt{2}}\sqrt{TK}\), we have \[\begin{align} \label{eq:regretTft} &\mathtt{R}(\tilde{f}) \overset{(a)}{\leq} \mathtt{R} (\hat{f})-\Phi (Q_T) \nonumber \\ &\quad\overset{(b)}{\leq} \gamma M_1 D (V+\lambda e^{\lambda Q_T})(\delta T + \frac{3}{\sqrt{2}}\sqrt{TK})-e^{\lambda Q_T}+1\nonumber\\ &\quad\overset{(c)} = \gamma M_1 D S + e^{\lambda Q_T} \left( \lambda \gamma M_1 D S-1 \right)+1 \end{align}\tag{11}\] where (a) uses Equation 7 , (b) uses Equation 8 , and (c) rearranges terms and adopts \(S\).

We make a few observation of Equation 11 . Note that if we take \(\gamma=(M_1D)^{-1}\), we can offset \(\gamma M_1 D\) term entirely. If we choose \(\lambda=\frac{1}{2S}\), then \(\lambda \gamma M_1 D S -1 = -\frac{1}{2}<0\). Thus, based on Equation 11 , we have \[\begin{align} &\mathtt{R}(\tilde{f}) \leq S+1= \delta T + \frac{3}{\sqrt{2}}\sqrt{TK}+1. \end{align}\] Since \(\tilde{f}_t=\gamma f_t\), we have \(\mathtt{R}(\tilde{f}) = \gamma\mathtt{Regret}(T)\). Let \(\beta\in[0,\frac{1}{2}]\) be some real number. Thus, if we choose \(\delta=\Theta(T^{-\beta})\) and \(K=\Theta(T^{1-2\beta})\), \[\begin{align} \mathtt{Regret}(T) &= \gamma^{-1} \mathtt{R}(\tilde{f}) \\ &= D M_1 \delta T + \frac{3}{\sqrt{2}}DM_1\sqrt{TK}+DM_1 \\ &= \mathcal{O}(DM_1 T^{1-\beta}). \end{align}\]

We now take a closer look at the Cumulative Constraint Violation (CCV). With \(\tilde{f}_t=\gamma f_t\) and \(f_t\) being \(M_1\)-Lipschitz, we have \(\tilde{f}_t\) is \(\gamma M_1\)-Lipscitz continuous, and thus \(\tilde{f}_t(\mathbf{x}_t)-\tilde{f}_t(\mathbf{x}^*) \geq -\gamma M_1 (\mathbf{x}_t-\mathbf{x}^*) \geq -1\). Taking sum over \(t\in[T]\), we have \[\begin{align} \label{eq:lowbon4regret} \mathtt{R}(\tilde{f})=\sum\limits_{t=1}^T(\tilde{f}_t(\mathbf{x}_t)-\tilde{f}_t(\mathbf{x}^*)) \geq -T \end{align}\tag{12}\] Replacing \(\mathtt{R}(\tilde{f})\) in Equation 11 with the lower bound in Equation 12 and rearranging terms, we have \[\begin{align} e^{\lambda Q_T} \leq \frac{VS + 1 + VT }{1-\lambda S}. \end{align}\] Since \(\lambda=\frac{1}{2S}\), we have \[\begin{align} Q_T &\leq 2S \log\left( 2(S + \frac{1}{V} + T)\right) \end{align}\] Considering that \(Q_T=\sum\limits_{t=1}^T(\tilde{g}_t)^+=\sum\limits_{t=1}^T\gamma(g_t)^+=\gamma \mathtt{CCV}(T)\), with \(S = \delta T + \frac{3}{\sqrt{2}}\sqrt{TK}\) and \(\gamma=(DM_1)^{-1}\), if we choose \(\delta=\Theta(T^{-\beta})\) and \(K=\Theta(T^{1-2\beta})\) for some \(\beta\in(0,\frac{1}{2}]\), we have \[\begin{align} \mathtt{CCV}(T) &= \gamma^{-1} Q_T \leq 2DM_1S * \mathcal{O}(\log T) \\ &\leq 2 D M_1 (\delta T + \frac{3}{\sqrt{2}}\sqrt{TK}) * \mathcal{O}(\log T) \\ &\leq \mathcal{O}(DM_1T^{1-\beta}\log T) \end{align}\]

Since calls to the infeasible projection and separation oracles are done in \(\mathcal{A}\), we can extend results from Corollary 1 and derive that the oracle calls are bounded as \(\tilde{\mathcal{O}}(T^{2\beta})\).

12 Analysis of \(\mathtt{BAGEL}\) for Strongly Convex Costs↩︎

We note that the regret bounds can improve when the cost functions are strongly convex. In this section, we describe how the proposed algorithm, \(\mathtt{BAGEL}\), can be implemented when the cost functions are strongly convex, and analyze the corresponding \(\mathtt{Regret}\), \(\mathtt{CCV}\), and total number of calls to the separation oracle guarantees.

Let the cost functions \(f_t\) be \(\theta\)-strongly convex while the constraint functions are considered to be convex, not necessarily strongly convex. Let them all be \(M_1\)-Lipschitz continuous. In this case, we still apply \(\mathtt{BAGEL}\) (Algorithm [alg:constrained]) with different parameters. In line 10, we add a regularization parameter \(V\) to control the influence of costs on the surrogate function, i.e., we let \(\hat{f}_t \gets V\,\tilde{f}_t + \Phi'(Q_t)\,\tilde{g}_t\). Besides, we choose \(\gamma = 1\), \(V = \frac{8M_1^2 K \log(Te/K)}{\theta}\), and \(\Phi(\cdot) = (\cdot)^2\). Further, the Base Algorithm instance \(\mathcal{A}\) uses step size \(\eta_m = \frac{1}{m\theta}\). For clarity, we include the updated BAGEL algorithm for strongly-convex costs in Algorithm [alg:strongly-convex].

Having studied the regret for OCO for strongly convex functions in Section 4, we now use the result to study the regret and CCV for the adversarial COCO problem for strongly convex costs, with similar approach to the proofs in Section 5. The results are given in Theorem 4, and the detailed proof can be found in Appendix 12.

References↩︎

---

1. For simplicity, in Table ¿tbl:tbl:comparison?, we only compare results with respect to time horizon \(T\); for more detailed discussion, we refer to our theorem statements and remarks.↩︎