An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints

\nameJordan Lekeufack \email[email protected]
\addrDepartment of Statistics
University of California, Berkeley
\AND\nameMichael I. Jordan \email[email protected]
\addrDepartment of Statistics / Department of Electrical Engineering and Computer Science
University of California, Berkeley

Abstract

We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make repeated decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ cumulative constraint violations to $O(\sqrt{\mathcal{E}_{T}(f)})$ and $\tilde{O}(\sqrt{\mathcal{E}_{T}(g)})$ , respectively, where $\mathcal{E}_{T}(f)$ and $\mathcal{E}_{T}(g)$ represent the cumulative prediction errors of the loss and constraint functions. In the worst case, where $\mathcal{E}_{T}(f)=O(T)$ and $\mathcal{E}_{T}(g)=O(T)$ (assuming bounded loss and constraint functions), our rates match the prior $O(\sqrt{T})$ results. However, when the loss and constraint predictions are accurate, our approach yields significantly smaller regret and cumulative constraint violations. Notably, if the constraint function remains constant over time, we achieve $\tilde{O}(1)$ cumulative constraint violation, aligning with prior results.

1 Introduction

We are interested in generalizations of Online Convex Optimization (OCO) to problems in which constraints are imposed—generalizations which we refer to as Constrained Online Convex Optimization (COCO). Recall the standard formulation of OCO (Orabona, 2019; Hazan, 2023): At each round $t$ , a learner makes a decision $x_{t}\in{\cal X}$ , receives a loss function $f_{t}$ from the environment, and suffers the loss $f_{t}(x_{t})$ . The goal of the learner is to minimize the cumulative loss $\sum_{t=1}^{T}f_{t}(x_{t})$ . In COCO, the learner additionally must attempt to satisfy a (potentially adversarial) constraint of the form $g_{t}(x_{t})\leq 0$ at every time step. The learner observes $g_{t}$ only after selecting $x_{t}$ , and cannot always satisfy the constraint exactly but can hope to have a small cumulative constraint violation. In the adversarial setting it is not viable to seek absolute minima of the cumulative loss, and the problem is generally formulated in terms of obtaining a sublinear Regret—the difference between the learner’s cumulative loss and the cumulative loss of a fixed decision. Having a sublinear regret means that we perform as well as the best action in hindsight. In the COCO problem we also aim to ensure small cumulative constraint violation.

COCO has been studied extensively over the past two decades, starting with Mahdavi et al. (2012); Jenatton et al. (2016); Yu and Neely (2020) that assumed time-invariant constraints. There has also been work on time-varying constraints (Neely and Yu, 2017; Liu et al., 2022) under a Slater assumption: ( $\exists\check{x}\in{\cal X},\xi>0,\forall t,g_{t}(\check{x})\leq-\xi)$ . The guarantees presented by those authors are polynomial in $\xi$ , which unfortunately can be made arbitrarily small by the adversary. More recent work has established bounds on regret that scale as $O(\sqrt{T})$ with constraint violations scaling as $O(\sqrt{T}\log T)$ (Guo et al., 2022; Yi et al., 2023; Sinha and Vaze, 2024).

Recent work in OCO has considered settings in which the adversary is predictable—i.e., not entirely arbitrary—aiming to obtain improved regret bounds. For example, Chiang et al. (2012); Rakhlin and Sridharan (2013b) studied the case in which using the previous function $f_{t-1}$ is used as a prediction at the current time step (i.e., $\hat{f}_{t}=f_{t-1}$ ). They showed that the regret improved from $O(\sqrt{T})$ to $O(\sqrt{{\cal E}_{T}(f)})$ where ${\cal E}_{T}(f)$ is a measure of the cumulative prediction error. This optimistic framework has also been studied in the COCO setting by Qiu et al. (2023), who focused on time-invariant constraints. Those authors established a similar bound for regret with $O(1)$ violations. This line of work was pursued further in Anderson et al. (2022), who, considering the case of the case of adaptive constraints and perfect predictions, established a $O(1)$ bound on regret with constraint violations of the order $O(\sqrt{T})$ .

In the current paper we go beyond earlier work to consider the case of adversarial constraints. Specifically, our contributions are as follows:

1.

We present the first algorithm to solve COCO problems in which the constraints are adversarial but also predictable. We present a meta-algorithm that, when built on an optimistic OCO algorithm, achieves $O(\sqrt{{\cal E}_{T}(f)})$ regret and $O((\sqrt{{\cal E}_{T}(g)}+G)\log T)$ constraint violation.
2.

When applied to problems having fixed constraints our meta-algorithm achieves a $O(\sqrt{{\cal E}_{T}(f)})$ regret and $O(\log T)$ constraint violation, matching previous work up to a $\log T$ term.

The rest of the paper is structured as follow: We present previous work in Appendix 2, introduce the main assumptions and notation in Appendix 3, and review optimistic OCO in Appendix 4. In Appendix 5, we present our meta-algorithm for the COCO problem and establish theoretical guarantees.

Reference	Complexity per round	Constraints	Loss Function	Regret	Violation
Guo et al. (2022)	Conv-OPT	Fixed	Convex	$O(\sqrt{T})$	$O(1)$
		Adversarial	Convex	$O(\sqrt{T})$	$O(T^{3/4})$
