On the Power of Optimism in Constrained Online Convex Optimization

1 Introduction

Constrained Online Convex Optimization (COCO) is a generalization of the online convex optimization framework (OCO) and has become increasingly popular as more online decision-making problems require balancing objectives with adherence to operational constraints. For example, in an advertisement platform [Goldfarb and Tucker, 2011], the advertisers aim to maximize the click/conversion rates within the weekly or monthly budgets; in the network traffic management [Mannor and Tsitsiklis, 2006], the operator aims to minimize the latency of network flows within the network's capacity limits; in the portfolio management [Li and Hoi, 2014], the investor seeks to maximize returns while adhering to risk constraints and maintaining a balanced allocation across various classes. In COCO, at each round t, the learner makes a decision xt from a constrained set and then observes the full information of ft(·). The goal is to minimize regret ∑Tt=1 ft(xt) - ∑Tt=1 ft(x∗ ), while satisfying g(xt) ≤ 0, ∀t ∈ [T], where x∗ is the optimal solution to the offline problem

∗Corresponding Author

A straightforward solution to COCO is a projection-based gradient descent method [Hazan and others, 2016], which projects the decision into the feasible region at each round defined by

However, the projection operator is often computationally burdensome and might be impractical, especially when the constraint set is complicated (i.e., g is a complex function). To address the challenge, [Mahdavi et al., 2012; Yu and Neely, 2020; Qiu et al., 2023] studied slightly relaxed long-term constraints, where the constraints are allowed to be violated and as long as they are satisfied over the long term. In other words, the constraint violation over T rounds V(T) := ∑Tt=1 g(xt) should be minimal. In this problem setting, [Mahdavi et al., 2012] proposes a regularized primaldual subgradient algorithm and achieves O(√T) regret and O(T 3/4 ) violation bound. The regret and violation performance is greatly improved to O(√T) and O(1) in [Yu and Neely, 2020] with a novel "drift-plus-penalty" framework. However, these methods present their results with respect to T, which only leads to worst-case performance. But, intuitively, when the loss functions change slowly (or even remain static) in a benign environment, one would expect a better regret than the O(√T) worst-case regret.

To account for this, [Chiang et al., 2012] introduced a type of gradient variation defined as

which measures the dynamics of the environment. Using this definition, [Chiang et al., 2012] achieves a problem-dependent regret of O(√V max T ) in OCO through an optimistic-type two-step mirror descent algorithm. This approach captures the worst-case O(√T) regret, but also improves the regret bound when the variations are small, offering better guarantees than the traditional O(√T) bound.

More recently, [Qiu et al., 2023] studied OCO with constraints and established both a problem-dependent regret and an O(1) violation bound, by assuming the non-causal information of V max T .

However, the existing approaches are not adaptive or environment-agnostic. They rely on prior knowledge of the total number of rounds, T , or more challenging, the total gradient variations of the loss functions, V max T , to properly schedule the learning rate or other penalty parameters in the algorithm. This assumption is overly strict in practice because the learner can only observe the current loss function (or the casual cumulative gradient variation V max t ). Estimating the full variation of the problem at the beginning is extremely challenging, if not impossible. Therefore, an open question raised by [Qiu et al., 2023] is both critical and challenging:

Is it possible to design an adaptive algorithm for COCO such that it achieves a problem-dependent regret and constant violation without any prior knowledge of the key environment parameters?

In this paper, we provide a positive answer to this question by introducing Optimistic-COCO, an efficient first-order primal-dual method that incorporates the optimistic gradient descent and Lyapunov optimization technique. Our contributions are summarized as follows:

