Constrained Online Convex Optimization
without Slater’s Condition
June 30, 2026
Abstract
We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater’s condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater’s condition. For stochastic constraints and convex losses, our algorithm achieves \(O(\sqrt{T})\) expected regret and \(O(\sqrt{T}\log T)\) expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to \(O(\log T)\) with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.
1 Introduction↩︎
Constrained Online Convex Optimization (COCO) is a sequential decision-making problem under uncertainty in which, at each round, a decision maker selects an action without prior knowledge of the convex loss function, while feasibility requirements restrict the decision-making process. The goal is to minimize the cumulative loss while satisfying these requirements over time. COCO arises naturally in a wide variety of real-world applications, including online advertising with budget constraints [1], portfolio optimization with risk constraints [2], [3], wireless network resource management under power constraints [4], and online recommendation systems with fairness constraints [5].
The COCO problem is typically formulated as follows (a detailed formulation is provided in 2). In each round \(t\), the decision maker selects an action \(\mathbf{x}_t\in\mathcal{X}\). Then, the loss function \(f_t\) and the constraint function \(g_t\) are revealed to the decision maker, where feasibility is characterized by the functional constraint \(g_t(\mathbf{x}) \leq 0\). Given a comparator \(\mathbf{x}^\star\in \mathcal{X}\), the performance of the decision maker is measured by the regret and cumulative constraint violation over \(T\) rounds, denoted by \(\mathrm{Regret}(T)\) and \(\mathrm{Violation}(T)\), respectively: \[\begin{align} &\mathrm{Regret}(T) = \sum_{t=1}^T (f_t(\mathbf{x}_t) - f_t(\mathbf{x}^\star)), \quad \mathrm{Violation}(T) = \sum_{t=1}^T g_t(\mathbf{x}_t). \end{align}\]
COCO has been studied under various settings. One line of work considers COCO with stochastic constraints [6], [7]. In this setting, the constraint functions are sampled i.i.d. from an underlying distribution, whereas the loss functions may vary arbitrarily over time. [6] proposed a drift-plus-penalty algorithm that achieves \({O}(\sqrt{T})\) bounds on regret and cumulative constraint violation. However, their analysis relies on Slater’s condition, which assumes the existence of a strictly feasible decision in expectation, i.e., there exist \(\hat{\mathbf{x}}\) and \(\varepsilon>0\) such that \(\mathbb{E}[g_1(\hat{\mathbf{x}})]=\cdots=\mathbb{E}[g_T(\hat{\mathbf{x}})]\leq -\varepsilon\), where the expectation is taken over the randomness of the constraint functions. More importantly, their bound on cumulative constraint violation is \(O(\varepsilon^{-1}\sqrt{T})\), which deteriorates as \(\varepsilon\) approaches zero. This motivates us to investigate whether this condition can be relaxed while maintaining regret and constraint violation guarantees.
[7] made some progress in this direction for the same setting by replacing Slater’s condition with what they call the sequential existence of Lagrange multipliers (SELM) condition, which assumes the existence of uniformly bounded Lagrange multipliers. Since Slater’s condition implies SELM, the latter is a weaker assumption. Nevertheless, their analysis still relies on the boundedness of the Lagrange multipliers, with the hidden constant in the constraint violation bound depending on the corresponding multiplier bound. Consequently, whether these guarantees can be achieved without such regularity assumptions has remained unresolved for COCO with stochastic constraints.
In contrast to the stochastic constraint setting, one can remove the necessity of a regularity assumption in another line of settings, called COCO with adversarial constraints against a restrictive comparator, where the constraint functions as well as the loss functions can vary arbitrarily over time [8], [9]. Here, the comparator is restrictive in that it is defined to be round-wise feasible: \(g_t(\mathbf{x}^\star) \leq 0, \; \forall t=1,\ldots,T\). For this setting, [8] proposed an algorithm without assuming Slater’s condition or bounded Lagrange multipliers, but its guarantees are suboptimal. Later, [9] proposed an algorithm that does not rely on these conditions but achieves nearly optimal regret and constraint violation bounds of \({O}(\sqrt{T})\) and \(\widetilde{{O}}(\sqrt{T})\)1, respectively. The bounds are independent of any Slater constant or Lagrange multiplier bound. Additionally, [10] developed an anytime extension that does not require prior knowledge of the horizon \(T\).
Given the success in the adversarial constraint setting, one may ask whether the same guarantees carry over to the stochastic constraint setting, since any realized stochastic constraint sequence can be viewed as a special case of adversarial constraint sequences. Unfortunately, the answer is no. The key distinction between the two settings lies in the definition of the comparator \(\mathbf{x}^\star\), which plays a central role in the performance metrics. As mentioned above, the previous work for the adversarial setting takes a round-wise feasible comparator, but in the stochastic constraint setting, the comparator is defined to be feasible in expectation: \(\mathbb{E}[g_1(\mathbf{x}^\star)]=\cdots= \mathbb{E}[g_T(\mathbf{x}^\star)]\leq 0\). This distinction implies that directly applying the algorithm of [9] to the stochastic constraint setting can provide guarantees only under the stronger assumption that \(\mathbf{x}^\star\) is feasible almost surely, i.e., \(g_t(\mathbf{x}^\star) \leq 0\) with probability \(1\). This yields a weaker notion of regret, which is not satisfactory for the stochastic constraint setting.
1.1 Our Contributions↩︎
Prior guarantees for COCO with stochastic constraints can be achieved only under additional assumptions or with respect to a weaker notion of regret. Motivated by this gap, this paper develops an algorithm for this setting that achieves nearly optimal guarantees2 without these limitations. We summarize the main contributions below and provide a comparison with recent works in ¿tbl:tab:comparison?.
We propose a novel algorithm (1) for COCO with stochastic constraints that does not rely on additional assumptions, including Slater’s condition and bounded Lagrange multipliers. For the stochastic constraint setting, we show that our algorithm achieves expected regret and constraint violation bounds of \({O}(\sqrt{T})\) and \(\widetilde{{O}}(\sqrt{T})\), respectively (1). The novelty of our algorithm stems from incorporating an adaptive regularizer into the dual update. In principle, this step stabilizes the dual process without relying on the negative drift induced by Slater’s condition. More technically, our regularizer is carefully designed to offset an accumulated term involving the derivative of a Lyapunov function that arises in the regret analysis.
Beyond expected guarantees, we also provide high-probability guarantees. In particular, given a confidence parameter \(\delta\), with probability at least \(1-\delta\), our algorithm achieves regret and violation bounds of order \({O}(\sqrt{T})\) and \(\widetilde{{O}}(\sqrt{T})\), respectively (2). The key step is to obtain an upper bound on the Lyapunov-weighted sum of comparator constraints by applying a concentration inequality for supermartingales. We then modify the regularizer appropriately so that it can offset this bound as well.
We further extend the guarantees to strongly convex losses and adversarial constraints. Under stochastic constraints, when losses are strongly convex, our algorithm improves the expected and high-probability regret bounds to \({O}(\log T)\) and \({O}(\log T + \sqrt{\log(1/\delta)})\), respectively, while the constraint violation bounds remain the same as in the convex loss case (Theorems 3 and 4).
Moreover, under adversarial constraints, a slightly modified version of our algorithm achieves regret and hard constraint violation bounds of \({O}(\sqrt{T})\) and \(\widetilde{{O}}(\sqrt{T})\), respectively, for convex losses (5), and improves the regret bound to \({O}(\log T)\) for strongly convex losses (6). Here, hard constraint violation is a stronger notion of constraint violation that does not allow cancellation across rounds.
Our algorithm is unified and anytime. The same algorithmic framework, based on the dual update with a regularizer, applies to both stochastic and adversarial constraint settings, as well as to both convex and strongly convex losses. Moreover, the parameter choices of our algorithm do not require prior knowledge of the horizon \(T\), and hence the algorithm runs in an anytime manner without using the doubling trick.
The rest of the paper is organized as follows. 1.2 reviews additional related work. 2 presents the problem formulations and assumptions. 3 introduces our anytime primal-dual algorithm, and 4 explains the intuition for how the regularizer stabilizes the dual process. 5 presents the main theoretical results for stochastic and adversarial constraints under convex and strongly convex losses, together with an overview of the proofs. Sections 6 and 7 provide the analyses for expected and high-probability guarantees under stochastic constraints, respectively, and 8 extends the analysis to strongly convex losses. 9 concludes the paper, and the appendix contains the deferred proofs, the analysis for adversarial constraints, and auxiliary lemmas.
| Algorithm | Stochastic | Adversarial | w/o Slater | S.C. | Anytime | ||
|---|---|---|---|---|---|---|---|
| 2-3 | Exp. | H.P. | |||||
| [6] | \(^\dagger\) | ||||||
| [7] | \(\triangle\) | ||||||
| [9] | |||||||
| [10] | |||||||
| Ours | |||||||
1.2 Related Work↩︎
Online Convex Optimization (OCO) provides a general framework for sequential decision-making with convex losses over a fixed feasible set. In the classical OCO setting, a decision maker selects an action in each round and then observes a convex loss function, with the goal of minimizing regret against a fixed comparator in hindsight. Since the foundational work of [12], OCO has been extensively studied in the online learning literature [13]–[17].
In contrast to the classical OCO setting, COCO captures more complex feasible regions characterized by functional constraints and additionally requires the decision maker to control constraint violations over time. A line of work studies COCO with fixed or known constraint functions. A common formulation in this line is OCO with long-term constraints, where the constraints may be violated at individual rounds but their cumulative violation should be controlled over the entire horizon. This formulation was initiated by [18]. Subsequent works developed adaptive algorithms [19], established guarantees for cumulative squared constraint violations [20], and improved guarantees [21], [22]. Another line of work studies COCO with stochastic constraints, where the constraint functions are sampled i.i.d. from an underlying distribution while the loss functions may vary adversarially. In this literature, [6] established expected and high-probability regret and constraint violation bounds, but their analysis relies on Slater’s condition. Later, [7] relaxed this requirement by assuming the existence of bounded Lagrange multipliers. In contrast, our work requires none of these assumptions but still achieves nearly optimal guarantees for stochastic constraints. Recently, COCO has also been extensively studied under adversarial constraints, where the loss and constraint functions may vary adversarially over time. The early work of [23] considered online learning with a comparator that satisfies a sample path constraint \(\sum_{t=1}^T g_t(x)\leq 0\). They proved that for their setting, no online algorithm can achieve sublinear bounds on both regret and constraint violation at the same time. Subsequent works then studied adversarial constraints under restrictive comparators with round-wise feasibility requirements [9], [11], [24], [25]. This line of research has since been extended to broader settings [26]–[29]. In particular, [30]–[32] proposed projection-free algorithms, [8], [33], [34] studied distributed settings, [35] proposed instance-dependent guarantees, [36] improved guarantees, and [10] proposed anytime algorithms. Although these results provide strong guarantees in the adversarial constraint setting, they do not directly apply to the stochastic constraint setting, where the comparator is required to be feasible only in expectation.
2 Preliminaries↩︎
This section presents the formulations of COCO studied in this paper and the required assumptions. Before introducing them, we first establish some basic notation used throughout the paper. Let \(\mathbb{E}\) denote the expectation taken over randomness of the constraint functions, let \(\mathbb{R}_+\) denote the set of nonnegative real numbers, let \(\|\cdot\|\) denote the Euclidean norm, and let \([\cdot]_+ = \max\{0,\cdot\}\). Moreover, for a subdifferentiable function \(f:\mathbb{R}^d \to \mathbb{R}\), let \(\nabla f(\mathbf{x})\) denote a subgradient of \(f\) at \(\mathbf{x}\). For a positive integer \(T\), let \([T] = \{1,2,\ldots, T\}\).
Let \({\mathcal{X}}\subseteq \mathbb{R}^d\) be a compact convex set for some positive integer \(d\). Let \(\{f_t\}_{t\geq 1}\) and \(\{g_t\}_{t\geq 1}\) denote sequences of convex loss and constraint functions, respectively, that are subdifferentiable on \({\mathcal{X}}\). Additionally, we impose the following assumptions throughout the paper.
Assumption 1. There exists a constant \(D > 0\) such that \(\|\mathbf{x}- \mathbf{y}\|\leq D\) for all \(\mathbf{x},\mathbf{y}\in {\mathcal{X}}\).
Assumption 2. There exist constants \(L,G > 0\) such that \(\|\nabla f_t(\mathbf{x})\| \leq L\), \(\|\nabla g_t(\mathbf{x})\|\leq L\), and \(|g_t(\mathbf{x})|\leq G\) for all \(\mathbf{x}\in{\mathcal{X}}\) and \(t\geq 1\).
The first assumption ensures that \({\mathcal{X}}\) is bounded, while the second assumes that the subgradients and constraint functions are bounded. Both assumptions are common in the COCO literature [6].
We now formulate an online learning problem for COCO. In each round \(t\), the decision maker selects an action \(\mathbf{x}_t \in {\mathcal{X}}\), after which the loss function \(f_t\) and the constraint function \(g_t\) are revealed. We consider two settings that differ in how the constraint functions are given: the stochastic constraint setting [6] and the adversarial constraint setting [9].
Stochastic Constraint Setting: In each round \(t\), \(g_t\) is sampled i.i.d. from an unknown distribution \({\mathcal{D}}\), while \(f_t\) is chosen arbitrarily and independently of the samples of the constraint functions. In this case, we consider the following performance metrics, which are regret and constraint violation over \(T\) rounds: \[\begin{align} \label{def:reg32viol} &\mathrm{Regret}(T) = \sum_{t=1}^T (f_t(\mathbf{x}_t) - f_t(\mathbf{x}^\star)), \quad \mathrm{Violation}(T) = \sum_{t=1}^T g_t(\mathbf{x}_t), \end{align}\tag{1}\] where the comparator \(\mathbf{x}^\star \in {\mathcal{X}}\) is independent of \(\{g_t\}_{t=1}^T\) and is defined to be feasible in expectation, i.e., \[\begin{align} \label{def:xstar32stoc} \mathbf{x}^\star \in \mathop{\mathrm{arg\,min}}_{\mathbf{x}\in{\mathcal{X}}}\; \sum_{t=1}^T f_t(\mathbf{x}) \quad\mathrm{s.t.}\quad\mathbb{E}[g_1(\mathbf{x})]=\cdots= \mathbb{E}[g_T(\mathbf{x})] \leq 0. \end{align}\tag{2}\]
Adversarial Constraint Setting: In each round \(t\), \(g_t\) is chosen adversarially, just as \(f_t\) is. In this case, we consider the regret measure defined in the same way as in 1 , while the notion of hard constraint violation is considered, which is defined as \[\begin{align} \mathrm{Violation}_+(T) = \sum_{t=1}^T [g_t(\mathbf{x}_t)]_+. \end{align}\] Here, under the assumption that \(\{\mathbf{x}\in{\mathcal{X}}: g_t(\mathbf{x})\leq 0,\;\forall t\in [T]\}\) is nonempty [9], \(\mathbf{x}^\star\) is defined as round-wise feasible, i.e., \[\label{def:xstar32adv} \mathbf{x}^\star \in \mathop{\mathrm{arg\,min}}_{\mathbf{x}\in{\mathcal{X}}} \sum_{t=1}^T f_t(\mathbf{x}) \quad\mathrm{s.t.}\quad g_t(\mathbf{x}) \leq 0, \; \forall t\in [T].\tag{3}\]
Again, it is worth comparing the definitions of \(\mathbf{x}^\star\) in the two settings: feasible in expectation 2 versus round-wise feasible 3 . In particular, for the adversarial constraint setting, \(\mathbf{x}^\star\) is defined to be round-wise feasible, since no online algorithm can achieve sublinear bounds on both regret and constraint violation at the same time if \(\mathbf{x}^\star\) is instead defined as \(\mathop{\mathrm{arg\,min}}_{\mathbf{x}\in {\mathcal{X}}} \sum_{t=1}^T f_t(\mathbf{x}) \;\mathrm{s.t.}\;\sum_{t=1}^T g_t(\mathbf{x}) \leq 0\) [23]. Moreover, under the restrictive definition of \(\mathbf{x}^\star\) given in 3 , we may obtain guarantees for the hard constraint violation. On the other hand, under the stochastic constraint setting, \(\mathbf{x}^\star\) is only needed to satisfy the constraint in expectation rather than for all rounds. Therefore, the difference between two choices of \(\mathbf{x}^\star\) suggests that algorithms for the adversarial constraint setting do not directly translate to the stochastic constraint setting, requiring additional techniques.
3 Unified Algorithm for COCO↩︎
In this section, we present 1, an anytime algorithm for solving COCO. We emphasize that it is a unified algorithm that does not rely on Slater’s condition and achieves nearly optimal guarantees in both stochastic and adversarial constraint settings under both convex and strongly convex losses. The key principle is to incorporate an adaptive regularizer into the dual update that stabilizes the dual process without relying on the negative drift induced by Slater’s condition. A more detailed discussion of the regularizer is provided in 4.
Our algorithm proceeds as follows; the choices of \(\Psi, \gamma_t\), and \(\eta_t\) will be given in the subsequent paragraph. Initially, the decision maker selects an arbitrary point \(\mathbf{x}_1\in{\mathcal{X}}\) and sets the initial dual variable \(Q_1=0\). In each round \(t\geq 1\), the decision maker first plays \(\mathbf{x}_t\) and then observes the loss function \(f_t\) and the constraint function \(g_t\). Using the current dual variable \(Q_t\), inspired by the works of [9], [10], the algorithm constructs an exponential Lyapunov function given by \(\Phi_t(x)=e^{\gamma_t x}-1\) and performs a primal update based on the surrogate subgradient \(\nabla f_t(\mathbf{x}_t)+\Phi_t'(Q_t)\nabla g_t(\mathbf{x}_t)\). The exponential Lyapunov function is particularly useful compared to quadratic Lyapunov functions because its derivative is strictly positive for all \(Q_t\) when \(\gamma_t>0\), implying that the surrogate function \(f_t+\Phi_t'(Q_t)g_t\) always remains convex. The dual variable is then updated according to the observed constraint violation together with the regularizer term \(R_t\), which adaptively controls its growth.
The key parameters of 1 are \(\Psi, \gamma_t,\) and \(\eta_t\). Indeed, these parameters do not require knowledge of \(T\), hence our algorithm is anytime. The choices of \(\Psi, \gamma_t,\) and \(\eta_t\) are given as follows, depending on the setting under consideration.
The parameter \(\gamma_t\) defines the exponential Lyapunov function \(\Phi_t\), while \(\Psi\) is an auxiliary function used to define \(R_t\). Under the stochastic constraint setting, both \(\Psi\) and \(\gamma_t\) are chosen according to the type of guarantee desired, namely, expected or high-probability guarantees. The precise choices of \(\Psi\) and \(\gamma_t\) are given as follows: if the expected guarantees are desired, then we take \[\label{eq:psi324332gamma32exp} \Psi(x)=4DL\sqrt{x}, \qquad \gamma_t = \min\left\{\frac{1}{12G\sqrt{t}},\frac{1}{24DL},1\right\}.\tag{4}\] To obtain high-probability guarantees with confidence \(\delta\in (0,1)\), we instead take \[\begin{align} \label{eq:psi324332gamma32hp} \begin{aligned} &\Psi(x)=4DL\sqrt{x}+4G\sqrt{(1+x)\log\frac{(\pi^2/6)(1+\log_2(1+x))^2}{\delta}},\\ &\gamma_t =\min\left\{\frac{1}{12G\sqrt{t}},\frac{1}{24\!\left(DL+8G\sqrt{\log(12t^2/\delta)}\right)},1\right\}. \end{aligned} \end{align}\tag{5}\] For the adversarial constraint setting, we use the same choices of \(\Psi\) and \(\gamma_t\) as in the expected bound setting with stochastic constraints. Moreover, with a minor modification, the algorithm can also provide guarantees for hard constraint violation. The modified algorithm is given in 2, and the corresponding results are presented in 5.3.
The primal step size \(\eta_t\) is used in the projected subgradient descent update and is chosen according to the properties of the loss functions. Specifically, when the loss functions are convex, we employ an AdaGrad-type step size for \(\eta_t\) [37]. In contrast, to deduce improved performance when the loss functions are strongly convex, we use a step size based on that of [38], with appropriate modifications to accommodate our setting. The precise choice of \(\eta_t\) is summarized as follows: if losses are convex, then we take \[\begin{align} \label{eq:eta32cvx} \eta_t =\frac{\sqrt{2}D}{2\sqrt{1+\sum_{\tau=1}^t\|\nabla f_\tau(\mathbf{x}_\tau)+\Phi_\tau'(Q_\tau)\nabla g_\tau(\mathbf{x}_\tau)\|^2}}. \end{align}\tag{6}\] If losses are \(\mu\)-strongly convex, then we take \[\begin{align} \label{eq:eta32strcvx} \eta_t =\frac{1}{\mu t + (2L/D)\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}}. \end{align}\tag{7}\]
4 The Role of the Regularizer↩︎
This section explains the role of the regularizer \(R_t\). In the stochastic constraint setting, the main challenge arises from the less restrictive definition of comparator \(\mathbf{x}^\star\), that is, a solution satisfying the expected constraint \(\mathbb{E}[g_t(\mathbf{x}^\star)] \leq 0\). Specifically, although the algorithm proposed by [9] attained nearly optimal guarantees in the adversarial constraint setting, its analysis heavily relies on the fact that \(g_t(\mathbf{x}^\star) \leq 0\) for all \(t\geq 1\), which no longer holds in our setting. To address this issue, our technique is to incorporate an adaptive regularizer into the dual update.
4.1 Key Mechanism↩︎
Before explaining how the regularizer works, we first introduce the main direction of the analysis. Inspired by [9], we aim to show the following key relation, which simultaneously guarantees small regret and stability of the dual process. Letting \(\lesssim\) denote an informal notation used only to convey intuition, \[\label{eq:Role32of32Reg:goal} \mathrm{Regret}(T) + \Phi_{T+1}(Q_{T+1}) \lesssim {O}(\sqrt{T}).\tag{8}\]
To derive this relation in the stochastic constraint setting, we then explain why the regularizer is essential. For this purpose, we first observe that the regularizer enables us to control the Lyapunov drift more carefully, which is defined as \(\Phi_{t+1}(Q_{t+1})-\Phi_{t}(Q_{t})\). Intuitively, since this quantity represents the change in the dual variable, it is desirable for it to remain small in order to stabilize the dual process. Roughly, the Lyapunov drift satisfies the following relation, suggesting that \(R_t\) helps control the Lyapunov drift and thereby stabilizes the dual process. \[\label{eq:Role32of32Reg:drift} \Phi_{t+1}(Q_{t+1})-\Phi_{t}(Q_{t}) \lesssim \Phi_t'(Q_t)\bigl(g_t(\mathbf{x}_t)-R_t\bigr).\tag{9}\]
Combining this drift analysis with the regret analysis for the surrogate loss \(f_t + \Phi_t'(Q_t) g_t\) gives us \[\begin{align} \label{eq:Role32of32Reg:I32II32III} \begin{aligned} &\mathrm{Regret}(T) + \Phi_{T+1}(Q_{T+1}) \\ &\lesssim {O}\left(\sqrt{T}\right) + \underbrace{\sqrt{\sum_{t=1}^T\Phi_t'(Q_t)^2}}_{\textrm{(I)}} - \underbrace{\sum_{t=1}^T \Phi_t'(Q_t)R_t}_{\textrm{(II)}} + \underbrace{\sum_{t=1}^T \Phi_t'(Q_t) g_t(\mathbf{x}^\star)}_{\textrm{(III)}}. \end{aligned} \end{align}\tag{10}\]
This relation clarifies how \(R_t\) works. In particular, to deduce 8 from the above relation, the most problematic term is (I), whereas (III)—Lyapunov-weighted sum of comparator constraints—is nonpositive in expectation from the feasibility of \(\mathbf{x}^\star\). We emphasize that, by adopting a carefully designed regularizer, (II) can offset this problematic term (I), resulting in 8 . This observation motivates us to choose \(R_t\) as \[R_t \approx \frac{\sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} - \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}}{\Phi_t'(Q_t)},\] which justifies the choice of \(R_t\). Without the regularizer, it is nontrivial to bound (I), which highlights that our regularizer is essential for deriving small regret and stability of the dual process.
So far, we have demonstrated the mechanism of \(R_t\) in the dual update. Although adopting \(R_t\) is useful for achieving small regret and stability of the dual process, there is another caveat in the choice of \(R_t\). That is, when \(R_t\) is too large, the constraint violation cannot be bounded, based on the observation that \(\mathrm{Violation}(T) = Q_{T+1} + \sum_{t=1}^T R_t\). Hence, there is a trade-off in the choice of \(R_t\) in the sense that it is helpful to stabilize the dual process but, at the same time, it could harm the violation of the constraint. Nevertheless, under our choice of \(R_t\), we prove that its cumulative sums are sublinear, e.g., [lem:R32sum:stoc324332exp324332cvx]. Consequently, our choice of \(R_t\) yields the desired nearly optimal guarantees without Slater’s condition.
4.2 Comparison with the Existing Dual Updates↩︎
In this subsection, we compare our algorithm with the algorithms of [9] and [6]. We first discuss the relation to [9], which studied the adversarial constraint setting without Slater’s condition. In particular, we focus on addressing the following question: why is \(R_t\) unnecessary in the adversarial setting, whose dual update is \(Q_t = Q_{t-1} + [g_t(\mathbf{x}_t)]_+\)? To see this, we provide the analogue of 10 , which can be written as \[\begin{align} \label{eq:Role32of32Reg:I32II32III:analouge} \begin{aligned} &\mathrm{Regret}(T) + \Phi(Q_{T}) \lesssim {O}\left(\sqrt{T}\right) + \underbrace{\sqrt{\sum_{t=1}^T\Phi'(Q_t)^2}}_{\mathrm{(I')}} + \underbrace{\sum_{t=1}^T \Phi'(Q_t) [g_t(\mathbf{x}^\star)]_+}_{\mathrm{(III')}}. \end{aligned} \end{align}\tag{11}\]
Since their dual update ensures that \(\{Q_t\}_{t\geq 1}\) is an increasing sequence, choosing \(\Phi(x) = e^{\gamma x}-1\) with \(\gamma = 1/(2\sqrt{T})\) yields \(\mathrm{(I')} \leq \Phi(Q_T)/2\). Hence, \(\mathrm{(I')}\) can be absorbed into \(\Phi(Q_{T})\) on the left-hand side, without relying on a regularizer. Moreover, \(\mathrm{(III')}\) is \(0\) under their choice of \(\mathbf{x}^\star\), since \(g_t(\mathbf{x}^\star) \leq 0\) for all \(t\). These observations explain why the algorithm of [9] works without a regularizer. However, this approach no longer holds in our setting. The main reason is that since we only have \(\mathbb{E}[g_t(\mathbf{x}^\star)] \leq 0\) in the stochastic constraint setting, \(\mathrm{(III')}\) does not coincide with \(0\), even after taking expectations. In summary, in the adversarial constraint setting, 8 is attained without a regularizer, and this is possible due to the restrictive definition of \(\mathbf{x}^\star\). This highlights both the challenge in the stochastic constraint setting and the importance of adopting \(R_t\).
We conclude the section by comparing our approach with [6], which studies the same setting as ours but requires Slater’s condition. This comparison explains why our approach does not require Slater’s condition. To see this, under the quadratic Lyapunov function \(\Phi(x) = x^2/2\) and the dual update \(Q_{t+1} = [Q_t + g_t(\mathbf{x}_t) + \nabla g_t(\mathbf{x}_t)^\top(\mathbf{x}_{t+1} -\mathbf{x}_t)]_+\), their analysis shows that the conditional expected Lyapunov drift can be bounded as follows (see the proof of Lemma 7 in [6]): \[\mathbb{E}[\Phi(Q_{t+t_0}) - \Phi(Q_{t})|{\mathcal{F}}_{t-1}] \lesssim -\varepsilon t_0 \Phi'(Q_t) + C\] where \(\varepsilon\) is a Slater constant, \(t_0\) is a window parameter, \({\mathcal{F}}_{t-1}\) is the \(\sigma\)-algebra generated by the history up to round \(t-1\), and \(C\) collects the remaining positive terms. This shows that the stability of their dual process stems from \(-\varepsilon t_0 \Phi'(Q_t)\), as it is the only negative term on the right-hand side. Therefore, their analysis necessitates Slater’s condition. In contrast, our analysis relies on the regularizer as in 9 . This is the key reason why our algorithm is free from Slater’s condition.
5 Main Results↩︎
In this section, we present the theoretical guarantees of our algorithm. In particular, we establish guarantees for both convex and strongly convex loss functions under stochastic and adversarial constraints. For the stochastic constraint setting, we further provide both expected and high-probability guarantees. An overview of the analysis is presented in 5.4.
5.1 Stochastic Constraints↩︎
We first consider the stochastic constraint setting, where the loss functions may vary adversarially over time while the constraint functions are stochastic. Throughout this subsection, both the loss and constraint functions are assumed to be convex. To attain expected guarantees in this setting, recall that we choose the auxiliary function \(\Psi\), the Lyapunov parameter \(\gamma_t\) as in 4 , and the primal step size \(\eta_t\) as in 6 . We are now ready to present our first theoretical guarantee, where the corresponding analysis is provided in 6.
Theorem 1. Consider convex losses and stochastic constraints. For any \(T\geq 1\), suppose that we run 1 for \(T\) rounds with \(\Psi, \gamma_t\) given by 4 and \(\eta_t\) given by 6 . Then, we have \[\begin{align} \mathbb{E}[\mathrm{Regret}(T)] = {O}\left(\sqrt{T}\right), \quad \mathbb{E}[\mathrm{Violation}(T)] = {O}\left(\sqrt{T}\log T\right), \end{align}\] where the expectation is taken with respect to the randomness of \(\{g_t\}_{t\geq 1}\).
We note that this theorem demonstrates that our algorithm achieves nearly optimal expected guarantees in \(T\), without relying on Slater’s condition.
While 1 attains guarantees in expectation, it is often desirable to obtain realized guarantees that hold with high confidence. Thus, given a confidence parameter \(\delta \in (0,1)\), we establish high-probability guarantees under the same setting as in 1. To this end, we modify \(\Psi\), \(\gamma_t\) as in 5 , while retaining the same primal step size \(\eta_t\) as in 6 . Under these modified algorithmic parameters, the algorithm enjoys the following high-probability guarantees. The analysis of the following theorem is presented in 7.
Theorem 2. Consider convex losses and stochastic constraints. For any \(T\geq 1\) and \(\delta \in (0,1)\), suppose that we run 1 for \(T\) rounds with \(\Psi, \gamma_t\) given by 5 and \(\eta_t\) given by 6 . Then, with probability at least \(1-\delta\), we have \[\begin{align} \mathrm{Regret}(T) = {O}\left(\sqrt{T} + \sqrt{\log(1/\delta)}\right), \quad \mathrm{Violation}(T) = {O}\left(\sqrt{T}\log(T/\delta) + \log^{3/2}(T/\delta)\right). \end{align}\]
5.2 Extension to Strongly Convex Losses↩︎
We next extend the preceding results to the setting with \(\mu\)-strongly convex losses, while the remaining assumptions are identical to those in 5.1. To obtain improved guarantees, it is sufficient to modify the primal step size \(\eta_t\) as in 7 , which more properly exploits strong convexity ([lem:strcvx32regret]). We then obtain the following expected and high-probability guarantees.
Theorem 3. Consider \(\mu\)-strongly convex losses for \(\mu > 0\) and stochastic constraints. For any \(T\geq 1\), suppose that we run 1 for \(T\) rounds with \(\Psi, \gamma_t\) given by 4 and \(\eta_t\) given by 7 . Then, we have \[\begin{align} \mathbb{E}[\mathrm{Regret}(T)] = {O}\left(\log T\right), \quad \mathbb{E}[\mathrm{Violation}(T)] = {O}\left(\sqrt{T}\log T\right), \end{align}\] where the expectation is taken with respect to the randomness of \(\{g_t\}_{t\geq 1}\).
Theorem 4. Consider \(\mu\)-strongly convex losses for \(\mu >0\) and stochastic constraints. For all \(T\geq 1\) and \(\delta \in (0,1)\), suppose that we run 1 for \(T\) rounds with \(\Psi, \gamma_t\) given by 5 and \(\eta_t\) given by 7 . Then, with probability at least \(1-\delta\), we have \[\begin{align} \mathrm{Regret}(T) = {O}\left(\log T + \sqrt{\log(1/\delta)}\right), \quad \mathrm{Violation}(T) = {O}\left(\sqrt{T}\log(T/\delta) + \log^{3/2}(T/\delta)\right). \end{align}\]
Both theorems demonstrate that our algorithm can achieve improved expected and high-probability regret bounds that scale as \(\log T\) when the losses are strongly convex. The analyses of Theorems 3 and 4 are presented in 8.
5.3 Adversarial Constraints↩︎
Finally, we consider the adversarial constraint setting. Although [9] already established nearly optimal guarantees in this setting, the following results demonstrate that our framework is unified in the sense that it achieves nearly optimal guarantees under both stochastic and adversarial constraints.3
Although we may directly apply Algorithm 1 to the adversarial constraint setting, the resulting guarantees are on cumulative constraint violation, given by \(\mathrm{Violation}(T)=\sum_{t=1}^T g_t(\mathbf{x}_t)\). Since this quantity allows cancellation between positive and negative violations across time, it is weaker than the notion of hard constraint violation, given by \(\mathrm{Violation}_+(T)=\sum_{t=1}^T [g_t(\mathbf{x}_t)]_+\), which is often the performance metric adopted by adversarial-constraint algorithms. To obtain guarantees with respect to \(\mathrm{Violation}_+(T)\), we introduce several modifications to Algorithm 1.
The only difference is that 2 uses \(\tilde{g}_t\) in place of \(g_t\), where \(\tilde{g}_t:\mathbf{x}\mapsto [g_t(\mathbf{x})]_+\), and \(\nabla \tilde{g}_t(\mathbf{x}_t)\) denotes a subgradient of \(\tilde{g}_t\). Note that this modification yields hard constraint violation guarantees, since \(\tilde{g}_t(\mathbf{x}_t)\) is accumulated in the dual variable update and \(\sum_{t=1}^T \tilde{g}_t(\mathbf{x}_t)\) coincides with \(\mathrm{Violation}_+(T)\). Hence, with 2, we can obtain guarantees for \(\mathrm{Violation}_+(T)\) by applying the same analysis strategy used for the stochastic constraint setting. This is possible because the comparator \(\mathbf{x}^\star\) in the adversarial constraint setting is feasible in every round, i.e., \(g_t(\mathbf{x}^\star)\leq 0\) for all \(t\geq 1\), which is stronger than feasibility in expectation used in the stochastic constraint setting. Finally, we obtain the following results, whose analyses are deferred to Appendix 11, as they follow from straightforward modifications of the previous analysis.
Theorem 5. Consider convex losses and adversarial constraints. For all \(T\geq 1\), suppose that we run 2 for \(T\) rounds with \(\Psi, \gamma_t\) given by 4 and \(\eta_t\) given by 6 . Then, we have \[\begin{align} \mathrm{Regret}(T) = {O}\left(\sqrt{T}\right), \quad \mathrm{Violation}_+(T) = {O}\left(\sqrt{T}\log T\right). \end{align}\]
Theorem 6. Consider \(\mu\)-strongly convex losses for \(\mu > 0\) and adversarial constraints. For all \(T\geq 1\), suppose that we run 2 for \(T\) rounds with \(\Psi, \gamma_t\) given by 4 and \(\eta_t\) given by 7 . Then, we have \[\begin{align} \mathrm{Regret}(T) = {O}\left(\log T\right), \quad \mathrm{Violation}_+(T) = {O}\left(\sqrt{T}\log T\right). \end{align}\]
5.4 Overview of Proofs↩︎
The analyses of all theorems follow the same template, while additional techniques are required for handling high-probability guarantees and strongly convex losses. First, we establish a drift bound for the time-varying exponential Lyapunov function. Second, we combine this drift bound with a surrogate regret guarantee with respect to \(f_t + \Phi_t'(Q_t)g_t\). Third, the regularizer cancels the accumulated term involving \(\sum_{t=1}^T \Phi_t'(Q_t)^2\). The remaining work is to control the Lyapunov-weighted comparator constraint term, which is nonpositive in expectation and controlled by a supermartingale concentration inequality with high probability, and then to bound the cumulative sum of regularizers \(\sum_{t=1}^T R_t\).
6 Analysis under Stochastic Constraints: Expected Bounds↩︎
In this section, we present the analysis of 1, which establishes expected guarantees under convex losses and stochastic constraints. Throughout, \(\mathbb{E}\) denotes the expectation taken with respect to the randomness of \(\{g_t\}_{t\geq 1}\), and \({\mathcal{F}}_{t}\) denotes the \(\sigma\)-algebra generated by \(\{f_\tau\}_{\tau\geq 1}\) and \(\{g_\tau\}_{\tau=1}^t\).
Suppose that we run 1 with \(\gamma_t,\Psi\) as given by 4 . Then, for all \(t\geq 1\), we have \[\Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_{t}) \leq \Phi_t'(Q_{t})\left(g_t(\mathbf{x}_t) - \frac{R_t}{2}\right) + \frac{\gamma_t - \gamma_{t+1}}{e\gamma_{t+1}}.\]
Proof. Note that the Lyapunov drift can be decomposed as \[\begin{align} \label{eq:lem1:40I414340II41:stoc} \Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_t) = \underbrace{\Phi_t(Q_{t+1}) - \Phi_t(Q_t)}_{\textrm{(I)}} + \underbrace{\Phi_{t+1}(Q_{t+1}) - \Phi_{t}(Q_{t+1})}_{\textrm{(II)}}. \end{align}\tag{12}\] Now, we first bound (I). Recall that \(\Phi_t(x) = e^{\gamma_t x} - 1\) and \(\Phi_t'(x) = \gamma_t e^{\gamma_t x}\). It follows that \[\begin{align} \Phi_{t}(Q_{t+1}) - \Phi_t(Q_t) &= e^{\gamma_{t} Q_{t+1}} - e^{\gamma_t Q_t}\\ &= e^{\gamma_t Q_t}(e^{\gamma_t (Q_{t+1}-Q_t)} - 1)\\ &= e^{\gamma_t Q_t}(e^{\gamma_t (g_t(\mathbf{x}_t) - R_t)} - 1)\\ &= \frac{1}{\gamma_t}\Phi_t'(Q_t)(e^{\gamma_t (g_t(\mathbf{x}_t) - R_t)} - 1). \end{align}\] Note that \(e^{x}\leq 1+ x + x^2\) for all \(x\leq 1\), \(\gamma_t (g_t(\mathbf{x}_t) - R_t) \leq \gamma_t G \leq 1\), and \(\Phi_t'(Q_t)/\gamma_t > 0\). Then it follows that \[\begin{align} \label{eq:lem1:40I4132decomp:stoc324332exp324332cvx} &\Phi_t(Q_{t+1}) - \Phi_t(Q_t) \notag\\ &\leq \frac{1}{\gamma_t} \Phi_t'(Q_t) \left(\gamma_t(g_t(\mathbf{x}_t)-R_t) + \gamma_t^2 (g_t(\mathbf{x}_t) - R_t)^2\right)\\ &\leq \Phi_t'(Q_t) \left(g_t(\mathbf{x}_t)-R_t + 3\gamma_tG^2 + 432\gamma_t^3G^4 + 3\gamma_t \left(\frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{\Phi_t'(Q_t)}\right)^2\right)\notag \end{align}\tag{13}\] where the second inequality is due to the fact that \((x+y+z)^2 \leq 3(x^2+y^2+z^2)\) for any \(x,y,z \in \mathbb{R}\). Since \(\gamma_t \leq 1/(12G)\), we have \[\begin{align} \label{eq:lem1:40I4132decomp321:stoc324332exp324332cvx} 3\gamma_t G^2 + 432\gamma_t^3G^4 \leq 3\gamma_t G^2 + 432\gamma_t G^4\cdot \frac{1}{144G^2} = 6\gamma_t G^2. \end{align}\tag{14}\] Moreover, we have \[\begin{align} \label{eq:lem1:40I4132decomp322:stoc324332exp324332cvx} \begin{aligned} &3\gamma_t \frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{\Phi_t'(Q_t)} \\ &= 12\gamma_tDL\frac{\sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} - \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}}{\Phi_t'(Q_t)}\\ &= \frac{12\gamma_t DL\Phi_t'(Q_t)}{\sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}}\\ &\leq 12\gamma_t DL\\ &\leq \frac{1}{2} \end{aligned} \end{align}\tag{15}\] where the first inequality follows from \(\Phi_t'(Q_t) \leq \sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}\), and the second inequality is due to \(\gamma_t\leq 1/(24DL)\). Note that \(\Psi\) is an increasing function, implying that \(\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)\) is nonnegative. Then, by applying 14 and 15 to 13 , (I) is bounded as \[\begin{align} \textrm{(I)}& = \Phi_{t}(Q_{t+1}) - \Phi_t(Q_t) \\ &\leq \Phi_t'(Q_t) \left(g_t(\mathbf{x}_t)-R_t + 6\gamma_tG^2 + \frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{2\Phi_t'(Q_t)}\right) \\ &= \Phi_t'(Q_t)\left(g_t(\mathbf{x}_t) - \frac{1}{2}R_t\right). \end{align}\] Next, we bound (II). Since \(\gamma_{t+1}\leq \gamma_t\), by [prop:Phi], we have \[\textrm{(II)}=\Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_{t+1}) \leq \frac{\gamma_t - \gamma_{t+1}}{e\gamma_{t+1}}.\] By applying bounds on (I) and (II) to 12 , we conclude the proof. ◻
From the right-hand side of the inequality in [lem:drift:stoc324332exp324332cvx], we observe that the cost of employing time-varying Lyapunov functions is \((\gamma_t - \gamma_{t+1})/(e\gamma_{t+1})\). Indeed, the following lemma demonstrates that this cost is not significant by showing that its summation over \(\tau=1,\ldots,t\) grows only logarithmically with \(t\). Consider \(\gamma_t\) given by 4 . Then, we have \[\sum_{\tau=1}^t \frac{\gamma_\tau - \gamma_{\tau+1}}{\gamma_{\tau+1}} \leq \frac{1 + \log t}{2}.\]
Proof. Recall that \(1/\gamma_\tau = \max\{12G\sqrt{\tau}, 24DL, 1\}\). Then it follows that \[\begin{align} \frac{\gamma_\tau - \gamma_{\tau+1}}{\gamma_{\tau+1}} &= \frac{\frac{1}{\gamma_{\tau+1}} - \frac{1}{\gamma_\tau}}{\frac{1}{\gamma_\tau}} \leq \frac{\sqrt{\tau+1} - \sqrt{\tau}}{\sqrt{\tau}} = \frac{1}{(\sqrt{\tau+1} + \sqrt{\tau})\sqrt{\tau}} \leq \frac{1}{2\tau} \end{align}\] where the first inequality follows from \(\max\{x,y,z\} - \max\{x',y,z\} \leq x-x'\) for any \(x > x'\) and \(1/\gamma_\tau \geq 12G\sqrt{\tau}\). Thus, we have \[\begin{align} \sum_{\tau=1}^t \frac{\gamma_\tau - \gamma_{\tau+1}}{\gamma_{\tau+1}} \leq \sum_{\tau=1}^t \frac{1}{2\tau} \leq \frac{1 + \log t}{2}, \end{align}\] as required. ◻
Next, we introduce [lem:adagrad], which provides an AdaGrad-type guarantee for the surrogate loss \(f_t+\Phi_t'(Q_t)g_t\). Consider the setting of 1. Suppose that we run 1 with \(\eta_t\) given by 6 . Then, for all \(t\geq 1\), we have \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})g_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + 2DL \sqrt{t}+ 2DL \sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + D. \end{align}\]
Proof. For simplicity, let \(\hat{f}_\tau = f_\tau + \Phi_\tau'(Q_\tau)g_\tau\) for each \(\tau \in [t]\). Note that since \(\Phi_\tau'(Q_\tau) > 0\), \(\hat{f}_\tau\) is convex. Since projection onto \({\mathcal{X}}\) is a contraction mapping, we have for any \(\mathbf{x}^\star \in {\mathcal{X}}\), \[\begin{align} \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2 &\leq \| \mathbf{x}_\tau -\eta_\tau\nabla \hat{f}_\tau(\mathbf{x}_\tau) - \mathbf{x}^\star\|^2 \\ &\leq \|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 + \eta_\tau^2\|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2 - 2\eta_\tau\nabla \hat{f}_\tau(\mathbf{x}_\tau)^\top (\mathbf{x}_\tau - \mathbf{x}^\star). \end{align}\] By convexity, we have \(\hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star)\leq \nabla \hat{f}_\tau(\mathbf{x}_\tau)^\top(\mathbf{x}_\tau - \mathbf{x}^\star)\). It follows that \[\begin{align} \hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star) \leq \frac{\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2}{2\eta_\tau} + \frac{\eta_\tau \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2}{2}. \end{align}\] Summing over \(\tau=1,\ldots, t\) yields \[\begin{align} \sum_{\tau=1}^t(\hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star)) \leq \sum_{\tau=1}^t\frac{\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2}{2\eta_\tau} + \sum_{\tau=1}^t\frac{\eta_\tau \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2}{2}. \end{align}\] Note that \[\begin{align} \sum_{\tau=1}^t\frac{\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2}{2\eta_\tau} &\leq \sum_{\tau=1}^{t-1}\frac{\|\mathbf{x}_{\tau+1}-\mathbf{x}^\star\|^2}{2}\left(\frac{1}{\eta_{\tau+1}} - \frac{1}{\eta_\tau}\right) + \frac{D^2}{2\eta_1} \\ &\leq \frac{D^2}{2\eta_t}\\ &= \frac{D}{\sqrt{2}}\sqrt{1 + \sum_{\tau=1}^t \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2}\\ &\leq\frac{D}{\sqrt{2}}\sqrt{\sum_{\tau=1}^t \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2} + \frac{D}{\sqrt{2}} \end{align}\] where the second inequality follows from \(1/\eta_{\tau+1} - 1/\eta_\tau \geq 0\) and \(\|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2 \leq D^2\), and the last inequality follows from \(\sqrt{a+b}\leq \sqrt{a}+\sqrt{b}\) for any \(a,b\geq 0\). Moreover, \[\begin{align} \sum_{\tau=1}^t\frac{\eta_\tau \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2}{2} &= \frac{D}{2\sqrt{2}}\sum_{\tau=1}^t\frac{\|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2}{\sqrt{1 + \sum_{s=1}^\tau\|\nabla \hat{f}_s(\mathbf{x}_s)\|^2}}\\ &\leq \frac{D}{2\sqrt{2}}\cdot 2\left(\sqrt{1 + \sum_{\tau=1}^t \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2} - 1\right) \\ &\leq \frac{D}{\sqrt{2}}\sqrt{\sum_{\tau=1}^t \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2} \end{align}\] where the second inequality follows from \(\sum_{\tau=1}^t y_\tau/\sqrt{1+\sum_{s=1}^\tau y_s} \leq 2(\sqrt{1+\sum_{\tau=1}^ty_\tau}-1)\) for any nonnegative sequence \(\{y_\tau\}_{\tau\geq 1}\), and the last inequality follows from \(\sqrt{a+b}\leq \sqrt{a} + \sqrt{b}\) for any \(a,b \geq0\). Since \(1/\sqrt{2} \leq 1\), it follows that \[\begin{align} \sum_{\tau=1}^t(\hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star)) \leq \sqrt{2}D\sqrt{\sum_{\tau=1}^t \|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2} + D. \end{align}\] Recall that \(\hat{f}_\tau = f_\tau + \Phi_\tau'(Q_\tau)g_\tau\) and \(\|\nabla f_\tau(\mathbf{x}_\tau)\|^2, \|\nabla g_\tau(\mathbf{x}_\tau)\|^2 \leq L^2\). It follows that \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)(g_\tau(\mathbf{x}_\tau) - g_\tau(\mathbf{x}^\star)) \\ &\leq 2DL\sqrt{t} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} + D. \end{align}\] By rearranging the above inequality, we conclude the proof. ◻
We now combine Lemmas [lem:drift:stoc324332exp324332cvx] and [lem:adagrad]. This yields the following lemma, which establishes both a small regret bound and the stability of the dual process in expectation. Consider the setting of 1. Suppose that we run 1 with \(\gamma_t,\Psi\) given by 4 and \(\eta_t\) given by 6 . Then, for all \(t\geq 1\), we have \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\right] + \mathbb{E}\left[\Phi_{t+1}(Q_{t+1})\right] \leq 2DL\sqrt{t} + \log t + 1 + D. \end{align}\]
Proof. By [lem:adagrad], we have \[\begin{align} \begin{aligned} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}_\tau) \\ &\leq\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + 2DL\sqrt{t} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} + D. \end{aligned} \end{align}\] By summing the inequality in [lem:drift:stoc324332exp324332cvx] over \(\tau=1, \ldots,t\), since \(\Phi_1(Q_1) = 0\), we have \[\begin{align} \Phi_{t+1}(Q_{t+1}) - \Phi_1(Q_1) \leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\left(g_\tau(\mathbf{x}_\tau) - \frac{R_\tau}{2}\right) + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}}. \end{align}\] Since \(\Phi_1(Q_1) = 0\), it follows that \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) \\ &\leq\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + 2DL\sqrt{t} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} + D + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} - \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)R_\tau. \end{align}\] Note that \[\begin{align} \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)R_\tau &\geq \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\cdot\frac{\Psi(\sum_{s=1}^\tau \Phi_s'(Q_s)^2)-\Psi(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2)}{\Phi_\tau'(Q_\tau)} \\ &= \frac{1}{2}\Psi\left(\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2\right) - \frac{1}{2}\Psi\left(0\right)\\ &=2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] Thus, we deduce that \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) &\leq \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star)+2DL\sqrt{t} + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} + D\\ &\leq \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star)+2DL\sqrt{t} + \log t + 1 + D. \end{align}\] where the second inequality follows from [lem:gamma32sum32exp] and \(1/(2e) \leq 1\). Now, taking expectations on both sides yields \[\begin{align} &\mathbb{E}\left[\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star))\right] + \mathbb{E}\left[\Phi_{t+1}(Q_{t+1})\right]\\ &\leq \sum_{\tau=1}^t \mathbb{E}\left[\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star)\right]+2DL\sqrt{t} + \log t + 1 + D\\ &= \sum_{\tau=1}^t \mathbb{E}\left[\Phi_\tau'(Q_\tau)\mathbb{E}[g_\tau(\mathbf{x}^\star)|{\mathcal{F}}_{\tau-1}]\right]+2DL\sqrt{t} + \log t + 1 + D \\ &\leq 2DL\sqrt{t} + \log t + 1 + D \end{align}\] where the equality follows from the tower rule and \(\Phi_\tau'(Q_\tau)\) is \({\mathcal{F}}_{\tau-1}\)-measurable, and the second inequality follows from the feasibility assumption that \(\mathbb{E}[g_\tau(\mathbf{x}^\star)] \leq 0\) for fixed \(\mathbf{x}^\star\) and that \(\{g_\tau\}_{\tau\geq 1}\) are i.i.d. samples. This concludes the proof. ◻
Next, we introduce [lem:R32sum:stoc324332exp324332cvx], which shows that the cumulative sum of \(R_\tau\) up to round \(t\) scales as \(\sqrt{t \log t}\) in expectation. Consider the setting of 1. Suppose that we run 1 with \(\gamma_t,\Psi\) given by 4 , and \(\eta_t\) given by 6 . Then, for all \(t\geq 1\), we have \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] = {O}\left(\sqrt{t \log t}\right). \end{align}\]
Proof. We first bound \(\mathbb{E}[\Phi_{t+1}'(Q_{t+1})]\), which is frequently used throughout the proof. By Lipschitzness, we have \(f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star) \geq -LD\). Then it leads to \(\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\geq -LDt\) almost surely. By [lem:Regret43Phi:stoc324332exp324332cvx], we have \[\begin{align} \mathbb{E}[\Phi_{t+1}(Q_{t+1})] &\leq 3DLt + \log t + 1 + D. \end{align}\] This leads to \[\begin{align} \label{eq:Phi3932bound:stoc324332exp324332cvx} \begin{aligned} \mathbb{E}[\Phi_{t+1}'(Q_{t+1})] &\leq \gamma_{t+1}\left(3DLt + \log t + D + 2\right)\leq 3DLt + \log t + D + 2. \end{aligned} \end{align}\tag{16}\] Now, we bound \(\sum_{\tau=1}^t R_\tau\). Since \(\gamma_\tau \leq 1/(12G\sqrt{\tau})\), we have \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] \leq \sum_{\tau=1}^t\frac{G}{\sqrt{\tau}} + \sum_{\tau=1}^t \mathbb{E}\left[\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\right]. \end{align}\] It is clear that \(\sum_{\tau=1}^t G/\sqrt{\tau} \leq 2G\sqrt{t}\). Moreover, it follows that \[\begin{align} &\sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)} \\ &= 4DL\sum_{\tau=1}^t \frac{\sqrt{ \sum_{s=1}^\tau\Phi_s'(Q_s)^2}-\sqrt{ \sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2}}{\Phi_\tau'(Q_\tau)}\\ &= 4DL\sum_{\tau=1}^t\frac{\Phi_\tau'(Q_\tau)}{\sqrt{ \sum_{s=1}^\tau\Phi_s'(Q_s)^2}+\sqrt{ \sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2}}\\ &\leq 4DL\sum_{\tau=1}^t\frac{\Phi_\tau'(Q_\tau)}{\sqrt{ \sum_{s=1}^\tau\Phi_s'(Q_s)^2}} \\ &\leq 4DL\sqrt{t}\sqrt{\sum_{\tau=1}^t\frac{\Phi_\tau'(Q_\tau)^2}{\sum_{s=1}^\tau \Phi_s'(Q_s)^2}}\\ &= 4DL\sqrt{t}\sqrt{\sum_{\tau=2}^t\frac{\sum_{s=1}^\tau\Phi_s'(Q_s)^2 - \sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2}{\sum_{s=1}^\tau \Phi_s'(Q_s)^2} + 1} \\ &\leq 4DL\sqrt{t}\sqrt{\log\frac{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}{\Phi_1'(Q_1)^2} +1}\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)}{\Phi_1'(Q_1)} +1}. \end{align}\] where the second inequality follows from the Cauchy-Schwarz inequality, the third inequality is due to [lem:integral32147x], and the last inequality follows from \(\sum_{\tau=1}^t a_\tau^2 \leq (\sum_{\tau=1}^t a_\tau)^2\) for any nonnegative sequence \(\{a_\tau\}_{\tau=1}^t\). Now, by taking \(\mathbb{E}\) on both sides, since \(\sqrt{x}\) and \(\log x\) are concave functions, it follows that \[\begin{align} &\sum_{\tau=1}^t\mathbb{E}\left[\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\right] \\ &\leq \mathbb{E}\left[4DL\sqrt{t}\sqrt{2\log\frac{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)}{\Phi_1'(Q_1)} +1}\right]\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{\sum_{\tau=1}^t\mathbb{E}[\Phi_\tau'(Q_\tau)]}{\Phi_1'(Q_1)} +1} \\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{t(3DLt + \log t + D + 2)}{\gamma_1} + 1} \end{align}\] where the second inequality follows from Jensen’s inequality, and the last inequality follows from 16 . Consequently, we deduce that \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] \leq 2G\sqrt{t} + 4DL\sqrt{t}\sqrt{2\log\frac{t(3DLt + \log t + D + 2)}{\gamma_1}+1}. \end{align}\] It can be written as \(\mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] = {O}\left(\sqrt{t \log t}\right)\). ◻
6.1 Proof of Theorem 1↩︎
Now, we are ready to prove 1.
Proof. By [lem:Regret43Phi:stoc324332exp324332cvx], since \(\Phi_{t+1}(Q_{t+1}) \geq -1\), we have \[\begin{align} \mathbb{E}[\mathrm{Regret}(t)]=\mathbb{E}\left[\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\right]\leq 2DL\sqrt{t} + \log t + 2 + D. \end{align}\] Next, to bound \(\mathbb{E}[\mathrm{Violation}(t)]\), we observe that \(\mathbb{E}\left[\sum_{\tau=1}^t g_\tau(\mathbf{x}_\tau)\right] = \mathbb{E}[Q_{t+1}] + \sum_{\tau=1}^t \mathbb{E}[R_\tau]\). Thus, we first bound \(\mathbb{E}[Q_{t+1}]\). As done in the proof of [lem:R32sum:stoc324332exp324332cvx], we have \[\begin{align} \begin{aligned} \mathbb{E}[\Phi_{t+1}(Q_{t+1})]\leq 3DLt + \log t + 1 + D. \end{aligned} \end{align}\] By Jensen’s inequality, we have \(e^{\gamma_{t+1}\mathbb{E}[Q_{t+1}]}-1 \leq \mathbb{E}[e^{\gamma_{t+1}Q_{t+1}}-1] = \mathbb{E}[\Phi_{t+1}(Q_{t+1})]\). Thus, we have \[\begin{align} \mathbb{E}[Q_{t+1}] &\leq \frac{1}{\gamma_{t+1}}\log\left(3DLt + \log t + 2 + D\right)\\ &\leq \left(12G\sqrt{t+1} + 24DL + 1\right)\log\left(3DLt + \log t + 2 + D\right) \end{align}\] It can be written as \[\mathbb{E}[Q_{t+1}] = {O}\left(\sqrt{t}\log t\right).\] Moreover, by [lem:R32sum:stoc324332exp324332cvx], we have \(\mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] = {O}(\sqrt{t \log t})\). Consequently, we have \[\mathbb{E}[\mathrm{Regret}(t)] = {O}\left(\sqrt{t}\right), \quad \mathbb{E}[\mathrm{Violation}(t)] = {O}\left(\sqrt{t}\log t\right),\] as required. ◻
7 Analysis under Stochastic Constraints: High-Probability Bounds↩︎
In this section, we present the analysis of 2, which establishes high-probability guarantees under convex losses and stochastic constraints. The key challenge is to obtain a high-probability bound on \[\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star),\] which is required to derive a high-probability analogue of [lem:Regret43Phi:stoc324332exp324332cvx]. In contrast, in the expected bound setting, the above summation is nonpositive in expectation as a consequence of feasibility, i.e., \(\mathbb{E}[g_t(\mathbf{x}^\star)]\leq 0\). Therefore, we must derive a high-probability upper bound on this summation under the sole assumption that \(\mathbb{E}[g_t(\mathbf{x}^\star)]\leq 0\). To this end, we introduce the following lemma, which provides an anytime concentration inequality for supermartingales. Let \(\{X_t\}_{t\geq 1}\) be a random process adapted to a filtration \(\{{\mathcal{F}}_t\}_{t\geq 0}\), satisfying \(\mathbb{E}[X_t|{\mathcal{F}}_{t-1}] \leq 0\) for all \(t\geq 1\). Let \(\{w_t\}_{t\geq1}\) be a random process such that \(w_t\) is positive and \({\mathcal{F}}_{t-1}\)-measurable for all \(t\geq 1\). For some constant \(G\), suppose that \(|X_t| \leq G\) almost surely for all \(t\geq 1\). Define \(\{S_t\}_{t\geq 1}\) such that \[S_t = \sum_{\tau=1}^t w_\tau X_\tau, \quad \forall t \geq 1.\] Let \(\delta \in (0,1)\). With probability at least \(1-\delta\), for all \(t \geq 1\), \[S_t \leq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{(\pi^2/6)(1+\log_2(1 + \sum_{\tau=1}^t w_\tau^2))^2}{\delta}}.\]
Proof. Since \(|X_t| \leq G\), we have \(|w_tX_t| \leq Gw_t\) almost surely. Fix \(\lambda > 0\). By [lem:hoeffding32lemma], we have for each \(t\geq 1\), \[\begin{align} \mathbb{E}\left[\exp\left({\lambda w_t X_t}\right) | {\mathcal{F}}_{t-1}\right] \leq \exp\left(\frac{\lambda^2 G^2 w_t^2}{2}\right) \end{align}\] Since \(w_t\) is \({\mathcal{F}}_{t-1}\)-measurable, it can be rewritten as \[\begin{align} \label{eq:lem:supmt32ci321} \mathbb{E}\left[\exp\left({\lambda w_t X_t}- \frac{\lambda^2G^2w_t^2}{2}\right) | {\mathcal{F}}_{t-1}\right] \leq 1. \end{align}\tag{17}\] Define \(\{M_t\}_{t\geq0}\) such that \(M_0=1\) and \[\begin{align} M_t = M_{t-1} \exp\left({\lambda w_t X_t}- \frac{\lambda^2G^2w_t^2}{2}\right), \quad \forall t \geq 1. \end{align}\] Note that \(\{M_t\}_{t\geq 0}\) is adapted to \(\{{\mathcal{F}}_t\}_{t\geq 0}\). Moreover, it is a supermartingale, since \[\mathbb{E}[M_t|{\mathcal{F}}_{t-1}] \leq M_{t-1}\mathbb{E}\left[\exp\left({\lambda w_t X_t}- \frac{\lambda^2G^2w_t^2}{2}\right) | {\mathcal{F}}_{t-1}\right] \leq M_{t-1}.\] By [lem:maximal32ineq], it follows that for any \(\epsilon > 0\), \[\begin{align} \mathbb{P}\left(\sup_{t\geq 0} M_t \geq \epsilon\right) \leq \frac{\mathbb{E}[M_0]}{\epsilon} = \frac{1}{\epsilon}. \end{align}\] Note that \(\mathbb{P}(\sup_{t\geq 1}M_t \geq \epsilon) \leq \mathbb{P}(\sup_{t\geq 0}M_t \geq \epsilon)\). Moreover, \(M_t = \exp\left(\lambda S_t - (\lambda^2 G^2/2) \sum_{\tau=1}^t w_\tau^2\right)\) for every \(t\geq 1\). By taking \(\epsilon = 1/\delta\), it follows that \[\begin{align} &\quad \mathbb{P}\left(\exists t\geq 1:\; \exp\left(\lambda S_t - \frac{\lambda^2G^2}{2} \sum_{\tau=1}^t w_\tau^2\right)\geq \frac{1}{\delta} \right) \leq \delta \\ \Leftrightarrow &\quad \mathbb{P}\left(\exists t\geq 1:\; S_t \geq \frac{\lambda G^2}{2} \sum_{\tau=1}^t w_\tau^2 + \frac{1}{\lambda}\log\frac{1}{\delta} \right) \leq \delta. \end{align}\] Note that this implies that for any \(\delta \in (0,1)\), \[\mathbb{P}\left(\exists t\geq 1:\; S_t \geq \frac{\lambda G^2}{2} \left(1+\sum_{\tau=1}^t w_\tau^2\right) + \frac{1}{\lambda}\log\frac{1}{\delta} \right) \leq \delta.\] To conclude the proof, we apply the peeling argument. In particular, let the index set \({\mathcal{I}}_k\) be defined as for \(k \geq 0\), \[{\mathcal{I}}_k = \left\{t\geq 1:\; 2^k\leq 1 + \sum_{\tau=1}^t w_\tau^2 < 2^{k+1}\right\}.\] Furthermore, for each \(t \in {\mathcal{I}}_k\), we have \[\begin{align} \frac{\lambda G^2}{2} \left(1+\sum_{\tau=1}^t w_\tau^2\right) + \frac{1}{\lambda}\log\frac{1}{\delta} &< {\lambda G^2}2^{k} + \frac{1}{\lambda}\log\frac{1}{\delta} \\ &= 2G\sqrt{2^k \log \frac{1}{\delta}} \\ &\leq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{1}{\delta}} \end{align}\] where the equality follows from taking \(\lambda = \sqrt{\log(1/\delta)/G^22^k}\), and the inequalities follow from the definition of \({\mathcal{I}}_k\). Then it follows that for any \(\delta \in (0,1)\), \[\begin{align} \mathbb{P}\left(\exists t \in {\mathcal{I}}_k:\; S_t \geq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{1}{\delta}} \right) \leq \delta. \end{align}\] Moreover, given \(\delta \in (0,1)\), define \(\delta_k = \frac{\delta}{(\pi^2/6)(k+1)^2}\), hence we have \(\sum_{k=0}^\infty \delta_k = \delta\), as \(\sum_{k=0}^\infty \frac{1}{(k+1)^2} = \frac{\pi^2}{6}\). By taking \(\delta \leftarrow \delta_k\), it follows that \[\begin{align} &\mathbb{P}\left(\exists t \in {\mathcal{I}}_k:\; S_t \geq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{1}{\delta_k}} \right) \leq \delta_k\\ \Leftrightarrow \quad& \mathbb{P}\left(\exists t \in {\mathcal{I}}_k:\; S_t \geq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{(\pi^2/6)(k+1)^2}{\delta}} \right) \leq \delta_k. \end{align}\] For each \(t \in {\mathcal{I}}_k\), we know that \(k \leq \log_2(1 + \sum_{\tau=1}^t w_\tau^2)\). This implies that \[\begin{align} \mathbb{P}\left(\exists t \in {\mathcal{I}}_k:\; S_t \geq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{(\pi^2/6)(1+\log_2(1 + \sum_{\tau=1}^t w_\tau^2))^2}{\delta}} \right) \leq \delta_k. \end{align}\] Since \(\{t \geq 1\} = \bigcup_{k=0}^\infty {\mathcal{I}}_k\), by taking union bound over \(k = 0,1,2,\ldots\), we have \[\begin{align} \mathbb{P}\left(\exists t \geq1:\; S_t \geq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{(\pi^2/6)(1+\log_2(1 + \sum_{\tau=1}^t w_\tau^2))^2}{\delta}} \right) \leq \sum_{k=0}^\infty \delta_k = \delta. \end{align}\] Thus, with probability at least \(1-\delta\), for all \(t \geq 1\), we have \[S_t \leq 2G\sqrt{\left(1 + \sum_{\tau=1}^t w_\tau^2\right) \log \frac{(\pi^2/6)(1+\log_2(1 + \sum_{\tau=1}^t w_\tau^2))^2}{\delta}}.\] ◻
Note that [lem:supmg32ci] suggests that \[\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) \leq 2G\sqrt{\left(1 + \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}}.\] This observation motivates us to modify the definition of \(\Psi\) compared to the expected bound setting. Specifically, since \[\mathbb{E}\left[\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star)\right]\leq 0\] in the expected bound setting, the only term that needs to be canceled is \[2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2},\] which leads to the choice \(\Psi(x)=4DL\sqrt{x}\). In contrast, under the high-probability setting, the term that must be canceled becomes \[2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} + 2G\sqrt{\left(1 + \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}}.\] This leads to the modified choice of \(\Psi\) in 5 . While the overall structure of the algorithm remains unchanged, the high-probability setting requires a more sophisticated choice of both \(\Psi\) and \(\gamma_t\). We now proceed to establish high-probability analogues of the previous lemmas under these updated parameter choices.
Suppose that we run 1 with \(\gamma_t,\Psi\) given by 5 . Then, for all \(t\geq 1\), we have \[\label{eq:time-varying32drift} \Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_{t}) \leq \Phi_t'(Q_{t})\left(g_t(\mathbf{x}_t) - \frac{R_t}{2}\right) + \frac{\gamma_t - \gamma_{t+1}}{e\gamma_{t+1}}.\tag{18}\]
Proof. Note that the left-hand side of 18 can be decomposed as \[\begin{align} \label{eq:lem1:40I414340II41:hp} \Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_t) = \underbrace{\Phi_t(Q_{t+1}) - \Phi_t(Q_t)}_{\textrm{(I)}} + \underbrace{\Phi_{t+1}(Q_{t+1}) - \Phi_{t}(Q_{t+1})}_{\textrm{(II)}}. \end{align}\tag{19}\] Now, we first bound (I). Recall that \(\Phi_t(x) = e^{\gamma_t x} - 1\) and \(\Phi_t'(x) = \gamma_t e^{\gamma_t x}\). It follows that \[\begin{align} \Phi_{t}(Q_{t+1}) - \Phi_t(Q_t) &= e^{\gamma_{t} Q_{t+1}} - e^{\gamma_t Q_t}\\ &= e^{\gamma_t Q_t}(e^{\gamma_t (Q_{t+1}-Q_t)} - 1)\\ &= e^{\gamma_t Q_t}(e^{\gamma_t (g_t(\mathbf{x}_t) - R_t)} - 1)\\ &= \frac{1}{\gamma_t}\Phi_t'(Q_t)(e^{\gamma_t (g_t(\mathbf{x}_t) - R_t)} - 1). \end{align}\] Note that \(e^{x}\leq 1+ x + x^2\) for all \(x\leq 1\), \(\gamma_t (g_t(\mathbf{x}_t) - R_t) \leq \gamma_t G \leq 1\), and \(\Phi_t'(Q_t)/\gamma_t > 0\). Then it follows that \[\begin{align} \label{eq:lem1:40I4132decomp} &\Phi_t(Q_{t+1}) - \Phi_t(Q_t) \notag\\ &\leq \frac{1}{\gamma_t} \Phi_t'(Q_t) \left(\gamma_t(g_t(\mathbf{x}_t)-R_t) + \gamma_t^2 (g_t(\mathbf{x}_t) - R_t)^2\right)\\ &\leq \Phi_t'(Q_t) \left(g_t(\mathbf{x}_t)-R_t + 3\gamma_tG^2 + 432\gamma_t^3G^4 + 3\gamma_t \left(\frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{\Phi_t'(Q_t)}\right)^2\right)\notag \end{align}\tag{20}\] where the second inequality is due to the Cauchy-Schwarz inequality. Since \(\gamma_t \leq 1/(12G)\), we have \[\begin{align} \label{eq:lem1:40I4132decomp321} 3\gamma_t G^2 + 432\gamma_t^3G^4 \leq 3\gamma_t G^2 + 432\gamma_t G^4\cdot \frac{1}{144G^2} = 6\gamma_t G^2. \end{align}\tag{21}\] Moreover, we have \[\begin{align} \label{eq:lem1:40I4132decomp322} \begin{aligned} &3\gamma_t \frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{\Phi_t'(Q_t)} \\ &= \underbrace{12\gamma_tDL\frac{\sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} - \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}}{\Phi_t'(Q_t)}}_{\textrm{(I-a)}} \\ &\quad+ \underbrace{ 12\gamma_tG \frac{\sqrt{\psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)} - \sqrt{\psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}}{\Phi_t'(Q_t)} }_{\textrm{(I-b)}} \end{aligned} \end{align}\tag{22}\] where \(\psi(x) = (1+x)\log\frac{(\pi^2/6)(1+\log_2(1+x))^2}{\delta}\). For (I-a), we have \[\begin{align} \label{eq:lem1:40I-a41} \begin{aligned} \textrm{(I-a)} &= \frac{12\gamma_t DL\Phi_t'(Q_t)}{\sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}}\\ &\leq 12\gamma_t DL \end{aligned} \end{align}\tag{23}\] where the inequality follows from \(\Phi_t'(Q_t) \leq \sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + \sqrt{\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2}\). To bound (I-b), we observe that \(\Phi_t'(Q_t) = \sqrt{(1 + \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2)-(1+\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2)}\). Then, by [prop:psi], we have \[\begin{align} \begin{aligned} \textrm{(I-b)} &\leq 96\gamma_t G \sqrt{\log\frac{(\pi^2/6)(1 + \log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}}. \end{aligned} \end{align}\] To further bound, we observe that \(Q_{t+1} \leq \sum_{\tau=1}^tg_\tau(\mathbf{x}_\tau) \leq Gt\) for all \(t \geq 1\) and \(Q_1 = 0\), implying that \(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2 \leq \sum_{\tau=1}^t \gamma_\tau^2e^{2\gamma_\tau G\tau}\). Note that \(\gamma_\tau \leq 1/(12G\sqrt{\tau})\) and \(\gamma_\tau \leq 1\). Then it follows that \[\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2 \leq te^{\sqrt{t}/6}.\] Since \(\log(1+t)\leq t\), it leads to \[\log_2\left(1+ \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)=\frac{\log\left(1+ te^{\sqrt{t}/6}\right)}{\log 2} \leq \frac{\log(1+t)+t/6}{\log 2} \leq \frac{t+t/6}{\log 2} = \frac{7t}{6\log2}.\] Hence, it follows that \[\log \frac{\pi^2}{6\delta}\left(1 + \log_2\left(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)\right)^2 \leq \log \frac{\pi^2}{6\delta}\left(t + \frac{7t}{6\log2}\right)^2 \leq \log \frac{12t^2}{\delta}.\] Finally, we deduce that \[\begin{align} \label{eq:lem1:40I-b41} \textrm{(I-b)}\leq 96\gamma_t G\sqrt{\log\frac{12t^2}{\delta}}. \end{align}\tag{24}\] By substituting 23 and 24 into 22 , we have \[\begin{align} \label{eq:lem1:40I4132decomp323} \begin{aligned} 3\gamma_t \frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{\Phi_t'(Q_t)} &\leq \gamma_t\left(12DL + 96G\sqrt{\log\frac{12t^2}{\delta}}\right)\\ &\leq \frac{1}{2} \end{aligned} \end{align}\tag{25}\] where the second inequality follows from \(\gamma_t \leq 1/(24(DL+8G\sqrt{\log(12t^2/\delta)}))\). Note that \(\Psi\) is an increasing function, implying that \(\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)\) is nonnegative. Then, by applying 21 and 25 to 20 , (I) is bounded as \[\begin{align} &\textrm{(I)} = \Phi_{t}(Q_{t+1}) - \Phi_t(Q_t) \\ &\leq \Phi_t'(Q_t) \left(g_t(\mathbf{x}_t)-R_t + 6\gamma_tG^2 + \frac{\Psi\left(\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)-\Psi\left(\sum_{\tau=1}^{t-1}\Phi_\tau'(Q_\tau)^2\right)}{2\Phi_t'(Q_t)}\right) \\ &= \Phi_t'(Q_t)\left(g_t(\mathbf{x}_t) - \frac{1}{2}R_t\right). \end{align}\] Next, we bound (II). Since \(\gamma_{t+1}\leq \gamma_t\), by [prop:Phi], we have \[\textrm{(II)}=\Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_{t+1}) \leq \frac{\gamma_t - \gamma_{t+1}}{e\gamma_{t+1}}.\] By applying bounds on (I) and (II) to 19 , we conclude the proof. ◻
The following lemma shows that the cost incurred by using time-varying Lyapunov functions with the modified \(\gamma_t\) defined in 5 is negligible in the sense that its summation scales as \(\log t\). Consider \(\gamma_t\) given by 5 . Then, we have \[\sum_{\tau=1}^t \frac{\gamma_\tau - \gamma_{\tau+1}}{\gamma_{\tau+1}} \leq \frac{3(1+\log t)}{2}.\]
Proof. Recall that \(1/\gamma_\tau = \max\{12G\sqrt{\tau}, 24(DL+8G\sqrt{\log(12\tau^2/\delta)}), 1\}\). Note that \(\max\{x,y,z\} - \max\{x',y',z\} \leq x-x' + y-y'\) for any \(x > x'\) and \(y > y'\). Moreover, we know that \(1/\gamma_\tau \geq 12G\sqrt{\tau}\) and \(1/\gamma_\tau \geq 192G\sqrt{\log (12\tau^2/\delta)}\). Then we have \[\begin{align} \frac{\gamma_\tau - \gamma_{\tau+1}}{\gamma_{\tau+1}} &= \frac{\frac{1}{\gamma_{\tau+1}} - \frac{1}{\gamma_\tau}}{\frac{1}{\gamma_\tau}}\\ &\leq \frac{\sqrt{\tau+1} -\sqrt{\tau}}{\sqrt{\tau}} + \frac{\sqrt{\log(12(\tau+1)^2/\delta)} - \sqrt{\log(12\tau^2/\delta)}}{\sqrt{\log(12\tau^2/\delta)}} \\ &\leq \frac{1}{2\tau} + \frac{\log(1 + 1/\tau)}{\log(12\tau^2/\delta)}\\ &\leq \frac{1}{2\tau} + \frac{1}{\tau\log(12\tau^2/\delta)} \\ &\leq \frac{3}{2\tau} \end{align}\] where the last two inequality follow from \(\log(1 + x) \leq x\) for any \(x \geq 0\) and \(\log (12\tau^2/\delta) \geq 1\), respectively. Hence, we have \[\begin{align} \sum_{\tau=1}^t \frac{\gamma_\tau - \gamma_{\tau+1}}{\gamma_{\tau+1}} \leq \sum_{\tau=1}^t \frac{3}{2\tau} \leq \frac{3(1+\log t)}{2}. \end{align}\] ◻
Consider the setting of 2. Suppose that we run 1 with \(\gamma_t,\Psi\) given by 5 , and \(\eta_t\) given by 6 . Then, with probability at least \(1-\delta\), for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) \leq 2DL\sqrt{t} + \log t+ 1 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{align}\]
Proof. By [lem:adagrad], we have \[\begin{align} \label{eq:Regret43Phi:1} \begin{aligned} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})g_\tau(\mathbf{x}_\tau)\\ &\leq\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + 2DL\sqrt{t} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} + D. \end{aligned} \end{align}\tag{26}\] Moreover, the first term on the right-hand side can be bounded using [lem:supmg32ci]. In particular, since \(\Phi_\tau'(Q_\tau)\) is \({\mathcal{F}}_{\tau-1}\)-measurable and positive, \(g_\tau(\mathbf{x}^\star)\) is \({\mathcal{F}}_\tau\)-measurable satisfying \(|g_\tau(\mathbf{x}^\star)|\leq G\), and \(\mathbb{E}[g_\tau(\mathbf{x}^\star)|{\mathcal{F}}_{\tau-1}] = \mathbb{E}[g_\tau(\mathbf{x}^\star)] \leq 0\), it leads to the following: with probability at least \(1-\delta\), for all \(t\geq 1\), \[\begin{align} \label{eq:Regret43Phi:2} \begin{aligned} &\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star)\\ &\leq 2G\sqrt{\left(1 + \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}}. \end{aligned} \end{align}\tag{27}\] Moreover, by summing the inequality in [lem:drift:stoc324332hp324332cvx] over \(\tau=1, \ldots,t\), since \(\Phi_1(Q_1) = 0\), we have \[\begin{align} \label{eq:Regret43Phi:3} \Phi_{t+1}(Q_{t+1}) - \Phi_1(Q_1) \leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\left(g_\tau(\mathbf{x}_\tau) - \frac{R_\tau}{2}\right) + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}}. \end{align}\tag{28}\] By applying 27 and 28 to 26 , we have \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) \\ &\leq 2G\sqrt{\left(1 + \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2\right)\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}} \\ &\quad+ 2DL\sqrt{t} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} + D + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} - \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)R_\tau. \end{align}\] Note that \[\begin{align} \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)R_\tau &\geq \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\cdot\frac{\Psi(\sum_{s=1}^\tau \Phi_s'(Q_s)^2)-\Psi(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2)}{\Phi_\tau'(Q_\tau)} \\ &= \frac{1}{2}\Psi\left(\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2\right) - \frac{1}{2}\Psi\left(0\right)\\ &=2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} - 2G\sqrt{\log\frac{\pi^2}{6\delta}} \\ &\quad+ 2G\sqrt{\left(1+\sum_{\tau=1}^t\Phi_\tau'(Q_{\tau})^2\right)\log\frac{(\pi^2/6)(1 + \log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}}. \end{align}\] Thus, we deduce that \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) &\leq 2DL\sqrt{t} + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} + D+ 2G\sqrt{\log\frac{\pi^2}{6\delta}} \\ &\leq 2DL\sqrt{t} + \log t+ 1 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}} \end{align}\] where the second inequality follows from [lem:gamma32sum32hp] and \(3/(2e) \leq1\). This concludes the proof. ◻
Consider the setting of 2. Suppose that we run 1 with \(\gamma_t,\Psi\) given by 5 , and \(\eta_t\) given by 6 . Suppose that [lem:Regret43Phi:stoc324332hp324332cvx] holds. Then, for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t}\log(t/\delta)\right). \end{align}\]
Proof. We first bound \(\Phi_{t+1}'(Q_{t+1})\), which is frequently used throughout the proof. By Lipschitzness, we have \(f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star) \geq -LD\). Then it leads to \(\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\geq -LDt\). By [lem:Regret43Phi:stoc324332hp324332cvx], we have \[\begin{align} \Phi_{t+1}(Q_{t+1}) &\leq 3DLt + \log t + 1 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{align}\] This leads to \[\begin{align} \label{eq:Phi3932bound} \begin{aligned} \Phi_{t+1}'(Q_{t+1}) &\leq \gamma_{t+1}\left(3DLt + \log t + 2 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\right)\\ &\leq 3DLt + \log t + 2 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{aligned} \end{align}\tag{29}\] Now, we bound \(\sum_{\tau=1}^t R_\tau\). Since \(\gamma_\tau \leq 1/(12G\sqrt{\tau})\), we have \[\begin{align} \sum_{\tau=1}^t R_\tau \leq \sum_{\tau=1}^t\frac{G}{\sqrt{\tau}} + \sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}. \end{align}\] It is clear that \(\sum_{\tau=1}^t G/\sqrt{\tau} \leq 2G\sqrt{t}\). Moreover, it follows that \[\begin{align} &\sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)} \\ &= \underbrace{4DL\sum_{\tau=1}^t \frac{\sqrt{ \sum_{s=1}^\tau\Phi_s'(Q_s)^2}-\sqrt{ \sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2}}{\Phi_\tau'(Q_\tau)}}_{\textrm{(I)}} \\ &\quad+\underbrace{4G\sum_{\tau=1}^t \frac{\sqrt{\psi(\sum_{s=1}^\tau\Phi_s'(Q_s)^2)} - \sqrt{ \psi(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2)}}{\Phi_\tau'(Q_\tau)}}_{\textrm{(II)}}. \end{align}\] We bound (I) as follows. \[\begin{align} \textrm{(I)} &= 4DL\sum_{\tau=1}^t\frac{\Phi_\tau'(Q_\tau)}{\sqrt{ \sum_{s=1}^\tau\Phi_s'(Q_s)^2}+\sqrt{ \sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2}}\\ &\leq 4DL\sum_{\tau=1}^t\frac{\Phi_\tau'(Q_\tau)}{\sqrt{ \sum_{s=1}^\tau\Phi_s'(Q_s)^2}} \\ &\leq 4DL\sqrt{t}\sqrt{\sum_{\tau=1}^t\frac{\Phi_\tau'(Q_\tau)^2}{\sum_{s=1}^\tau \Phi_s'(Q_s)^2}}\\ &= 4DL\sqrt{t}\sqrt{\sum_{\tau=2}^t\frac{\sum_{s=1}^\tau\Phi_s'(Q_s)^2 - \sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2}{\sum_{s=1}^\tau \Phi_s'(Q_s)^2} + 1} \\ &\leq 4DL\sqrt{t}\sqrt{\log\frac{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}{\Phi_1'(Q_1)^2} +1}\\ &\leq4DL\sqrt{t}\sqrt{\log\frac{t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2}{\gamma_1^2} + 1}. \end{align}\] where the second inequality follows from the Cauchy-Schwarz inequality, the third inequality is due to [lem:integral32147x], and the last inequality follows from 29 , i.e., since \(\Phi_1'(Q_1)^2=\gamma_1^2 \leq 1\), \[\begin{align} \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2=\sum_{\tau=0}^{t-1} \Phi_{\tau+1}'(Q_{\tau+1})^2 &\leq 1+(t-1)(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2\\ &\leq t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2. \end{align}\] To bound (II), by [prop:psi], \[\begin{align} \textrm{(II)} &\leq 32G\sum_{\tau=1}^t \sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{s=1}^\tau \Phi_s'(Q_s)^2))^2}{\delta}}\\ &\quad\times\frac{\sqrt{1+ \sum_{s=1}^\tau \Phi_s'(Q_s)^2}-\sqrt{1+ \sum_{s=1}^{\tau-1} \Phi_s'(Q_s)^2}}{\Phi_\tau'(Q_\tau)} \\ &\leq 32G\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2))^2}{\delta}}\\ &\quad\times\sum_{\tau=1}^t \frac{\sqrt{1+ \sum_{s=1}^\tau \Phi_s'(Q_s)^2}-\sqrt{1+ \sum_{s=1}^{\tau-1} \Phi_s'(Q_s)^2}}{\Phi_\tau'(Q_\tau)} \\ &\leq 32G\sqrt{t}\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2))^2}{\delta}}\\ &\quad \times\sqrt{\log \frac{t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2}{\gamma_1^2} + 1}. \end{align}\] where the first inequality follows from [prop:psi], and the third inequality follows from the same argument used for bounding (I). Hence, we deduce that \[\begin{align} \sum_{\tau=1}^t R_\tau &\leq 2G\sqrt{t} + 4DL\sqrt{t}\sqrt{\log\frac{t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2}{\gamma_1^2} + 1} \\ &\quad+32G\sqrt{t}\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2))^2}{\delta}}\\ &\quad \times\sqrt{\log \frac{t(3DLt + \log t + 2 + D + 2G\sqrt{\log(\pi^2/(6\delta))})^2}{\gamma_1^2} + 1}. \end{align}\] It can be written as \(\sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t}\log(t/\delta)\right)\). ◻
7.1 Proof of Theorem 2↩︎
Proof. We assume that [lem:Regret43Phi:stoc324332hp324332cvx] holds, which occurs with probability at least \(1-\delta\). Since \(\Phi_{t+1}(Q_{t+1}) \geq -1\), we have \[\begin{align} \mathrm{Regret}(t)=\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\leq 2DL\sqrt{t} + \log t + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}} + 2 \end{align}\] Next, to bound \(\mathrm{Violation}(t)\), we observe that \(\sum_{\tau=1}^t g_\tau(\mathbf{x}_\tau) = Q_{t+1} + \sum_{\tau=1}^t R_\tau\). Thus, we first bound \(Q_{t+1}\). As done in the proof of [lem:R32sum:stoc324332hp324332cvx], we have \[\begin{align} \begin{aligned} \Phi_{t+1}(Q_{t+1}) &\leq 3DLt + \log t + 1 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{aligned} \end{align}\] By the definition of \(\Phi_{t+1}\), since \(Q_{t+1} = (1/\gamma_{t+1})\log(\Phi_{t+1}(Q_{t+1})+1)\), we have \[\begin{align} Q_{t+1} &\leq \frac{1}{\gamma_{t+1}}\log\left(3DLt + \log t + 2 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\right)\\ &\leq \left(12G\sqrt{t+1} + 24\left(DL+8G\sqrt{\log(12(t+1)^2/\delta)}\right) + 1\right) \\ &\quad \times \log\left(3DLt + \log t + 2 + D + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\right). \end{align}\] It can be written as \[Q_{t+1} = {O}\left(\sqrt{t}\log(t/\delta) + \log^{3/2}(t/\delta)\right)\] Moreover, by [lem:R32sum:stoc324332hp324332cvx], we have \(\sum_{\tau=1}^t R_\tau = {O}(\sqrt{t}\log(t/\delta))\). Consequently, we have \[\mathrm{Regret}(t) = {O}\left(\sqrt{t} + \sqrt{\log(1/\delta)}\right), \quad \mathrm{Violation}(t) = {O}\left(\sqrt{t}\log(t/\delta) + \log^{3/2}(t/\delta)\right).\] ◻
8 Analysis under Strongly Convex Losses↩︎
In this section, we present the analysis of Theorems 3 and 4. The key difference in the analysis is to derive an analogue of [lem:adagrad] with an improved guarantee under the modified primal step size defined in 7 . Consider \(\mu\)-strongly convex losses for some \(\mu>0\). Suppose that we run 1 with \(\eta_\tau\) given by 7 . Then, for all \(t\geq 1\), we have \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})g_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\]
Proof. For simplicity, let \(\hat{f}_\tau = f_\tau + \Phi_\tau'(Q_\tau)g_\tau\) for each \(\tau \in [t]\). Note that since \(\Phi_\tau'(Q_\tau) > 0\), \(\Phi_\tau'(Q_\tau)g_\tau\) is convex, and thus \(\hat{f}_\tau\) is \(\mu\)-strongly convex by [lem:strcvx32properties]. Since projection onto \({\mathcal{X}}\) is a contraction mapping, we have for any \(\mathbf{x}^\star \in {\mathcal{X}}\), \[\begin{align} \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2 &\leq \|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 + \eta_\tau^2\|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2 - 2\eta_\tau\nabla \hat{f}_\tau(\mathbf{x}_\tau)^\top (\mathbf{x}_\tau - \mathbf{x}^\star). \end{align}\] By strong convexity ([lem:strcvx32properties]), we have \[\begin{align} \hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star) + \frac{\mu}{2}\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 \leq \nabla \hat{f}_\tau(\mathbf{x}_\tau)^\top (\mathbf{x}_\tau -\mathbf{x}^\star). \end{align}\] Recall that \[\begin{align} \eta_\tau = \frac{1}{\mu\tau + (2L/D)\sqrt{\sum_{s=1}^\tau \Phi_s'(Q_s)^2}}. \end{align}\] Then it follows that \[\begin{align} &\hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star) \\ &\leq \left(\frac{1}{2\eta_\tau} - \frac{\mu}{2}\right)\|\mathbf{x}_\tau -\mathbf{x}^\star\|^2 - \frac{1}{2\eta_\tau}\|\mathbf{x}_{\tau+1}-\mathbf{x}^\star\|^2 + \frac{\eta_\tau}{2}\|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2\\ &= \frac{\mu(\tau-1)}{2}\|\mathbf{x}_\tau-\mathbf{x}^\star\|^2 - \frac{\mu \tau}{2}\|\mathbf{x}_{\tau+1}-\mathbf{x}^\star\|^2 \\ &\quad+ \frac{L}{D}\sqrt{\sum_{s=1}^\tau \Phi_s'(Q_s)^2} (\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2) + \frac{\eta_\tau}{2}\|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2\\ &\leq \frac{\mu(\tau-1)}{2}\|\mathbf{x}_\tau-\mathbf{x}^\star\|^2 - \frac{\mu \tau}{2}\|\mathbf{x}_{\tau+1}-\mathbf{x}^\star\|^2 \\ &\quad+ \frac{L}{D}\sqrt{\sum_{s=1}^\tau \Phi_s'(Q_s)^2} (\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2) + \eta_\tau L^2 + \eta_\tau L^2\Phi_\tau'(Q_\tau)^2 \end{align}\] where the last inequality follows from that \(\|\nabla \hat{f}_\tau(\mathbf{x}_\tau)\|^2 \leq 2\|\nabla f_\tau(\mathbf{x}_\tau)\|^2 + 2\Phi_\tau'(Q_\tau)^2\|\nabla g_\tau(\mathbf{x}_\tau)\|^2 \leq 2L^2(1+\Phi_\tau'(Q_\tau)^2)\). By summing over \(\tau = 1,\ldots, t\), we have \[\begin{align} \sum_{\tau=1}^t(\hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star)) &\leq \frac{L}{D}\sum_{\tau=1}^t\sqrt{\sum_{s=1}^\tau \Phi_s'(Q_s)^2} (\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2) \\ &\quad+ L^2\sum_{\tau=1}^t\eta_\tau + L^2\sum_{\tau=1}^t\eta_\tau \Phi_\tau'(Q_\tau)^2. \end{align}\] Note that \[\begin{align} \sum_{\tau=1}^t\sqrt{\sum_{s=1}^\tau \Phi_s'(Q_s)^2} (\|\mathbf{x}_\tau - \mathbf{x}^\star\|^2 - \|\mathbf{x}_{\tau+1} - \mathbf{x}^\star\|^2) &\leq D^2\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] Moreover, since \(\sum_{\tau=1}^t (1/\tau) \leq 1+\log t\), we have \[\begin{align} \sum_{\tau=1}^t \eta_\tau \leq \sum_{\tau=1}^t \frac{1}{\mu\tau} \leq \frac{1 + \log t}{\mu}. \end{align}\] Similarly, since \(\sum_{\tau=1}^t y_\tau / \sqrt{\sum_{s=1}^\tau y_s} \leq 2\sqrt{\sum_{\tau=1}^t y_\tau}\) for any positive sequence \(\{y_\tau\}_{\tau\geq 1}\), we have \[\begin{align} \sum_{\tau=1}^t \eta_\tau \Phi_\tau'(Q_\tau)^2 \leq \frac{D}{2L}\sum_{\tau=1}^t \frac{\Phi_\tau'(Q_\tau)^2}{\sqrt{\sum_{s=1}^\tau \Phi_s'(Q_s)^2}} \leq \frac{D}{L} \sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] Combining these yields \[\begin{align} \sum_{\tau=1}^t(\hat{f}_\tau(\mathbf{x}_\tau) - \hat{f}_\tau(\mathbf{x}^\star)) \leq \frac{L^2(1+\log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] Recall that \(\hat{f}_\tau = f_\tau + \Phi_\tau'(Q_\tau)g_\tau\). Therefore, we have \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})g_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + \frac{L^2(1 + \log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] ◻
8.1 Expected Bounds↩︎
The proofs of the following lemmas are deferred to Appendix 10. Consider the setting of 3. Suppose that we run 1 with \(\gamma_t,\Psi\) given by 4 , and \(\eta_t\) given by 7 . Then, for all \(t\geq 1\), we have \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\right] + \mathbb{E}\left[\Phi_{t+1}(Q_{t+1})\right] \leq \frac{L^2(1+\log t)}{\mu} + \log t + 1. \end{align}\]
Consider the setting of 3. Suppose that we run 1 with \(\gamma_t,\Psi\) given by 4 , and \(\eta_t\) given by 7 . Then, for all \(t\geq 1\), we have \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] = {O}\left(\sqrt{t \log t}\right). \end{align}\]
8.1.1 Proof of Theorem 3↩︎
Proof. We closely follow the proof of 1, where the only difference is that we use [lem:Regret43Phi:stoc324332exp324332strcvx] and [lem:R32sum:stoc324332exp324332strcvx]. By [lem:Regret43Phi:stoc324332exp324332strcvx], \[\begin{align} \mathbb{E}[\mathrm{Regret}(t)] = \mathbb{E}\left[\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))\right] \leq \frac{L^2(1+\log t)}{\mu} + \log t + 2. \end{align}\] By applying the same argument in the proof of 1, we have \[\begin{align} \mathbb{E}[Q_{t+1}] &\leq \frac{1}{\gamma_{t+1}}\log\left(DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 1\right)\\ &\leq \left(12G\sqrt{t+1} + 24DL + 1\right)\log\left(DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 1\right) \end{align}\] which can be written as \(\mathbb{E}[Q_{t+1}] = {O}\left(\sqrt{t}\log t\right)\). Moreover, by [lem:R32sum:stoc324332exp324332strcvx], we have \(\mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] ={O}(\sqrt{t\log t})\). Since \(\mathbb{E}[\mathrm{Violation}(t)] = \mathbb{E}[Q_{t+1}] + \mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right]\), we have \[\mathbb{E}[\mathrm{Violation}(t)] = {O}\left(\sqrt{t}\log t\right).\] ◻
8.2 High-Probability Bounds↩︎
The proofs of the following lemmas are deferred to Appendix 10. Consider the setting of 4. Suppose that we run 1 with \(\gamma_t,\Psi\) as given by 5 , and \(\eta_t\) as given by 7 . Then, with probability at least \(1-\delta\), for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) \leq \frac{L^2(1+\log t)}{\mu} + \log t + 1 + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{align}\]
Consider the setting of 4. Suppose that we run 1 with \(\gamma_t,\Psi\) as given by 5 , and \(\eta_t\) as given by 7 . Suppose that [lem:Regret43Phi:stoc324332hp324332strcvx] holds. Then, for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t}\log(t/\delta)\right). \end{align}\]
8.2.1 Proof of Theorem 4↩︎
Proof. We closely follow the proof of 2, where the only difference is that we use [lem:Regret43Phi:stoc324332hp324332strcvx] and [lem:R32sum:stoc324332hp324332strcvx]. We assume that [lem:Regret43Phi:stoc324332hp324332strcvx] holds, which occurs with probability at least \(1-\delta\). By [lem:Regret43Phi:stoc324332hp324332strcvx], \[\begin{align} \mathrm{Regret}(t) = \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) \leq \frac{L^2(1+\log t)}{\mu} + \log t + 2 + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{align}\] By applying the same argument in the proof of 2, we have \[\begin{align} Q_{t+1} &\leq \frac{1}{\gamma_{t+1}}\log\left(DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 2 + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\right)\\ &\leq \left(12G\sqrt{t+1} + 24\left(DL+8G\sqrt{\log(12(t+1)^2/\delta)}\right) + 1\right)\\ &\quad\times\log\left(DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 2 + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\right) \end{align}\] which can be written as \(Q_{t+1} = {O}\left(\sqrt{t}\log t + \log^{3/2} (t/\delta)\right)\). Moreover, by [lem:R32sum:stoc324332hp324332strcvx], we have \(\sum_{\tau=1}^t R_\tau={O}(\sqrt{t}\log(t/\delta))\). Since \(\mathrm{Violation}(t) = Q_{t+1} + \sum_{\tau=1}^t R_\tau\), we have \[\mathrm{Violation}(t) = {O}\left(\sqrt{t}\log (t/\delta) + \log^{3/2}(t/\delta)\right),\] as required. ◻
9 Conclusion↩︎
In this paper, we study COCO with stochastic constraints without Slater’s condition. We propose a unified primal-dual algorithm with an anytime regularizer and show that it achieves nearly optimal regret and constraint violation guarantees under stochastic constraints. The key insight is that the regularizer stabilizes the dual process by offsetting an accumulated term involving the derivative of an exponential Lyapunov function. We also establish high-probability guarantees and extend the analysis to strongly convex losses and adversarial constraints. Several directions are worth further investigation. One direction is to obtain dynamic regret bounds under stochastic constraints, where dynamic regret is defined with respect to a comparator sequence \(\{\mathbf{x}_t^\star\}_{t=1}^T\) satisfying \(\{\mathbf{x}_t^\star\}_{t=1}^T \in \mathop{\mathrm{arg\,min}}_{\{\mathbf{x}_t\}_{t=1}^T} \sum_{t=1}^T f_t(\mathbf{x}_t) \;\mathrm{s.t.}\;\mathbb{E}[g_t(\mathbf{x}_t)] \leq 0\) for all \(t\in[T]\), while this paper considers a fixed comparator over time. Another direction is to develop projection-free algorithms, as the proposed algorithm requires a projection oracle onto \({\mathcal{X}}\).
10 Deferred Proofs of Section 8↩︎
Proof of Lemma [lem:Regret43Phi:stoc324332exp324332strcvx]. We closely follow the proof of [lem:Regret43Phi:stoc324332exp324332cvx], where the only difference is that we use [lem:strcvx32regret] instead of [lem:adagrad]. Since we take \(\eta_t\) as 7 and \(\gamma_t, \Psi\) as 4 , Lemmas [lem:strcvx32regret] and [lem:drift:stoc324332exp324332cvx] hold. By [lem:strcvx32regret], we have \[\begin{align} \begin{aligned} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})g_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{aligned} \end{align}\] By [lem:drift:stoc324332exp324332cvx], \[\begin{align} \Phi_{t+1}(Q_{t+1}) - \Phi_1(Q_1) \leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\left(g_\tau(\mathbf{x}_\tau) - \frac{R_\tau}{2}\right) + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}}. \end{align}\] Note that \[\begin{align} \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)R_\tau &\geq 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] Then it follows that \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) \\ &\leq\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} \\ &\leq\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + \log t + 1 \end{align}\] where the second inequality follows from [lem:gamma32sum32exp] and \(1/(2e) \leq 1\). By taking \(\mathbb{E}\) on both sides, since \(\sum_{\tau=1}^t\mathbb{E}[\Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star)] \leq 0\) by applying the same argument in the proof of [lem:Regret43Phi:stoc324332exp324332cvx], we conclude the proof. ◻
Proof of Lemma [lem:R32sum:stoc324332exp324332strcvx]. We closely follow the proof of [lem:R32sum:stoc324332exp324332cvx], where the only difference is that we use [lem:Regret43Phi:stoc324332exp324332strcvx] instead of [lem:Regret43Phi:stoc324332exp324332cvx]. By Lipschitzness and [lem:Regret43Phi:stoc324332exp324332strcvx], \[\begin{align} \mathbb{E}[\Phi_{t+1}'(Q_{t+1})] &\leq DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 1. \end{align}\] Note that \[\begin{align} \mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] \leq \sum_{\tau=1}^t\frac{G}{\sqrt{\tau}} + \sum_{\tau=1}^t \mathbb{E}\left[\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\right]. \end{align}\] It is clear that \(\sum_{\tau=1}^t G/\sqrt{\tau} \leq 2G\sqrt{t}\). Moreover, it follows that \[\begin{align} &\sum_{\tau=1}^t\mathbb{E}\left[\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\right]\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{\sum_{\tau=1}^t\mathbb{E}[\Phi_\tau'(Q_\tau)]}{\Phi_1'(Q_1)} +1}\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{t(DLt + L^2(1+\log t)/\mu +\log t + 1)}{\Phi_1'(Q_1)} +1}. \end{align}\] Finally, we have \(\mathbb{E}\left[\sum_{\tau=1}^t R_\tau\right] = {O}\left(\sqrt{t \log t}\right).\) ◻
Proof of Lemma [lem:Regret43Phi:stoc324332hp324332strcvx]. We closely follow the proof of [lem:Regret43Phi:stoc324332hp324332cvx], where the only difference is that we use [lem:strcvx32regret] instead of [lem:adagrad]. Since we take \(\eta_t\) as 7 and \(\gamma_t, \Psi\) as 5 , Lemmas [lem:strcvx32regret] and [lem:drift:stoc324332hp324332cvx] hold. By [lem:strcvx32regret], we have \[\begin{align} \begin{aligned} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})g_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)g_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{aligned} \end{align}\] By [lem:drift:stoc324332hp324332cvx], \[\begin{align} \Phi_{t+1}(Q_{t+1}) - \Phi_1(Q_1) \leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\left(g_\tau(\mathbf{x}_\tau) - \frac{R_\tau}{2}\right) + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}}. \end{align}\] Note that \[\begin{align} \frac{1}{2}\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)R_\tau &\geq2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2} - 2G\sqrt{\log\frac{\pi^2}{6\delta}} \\ &\quad+ 2G\sqrt{\left(1+\sum_{\tau=1}^t\Phi_\tau'(Q_{\tau})^2\right)\log\frac{(\pi^2/6)(1 + \log_2(1+\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2))^2}{\delta}}. \end{align}\] Then it follows that with probability at least \(1-\delta\), \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) &\leq \frac{L^2(1+\log t)}{\mu} + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\\ &\leq \frac{L^2(1+\log t)}{\mu} + \log t + 1 + 2G\sqrt{\log\frac{\pi^2}{6\delta}}\\ \end{align}\] where the second inequality follows from [lem:gamma32sum32hp] and \(3/(2e) \leq 1\). ◻
Proof of Lemma [lem:R32sum:stoc324332hp324332strcvx]. We closely follow the proof of [lem:R32sum:stoc324332hp324332cvx], where the only difference is that we use [lem:Regret43Phi:stoc324332hp324332strcvx] instead of [lem:Regret43Phi:stoc324332hp324332cvx]. By Lipschitzness and [lem:Regret43Phi:stoc324332hp324332strcvx], \[\begin{align} \Phi_{t+1}'(Q_{t+1}) &\leq DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 2 + 2G\sqrt{\log\frac{\pi^2}{6\delta}}. \end{align}\] Note that \[\begin{align} \sum_{\tau=1}^t R_\tau \leq \sum_{\tau=1}^t\frac{G}{\sqrt{\tau}} + \sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}. \end{align}\] It is clear that \(\sum_{\tau=1}^t G/\sqrt{\tau} \leq 2G\sqrt{t}\). Moreover, by applying the same argument in the proof of [lem:R32sum:stoc324332hp324332cvx], \[\begin{align} &\sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\\ &\leq\left(4DL + 32G\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2))^2}{\delta}}\right)\sqrt{t}\sqrt{\log\frac{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}{\Phi_1'(Q_1)^2} +1}. \end{align}\] Note that since \(\Phi_{t+1}'(Q_{t+1}) = {O}\left(t + \sqrt{\log(1/\delta)}\right)\), we have \(\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2 = {O}\left(t^3 + t\log(1/\delta)\right)\). Therefore, we have \[\begin{align} \sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)} = {O}\left(\sqrt{t}\log (t/\delta)\right). \end{align}\] Consequently, we have \(\sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t}\log(t/\delta)\right)\). ◻
11 Analysis under Adversarial Constraints↩︎
11.1 Convex Losses↩︎
Suppose that we run 2 with \(\gamma_t,\Psi\) as given by 4 . Then, for all \(t\geq 1\), we have \[\Phi_{t+1}(Q_{t+1}) - \Phi_t(Q_{t}) \leq \Phi_t'(Q_{t})\left( \tilde{g}_t(\mathbf{x}_t) - \frac{R_t}{2}\right) + \frac{\gamma_t - \gamma_{t+1}}{e\gamma_{t+1}}.\]
Proof. Note that \(|\tilde{g}_t(\mathbf{x}_t)| \leq |g_t(\mathbf{x}_t)| \leq G\). Therefore, by applying the same argument as in the proof of [lem:drift:stoc324332exp324332cvx], we conclude the proof. ◻
Consider the setting of 5. Suppose that we run 2 with \(\eta_t\) given by 6 . Then, for all \(t\geq 1\), we have \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})\tilde{g}_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\tilde{g}_\tau(\mathbf{x}^\star) + 2DL \sqrt{t}+ 2DL \sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + D. \end{align}\]
Proof. Recall that \(\nabla \tilde{g}_t(\mathbf{x}_t) = \nabla g_t(\mathbf{x}_t)\) if \(g_t(\mathbf{x}_t)>0\), and \(\boldsymbol{0}\) otherwise. It follows that \(\|\nabla \tilde{g}_t(\mathbf{x}_t)\|\leq L\). Moreover, we have that \(\nabla f_t(\mathbf{x}_t) + \Phi_t'(Q_t)\nabla \tilde{g}_t(\mathbf{x}_t)\) is a subgradient of \(f_t + \Phi_t'(Q_t)\tilde{g}_t\). Then, by applying the same argument as in [lem:adagrad], we conclude the proof. ◻
Consider the setting of 5. Suppose that we run 2 with \(\gamma_t,\Psi\) given by 4 , and \(\eta_t\) given by 6 . Then, for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))+ \Phi_{t+1}(Q_{t+1}) \leq 2DL\sqrt{t} + \log t + 1 + D. \end{align}\]
Proof. We closely follow the proof of [lem:Regret43Phi:stoc324332exp324332cvx]. By [lem:adagrad32adv], \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})\tilde{g}_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\tilde{g}_\tau(\mathbf{x}^\star) + 2DL \sqrt{t}+ 2DL \sqrt{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)^2} + D. \end{align}\] By [lem:drift:adv324332exp324332cvx], \[\begin{align} \Phi_{t+1}(Q_{t+1}) - \Phi_1(Q_1) \leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\left(\tilde{g}_\tau(\mathbf{x}_\tau) - \frac{R_\tau}{2}\right) + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}}. \end{align}\] By [lem:gamma32sum32exp], \[\begin{align} \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} \leq \frac{1+\log t}{2} \end{align}\] Combining these results yields \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) &\leq \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)\tilde{g}_\tau(\mathbf{x}^\star)+2DL\sqrt{t} + \log t + 1 + D. \end{align}\] Since we have \(g_t(\mathbf{x}^\star) \leq 0\) for all \(t\geq 1\) in the adversarial constraint setting, we know that \(\sum_{\tau=1}^t \Phi_\tau'(Q_\tau) \tilde{g}_\tau(\mathbf{x}^\star) = 0\). This concludes the proof. ◻
Consider the setting of 5. Suppose that we run 2 with \(\gamma_t,\Psi\) given by 4 , and \(\eta_t\) given by 6 . Then, for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t \log t}\right). \end{align}\]
Proof. We closely follow the proof of [lem:R32sum:stoc324332exp324332cvx], where the only difference is that we use [lem:Regret43Phi:adv324332exp324332cvx] instead of [lem:Regret43Phi:stoc324332exp324332cvx]. By Lipschitzness and [lem:Regret43Phi:adv324332exp324332cvx], \[\begin{align} \Phi_{t+1}'(Q_{t+1}) &\leq 3DLt + \log t + 2 + D. \end{align}\] Note that \[\begin{align} \sum_{\tau=1}^t R_\tau \leq \sum_{\tau=1}^t\frac{G}{\sqrt{\tau}} + \sum_{\tau=1}^t \frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}. \end{align}\] It is clear that \(\sum_{\tau=1}^t G/\sqrt{\tau} \leq 2G\sqrt{t}\). Moreover, it follows that \[\begin{align} &\sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)}{\Phi_1'(Q_1)} +1}\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{t(3DLt + \log t + 1 + D)}{\Phi_1'(Q_1)} +1}. \end{align}\] Finally, we have \(\sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t \log t}\right).\) ◻
11.1.1 Proof of Theorem 5↩︎
Proof. Under 2, we observe that \(\mathrm{Violation}_+(t) = \sum_{\tau=1}^t [g_\tau(\mathbf{x}_\tau)]_+ = Q_{t+1} + \sum_{\tau=1}^t R_\tau\). By [lem:Regret43Phi:adv324332exp324332cvx], \[\begin{align} \mathrm{Regret}(t) = \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) \leq 2DL\sqrt{t} + \log t + 2 + D. \end{align}\] By applying the same argument in the proof of 1, we have \[\begin{align} Q_{t+1} &\leq \frac{1}{\gamma_{t+1}}\log\left(3DLt + \log t + 1 + D\right)\\ &\leq \left(12G\sqrt{t+1} + 24DL + 1\right)\log\left(3DLt + \log t + 1 + D\right) \end{align}\] which can be written as \(Q_{t+1} = {O}\left(\sqrt{t}\log t\right)\). Moreover, by [lem:R32sum:adv324332exp324332cvx], we have \(\sum_{\tau=1}^t R_\tau ={O}(\sqrt{t\log t})\). Since \(\mathrm{Violation}_+(t) = Q_{t+1} + \sum_{\tau=1}^t R_\tau\), we have \[\mathrm{Violation}_+(t) = {O}\left(\sqrt{t}\log t\right).\] ◻
11.2 Strongly Convex Losses↩︎
Consider the setting of 6. Suppose that we run 2 with \(\eta_\tau\) given by 7 . Then, for all \(t\geq 1\), we have \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})\tilde{g}_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\tilde{g}_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\]
Proof. Recall that \(\nabla \tilde{g}_t(\mathbf{x}_t) = \nabla g_t(\mathbf{x}_t)\) if \(g_t(\mathbf{x}_t)>0\), and \(\boldsymbol{0}\) otherwise. It follows that \(\|\nabla \tilde{g}_t(\mathbf{x}_t)\|\leq L\). Moreover, we have that \(\nabla f_t(\mathbf{x}_t) + \Phi_t'(Q_t)\nabla \tilde{g}_t(\mathbf{x}_t)\) is a subgradient of \(f_t + \Phi_t'(Q_t)\tilde{g}_t\). Then, by applying the same argument as in [lem:strcvx32regret], we conclude the proof. ◻
Consider the setting of 6. Suppose that we run 2 with \(\gamma_t,\Psi\) as given by 4 , and \(\eta_t\) as given by 7 . Then, for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star))+ \Phi_{t+1}(Q_{t+1}) \leq \frac{L^2(1+\log t)}{\mu} + \log t + 1. \end{align}\]
Proof. We closely follow the proof of [lem:Regret43Phi:stoc324332exp324332cvx]. By [lem:strcvx32regret32adv], \[\begin{align} &\sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) + \sum_{\tau=1}^t \Phi_\tau'(Q_{\tau})\tilde{g}_\tau(\mathbf{x}_\tau) \\ &\leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\tilde{g}_\tau(\mathbf{x}^\star) + \frac{L^2(1+\log t)}{\mu} + 2DL\sqrt{\sum_{\tau=1}^t \Phi_\tau'(Q_\tau)^2}. \end{align}\] By [lem:drift:adv324332exp324332cvx], \[\begin{align} \Phi_{t+1}(Q_{t+1}) - \Phi_1(Q_1) \leq \sum_{\tau=1}^t \Phi_\tau'(Q_\tau)\left(\tilde{g}_\tau(\mathbf{x}_\tau) - \frac{R_\tau}{2}\right) + \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}}. \end{align}\] By [lem:gamma32sum32exp], \[\begin{align} \sum_{\tau=1}^t\frac{\gamma_\tau - \gamma_{\tau+1}}{e\gamma_{\tau+1}} \leq \frac{1+\log t}{2} \end{align}\] Combining these results yields \[\begin{align} \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau)-f_\tau(\mathbf{x}^\star)) + \Phi_{t+1}(Q_{t+1}) &\leq \sum_{\tau=1}^t\Phi_\tau'(Q_\tau)\tilde{g}_\tau(\mathbf{x}^\star)+\frac{L^2(1+\log t)}{\mu} + \log t + 1. \end{align}\] Since we have \(g_t(\mathbf{x}^\star) \leq 0\) for all \(t\geq 1\) in the adversarial constraint setting, we know that \(\sum_{\tau=1}^t \Phi_\tau'(Q_\tau) \tilde{g}_\tau(\mathbf{x}^\star) = 0\). This concludes the proof. ◻
Consider the setting of 6. Suppose that we run 2 with \(\gamma_t,\Psi\) as given by 4 , and \(\eta_t\) as given by 7 . Then, for all \(t\geq 1\), we have \[\begin{align} \sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t \log t}\right). \end{align}\]
Proof. We closely follow the proof of [lem:R32sum:stoc324332exp324332strcvx], where the only difference is that we use [lem:Regret43Phi:adv324332exp324332strcvx] instead of [lem:Regret43Phi:stoc324332exp324332cvx]. By Lipschitzness and [lem:Regret43Phi:adv324332exp324332strcvx], \[\begin{align} \Phi_{t+1}'(Q_{t+1}) &\leq DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 2. \end{align}\] Note that \[\begin{align} \sum_{\tau=1}^t R_\tau \leq \sum_{\tau=1}^t\frac{G}{\sqrt{\tau}} + \sum_{\tau=1}^t \frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}. \end{align}\] It is clear that \(\sum_{\tau=1}^t G/\sqrt{\tau} \leq 2G\sqrt{t}\). Moreover, it follows that \[\begin{align} &\sum_{\tau=1}^t\frac{\Psi\left(\sum_{s=1}^\tau\Phi_s'(Q_s)^2\right)-\Psi\left(\sum_{s=1}^{\tau-1}\Phi_s'(Q_s)^2\right)}{\Phi_\tau'(Q_\tau)}\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{\sum_{\tau=1}^t\Phi_\tau'(Q_\tau)}{\Phi_1'(Q_1)} +1}\\ &\leq 4DL\sqrt{t}\sqrt{2\log\frac{t(DLt + L^2(1+\log t)/\mu +\log t + 1)}{\Phi_1'(Q_1)} +1}. \end{align}\] Finally, we have \(\sum_{\tau=1}^t R_\tau = {O}\left(\sqrt{t \log t}\right).\) ◻
11.2.1 Proof of Theorem 6↩︎
Proof. Under 2, we observe that \(\mathrm{Violation}_+(t) = \sum_{\tau=1}^t [g_\tau(\mathbf{x}_\tau)]_+ = Q_{t+1} + \sum_{\tau=1}^t R_\tau\). By [lem:Regret43Phi:adv324332exp324332strcvx], \[\begin{align} \mathrm{Regret}(t) = \sum_{\tau=1}^t (f_\tau(\mathbf{x}_\tau) - f_\tau(\mathbf{x}^\star)) \leq \frac{L^2(1+\log t)}{\mu} + \log t + 2. \end{align}\] By applying the same argument in the proof of 3, we have \[\begin{align} Q_{t+1} &\leq \frac{1}{\gamma_{t+1}}\log\left(DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 1\right)\\ &\leq \left(12G\sqrt{t+1} + 24DL + 1\right)\log\left(DLt + \frac{L^2(1+\log t)}{\mu} + \log t + 1\right) \end{align}\] which can be written as \(Q_{t+1} = {O}\left(\sqrt{t}\log t\right)\). Moreover, by [lem:R32sum:adv324332exp324332strcvx], we have \(\sum_{\tau=1}^t R_\tau ={O}(\sqrt{t\log t})\). Since \(\mathrm{Violation}(t) = Q_{t+1} + \sum_{\tau=1}^t R_\tau\), we have \[\mathrm{Violation}_+(t) = {O}\left(\sqrt{t}\log t\right).\] ◻
12 Auxiliary Lemmas↩︎
For \(\gamma_1, \gamma_2 >0\), define \(\Phi_1, \Phi_2:\mathbb{R}\to\mathbb{R}\) as \(\Phi_1(x) =e^{\gamma_1x}-1\) and \(\Phi_2(x) = e^{\gamma_2x}-1\) for each \(x\in \mathbb{R}\). Suppose that \(\gamma_2 \leq \gamma_1\). Then we have \(\Phi_2(x) - \Phi_1(x) \leq (\gamma_1 - \gamma_2)/(\gamma_2e)\) for all \(x\in \mathbb{R}.\)
Proof. Note that \[\begin{align} \Phi_2(x) - \Phi_1(x) &= e^{\gamma_2x} - e^{\gamma_1x} \\ &= e^{\gamma_2x}(1 - e^{(\gamma_1-\gamma_2)x}) \\ &\leq e^{\gamma_2x} (\gamma_2 -\gamma_1)x \\ &=e^{\gamma_2x}(-\gamma_2x) \cdot \frac{\gamma_1 - \gamma_2}{\gamma_2} \\ &\leq \frac{\gamma_1 - \gamma_2}{e\gamma_2} \end{align}\] where the first inequality follows from \(1-e^{-y} \leq y\) for all \(y \in \mathbb{R}\), and the second inequality follows from the fact that \(e^{-y}y \leq 1/e\) for all \(y \in \mathbb{R}\) and that \((\gamma_1 - \gamma_2)/\gamma_2 \geq 0\). ◻
Let \(\delta\in (0,1)\). Define \(\psi:\mathbb{R}_+ \to \mathbb{R}\) as \(\psi(x) = (1+x)\log\frac{(\pi^2/6)(1 + \log_2 (1+x))^2}{\delta}\) for each \(x \in \mathbb{R}_+\). Suppose that \(0 \leq x_1 < x_2\). Then we have \[\begin{align} \sqrt{\psi(x_2)} - \sqrt{\psi(x_1)} \leq 8\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x_2))^2}{\delta}} \left(\sqrt{1+x_2} - \sqrt{1+x_1}\right). \end{align}\] Moreover, we have \[\begin{align} \frac{\sqrt{\psi(x_2)} - \sqrt{\psi(x_1)}}{\sqrt{x_2 - x_1}} \leq 8\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x_2))^2}{\delta}}. \end{align}\]
Proof. For \(x \in [x_1,x_2]\), we observe that \[\begin{align} &\frac{d}{dx}\sqrt{\psi(x)} \\ &= \frac{1}{2\sqrt{x+1}}\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x))^2}{\delta}} \\ &\quad+ \frac{1}{\log2\cdot\sqrt{1+x} (1+\log_2(1+x))\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x))^2}{\delta}}} \\ &\leq \frac{1}{2\sqrt{x+1}}\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x))^2}{\delta}} + \frac{1}{\log2\cdot\sqrt{\log(\pi^2/6)} \sqrt{x+1}}\\ &\leq \frac{4}{\sqrt{x+1}}\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x))^2}{\delta}}\\ &\leq \frac{4}{\sqrt{x+1}}\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x_2))^2}{\delta}}. \end{align}\] Then it follows that \[\begin{align} \sqrt{\psi(x_2)} - \sqrt{\psi(x_1)} &\leq \int_{x_1}^{x_2}\frac{d}{dx}\sqrt{\psi(x)}dx\\ &\leq 8\sqrt{\log\frac{(\pi^2/6)(1+\log_2(1+x_2))^2}{\delta}} \left(\sqrt{1+x_2} - \sqrt{1+x_1}\right). \end{align}\] Note that \(\sqrt{1+x_2} - \sqrt{1+x_1} \leq \sqrt{x_2 - x_1}\). This leads to the second statement. ◻
Let \(\{z_t\}_{t\geq 0}\) be an increasing sequence, and let \(z_0 > 0\). Then, we have \(\sum_{\tau=1}^t(z_\tau - z_{\tau-1})/z_\tau \leq \log\left(z_t/z_0\right)\) for all \(t\geq 1\).
Proof. Note that \(\sum_{\tau=1}^t (z_\tau - z_{\tau-1})/z_\tau \leq \int_{z_0}^{z_t} (1/x) dx = \log\left(z_t/z_0\right)\). ◻
The following lemma states the maximal inequality for supermartingales (Theorem 3.9 in [39]), which can be viewed as a Markov-type inequality for the maximum of a supermartingale. Let \(\{X_t\}_{t\geq 0}\) be a supermartingale with \(X_t \geq 0\) almost surely for all \(t \geq 0\). Then for every \(\epsilon > 0\), \[\mathbb{P}\left(\sup_{t \geq 0} X_t \geq \epsilon\right) \leq \frac{\mathbb{E}[X_0]}{\epsilon}.\]
The following lemma is a conditional variant of Hoeffding’s lemma (Lemma B.7 in [40]). Let \(X\) be a random variable, and let \({\mathcal{F}}\) be a \(\sigma\)-algebra. Suppose that \(\mathbb{E}[X|{\mathcal{F}}] \leq 0\) and \(|X| \leq Y\) almost surely, where \(Y\) is a positive \({\mathcal{F}}\)-measurable random variable. Then, for every \(\lambda > 0\), almost surely, \[\mathbb{E}[e^{\lambda X}|{\mathcal{F}}] \leq e^{\frac{\lambda^2 Y^2}{2}}.\]
Proof. We closely follow the proof of Lemma B.7 in [40]. Fix \(\lambda >0\). From the proof of Lemma B.7 in [40], for any \(y >0\) and \(x \in [-y, y]\) \[\begin{align} e^{\lambda x}\leq \frac{\left ( y-x \right )e^{-\lambda y}+(x+y)e^{\lambda y}}{2y}. \end{align}\] Since we have \(|X|\leq Y\) almost surely and \(Y\) is \({\mathcal{F}}\)-measurable, by letting \(x \leftarrow X,\;y \leftarrow Y\) and taking \(\mathbb{E}[\cdot|{\mathcal{F}}]\) on both sides, we have \[\begin{align} \mathbb{E}[e^{\lambda X}|\mathcal{F}]\leq \frac{\left ( Y-\mathbb{E}\left[X|{\mathcal{F}}\right] \right )e^{-\lambda Y}+(\mathbb{E}[X|{\mathcal{F}}]+Y)e^{\lambda Y}}{2Y} \leq \frac{e^{-\lambda Y}+e^{\lambda Y}}{2} \end{align}\] where the second inequality follows from that \(\mathbb{E}[X|{\mathcal{F}}] \leq 0\) and \(Y > 0\) imply \(\mathbb{E}[X|{\mathcal{F}}](e^{\lambda Y}-e^{-\lambda Y})/(2Y) \leq 0\). Again, from the proof of Lemma B.7 in [40], we know that \((e^{-x}+e^{x})/2 \leq e^{x^2/2}\) for all \(x\in \mathbb{R}\). This completes the proof. ◻
The following lemma states standard properties of strongly convex functions. Let \(f:\mathbb{R}^d\to (-\infty, \infty]\) be a proper convex function. Suppose that \(f\) is \(\mu\)-strongly convex for some \(\mu > 0\). We have for all \(\mathbf{x}\in \mathrm{ri\,dom}(f), \mathbf{y}\in \mathrm{dom}(f)\), \(\nabla f(\mathbf{x}) \in \partial f(\mathbf{x})\), \[f(\mathbf{y}) \geq f(\mathbf{x})+ \nabla f(\mathbf{x})^\top (\mathbf{y}-\mathbf{x}) + \frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|_2^2.\] Moreover, let \(g:\mathbb{R}^d\to (-\infty, \infty]\) be a proper convex function. Then, \(f+g\) is \(\mu\)-strongly convex.
Proof. The first statement follows from Theorem 5.24 in [41] and the fact that a proper convex function \(f\) is subdifferentiable in \(\mathrm{ri\,dom}(f)\) (Theorem 23.4 in [42]). The second statement follows from Lemma 5.20 in [41]. ◻
References↩︎
Notation \(\widetilde{{O}}(\cdot)\) is used to hide polylogarithmic factors, and the precise bound of [9] on constraint violation is \({O}(\sqrt{T}\log T)\).↩︎
By nearly optimal guarantees, we mean regret and violation bounds of order \(\widetilde{{O}}(\sqrt{T})\).↩︎
Recently, this line of work has been extended to various settings [27], [29], [32], [35], [36]. In contrast, our focus is to demonstrate that the proposed algorithm applies to both stochastic and adversarial constraint settings. We leave extensions of our algorithm to these broader settings for future work.↩︎