Yi et al. (2023)	Conv-OPT	Adversarial	Convex	$O(T^{\max(c,1-c})$	$O(T^{1-c/2})$
Sinha and Vaze (2024)	Projection	Adversarial	Convex	$O(\sqrt{T})$	$O(\sqrt{T}\log T)$
Qiu et al. (2023)	Projection	Fixed	Convex, Slater	$O(\sqrt{V_{\star}(T)})$	$O(1)$
Ours	Projection	Fixed	Convex	$O(\sqrt{{\cal E}_{T}(f)})$	$O(\log T)$
	Projection	Adversarial	Convex	$O(\sqrt{{\cal E}_{T}(f)})$	$O((\sqrt{{\cal E}_{T}(g)})\log T)$

Table 1: Comparison with existing work.

{\cal E}_{T}(f)

and

{\cal E}_{T}(g)

are measures of the prediction error.

V_{\star}=\sum_{t=2}^{T}\sup_{x}||\nabla f_{t}(x)-\nabla f_{t-1}(x)||_{\star}^{2}

. Note that when the prediction is the previous loss,

{\cal E}_{T}(f)=V_{\star}

2 Related Work

Unconstrained OCO

The OCO problem was introduced in Zinkevich (2003), who established a $O(\sqrt{T})$ guarantee based on projected online gradient descent (OGD). Hazan (2023); Orabona (2019) provide overviews of the burgeoning literature that has emerged since Zinkevich’s seminal work, in particular focusing on online mirror descent (OMD) as a general way to solve OCO problems.

Optimistic OCO

Optimistic OCO is often formulated as a problem involving gradual variation—i.e., where $\nabla{f}_{t}$ and $\nabla{f}_{t-1}$ are close in some appropriate metric. Chiang et al. (2012) exploit this assumption in an optimistic version of OMD that incorporates a prediction based on the most recent gradient, and establish a regret bound of $O(\sqrt{V_{*}})$ where $V_{*}=\sum_{t=2}^{T}\sup_{x\in{\cal X}}||\nabla{f}_{t}(x)-\nabla{f}_{t-1}(x)||_{\star}^{2}$ . Rakhlin and Sridharan (2013a, b) prove that when using a predictor $M_{t}$ that is not necessarily the past gradient, one can have regret of the form $O\left(\sqrt{\sum_{t=1}^{T}||\nabla{f}_{t}(x_{t})-M_{t}||_{\star}^{2}}\right)$ .

Constrained OCO

Constrained OCO was first studied in the context of time-invariant constraints; i.e., where $g_{t}:=g$ for all $t$ . In this setup one can employ projection-free algorithms, avoiding the potentially costly projection onto the set ${\cal X}=\{x\in{\cal X}_{0},g(x)\leq 0\}$ , by allowing the learner to violate the constraints in a controlled way (Mahdavi et al., 2012; Jenatton et al., 2016; Yu and Neely, 2020). Qiu et al. (2023) studied the case with gradual variations, proving a $O(\sqrt{V_{*}})$ regret guarantee and a $O(1)$ constraint violation. The case of time-varying constraints is significantly harder as the constraints $g_{t}$ are potentially adversarial. Most of the early work studying such constraints (Neely and Yu, 2017; Yi et al., 2023) accordingly incorporated an additional Slater condition: $\exists\check{x}\in{\cal X},\nu>0,\forall t,\;g_{t}(\check{x})\leq-\nu$ . These papers establish regret guarantees that grow with $\nu^{-1}$ , which unfortunately can be vacuous as $\nu$ can be arbitrarily small. Guo et al. (2022) present an algorithm that does not require the Slater condition and yielded improved bounds but it requires solving a convex optimization problem at each time step. In a more recent work, Sinha and Vaze (2024) presented a simple and efficient algorithm to solve the problem with just a projection and obtained state-of-the-art guarantees. See Table 1 for more comparison of our results with previous work.

3 Preliminaries

3.1 Problem setup and notation

Let $\mathbb{R}$ denote the set of real numbers, and let $\mathbb{R}^{d}$ denote the set of $d$ -dimensional real vectors. Let ${\cal X}_{0}\subseteq\mathbb{R}^{d}$ denote the set of possible actions of the learner, where $x\in{\cal X}_{0}$ is a specific action, and let $||\cdot||$ be a norm defined on ${\cal X}_{0}$ . Let the dual norm be denoted as $||\theta||_{\star}:=\max_{x,||x||=1}\langle\theta,\ x\rangle$ .

Online learning is a problem formulation in which the learner plays the following game with Nature. At each step $t$ :

1.

The learner plays action $x_{t}\subseteq{\cal X}_{0}$ .
2.

Nature reveals a loss function $f_{t}:{\cal X}_{0}\to\mathbb{R}$ and a constraint function $g_{t}:{\cal X}_{0}\to\mathbb{R}$ .¹¹1If we have multiple constraint functions ${\mathbf{g}}_{t,k}$ , we set $g_{t}:=\max_{k}{\mathbf{g}}_{t,k}$ .
3.

The learner receives the loss $f_{t}(x_{t})$ and the constraint violation $g_{t}(x_{t})$ .

In standard OCO, the loss function $f_{t}$ is convex, and the goal of the learner is to minimize the regret with respect to an oracle action $u$ , where:

\text{Regret}_{T}(u):=\sum_{t=1}^{T}f_{t}(x_{t})-f_{t}(u).

(1)

In COCO, we generalize the OCO problem to additionally ask the learner to obtain a small cumulative constraint violation, which we denote as $\text{CCV}_{T}$ :

\text{CCV}_{T}=\sum_{t=1}^{T}g_{t}^{+}(x_{t})\quad\text{where}\quad g_{t}^{+}(x):=\max\{0,g_{t}(x)\}.

(2)

Overall, the goal of the learner is to achieve both sublinear regret and sublinear CCV. This is a challenging problem, and indeed Mannor et al. (2009) proved that no algorithm can achieve both sublinear regret and sublinear cumulative constraint violation for an oracle in the set ${\cal X}^{\prime}:=\{x\in{\cal X}_{0},\sum_{t=1}^{T}g_{t}(x)\leq 0\}$ . However, it is possible to find algorithms that achieve sublinear regret for the smaller set ${\cal X}:=\{x\in{\cal X}_{0},g_{t}(x)\leq 0,\;\forall t\in[T]\}$ , and this latter problem is our focus.

Finally, we will assume that at the end of step $t$ , the learner can make predictions $\hat{f}_{t+1}$ and $\hat{g}_{t+1}$ . More precisely, we will be interested in predictions of the gradients, and, for any function $h$ , we will denote by $\nabla\hat{{h}}_{t}$ the prediction of the gradient of $h$ . We will abuse notation and denote by $\hat{h}$ the function whose gradient is $\nabla\hat{{h}}_{t}$ . Moreover, we define the following prediction errors

\begin{split}\varepsilon_{t}(h)&:=||\nabla{h}_{t}(x_{t})-\nabla\hat{{h}}_{t}(x_{t})||_{\star}^{2},\\ {\cal E}_{t}(h)&:=\sum_{\tau=1}^{t}\varepsilon_{\tau}(h),\end{split}

(3)

where $(x_{t})_{t=1\dots T}$ is the sequence of actions taken by the learner.

Additionally, for a given $\beta$ -strongly convex function $R$ , we define the Bregman divergence between two points:

B^{R}(x;y):=R(x)-R(y)-\langle\nabla R(x),\ x-y\rangle.

(4)

Two special cases that are particularly important:

1.

When $R(x):=\frac{1}{2}||x||_{2}^{2}$ , the Bregman divergence is the Euclidean distance $B^{R}(x;y)=||y-x||_{2}^{2}$ , $\beta=1$ with respect to the L2 norm, and $||\cdot||=||\cdot||_{\star}=||\cdot||_{2}$ .
2.

When $R(x):=-\sum_{i=1}^{d}x_{i}\log x_{i}$ , the Bregman divergence is the KL divergence : $B^{R}(x;y)=D_{\text{KL}}(x;y):=\sum_{i=1}^{d}x_{i}\log\frac{x_{i}}{y_{i}}$ , $\beta=1$ with respect to the L1 norm, and $||\cdot||=||\cdot||_{1}$ , $||\cdot||_{\star}=||\cdot||_{\infty}$ .

3.2 Assumptions

Throughout this paper we will use various combinations of the following assumptions.

Assumption 1 (Convex set, loss and constraints).

We make the following standard assumptions on the loss $f$ :

1.

${\cal X}_{0}$ is closed, convex and bounded with diameter $D$ .
2.

$\forall t$ , $f_{t}$ is convex and differentiable.
3.

$\forall t$ , $g_{t}$ is convex and differentiable.

Assumption 2 (Bounded losses).

The loss functions $f_{t}$ are bounded by $F$ and the constraints $g_{t}$ are bounded by $G$ .

Assumption 3 (Feasibility).

The set ${\cal X}$ is not empty.

Assumption 4 (Lipschitz gradients).

For any $t$ , the gradient of the loss function $f_{t}$ and the gradient of the constraint function $g_{t}$ are $L^{f}_{t}$ and $L^{g}_{t}$ Lipschitz, respectively. That is, $\forall x,y\in{\cal X}_{0}$ , we have:

	$\displaystyle\|\|\nabla{f}_{t}(x)-\nabla{f}_{t}(y)\|\|_{\star}$	$\displaystyle\leq L^{f}_{t}\|\|x-y\|\|,$
	$\displaystyle\|\|\nabla{g}_{t}(x)-\nabla{g}_{t}(y)\|\|_{\star}$	$\displaystyle\leq L^{g}_{t}\|\|x-y\|\|.$

We will abuse notation and denote $L^{f}_{t}:=\max_{\tau\leq t}L^{f}_{\tau}$ , and similarly for $\hat{L}^{g}_{t}$ . Moreover, we will assume that there is a constant $L^{f}$ such that $L^{f}=\max_{t}L^{f}_{t}$ . We similarly define $L^{g}$ .

Assumption 5 (Prediction Sequence Regularity).

The prediction sequence of loss functions is such that $\forall t,\nabla\hat{{f}}_{t}$ is $\alpha_{f}$ -smooth and $\nabla\hat{{g}}_{t}$ is $\alpha_{g}$ -smooth: $\forall x,y\in{\cal X}_{0}$

	$\displaystyle\|\|\nabla\hat{{f}}_{t}(x)-\nabla\hat{{f}}_{t}(y)\|\|_{\star}$	$\displaystyle\leq\hat{L}^{f}_{t}\|\|x-y\|\|,$
	$\displaystyle\|\|\nabla\hat{{g}}_{t}(x)-\nabla\hat{{g}}_{t}(y)\|\|_{\star}$	$\displaystyle\leq\hat{L}^{g}_{t}\|\|x-y\|\|.$

We again abuse notation and let $\hat{L}^{f}:=\max_{\tau\leq t}\hat{L}^{f}_{\tau}$ and similarly for $\hat{L}^{g}$ .

Remark 6.

Note that those assumptions are all standard for different types of problems:

•

Assumptions 1, 4 or 5 are standard in OCO with predictive sequences (Chiang et al., 2012; D’Orazio and Huang, 2021; Qiu et al., 2023).
•

Assumptions 1, 2, 3 are standard in COCO.

The only non-standard assumption in 5, but when using past functions as predictions, it is actually equivalent to 4.

4 Optimistic Algorithms for OCO

In this section, we introduce some of the foundational optimistic algorithms that have been used for OCO. Our meta-algorithm to solve COCO problems will repose on these foundational ingredients.

4.1 Optimistic OMD and Optimistic AdaGrad

Algorithm 1 Optimistic Online Mirror Descent (Rakhlin and Sridharan, 2013b)

1:Sequence

\eta_{t}>0

x_{1}

2:Initialize

\eta_{1}

3:for round

t=1\dots T

4: Play action

x_{t}

, receive

f_{t}

. Compute

\nabla{f}_{t}(x_{t})

5: Compute

\eta_{t+1}

\tilde{x}_{t+1}:=\arg\min_{x\in{\cal X}_{0}}\langle\nabla{f}_{t}(x_{t}),\ x\rangle+\frac{1}{\eta_{t}}B^{R}(x;\tilde{x}_{t}).

\triangleright

Mirror step.

7: Make prediction

\nabla\hat{{f}}_{{t+1}}(\tilde{x}_{t+1}).

x_{t+1}:=\arg\min_{x\in{\cal X}_{0}}\langle\nabla\hat{{f}}_{t}(\tilde{x}_{t+1}),\ x\rangle+\frac{1}{\eta_{t+1}}B^{R}(x;\tilde{x}_{t+1}).

\triangleright

Optimistic Mirror step.

9:end for

Theorem 7 (Optimistic OMD).

Under Assumptions 1, 5 with $L^{f}_{t}\leq\frac{\beta}{\eta_{t}}$ . If $\forall t,\eta_{t+1}\leq\eta_{t}$ , $\forall t$ , then for any $u\in{\cal X}_{0}$ ,

\text{Regret}_{T}(u)\leq\frac{2B}{\eta_{T+1}}+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}\varepsilon_{t}^{f},