• Algorithm Design: The design of Optimistic-COCO is inspired by optimistic gradient descent method and the Lyapunov optimization technique. For the primal domain, Optimistic-COCO achieves fully adaptive by leveraging historical information through optimistic gradient descent that captures the variation of the environment and well-designed adaptive parameters to control the loss-constraint tradeoff. For the dual domain, it designs an alternative virtual queue update to further track the constraint violation. Our algorithm does not require any prior knowledge of the total gradient variation and time horizon. It is adaptive to the non-casual variation and can effectively balance regret and constraint violation.
• Theoretical guarantees: Optimistic-COCO establishes anytime regret and violation bounds of R(t) = O(√Vt) and V(t) = O(1), where the gradient violation is

Vt := ∑ts=1 ∥∇fs(xs) -∇fs-1(xs)∥2 . This not only addresses the open question in [Qiu et al., 2023] regarding whether an adaptive and non-casual algorithm can achieve a problem-dependent regret and constant violation but also improves the regret to a relaxed one O(√Vt) (against O(√V max T )). We derive these strong results through the carefully designed virtual queue, adaptive trade-off parameters, and a refined multi-step Lyapunov drift analysis of the virtual queue process. Specifically, we establish a relationship between the trade-off parameter ϕt and the gradient variation Vt and prove that it greatly enhances our bounds. A detailed comparison to the most related results is summarized in Table 1.

• Experiments: We evaluate Optimistic-COCO using synthetic experiments in both dynamic and slowly changing environments. Our experimental results demonstrate that Optimistic-COCO outperforms baseline algorithms in both settings (even the algorithm in [Qiu et al., 2023] that uses the non-casual knowledge of the total gradient variation). Moreover, it is observed that in a slowly changing environment, OptimisticCOCO achieves a much better performance than other traditional worst-case algorithms. This proves our algorithm's effectiveness in different environments and demonstrates the theoretical results.

1.1 RelatedWork

Online convex optimization is a broad field that has been extensively studied with numerous variants [Chen et al., 2017; Yuan and Lamperski, 2018; Mokhtari et al., 2020; Yi et al., 2021; Guo et al., 2022; Sinha and Vaze, 2024; Liu et al., 2024]. In this paper, we focus on the works most relevant to ours.

"Optimism" in OCO: The concept of optimism in online convex optimization has been widely studied in [Hazan and Kale, 2010; Chiang et al., 2012; Rakhlin and Sridharan, 2013; Yang et al., 2014] to establish the problem-dependent regret beyond the traditional worst-case guarantee. The type of gradient variation result is first derived in [Hazan and Kale, 2010] for online linear optimization with the optimistic-style algorithm. [Chiang et al., 2012] studies linear and smooth loss functions to achieve O(√V max T ) regret bound. [Rakhlin and Sridharan, 2013] generalizes the results in [Hazan and Kale, 2010] by introducing optimism in Follow the Regularized Leader and Online Mirror Descent. [Yang et al., 2014] extends results in [Chiang et al., 2012] to the non-smooth setting and provides a guarantee of O(√V max T ) in the general non-Euclidean space. These results leverage the power of "optimism", though it remains uncertain whether this approach can be effectively applied to constrained settings to achieve strong performance.

COCO: Constrained online convex optimization was initialized by [Mahdavi et al., 2012] where a regularized primaldual algorithm is proposed to achieve a O(√T) regret bound and a O(T 3/4 ) violation bound. It can also achieve an O(T 2/3 ) bound for both regret and violation when the constraint function g(x) is linear. [Jenatton et al., 2016] extends these results to the setting that the total round T is unknown, providing regret and violation bound of O (T max{c,1-c} ) and O (T 1-c/2 ), respectively, with c ∈ (0, 1) as a trade-off parameter. But this result is much worse than ours. [Yu et al., 2017] shows O(√T) bound both in regret and constraint violation, but they study a different constraint setting, which is stochastic with the environment. When the Slater's condition holds, [Yu and Neely, 2020] proposes a "drift-pluspenalty" framework to achieve O(√T) regret and O(1) violation bound. However, these results fail to capture the variation of the loss functions, making them unable to achieve improved performance even when the environment is benign. Motivated by the optimism in OCO, a primal-dual gradient descent-ascent algorithm is introduced in [Qiu et al., 2023] that achieves problem-dependent O(√V max T ) regret andO(1) violation bound. Recently, the paper [Lekeufack and Jordan, 2024] extends [Sinha and Vaze, 2024] to the setting of both adversarial and fixed constraints by incorporating an optimistic design on a surrogate Lagrange function. While they can achieve O(√VT ) regret and O(logT) violation bound in the fixed constraint setting, they focus on hard constraint violation and require prior knowledge of the total gradient variation VT to schedule the learning rates in the algorithms carefully. As we discussed before, obtaining such non-casual information is usually infeasible or even impossible in the practical system.