(5)

where $B\geq\max_{t\in[T],x\in{\cal X}_{0}}B^{R}(x;\tilde{x}_{t})$ .

If $\eta_{t}:=\eta$ constant, we have

\text{Regret}_{T}(u)\leq\frac{2B^{R}(u;x_{1})}{\eta}+\frac{\eta}{\beta}{\cal E}_{T}(f).

(6)

For completeness we present a proof of this result in Appendix A, adapting the proof from Rakhlin and Sridharan (2013b) with the important change that the regret depends on $\varepsilon_{t}(f)$ instead of $||\nabla\hat{{f}}_{t}(\tilde{x})-\nabla{f}_{t}(x)||_{\star}^{2}$ . This is significant as $\varepsilon_{t}(f)$ equals zero when the predictions are perfect, but $||\nabla\hat{{f}}_{t}(\tilde{x})-\nabla{f}_{t}(x)||_{\star}^{2}$ might not be zero.

In order to obtain the optimal convergence rate with a fixed learning learning rate, we must set $\eta=\sqrt{\frac{\beta B^{R}(u;x_{1})}{{\cal E}_{T}(f)}}$ with requires knowing ${\cal E}_{T}(f)$ in advance. We mitigate this issue via the use of adaptive learning rates, in the style of Rakhlin and Sridharan (2013b). Note also that D’Orazio and Huang (2021) present an algorithm for a more general class of algorithms called Lagrangian hedging, OMD being a special case. However, this algorithm requires knowledge of $\max_{t}\varepsilon_{t}(f)$ , which our approach does not require.

Theorem 8 (Adapted from Rakhlin and Sridharan (2013b), Corollary 2).

Under Assumptions 1, 3, 5 with $\hat{L}^{f}_{t}\leq\sqrt{\beta}L^{f}_{t}$ , if $\eta_{t}$ is:

\eta_{t}=\min\left\{\frac{\sqrt{\beta B}}{\sqrt{{\cal E}_{t-1}(f)}+\sqrt{{\cal E}_{t-2}(f)}},\frac{\sqrt{\beta}}{L^{f}_{t}}\right\},

(7)

then Algorithm 1 has regret

\text{Regret}_{T}(u)\leq 5\sqrt{\frac{B}{\beta}}\left(\sqrt{{\cal E}_{T}(f)}+\sqrt{B}L^{f}_{T}\right)=O\left(\sqrt{{\cal E}_{T}(f)}\vee L^{f}_{T}\right),

(8)

where $B\geq\max_{t\in[T],x\in{\cal X}_{0}}B^{R}(x;\tilde{x}_{t})$ .

Rakhlin and Sridharan (2013b) use a slightly different learning rate—instead of $\sqrt{\beta}/L^{f}_{t}$ , they use 1. We modify that learning rate to be dependent on $L^{f}_{t}$ because this allows the scale of the function to vary over time, which will be useful in the generalization to COCO. If the functions $f_{t}$ are linear, we can use any $L_{t}^{f}>0$ .

The proof is in Appendix B.

Remark 9.

Note that the algorithm is computationally efficient. Indeed, a mirror step $x^{\star}=\arg\min_{x\in{\cal X}_{0}}\langle\ell,\ x\rangle+\frac{1}{\eta}B^{R}(x;z)$ can be computed in two steps:

1.

Compute $y$ such that $\nabla R(y)=\nabla R(z)-\eta\ell$ . In particular, if $\nabla R$ is invertible, $y=(\nabla R)^{-1}(\nabla R(z)-\eta\ell)$ .
2.

Let $x^{\star}=\Pi_{{\cal X}_{0},R}(y):=\arg\min_{x\in{\cal X}_{0}}B^{R}(x;y)$ .

Moreover, we have two special cases of interest:

1.

When $||\cdot||=||\cdot||_{\star}$ and $R(x)=\frac{1}{2}||x||_{2}^{2}$ , this is simply projected gradient descent, $x^{\star}=\Pi_{{\cal X}_{0}}\left(z-\eta\ell\right)$ .
2.

When ${\cal X}=\Delta_{d}$ the $d$ -dimensional simplex, with $R$ being the entropy, $x^{\star}_{i}=\frac{z_{i}}{Z}\exp(-\eta\ell_{i})$ , where $Z$ is a normalizing factor to ensure $||x^{\star}||_{1}=1$ .

4.2 Optimistic OMD for learning with experts

In this setting, the agent has access to $d$ experts and has to form a distribution for selecting among them. She observes the loss of each expert and suffers an overall loss which is the expected value over the experts. Formally, we assume ${\cal X}_{0}=\Delta_{d}$ where $d$ is the number of experts. At each step $t$ , the learner selects $x_{t}\in\Delta_{d}$ , a distribution over experts, and observes $\ell_{t}\in\mathbb{R}^{d}$ , which is the vector of loss across the experts. The learner then suffers the loss $f_{t}(x_{t})=\langle\ell_{t},\ x_{t}\rangle$ . We will let $\hat{\ell}_{t}$ denote the prediction of $\ell_{t}$ .

We could use the Algorithm 1 with $||\cdot||=||\cdot||_{2}$ , but in the worst case $B$ can be as large as $O(d)$ resulting in a regret scaling in $O(\sqrt{d})$ . We instead are able achieve a scaling of $O(\log(d))$ . Let $||\cdot||=||\cdot||_{1}$ and $||\cdot||_{\star}=||\cdot||_{\infty}$ . In that case, the Bregman divergence is the KL divergence and $\beta=1$ . However, the KL divergence is not upper bounded as any $x_{t,i}$ can be close to zero. We circumvent this problem in Algorithm 2 by introducing the mixture $y_{t}=(1-\delta)\tilde{x}_{t}+\frac{\delta}{d}\bm{1}$ . This algorithm can be found in Rakhlin and Sridharan (2013b) in the context of a two-player zero-sum game.