2 Constrained Online Convex Optimization

In this section, we formally define the COCO problem and introduce necessary assumptions. Let X0 ∈ Rd be a closed convex set. We define stacked vector g(x) as [g1(x), g2(x), · · · , gm(x)]⊤, where each gi(x) is a scalarvalue constraint function evaluated at the input x and m is the number of constraints. Assume ft(x), ∀t ∈ [T] and gi(x), ∀i ∈ [m] are convex and continuous functions. When not specified, we consider ∥ · ∥ to be an L2-norm.

We define the function h(x) as α-strongly convex if h(x) satisfies

for any x, y ∈ Rd . The cumulative gradient variation at round t is defined as

For ease of exposition, we also denote Vt = ∑ts=1 ∥∇fs - ∇fs-1∥2 .

In COCO, at each round t, the learner selects a decision xt from X0 and then observes the full information about ft(x). To quantify the performance of generated sequence {x1, x2, · · · , xT} by an algorithm, we compare them with a static baseline, which is the solution to the following offline COCO problem:

Let x∗ be the optimal solution to (2), define the anytime regret and violation at round t as follows:

Before introducing our algorithm and theoretical results, we present the following standard technical assumptions in COCO.

Assumption 1. The decision set X0 is convex and bounded with diameter D such that ∥x - x′ ∥ ≤ D, ∀x, x′ ∈ X0.

Assumption 2. The loss function ft(x) satisfies |ft(x) - ft(x′ )| ≤ F∥x - x′ ∥, ∥∇ft(x) - ∇ft(x′ )∥ ≤ F∥x - x′ ∥, ∀x, x′ ∈ X0, t ∈ [T ].

Assumption 3. The constraint function g(x) satisfies ∀x, x′ ∈ X0, ∥g(x) - g(x′ )∥ ≤ G∥x - x′ ∥, ∥g(x)∥ ≤ R, and ∥∇gi(x) - ∇gi(x′ )∥ ≤ G∥x - x′ ∥, ∀i ∈ [m].

Assumptions 2 and 3 indicate the Lipschitz continuous of functions and function gradients of both loss and constraint functions. The bound of the constraint function follows directly from the continuity of g(x) and Assumption 1.

Assumption 4. There exists a point ˆx ∈ X0 and a positive constant δ > 0 such that gi(ˆx) ≤ -δ, ∀i ∈ [m].

This assumption, known as Slater's condition [Boyd and Vandenberghe, 2004], indicates the existence of a strictly feasible solution to the constrained problem and is crucial for establishing a constant violation bound. However, our algorithm is fully adaptive and does not require prior knowledge of δ for implementation; it is introduced solely to facilitate the analysis. Finally, note that these assumptions are common in online learning and easy to satisfy in practice [Cesa-Bianchi and Lugosi, 2006; Hazan et al., 2007].

3 Optimistic-COCO

In this section, we introduce Optimistic-COCO, an efficient optimistic gradient descent algorithm based on Lyapunov optimization techniques. To present our algorithm, we first define the approximated Lagrange function as

where virtual queue vector Qt = [Q1t ,Q2t , · · · ,Qmt ]⊤ represents the dual variable that controls constraint violation of decisions. In Optimistic-COCO, at each round t, it first computes the optimistic gradient θt and optimizes a surrogate decision function w.r.t. x. After submitting decision xt+1 and observing the loss function, the algorithm calculates the causal gradient variation Vt+1 to update the trade-off parameter ϕt+1 and learning rate ηt+1. The virtual queue is then updated based on the current violation. We summarize Optimistic-COCO in Algorithm 1.