Algorithm 2 Optimistic Online Mirror Descent For Experts (Rakhlin and Sridharan (2013b)

1:Sequence

x_{1},\delta

2:Initialize

\eta_{1}

3:for round

t=1\dots T

4: Play action

x_{t}

, receive

\ell_{t}

5: Compute

\eta_{t+1}

\tilde{x}_{t+1}:=\arg\min_{x\in{\cal X}_{0}}\langle\ell_{t},\ x\rangle+\frac{1}{\eta_{t}}D_{\text{KL}}(x;y_{t}).

\triangleright

Mirror step.

7: Construct mixture

y_{t+1}=(1-\delta)\tilde{x}_{t+1}+\frac{\delta}{d}\bm{1}.

8: Make prediction

\hat{\ell}_{t+1}

x_{t+1}:=\arg\min_{x\in{\cal X}_{0}}\langle\hat{\ell}_{t+1},\ x\rangle+\frac{1}{\eta_{t+1}}D_{\text{KL}}(x;y_{t+1}).

\triangleright

Optimistic Mirror step.

10:end for

Theorem 10 (Optimistic OMD with experts ).

Under Assumption 1 and for any $t$ , $\nabla\hat{{f}}_{t}$ is a constant function. If $\eta_{t+1}\leq\eta_{t},\forall t$ , and $\delta=1/T$ , then

\text{Regret}_{T}(u)\leq\frac{\log(d^{2}T)}{\eta_{T+1}}+\sum_{t=1}^{T}\eta_{t+1}\varepsilon_{t}(f)+\frac{1}{2}\left(\eta_{T+1}^{-1}-\eta_{1}^{-1}\right).

(9)

Moreover, by using $\eta_{t}$ defined as

\eta_{t}=\sqrt{\log(d^{2}Te)}\min\left\{\frac{1}{\sqrt{{\cal E}_{t-1}(f)}+\sqrt{{\cal E}_{t-2}(f)}},1\right\},

(10)

the regret guarantee becomes:

\text{Regret}_{T}(u)\leq 2\sqrt{\log(d^{2}Te)}\left(\sqrt{{\cal E}_{T}(f)}+1\right)=O\left(\sqrt{{\cal E}_{T}(f)\log T}\right).

(11)

5 Meta-Algorithm for Optimistic COCO

Algorithm 3 Optimistic learning with hard constraints

x_{1}\in{\cal X}_{0}

\lambda>0

Q_{0}=0

, OCO algorithm

{\cal A}

2:for round

t=1\dots T

3: Play action

x_{t}

, receive

f_{t}

and

g_{t}

4: Compute

{\cal L}

defined in (12).

5: Update

Q_{t+1}=Q_{t}+\lambda g^{+}_{t}(x_{t})

\triangleright

Dual update.

6: Compute prediction

\hat{\cal L}_{t+1}

as in (13).

7: Update

x_{t+1}:={\cal A}_{t}(x_{t},{\cal L}_{1},\dots,{\cal L}_{t},\hat{\cal L}_{t+1})

8:end for

Our meta-algorithm is inspired by Sinha and Vaze (2024). The main idea of that paper is to build a surrogate loss function ${\cal L}_{t}$ that can be seen as a Lagrangian of the optimization problem

\min_{x\in{\cal X}_{0},g_{t}(x)\leq 0}f_{t}(x).

The learner then runs AdaGrad (Duchi et al., 2011) on the surrogate, with a theoretical guarantee of bounded cumulative constraint violation (CCV) and Regret.

Our meta-algorithm is based on the use of optimistic methods, such as those presented in Appendix 4, which allows us to obtain stronger bounds that depends on the prediction quality. Presented in Algorithm 3, this algorithm assumes that at the end of every step $t$ , the learner makes a prediction $\hat{f}_{t+1}$ and $\hat{g}_{t+1}$ of the upcoming loss $f_{t+1}$ and constraint $g_{t+1}$ .²²2We are actually only interested in the predictions of the gradients, but for simplicity we will let $\hat{h}$ denote any function whose gradient is the prediction of the gradient $\nabla\hat{{h}}_{t}$ . At each time step $t$ , the learner forms a surrogate loss function, defined via a convex potential Lyapunov function: $\Phi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ , $\Phi(0)=0$ where $\Phi$ is non-decreasing. Specifically:

{\cal L}_{t}(x)=Vf_{t}(x)+\lambda\Phi^{\prime}(Q_{t})g^{+}_{t}(x).

(12)

Using the predictions $\hat{f}$ and $\hat{g}$ , we form a prediction of the Lagrange function $\hat{\cal L}_{t+1}$ , where $\hat{\cal L}_{t}$ is defined in Equation 13.

\hat{\cal L}_{t}(x)=V\hat{f}_{t}(x)+\lambda\Phi^{\prime}(Q_{t})\hat{g}^{+}_{t}(x).

(13)

In Sinha and Vaze (2024), the update is $Q_{t}=Q_{t-1}+\lambda g^{+}_{t}(x_{t})$ , but using $\hat{\cal L}_{t+1}$ at $t$ requires $Q_{t+1}$ to be known at the end of $t$ . We instead define the following update:

Q_{t+1}=Q_{t}+\lambda g^{+}_{t}(x_{t}),\quad\text{with }Q_{0}=Q_{1}=0.

(14)

The learner then executes the step $t$ of algorithm ${\cal A}$ , denoted ${\cal A}_{t}$ in Algorithm 3. We then have the following lemma that relates the regret on $f$ , CCV, and the regret of ${\cal A}$ on ${\cal L}$ .

Lemma 11 (Regret decomposition).

For any algorithm ${\cal A}$ , if $\Phi$ is a Lyapunov potential function, we have that for any $t\geq 1$ , and any $u\in{\cal X}$

\Phi(Q_{t+1})+\text{Regret}_{t}(u)\leq\text{Regret}_{t}^{\cal A}(u;\;{\cal L}_{1\dots t})+S_{t},

(15)

where $S_{t}=\lambda\sum_{\tau=1}^{t}g^{+}_{\tau}(x_{\tau})(\Phi^{\prime}(Q_{\tau+1})-\Phi^{\prime}(Q_{\tau}))$ , and $\text{Regret}_{t}^{\cal A}(u;\;{\cal L}_{1\dots t})$ is the regret of the algorithm running on ${\cal L}$ .

Proof By convexity of $\Phi$ :

\Phi(Q_{t+1})\leq\Phi(Q_{t})+\Phi^{\prime}(Q_{t+1})(Q_{t+1}-Q_{t})=\Phi(Q_{t})+\Phi^{\prime}(Q_{t+1})\lambda g^{+}_{t}(x_{t}).

Let $u\in{\cal X}$ , then by definition $g^{+}_{t}(u)=0,\forall t\geq 1$ , thus

	$\displaystyle\Phi(Q_{\tau+1})-\Phi(Q_{\tau})+$	$\displaystyle V(f_{\tau}(x_{\tau})-f_{\tau}(u))$
		$\displaystyle\leq\Phi^{\prime}(Q_{\tau+1})\lambda g^{+}_{\tau}(x_{\tau})+V(f_{\tau}(x_{\tau})-f_{\tau}(u))$
		$\displaystyle\leq Vf_{\tau}(x_{\tau})+\lambda\Phi^{\prime}(Q_{\tau})g^{+}_{\tau}(x_{\tau})-\big{(}(Vf_{\tau}(u)+\lambda\Phi^{\prime}(Q_{\tau})g^{+}_{\tau}(u)\big{)}$
		$\displaystyle\quad\quad+\lambda g^{+}_{\tau}(x_{\tau})(\Phi^{\prime}(Q_{\tau+1})-\Phi^{\prime}(Q_{\tau}))$
		$\displaystyle\leq{\cal L}_{\tau}(x_{\tau})-{\cal L}_{\tau}(u)+\lambda g^{+}_{\tau}(x_{\tau})(\Phi^{\prime}(Q_{\tau+1})-\Phi^{\prime}(Q_{\tau})).$

Summing $\tau$ from $1$ to $t$ :

\Phi(Q_{t+1})-\Phi(Q_{1})+V\text{Regret}_{t}(u)\leq\text{Regret}_{t}^{\cal A}(u;\;{\cal L}_{1\dots t})+S_{t},

where

S_{t}=\lambda\sum_{\tau=1}^{t}g^{+}_{\tau}(x_{\tau})(\Phi^{\prime}(Q_{\tau+1})-\Phi^{\prime}(Q_{\tau})).

Below we will make the assumption that the underlying optimistic OCO algorithm has standard regret guarantees that we will express in terms of a functional $\psi$ that takes as input a sequence of functions, and returns a constant. For simplicity, we will denote $\psi(f_{1\dots t}):=\psi_{t}(f)$ . One example is $\psi_{t}(f)=L^{f}_{t}$ , another is $\psi_{t}(f)=F_{t}=\max_{\tau\leq t}||f_{\tau}||_{\star}$ .

Assumption 12 (Regret of optimistic OCO).

The optimistic OCO algorithm ${\cal A}$ has the following regret guarantee: There is a constant $C\in\mathbb{R}$ and a sublinear functional $\psi$ such that for any sequence of functions $(f_{t})_{t=1\dots T}$ , and any $u\in{\cal X}_{0}$

\text{Regret}_{t}^{\cal A}(u;f_{1\dots t})\leq C\left(\sqrt{{\cal E}_{t}(f)}\vee\psi_{t}(f)\right).

(16)

Theorem 13 (Optimistic OCO regret and CCVguarantees).

Consider the following assumptions :

1.

${\cal L}_{t}$ and $\hat{\cal L}_{t}$ satisfy the assumptions of algorithm ${\cal A}$ for all $t$ .
2.

Assumptions (1), (2), and (3).
3.

${\cal A}$ satisfies 12 for some constant $C$
4.

$\Phi(Q):=\exp(Q)-1$ .
5.

$\lambda=\left(2C\left(\sqrt{2{\cal E}_{T}(g)}+\psi_{T}(g)\right)+2G\right)^{-1}$ .

Under these assumptions, Algorithm 3 has the following regret and CCV guarantees: $\forall T\geq 1,\forall u\in{\cal X},\forall t\in[T]$ ,

$\displaystyle\text{Regret}_{t}(u)$	$\displaystyle\leq C\left(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f)\right)+1=O\left(\sqrt{{\cal E}_{t}(f)}\vee\psi_{t}(f)\right),$	(17)
$\displaystyle\text{CCV}_{T}$	$\displaystyle\leq 2\left(C(\sqrt{2{\cal E}_{T}(g)}+\psi_{T}(g))+G\right)\log\left(2\left(C\left(\sqrt{2{\cal E}_{T}(f)}+\psi_{T}(f)\right)+2FVT+2\right)\right)$
	$\displaystyle=O\left(\left(\sqrt{{\cal E}_{T}(g)}\vee\psi_{T}(g)\vee G\right)\log T\right).$	(18)

Proof Note that ${\cal L}$ is convex, and using (13), we obtain the following instantaneous prediction error:

	$\displaystyle\varepsilon_{t}({\cal L})$	$\displaystyle:=\|\|\nabla{{\cal L}}_{t}(x_{t})-\nabla\hat{{{\cal L}}}_{t}(x_{t})\|\|_{\star}^{2}$
		$\displaystyle\leq 2V^{2}\varepsilon_{t}(f)+\Phi^{\prime}(Q_{t})^{2}\lambda^{2}\varepsilon_{t}(g),$	$\displaystyle\text{using }\|\|a+b\|\|_{\star}^{2}\leq 2\|\|a\|\|_{\star}^{2}+2\|\|b\|\|_{\star}^{2}.$

Thus,

$\displaystyle\sqrt{{\cal E}_{t}({\cal L})}$	$\displaystyle\leq\sqrt{\sum_{\tau=1}^{t}2V^{2}\varepsilon_{\tau}(f)+\sum_{\tau=1}^{t}2\Phi^{\prime}(Q_{\tau})^{2}\lambda^{2}\varepsilon_{t}(g)}$
	$\displaystyle\leq\sqrt{\sum_{\tau=1}^{t}2V^{2}\varepsilon_{\tau}(f)+\sum_{\tau=1}^{t}2\Phi^{\prime}(Q_{\tau})^{2}\lambda^{2}\varepsilon_{t}(g)}$
	$\displaystyle\leq V\sqrt{2{\cal E}_{t}(f)}+\sqrt{\sum_{\tau=1}^{t}2\Phi^{\prime}(Q_{\tau})^{2}\lambda^{2}\varepsilon_{t}(g)}$	$\displaystyle\text{using }\sqrt{a+b}\leq\sqrt{a}+\sqrt{b},$
	$\displaystyle\leq V\sqrt{2{\cal E}_{t}(f)}+\lambda\Phi^{\prime}(Q_{t+1})\sqrt{2{\cal E}_{t}(g)}.$		(19)

By sub-linearity of $\psi_{t}$ :

\psi_{t}({\cal L}_{t})\leq V\psi_{t}(f)+\lambda\Phi^{\prime}(Q_{t})\psi_{t}(g)\leq V\psi_{t}(f)+\lambda\Phi^{\prime}(Q_{t+1})\psi_{t}(g).

Finally, using 12, we have

\text{Regret}_{t}^{\cal A}(u;\;{\cal L}_{1\dots t})\leq V\left(\sqrt{2{\cal E}_{T}(f)}+\psi_{t}(f)\right)+\lambda\Phi^{\prime}(Q_{t+1})\left(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g)\right),

using the fact that $Q_{t}$ is non-decreasing and $\Phi^{\prime}$ is a non-decreasing function. With those two assumptions, and knowing that $g^{+}_{t}$ is non-negative and upper bounded by $G$ we can also upper bound $S_{t}$ :

\displaystyle S_{t}\leq G\lambda(\Phi^{\prime}(Q_{{t+1}})-\Phi^{\prime}(Q_{1})).

We can now upper bound the regret: for any $u\in{\cal X}$

	$\displaystyle\exp(Q_{t+1})-\exp(Q_{1})+V\text{Regret}_{t}(u)\leq$	$\displaystyle C\lambda\exp(Q_{t+1})(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))$
		$\displaystyle+CV(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f))$
		$\displaystyle+G\lambda(\exp(Q_{t+1})-\exp(Q_{1})).$

Thus

\text{Regret}_{t}(u)\leq\left(\lambda C(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+\lambda G-1\right)\frac{\exp(Q_{t+1})}{V}+\frac{(1-G\lambda)}{V}+C(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f)).

(20)

Therefore, if $\lambda\leq\frac{1}{C(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+G}$ ,

\text{Regret}_{t}(u)\leq C\sqrt{2{\cal E}_{t}(f)}+\frac{\exp(\lambda_{1}G)}{V}\leq C\left(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f)\right)+\frac{1}{V}.

Note that the final inequality comes from using $\lambda\leq\frac{1}{G}$ . Also note that $\text{Regret}_{t}(u)\geq-2Ft$ , thus:

\exp(Q_{t+1})\left(1-\lambda\left(C(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+G\right)\right)\leq CV(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f))+2FVt+1.

(21)