Algorithm 1 Optimistic-COCO

• 1: Initialization: x0, x1 ∈ X0, Q0 = 0, L0(x) = L1(x) = 0, ∀x ∈ X0, adaptive learning rates ηt = Θ( 1 √Vt ) and ϕt = Θ(√Vt).
• 2: for t = 1, · · · , T do
• 3: Calculate the optimistic gradient:

4: Take adaptive gradient decision:

• 5: Observe ft+1 and calculate: ϕt+1 and ηt+1.
• 6: Update virtual queue:

7: end for

To further explain the underlying intuition in the algorithm, we recall the offline COCO problem in (2) and introduce a Lagrange function to it:

where λ is the Lagrange multiplier associated with constraint functions. Since ft is observed after making the decision xt in online optimization. An efficient and classical method is to approximate Lt with first-order estimation that:

The problem can then be solved by applying gradient descent to both the primal and dual updates, which has been proven to ensure an O(√T) regret guarantee, as shown in [Mahdavi et al., 2012; Yu and Neely, 2020]. However, to achieve an improved problem-dependent guarantee, we require a more effective estimator capable of detecting environmental changes, along with a refined dual design to balance the tradeoff between loss and constraints.

In the primal domain, inspired by the concept of "optimism" in [Rakhlin and Sridharan, 2013], we design an optimistic gradient estimator:

Rather than relying solely on gradient information from the previous round, this estimator incorporates the momentum of gradients, accounting for function variation. With this updated gradient, we can compute the decision for the next time step by optimizing the surrogate function in (6). Note that this equation does not require computing the minimum of any function, but instead involves a gradient-based descent, which is computationally efficient.

In the decision in (6), we also introduce a regularization (or smoothing) term 1 2ηt ∥x - xt∥2 to stabilize the algorithm, where ηt = Θ( 1 √Vt ) represents the learning rate. Intuitively, when the environment changes slowly, it incurs a smaller ηt, encouraging the algorithm to make more stable decisions that prioritize exploitation. Moreover, since we have no prior knowledge of the total number of rounds T or the total gradient variation VT , the design of the adaptive learning rate should be carefully chosen. The specific value of ηt will be further discussed in the theorem statements in the following section. It is important to note that this design is non-trivial in constrained optimization, where the loss functions, constraints, and dual variables (or virtual queues) are all interdependent, making the analysis challenging.

For the dual domain, we employ the virtual queues Q to approximate the dual variables. Intuitively, Q captures the cumulative violation and encourages more conservative decisions when the queue length grows large. The traditional update rule of virtual queues also imposed "optimism" in the dual domain to achieve constant constraint violation, however, we design a novel update for the virtual queue in Optimistic-COCO which differs from previous approaches in two aspects:

• Our algorithm leverages the unique feature of alternative updating in networking systems such that we can leverage real queues as the signal to estimate dual variables directly. Specifically, at time slot t, we can observe the feedback from the current decision xt+1 and use it to update the queue length. In contrast, traditional "optimistic" optimization methods [Yu and Neely, 2020; Qiu et al., 2023] update both the primal variable xt+1 and the dual variable Qt+1 simultaneously, relying only on the previous decision xt.
• We do not introduce a trade-off parameter in the constraint function g(x) when updating the virtual queue, as seen in previous works. Instead, the adaptive trade-off parameter ϕt = Θ(√Vt), which balances regret and violation, is only applied to g(x) when making decisions. In the next section, we will show that simply adding the trade-off parameter to the virtual queue update, as in [Yu and Neely, 2020] and [Qiu et al., 2023], undermines the algorithm's ability to achieve real adaptiveness.