If $\lambda<\frac{1}{C(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+G}$ , then

Q_{t+1}\leq\log\frac{CV(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f))+2FVt+1}{1-\lambda\left((\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+G\right)},

and

\text{CCV}_{t}\leq\frac{Q_{t+1}}{\lambda}\leq\frac{1}{\lambda}\log\frac{C(\sqrt{2{\cal E}_{t}(f)}+\psi_{t}(f))+2FVt+1}{1-\lambda\left(C(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+G\right)}.

With $\lambda=\frac{1}{2C(\sqrt{2{\cal E}_{t}(g)}+\psi_{t}(g))+2G}$ and $V=1$ , we have

	$\displaystyle\text{CCV}_{T}$	$\displaystyle\leq\left(2C\left(\sqrt{2{\cal E}_{T}(g)}+\psi_{T}(g)\right)+2G\right)\log\left(2\left(C(\sqrt{2{\cal E}_{T}(f)}+\psi_{T}(f))+2FT+1\right)\right)$
		$\displaystyle\leq O\left((\sqrt{{\cal E}_{T}(g)}+\psi_{T}(g)+G)\log T\right).$

Remark 14.

For unknown $T$ , we can use the doubling trick, and use the previous prediction errors to estimate ${\cal E}_{T}(g)$ .

Finally, we have the following corollaries that are direct consequences of applying Algorithm 3, depending on the setting and the properties of the algorithm ${\cal A}$ .

Corollary 15 (Optimistic Adagrad COCO).

Consider the following assumptions:

1.

${\cal A}$ is optimistic Adagrad described in Algorithm 1 with $L^{{\cal L}}_{t}=VL^{f}_{t}+\Phi^{\prime}(Q_{t})L^{g}_{t}$ .
2.

5 with $\hat{L}^{f}_{t}\leq\sqrt{\beta}L^{f}_{t}$ and $\hat{L}^{g}_{t}\leq\sqrt{\beta}L^{g}_{t}$ .
3.

$\lambda$ and $\Phi$ are set as in Theorem 13.

Under these assumptions, the meta-algorithm (3) has the following regret and constraint violation guarantees:

\begin{split}\text{Regret}_{T}(u)&\leq O\left(\sqrt{{\cal E}_{T}(f)}\vee L^{f}\right),\\ \text{CCV}_{T}&\leq O\left(\left(\sqrt{{\cal E}_{T}(g)}\vee G\vee L^{g}\right)\log T\right).\end{split}

(22)

Proof This is a direct consequence of Theorem 13. We only need to show that $\hat{\cal L}$ satisfies the assumption of ${\cal A}$ :

1.

There is some $\hat{L}^{{\cal L}}_{t}$ such that $\nabla\hat{{{\cal L}}}_{t}$ is $\hat{L}^{{\cal L}}_{t}$ -Lipschitz.
2.

$\nabla{{\cal L}}_{t}$ is $L^{{\cal L}}_{t}$ -Lipschitz.
3.

$\hat{L}^{{\cal L}}_{t}\leq\sqrt{\beta}L^{{\cal L}}_{t}$ .

The first two statements are straightforward from the definition of $\hat{\cal L}_{t}$ , ${\cal L}_{t}$ and sublinearity of the norm. Note that $\nabla{{\cal L}}_{t}$ is $L^{L}_{t}$ -Lipschitz for the same reason. Finally, the third assumption of the corollary directly implies $\hat{L}^{{\cal L}}_{t}\leq\sqrt{\beta}L^{{\cal L}}_{t}$ .

Corollary 16 (Fixed constraint bounds).

If $g_{t}:=g$ is known for all $t$ , then by using $\nabla\hat{{g}}_{t}=\nabla g$ in Algorithm 3 we have

\begin{split}\text{Regret}_{t}(u)&\leq O\left(\sqrt{{\cal E}_{t}(f)}\right),\quad\forall t\in[T]\\ \text{CCV}_{T}&\leq O(\log T).\end{split}

(23)

Proof The proof is a direct consequence of Theorem 13 with ${\cal E}_{T}(g)=0$ .

Remark 17.

By applying the algorithm without predictions, i.e., using $\nabla\hat{{f}}_{t}=0$ , we obtain $\text{Regret}_{T}(u)\leq O(\sqrt{T})$ and $O(\log T)$ for constraint violations, improving on the $O(\sqrt{T\log T})$ result for constraint violation when applying Sinha and Vaze (2024)’s algorithm.

Corollary 18 (Application to the experts setting).

When using Algorithm 2 in the meta-algorithm, we have

\begin{split}\text{Regret}_{T}(u)&\leq O\left(\sqrt{\log(d^{2}Te){\cal E}_{t}(f)}\right),\\ \text{CCV}_{T}&\leq O\left(\left(\sqrt{{\cal E}_{T}(g)}\vee G\vee L^{g}\right)\sqrt{\log(d^{2}Te)}\log T\right).\end{split}

(24)

References

Anderson et al. (2022) Daron Anderson, George Iosifidis, and Douglas J Leith. Lazy Lagrangians with predictions for online learning. arXiv preprint arXiv:2201.02890, 2022.
Chiang et al. (2012) Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6–1. JMLR Workshop and Conference Proceedings, 2012.
D’Orazio and Huang (2021) Ryan D’Orazio and Ruitong Huang. Optimistic and adaptive Lagrangian hedging. arXiv preprint arXiv:2101.09603, 2021.
Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Guo et al. (2022) Hengquan Guo, Xin Liu, Honghao Wei, and Lei Ying. Online convex optimization with hard constraints: towards the best of two worlds and beyond. Advances in Neural Information Processing Systems, 35:36426–36439, 2022.
Hazan (2023) Elad Hazan. Introduction to online convex optimization, 2023. URL https://arxiv.org/abs/1909.05207.
Jenatton et al. (2016) Rodolphe Jenatton, Jim Huang, and Cedric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 402–411, New York, New York, USA, 20–22 Jun 2016. PMLR. URL https://proceedings.mlr.press/v48/jenatton16.html.
Liu et al. (2022) Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints. ACM SIGMETRICS Performance Evaluation Review, 49(3):4–5, 2022.
Mahdavi et al. (2012) Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1):2503–2528, 2012.
Mannor et al. (2009) Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(3), 2009.
Neely and Yu (2017) Michael J. Neely and Hao Yu. Online convex optimization with time-varying constraints, 2017. URL https://arxiv.org/abs/1702.04783.
Orabona (2019) Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019.
Qiu et al. (2023) Shuang Qiu, Xiaohan Wei, and Mladen Kolar. Gradient-variation bound for online convex optimization with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9534–9542, 2023.
Rakhlin and Sridharan (2013a) Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993–1019. PMLR, 2013a.
Rakhlin and Sridharan (2013b) Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences, 2013b. URL https://arxiv.org/abs/1311.1869.
Sinha and Vaze (2024) Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints, 2024. URL https://arxiv.org/abs/2310.18955.
Wei et al. (2020) Xiaohan Wei, Hao Yu, and Michael J Neely. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2):1–36, 2020.
Yi et al. (2023) Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou Chai, and Karl H Johansson. Distributed online convex optimization with adversarial constraints: reduced cumulative constraint violation bounds under Slater’s condition. arXiv preprint arXiv:2306.00149, 2023.
Yu and Neely (2020) Hao Yu and Michael J Neely. A low complexity algorithm with o ( $\sqrt{T}$ ) regret and o (1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1–24, 2020.
Zinkevich (2003) Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.

Appendix A Proof of Theorem 7

The theorem is a direct consequence of the following lemma.

Lemma 19.

One step of optimistic online mirror descent satisfies:

\eta_{t}\langle\ell_{t},\ x_{t}-u\rangle\leq B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})+\eta_{t}||\ell_{t}-\hat{\ell}_{t}||_{\star}\cdot||x_{t}-\tilde{x}_{t+1}||-(B^{R}(\tilde{x}_{t+1};x_{t})+B^{R}(x_{t};\tilde{x}_{t})).

(25)

Moreover, if $\nabla\hat{{f}}_{t}$ is $\hat{L}^{f}_{t}$ -smooth with $\hat{L}^{f}_{t}\leq\frac{\beta}{\eta_{t}}$ ,

\langle\ell_{t},\ x_{t}-u\rangle\leq\frac{B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})}{\eta_{t}}+B^{R}(x_{t};\tilde{x}_{t+1})(\eta_{t+1}^{-1}-\eta_{t}^{-1})+\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f).

(26)

We will need the following proposition to prove the lemma.

Proposition 20 (Chiang et al. (2012), proposition 18).

For any $x_{0}\in{\cal X},\ell\in\mathbb{R}^{d}$ , if $x^{\star}:=\arg\min_{x\in{\cal X}}\langle\ell,\ x\rangle+\frac{1}{\eta}B^{R}(x;x_{0})$ , then $\forall u\in{\cal X}$

\eta\langle\ell,\ x^{\star}-u\rangle=B^{R}(u;x_{0})-B^{R}(u;x^{\star})-B^{R}(x^{\star};x_{0}).

(27)

Proof [of Lemma 19] Let $u\in{\cal X}$

\displaystyle\eta_{t}\langle\ell_{t},\ x_{t}-u\rangle

\displaystyle=\langle\eta_{t}\ell_{t},\ \tilde{x}_{t+1}-u\rangle+\eta_{t}\langle\ell_{t}-\hat{\ell}_{t},\ x_{t}-\tilde{x}_{t+1}\rangle+\langle\eta_{t}\hat{\ell}_{t},\ x_{t}-\tilde{x}_{t+1}\rangle.

On one hand, using Proposition 20, the left and right terms can be upper bounded respectively :

	$\displaystyle\langle\eta_{t}\ell_{t},\ \tilde{x}_{t+1}-u\rangle$	$\displaystyle=B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})-B^{R}(\tilde{x}_{t+1};\tilde{x}_{t}),$
	$\displaystyle\langle\eta_{t}\hat{\ell}_{t},\ x_{t}-\tilde{x}_{t+1}\rangle$	$\displaystyle=B^{R}(\tilde{x}_{t+1};\tilde{x}_{t})-B^{R}(\tilde{x}_{t+1};x_{t})-B^{R}(x_{t};\tilde{x}_{t}).$

Therefore

\langle\eta_{t}\ell_{t},\ \tilde{x}_{t+1}-u\rangle+\langle\eta_{t}\hat{\ell}_{t},\ x_{t}-\tilde{x}_{t+1}\rangle=B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})-(B^{R}(\tilde{x}_{t+1};x_{t})+B^{R}(x_{t};\tilde{x}_{t})).

On the other hand,

\displaystyle\langle\ell_{t}-\hat{\ell}_{t},\ x_{t}-\tilde{x}_{t+1}\rangle

\displaystyle\leq||x_{t}-\tilde{x}_{t+1}||\cdot||\ell_{t}-\hat{\ell}_{t}||_{\star}.

By combining the last two inequalities, we obtain (25).
To prove (26), first note that by using the fact that $\forall a,b,\rho>0,ab\leq\frac{1}{2\rho}a^{2}+\frac{\rho}{2}b^{2}$ ,

||x_{t}-\tilde{x}_{t+1}||\cdot||\ell_{t}-\hat{\ell}_{t}||_{\star}\leq\frac{\eta_{t+1}}{2\beta}||\ell_{t}-\hat{\ell}_{t}||_{\star}^{2}+\frac{\beta}{2\eta_{t+1}}||x_{t}-\tilde{x}_{t+1}||^{2}\leq\frac{\eta_{t+1}}{2\beta}||\ell_{t}-\hat{\ell}_{t}||_{\star}^{2}+\frac{1}{\eta_{t+1}}B^{R}(x_{t};\tilde{x}_{t+1}).

For the second part of the statement, if $\nabla\hat{f}$ is $\hat{L}^{f}_{t}$ -smooth:

	$\displaystyle\|\|\ell_{t}-\hat{\ell}_{t}\|\|_{\star}^{2}$	$\displaystyle=\|\|\nabla{f}_{t}(x_{t})-\nabla\hat{{f}}_{t}(\tilde{x}_{t})\|\|_{\star}^{2}$
		$\displaystyle\leq 2\|\|\nabla{f}_{t}(x_{t})-\nabla\hat{{f}}_{t}(x_{t})\|\|_{\star}^{2}+2\|\|\nabla\hat{{f}}_{t}(x_{t})-\nabla\hat{{f}}_{t}(\tilde{x}_{t})\|\|_{\star}^{2}$
		$\displaystyle\leq 2\|\|\nabla{f}_{t}(x_{t})-\nabla\hat{{f}}_{t}(x_{t})\|\|_{\star}^{2}+2\left(\hat{L}^{f}_{t}\right)^{2}\|\|x_{t}-\tilde{x}_{t}\|\|^{2}$
		$\displaystyle\leq 2\varepsilon_{t}(f)+\frac{2\left(\hat{L}^{f}_{t}\right)^{2}}{\beta}B^{R}(x_{t};\tilde{x}_{t}).$

By inserting in (25) and dividing both sides by $\eta_{t}$ :

	$\displaystyle\langle\ell_{t},\ x_{t}-u\rangle$	$\displaystyle\leq\frac{B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})}{\eta_{t}}+\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f)+\frac{\left(\hat{L}^{f}_{t}\right)^{2}\eta_{t+1}}{\beta^{2}}B^{R}(x_{t};\tilde{x}_{t})$
		$\displaystyle\quad\quad-\frac{1}{\eta_{t}}(B^{R}(\tilde{x}_{t+1};x_{t})+B^{R}(x_{t};\tilde{x}_{t}))$
		$\displaystyle\leq\frac{B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})}{\eta_{t}}+\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f)+B^{R}(x_{t};\tilde{x}_{t})\left(\frac{\left(\hat{L}^{f}_{t}\right)^{2}\eta_{t+1}}{\beta^{2}}-\frac{1}{\eta_{t}}\right)$
		$\displaystyle\quad\quad+B^{R}(x_{t};\tilde{x}_{t+1})(\eta_{t+1}^{-1}-\eta_{t}^{-1}).$

If $\hat{L}^{f}_{t}\leq\beta/\eta_{t}$ , then $\left(\hat{L}^{f}_{t}\right)^{2}\leq\frac{\beta^{2}}{\eta_{t}\eta_{t+1}}$ since $\eta_{t}$ is non-increasing. We can upper bound the third term by zero.

Proof [of Theorem 7] From (26), we have for any $t\geq 1$

\langle\ell_{t},\ x_{t}-u\rangle\leq\frac{B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})}{\eta_{t}}+B^{R}(x_{t};\tilde{x}_{t+1})(\eta_{t+1}^{-1}-\eta_{t}^{-1})+\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f).

(28)

Note that by convexity of $f_{t}$ , $f_{t}(x_{t})-f_{t}(u)\leq\langle\ell_{t},\ x_{t}-u\rangle$ . Therefore, by taking the sum from 1 to T, we have

	$\displaystyle\text{Regret}_{T}(u)$	$\displaystyle\leq\sum_{t=1}^{T}\langle\ell_{t},\ x_{t}-u\rangle$
		$\displaystyle\leq\sum_{t=1}^{T}\frac{B^{R}(u;\tilde{x}_{t})-B^{R}(u;\tilde{x}_{t+1})}{\eta_{t}}+\sum_{t=1}^{T}B^{R}(x_{t};\tilde{x}_{t+1})(\eta_{t+1}^{-1}-\eta_{t}^{-1})+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f)$
		$\displaystyle\leq\frac{B^{R}(u;\tilde{x}_{1})}{\eta_{1}}+\sum_{t=1}^{T-1}\left(\frac{1}{\eta_{{t+1}}}-\frac{1}{\eta_{t}}\right)B^{R}(u;\tilde{x}_{t+1})+\sum_{t=1}^{T}\left(\frac{1}{\eta_{{t+1}}}-\frac{1}{\eta_{t}}\right)B^{R}(x_{t};\tilde{x}_{t+1})+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}{\cal E}_{T}(f)$
		$\displaystyle\leq\frac{B}{\eta_{T}}+\frac{B}{\eta_{T+1}}+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}{\cal E}_{T}(f)$
		$\displaystyle\leq\frac{2B}{\eta_{T+1}}+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}{\cal E}_{T}(f),$

where $B=\max_{t}B^{R}(u;x_{t})$

Appendix B Proof of Theorem 8

Proof Note that $\eta_{t}:=\sqrt{\beta B}\min\left\{\frac{1}{\sqrt{{\cal E}_{t-1}(f)}+\sqrt{{\cal E}_{t-2}(f)}},\frac{1}{L^{f}_{t}\sqrt{B}}\right\}$ is non-decreasing. Moreover, we have $\eta_{t}\leq\frac{\sqrt{\beta}}{L^{f}_{t}}$ . Therefore,

\hat{L}^{f}_{t}\leq\sqrt{\beta}L^{f}_{t}\Longrightarrow\hat{L}^{f}_{t}\leq\frac{\beta}{\eta_{t}}.

We can apply Theorem 7:

\text{Regret}_{T}(u)\leq\frac{2B}{\eta_{T+1}}+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f).

(29)

Note that we can rewrite:

\eta_{t}=\left(\sqrt{\beta B}\right)\min\left\{\frac{\sqrt{{\cal E}_{t-1}(f)}-\sqrt{{\cal E}_{t-2}(f)}}{\varepsilon_{t-1}(f)},L^{f}_{t}\sqrt{B}\right\}.

(30)

We can also show that

\eta_{t}^{-1}\leq(\sqrt{\beta B})^{-1}\max\left\{2\sqrt{{\cal E}_{t-1}(f)},L^{f}_{t}\sqrt{B}\right\}\leq 2(\sqrt{\beta B})^{-1}(\sqrt{{\cal E}_{t}(f)}+L^{f}_{t}\sqrt{B}).

(31)

Using (30) and (31) in the regret upper bound (29):

	$\displaystyle\text{Regret}_{T}(u)$	$\displaystyle\leq\frac{2B}{\eta_{T+1}}+\sum_{t=1}^{T}\frac{\eta_{t+1}}{\beta}\varepsilon_{t}(f)$
		$\displaystyle\leq 4\sqrt{\frac{B}{\beta}}\left(\sqrt{{\cal E}_{t}(f)}+L^{f}_{t}\sqrt{B}\right)+\sum_{t=1}^{T}\sqrt{{\cal E}_{t-1}(f)}-\sqrt{{\cal E}_{t-2}(f)}$
		$\displaystyle\leq 4\sqrt{\frac{B}{\beta}}\left(\sqrt{{\cal E}_{t}(f)}+L^{f}_{t}\sqrt{B}\right)+\sqrt{{\cal E}_{T-1}(f)}$
		$\displaystyle\leq 5\sqrt{\frac{B}{\beta}}\left(\sqrt{{\cal E}_{t}(f)}+L^{f}_{t}\sqrt{B}\right).$