Remark 1. We note that the definition of gradient variation used in this paper (VT = ∑Tt=1 ∥∇ft(xt) -∇ft-1(xt)∥2) is more relaxed and practical. Compared to the previous definition (V max T = ∑Tt=1 maxx∈X0 ∥∇ft(x) -∇ft-1(x)∥2) in [Chiang et al., 2012] and [Qiu et al., 2023], it is not necessary to solve a maximization problem in each round with the full knowledge of gradient functions. While the computation is simple when f is linear or quadratic, it might become even more time-consuming than the algorithm's runtime when the loss function f is complex. However, with our definition and analysis, the algorithm only needs to compute the gradient variation at the current decision xt in each round, thereby avoiding the heavy computational overhead in the existing formulation.

4 Main Results

In this section, we first present our main theoretical results on the bound of regret and constraint violation.

Theorem 1. Let the parameters be

Under Assumptions 1-4, Optimistic-COCO algorithm achieves the following regret and violation for any time t ∈ [T ]

where δ is the Slater's constant.

This result implies that Optimistic-COCO can achieve problem-dependent regret while maintaining constant constraint violation. Here, Vt represents the gradient variation that captures the problem's dynamics. When the environment is benign and the loss function remains fixed, this regret bound indicates no gap between the offline optimal solution and the online decision (since ∥∇ft(xt) -∇ft-1(xt)∥ = 0), whereas the traditional O(√T) regret still incurs a sub-linear gap. Furthermore, since the gradient of loss functions is bounded according to Assumption 2, our results also generalize the previous O(√T) bound for worst-case scenarios, where constant variation persists across all rounds. Therefore, our problem-dependent variation bound reflects the dynamic and complexity of the problem, providing a stronger guarantee for the algorithm.

In Optimistic-COCO, a non-increasing learning rate is employed to guide decision-making. The algorithm is fully adaptive and does not rely on prior knowledge of the environment, such as VT or T, unlike previous approaches [Yu and Neely, 2020; Qiu et al., 2023]. Instead, the learning rate increases progressively based on the accumulated gradient variation over time. Initially, when the gradient variation is small, the algorithm favors more aggressive exploration. As the experiment progresses, the algorithm transitions towards more stable behavior. Additionally, when the loss function is fixed, the algorithm maintains a constant learning rate by the definition of ηt, which is consistent with the optimization of a known convex problem. This constant learning rate also prevents excessively large updates at the start of the iterations. Furthermore, the trade-off parameter is adaptive, and its strategic placement is critical to achieving the algorithm's adaptivity and ensuring that constant constraint violation is maintained.

Proof of Theorem 1

We give some proof sketches of our theoretical results in this section and leave the full proof in the Appendix. To prove our main theorem, we first introduce the following critical lemma that provides a unified bound on both regret and drift.

Lemma 1. Under the Optimistic-COCO algorithm, we have for any x ∈ X0 such that

The proof of Theorem 1 follows this key lemma which provides a bound on the one-step regret and Lyapunov drift as a whole. Note this lemma holds for all x ∈ X0 including the optimal decision x∗ , which facilitates the subsequent proofs, so we highlight some key proof steps here.

Proof. For the Optimistic-COCO decision, we define

It is not hard to check h(x) is 1/ηt-strongly convex due to the quadratic term. Recall that xt+1 is the optimal solution to h(x) in Optimistic-COCO, we have for any x ∈ X0

which is one of the properties of the strongly convex function. Further define an error term ϵt = ∇Lt+1(xt+1,Qt+1) - θt and reformulate (8) as

Combine it with the convexity of Lt+1(x,Q) w.r.t. x, we have the inequality

To cancel the term Q⊤t+1g(xt+1), define a function of the queue dynamic

Since Qt+1 is the optimal solution to h(Q) in OptimisticCOCO, we have for any Q ≥ 0

Setting Q = 0 yields

Plugging it in inequality (9) and re-arranging the terms completes the proof.

Constraint Violation

Following the virtual queue update rule in Optimistic-COCO, we directly have