Appendix C Proof of Theorem 10

The proof is similar to that of Theorem 7. We will need a lemma from Wei et al. (2020) that relates $D_{\text{KL}}(u;\tilde{x}_{t})$ and $D_{\text{KL}}(u;y_{t})$ .

Lemma 21 (Wei et al. (2020), Lemma 31).

Let $\tilde{x},u\in\Delta$ and $y=(1-\delta)\tilde{x}+\frac{\delta}{d}\bm{1}$ , then

	$\displaystyle D_{\text{KL}}(u;y)$	$\displaystyle\leq\delta\log d+D_{\text{KL}}(u;\tilde{x}),$
	$\displaystyle D_{\text{KL}}(u;y)$	$\displaystyle\leq\log(d/\delta).$

Then we must show a lemma very similar to Lemma 19.

Lemma 22.

One step of optimistic online mirror descent satisfies:

\langle\ell_{t},\ x_{t}-u\rangle\leq\frac{D_{\text{KL}}(u;y_{t})-D_{\text{KL}}(u;y_{t+1})}{\eta_{t}}+\frac{1}{2}||x_{t}-\tilde{x}_{t+1}||_{1}^{2}(\eta_{t+1}^{-1}-\eta_{t}^{-1})+\frac{\eta_{t+1}}{2}\varepsilon_{t}(f)+\frac{\delta\log d}{\eta_{t}}.

(32)

Proof The proof is exactly the same as Lemma 19. First, we can retrieve an equation similar to (25), where we replace $\tilde{x}_{t}$ with $y_{t}$ :

\eta_{t}\langle\ell_{t},\ x_{t}-u\rangle\leq D_{\text{KL}}(u;y_{t})-D_{\text{KL}}(u;\tilde{x}_{t+1})+\eta_{t}||\ell_{t}-\hat{\ell}_{t}||_{\infty}\cdot||x_{t}-\tilde{x}_{t+1}||_{1}-(D_{\text{KL}}(\tilde{x}_{t+1};x_{t})+D_{\text{KL}}(x_{t};y_{t})).

(33)

Then we can upper bound

||\ell_{t}-\hat{\ell}_{t}||_{\infty}\cdot||x_{t}-\tilde{x}_{t+1}||_{1}\leq\frac{\eta_{t+1}}{2}||\ell_{t}-\hat{\ell}_{t}||_{\infty}^{2}+\frac{1}{2\eta_{t+1}}||x_{t}-\tilde{x}_{t+1}||_{1}^{2}.

We can also use Lemma 21 below to upper bound the KL divergence:

-D_{\text{KL}}(u;\tilde{x}_{t+1})\leq\delta\log d-D_{\text{KL}}(u;y_{t+1}),

and from Pinsker’s inequality:

D_{\text{KL}}(\tilde{x}_{t+1};x_{t})\geq\frac{1}{2}||\tilde{x}_{t+1}-x_{t}||_{1}^{2}\Longrightarrow-D_{\text{KL}}(\tilde{x}_{t+1};x_{t})\leq-\frac{1}{2}||\tilde{x}_{t+1}-x_{t}||_{1}^{2}.

By combining these results in (33) and dividing both sides by $\eta_{t}$ we obtain

\langle\ell_{t},\ x_{t}-u\rangle\leq\frac{D_{\text{KL}}(u;y_{t})-D_{\text{KL}}(u;y_{t+1})+\delta\log d}{\eta_{t}}+\frac{\eta_{t+1}}{2}\varepsilon_{t}(f)+\left(\eta_{t+1}^{-1}-\eta_{t}^{-1}\right)\frac{||x_{t}-\tilde{x}_{t+1}||_{1}^{2}}{2}.

Proof [of Theorem 10] By first dividing both sides of (32) by $\eta_{t}$ and summing over $t$ :

\displaystyle\text{Regret}_{T}(u)

\displaystyle\leq\sum_{t=1}^{T}\frac{D_{\text{KL}}(u;y_{t})-D_{\text{KL}}(u;y_{t+1})}{\eta_{t}}+\delta\log(d)\sum_{t=1}^{T}\frac{1}{\eta_{t}}+\sum_{t=1}^{T}\frac{\eta_{t+1}}{2}\varepsilon_{t}^{f}+\left(\eta_{t+1}^{-1}-\eta_{t}^{-1}\right)\frac{||x_{t}-\tilde{x}_{t+1}||_{1}^{2}}{2}.

We can upper bound the first term of the sum by noticing that:

$\displaystyle\sum_{t=1}^{T}\frac{D_{\text{KL}}(u;y_{t})-D_{\text{KL}}(u;y_{t+1})}{\eta_{t}}$	$\displaystyle\leq\frac{D_{\text{KL}}(u;y_{1})}{\eta_{1}}+\sum_{t=2}^{T}D_{\text{KL}}(u;y_{t})(\eta_{t}^{-1}-\eta_{t-1}^{-1})$
	$\displaystyle\leq\log(d/\delta)\frac{1}{\eta_{1}}+\log(d/\delta)\sum_{t=2}^{T}(\eta_{t}^{-1}-\eta_{t-1}^{-1})$	using Lemma 21
	$\displaystyle\leq\frac{\log(d/\delta)}{\eta_{T}}$
	$\displaystyle\leq\frac{\log(d/\delta)}{\eta_{T+1}}.$

The second term can be upper bounded by:

\delta\log(d)\sum_{t=1}^{T}\frac{1}{\eta_{t}}\leq T\delta\frac{\log d}{\eta_{T+1}}.

The last term can be upper bounded by $||x_{t}-\tilde{x}_{t+1}||_{1}\leq 1$ . By combining all of these terms, and setting $\delta=\frac{1}{T}$ we obtain (9):

\text{Regret}_{T}(u)\leq\frac{\log(d^{2}T)}{\eta_{T+1}}+\sum_{t=1}^{T}\eta_{t+1}\varepsilon_{t}(f)+\frac{1}{2}\left(\eta_{T+1}^{-1}-\eta_{1}^{-1}\right).

To prove (11), we use the same reasoning as in Theorem 8 where we let

\eta_{t}=\sqrt{\log(d^{2}Te)}\min\left\{\frac{1}{\sqrt{{\cal E}_{t-1}(f)}+\sqrt{{\cal E}_{t-2}(f)}},1\right\}.

(34)

	$\displaystyle\|\|\nabla{f}_{t}(x)-\nabla{f}_{t}(y)\|\|_{\star}$	$\displaystyle\leq L^{f}_{t}\|\|x-y\|\|,$
	$\displaystyle\|\|\nabla{g}_{t}(x)-\nabla{g}_{t}(y)\|\|_{\star}$	$\displaystyle\leq L^{g}_{t}\|\|x-y\|\|.$

	$\displaystyle\|\|\nabla\hat{{f}}_{t}(x)-\nabla\hat{{f}}_{t}(y)\|\|_{\star}$	$\displaystyle\leq\hat{L}^{f}_{t}\|\|x-y\|\|,$
	$\displaystyle\|\|\nabla\hat{{g}}_{t}(x)-\nabla\hat{{g}}_{t}(y)\|\|_{\star}$	$\displaystyle\leq\hat{L}^{g}_{t}\|\|x-y\|\|.$

	$\displaystyle\|\|\ell_{t}-\hat{\ell}_{t}\|\|_{\star}^{2}$	$\displaystyle=\|\|\nabla{f}_{t}(x_{t})-\nabla\hat{{f}}_{t}(\tilde{x}_{t})\|\|_{\star}^{2}$
		$\displaystyle\leq 2\|\|\nabla{f}_{t}(x_{t})-\nabla\hat{{f}}_{t}(x_{t})\|\|_{\star}^{2}+2\|\|\nabla\hat{{f}}_{t}(x_{t})-\nabla\hat{{f}}_{t}(\tilde{x}_{t})\|\|_{\star}^{2}$
		$\displaystyle\leq 2\|\|\nabla{f}_{t}(x_{t})-\nabla\hat{{f}}_{t}(x_{t})\|\|_{\star}^{2}+2\left(\hat{L}^{f}_{t}\right)^{2}\|\|x_{t}-\tilde{x}_{t}\|\|^{2}$
		$\displaystyle\leq 2\varepsilon_{t}(f)+\frac{2\left(\hat{L}^{f}_{t}\right)^{2}}{\beta}B^{R}(x_{t};\tilde{x}_{t}).$