which implies that the constraint violation of OptimisticCOCO is bounded by the value of virtual queue and the problem reduces to determining the bound of the virtual queue. We remark that, in previous works [Yu and Neely, 2020; Qiu et al., 2023], their algorithms typically introduced a trade-off parameter ϕ into the constraint function when updating the virtual queue Qt, leading to a violation bound of ∥Qt∥/ϕ. This method is valid when the total gradient variation VT and time horizon T are known to set ϕ. However, when these parameters are unknown, incorporating an adaptive parameter ϕt into the constraint function invalidates inequality (10), making it impossible to use virtual queue to establish the violation bound. Therefore, in our algorithm, we do not impose ϕt on the constraint function during the virtual queue update and employ a "Lyapunov drift" analysis to Lemma 1 to derive the bound on ∥Qt∥.

Lyapunov drift analysis is used to investigate the stability properties of control policies where a stable policy results in bounded queue lengths. In our analysis, when Slater's condition holds as stated in Assumption 4, we study the upper bound of queue length through a refined multiple-step Lyapunov drift analysis.

Lemma 2. Set x = ˆx satisfy Slater's condition in Lemma 1, i.e., gi(ˆx) ≤ -δ (δ > 0), ∀i ∈ [m]. Under Assumptions 1-4, there exists a positive constant C and an integer K such that the following multi-step Lyapunov drift holds:

The derivation of the Lyapunov drift over K steps is based on the one-step drift. Specifically, in the proof for a single step, we bound the error term ⟨ϵt, xt+1 - x⟩ using both constant terms and quadratic terms like ∥xt+1-x∥2 , with the objective of applying a telescoping summation across K steps. Another key point in obtaining the (K)-step Lyapunov drift lies in determining the values of ϕt and ηt, which control the behavior of the drift.

This lemma implies that if the norm of the virtual queue satisfies ∥Qt∥ ≥ K2 δ+KC Kδ-G-D2 , the drift becomes negative, leading to a decrease in the virtual queue norm over the next K steps, i.e., ∥Qt+K∥2 ≤ ∥Qt∥2 . Intuitively, when the current violation is large at step t, the algorithm will reduce the violation after K steps. This is the central mechanism that ensures our algorithm achieves constant constraint violation.

Lemma 3. Under Assumptions 1-4, Optimistic-COCO ensures that

This lemma is derived from Lemma 2, the update rule of Optimistic-COCO, and the idea of contradiction. Then, the proof of constraint violation in Theorem 1 is directly derived by combining inequality (10) and this lemma.

Regret Analysis

Let x = x∗ in Lemma 1 and note Q⊤t+1g(x∗ ) ≤ 0 because Qt+1 ≥ 0 from the update rule of virtual queue and x∗ is a feasible solution to COCO such that g(x∗ ) ≤ 0. Then we have the following lemma.

Lemma 4. Based on Lemma 1, set αt = 8ηt, we can bound the one-step regret as

Note that most of the terms in this lemma can be bounded by telescope summation when proving the regret bound because ϕt+1 ≥ ϕt and 1 2ηt+1 ≥ 1 2ηt from the definition of ϕt and ηt. And it can be seen that the terms (ϕt-1 - ϕt-2)∥Qt-1∥ and αt 2 ∥∇ft -∇ft-1∥2 are part of the costs that our algorithm incurs to achieve adaptiveness. If we have prior knowledge of VT , the bound is obvious. While in our proof, ∑ts=1 (ϕs-1 - ϕs-2)∥Qs-1∥ can be well bounded by Lemma 3 and the term ∑t-1 s=1 αs 2 ∥∇fs - ∇fs-1∥2 can be bound by the following lemma.

Lemma 5. Recall the definition of ηt in Theorem 1 and αt = 8ηt, we have the following inequality,

Now we are ready to present the final bound of regret. Taking summation of the inequality (11) over time step t, we get that, for all t ∈ [T],

where we use the definition of ϕt and ∥Qt∥ = O(1) from Lemma 3. C1,C2,C3 are constants and the full proof can be found in the Appendix.

5 Experiment

In this section, we present a series of synthetic experiments designed to evaluate the performance of the OptimisticCOCO algorithm under both dynamic and slowly-changing environments. Our goal is to assess how well our algorithm adapts to varying conditions and to compare its performance against several well-established algorithms, specifically, those proposed in [Mahdavi et al., 2012; Yu and Neely, 2020; Qiu et al., 2023]. Similar to the setups used in [Yu and Neely, 2020; Yi et al., 2021], we consider a scenario where the loss functions are linear, defined as ft(x) = ⟨ct, x⟩, where ct is a time-varying coefficient. The constraint function is expressed as Ax ≤ b, with the decision variable x belonging to R2 . The constraint matrix A ∈ R3×2 and vector b ∈ R2 are fixed and generated uniformly within the intervals [0.1, 0.5] for A and [0, 0.2] for b, respectively. We set the total number of rounds to T = 5000 and select the feasible set X0 = [-1, 1]2 . For each algorithm, we track and plot the cumulative loss and violation over time.

Dynamic environment: In the dynamic setting, we define ct = c1(t) + c2(t) + c3(t), where c1(t) is uniformly drawn from [-t1/10 , t1/10 ], c2(t) is uniformly drawn from [-1, 0] for t ∈ [1, 1500] ∪ [2000, 3500] ∪ [4000, 5000] and from [0, 1] otherwise, and c3(t) = (-1)µ(t) , where µ(t) is a random permutation of the vector [1, T]. Figures 1(a) and 1(b) demonstrate that Optimistic-COCO outperforms the baseline algorithms in both regret and violation. From Figure 1(a), it can be seen that all algorithms achieve similar performance level of regret, consistent with the O(√T) guarantee in the worstcase scenario under a highly dynamic environment. And algorithms with O(1) violation guarantee show better performance in Figure 1(b).

Slowly-changing environment: We also conduct experiments in a slowly-changing environment to justify the problem-dependent theoretical guarantees. The loss functions remain fixed within each 100-round segment. At the start of each segment, the linear factor c is uniformly drawn from [0, 1], and ct = c remains constant for the following 100 rounds. In this setting, the regret bound of O(√Vt) is much smaller than O(√T) since the loss functions do not vary at each round. Figures 1(c) and 1(d) show that Optimistic-COCO consistently outperforms all baseline algorithms and significantly surpasses the algorithms in [Mahdavi et al., 2012; Yu and Neely, 2020], which aligns with the theoretical gap between O(√VT ) and O(√T). Figure 1(d) demonstrates that algorithms with O(1) guarantee still maintain strong violation performance, with Optimistic-COCO performing slightly better

It's important to highlight that our algorithm is fully adaptive, whereas we provided non-causal information about T and VT to algorithms in [Mahdavi et al., 2012; Yu and Neely, 2020; Qiu et al., 2023] to configure the learning rate. Despite this advantage, our algorithm achieves the best performance in both environments without requiring any prior knowledge, thereby validating our theoretical guarantees.

6 Conclusion

In this paper, we investigate constrained online convex optimization (COCO) and introduce Optimistic-COCO, a gradient-based algorithm that integrates optimistic designs with the "drift-plus-penalty" framework. We prove that Optimistic-COCO achieves a gradient-variation bound of O(√Vt) for regret and constant bound for violation, thereby encompassing and improving upon state-of-the-art results. Our algorithm is fully adaptive, requiring no prior knowledge of the time horizon T or the total gradient variation VT , effectively addressing the open problem highlighted in [Qiu et al., 2023]. These advances are made possible through a refined design of the scaled virtual queue and an optimistic regret analysis. Our experimental results further corroborate the theoretical findings.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant 62302305 and the Core Facility Platform of Computer Science and Communication, SIST, ShanghaiTech University.