Optimal Algorithms for Online Convex Optimization with Adversarial Constraints

Summary

In this work, the authors study online convex optimization with adversarial and time-varying constraints, and aim to bound both the regret and the cumulative constraint violation (CCV). Compared with previous studies, the main contributions of this work can be summarized as: 1) a new algorithm with $O(\sqrt{T})$ regret and $O(\sqrt{T}\log T)$ CCV for convex functions; 2) a lower bound of $O(\sqrt{T})$ for the regret and CCV with convex functions; 3) a new algorithm with $O(\log T)$ regret and $O(\sqrt{T\\log T})$ CCV for strongly convex functions (or $O(\log T)$ CCV for strongly convex functions with *non-negative* regret); 4) an extension to the online constraint satisfaction problem.

Strengths

Compared with previous studies, this paper has the following strengths. 1) For convex functions, an improved algorithm is proposed to achieve the $O(\sqrt{T}\log T)$ regret and CCV bounds. By contrast, previous studies can only achieve the $O(T^{3/4})$ CCV bound when keeping the $O(\sqrt{T})$ regret bound. 2) A matching lower bound of $O(\sqrt{T})$ is established for the regret and CCV when functions are convex, which reveals the optimality of the proposed algorithm. 3) For strongly convex functions, this paper proposed an algorithm with $O(\log T)$ regret and $O(\sqrt{T\\log T})$ CCV. Although previous studies have achieved these regret and CCV bounds, they need to utilize Conv-OPT per round. By contrast, the proposed algorithm only needs to perform one projection per round. Moreover, if further assuming that the regret is *non-negative*, the CCV can be further reduced to $O(\log T)$.

Weaknesses

Although this paper provides some new results for online convex optimization with adversarial and time-varying constraints, I have some concerns. 1) The lower bound for convex functions only holds for the case with $d=T$ or $d>T$. However, for online problems, it may be common to consider a very large $T\gg d$, which implies that the optimality of the proposed algorithm for convex functions may only hold in limited cases. 2) Different from the case with convex functions, the authors do not provide a lower bound for strongly convex functions. So, it is not clear whether the $O(\log T)$ regret and $O(\sqrt{T\\log T})$ CCV can still be improved. 3) It seems to be trivial to derive the $O(\log T)$ regret and $O(\log T)$ CCV for strongly convex functions under the *non-negative* regret assumption. I cannot find any challenge in the analysis, and the existing algorithms may also enjoy the same result. 4) Although it may be valuable to develop an extension to the online constraint satisfaction problem, the derived CCV bounds depend on some problem-dependent variables, and thus could be even linear in $T$.

Questions

Besides the concerns discussed above, I also have the following two questions. 1) Is it possible to derive the $O(\log T)$ regret and $O(\log T)$ CCV for strongly convex functions without the *non-negative* regret? 2) Can the authors provide more discussions on the CCV bounds established in Theorems 4 and 5?

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

The authors have provided some discussions on the limitations of their work.

Summary

This paper considers online convex optimization with constraint. The authors propose a new surrogate loss function, and by applying traditional online learning algorithms to the surrogate loss, $\mathcal{O}(\sqrt{T})$ regret and $\mathcal{O}(\sqrt{T \log T})$ can be obtained in the online learning setting. The result improves the state-of-the-art in the domain.

Strengths

This paper proposes an interesting construction of surrogate loss function and transforms the regret analysis of constrained online learning into the analysis of a standard online convex optimization problem. The choice of the regularization function $\Phi$ is interesting and novel to me.

Weaknesses

1. Compared with Section 2, the results from Section 3 looks not less interesting and they are not the focus of the paper. I suggest the authors could conduct some demonstrating experiments and reduce the contents in Section 3.

Questions

**Minor issues** 1. Line 17 modelling => modeling 2. Line 198 Please ensure that $x^\star$ and $x^\ast$ are consistent 3. Line 228 0,) => 0),

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Please add a section on limitations.

Summary

The authors study Online Convex Optimization (OCO) under adversarial constraints of the form $g_{t,i}(x) \leq 0$ where $g_{t,i}$ are arbitrary convex and Lipschitz. The authors design a simple algorithm based on Lyapunov optimization which obtains an optimal regret rate and simultaneously optimal constraint violation (CCV) of $\widetilde O(\sqrt{T})$, and prove a matching lower bound. Their algorithm is based on performing projected OGD updates on surrogate loss functions which are a combination of the objective functions and the constraint functions, with coefficients that depend on a predetermined potential function. For strongly convex losses, the authors establish an improved logarithmic regret bound while maintaining the $\widetilde O(\sqrt{T})$ constraint violation.

Strengths

* The authors provide the first provably optimal algorithm in the general COCO setting for convex and Lipschitz loss functions and constraints. * The algorithm is strikingly simple and the its analysis is not too complicated given standard OCO regret bound from the literature. * The paper is nicely written and the authors provide an overview of the analysis which helps understand the technical contributions. * A single algorithmic framework obtains the optimal regret bounds for both convex & Lipschitz and strongly convex settings, with changes made only in choosing the hyperparameters of the algorithm.

Weaknesses

* The authors do not formally define the interaction protocol in the online setting studied in this paper. Specifically, from lines 27-28 is is implied that the adversary chooses the loss function $f_t(\cdot)$ adaptively after seeing $x_t$, which of course cannot be the case if sublinear regret is obtained. It is my understanding that the adversary is actually oblivious (the functions and constraints are fixed in advance) and the functions are only revealed to the algorithm after choosing $x_t$. In any case, the authors should properly define the interaction protocol and the exact notion of the adversary in question. * It is a bit unclear to me what are the novel techniques utilized in this paper compared to previous works on constrained OCO. Since the analysis seems relatively simple, I think the authors should elaborate on the technical challenges faced when proving their main results, and what novel techniques they used. * While the authors claim to only require a call to a projection oracle at every round, there is a subtle point in which they also call a gradient oracle on a combination of the objective function and the constraint function. I am not an expert in the constrained OCO literature, so if this is a standard assumption in this setting I think the authors should mention it or alternatively formally define the type of gradient oracle used.

Questions

Beside the points I raised under "Weaknesses", I would appreciate it if the authors could address the following: * The authors remark that the setting of $k$ constraints is equivalent to the single constraint setting by defining the constraint function as the pointwise max over the constraints. While this is true in the offline setting, there is a subtle point in the online setting where the definitions of CCV are not equivalent. Specifically, for $k$ constraints the CCV is essentially a maximum over sum while for a single constraint the CCV is a sum over maximum which is only larger, and thus it suffices, when proving an upper bound, to consider the single constraint setting. I think the authors should elaborate a bit on this point since this is not trivial at first glance.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Summary

The major part of this paper studies adversarial OCO with unknown, time varying constraints in the soft-enforcement setup, wherein at each round, both a loss $f_t$, and constraints $g_{t,i}$ are revealed. The performance metrics are the usual regret $\mathrm{Regret}_T = \sum_t f_t(x_t) - f_t(x^*),$ and the cumulative constraint violation $\mathrm{CCV}_T := \max\_i \sum\_t (g\_{t,i}(x\_t))^+,$ where $(\cdot)^+ = \max(0,\cdot),$ and $x^*$ is the best-in-hindsight competitor that satisfies _all_ of the constraints, i.e., $\forall i, t: g_{i,t}(x^*) \le 0$. The paper shows that under the standard smoothness assumption, a simple modification of OGD, which can be seen as OGD on a loss that regularises constraint violation through a Lyapunov function, ensures that both $\mathrm{Regret}_T$ and $\mathrm{CCV}_T$ are $\tilde{O}(\sqrt{T})$, without any further assumptions, as were made by prior work when deriving such a result. Further, under strong convexity, the regret bounds improve to $\log T$ with the same CCV bound. Surprisingly, under strong convexity, the CCV bounds further improve to $\log T$ if $\mathrm{Regret}_T > 0$. The authors complement this result with a lower bound that simultaneously asserts that these metrics must both be larger than $\sqrt{T}$, at least if $T \le d,$ the dimension of the space. The remainder of the paper is devoted to defining and studying the 'Online Constraint Satisfaction' (OCS) problem, which relaxes the assumption that a point satisfying all constraints exists, and demands methods for selecting $x_t$ such that $\sum g_t(x_t)$ is small over all intervals in $[1:T]$. Under natural relaxations of the existence of an $x$ satisfying all constraints (either by assuming that some $x$ satisfies all "somewhat aggregated" constraints, or quantitatively demanding that some $x$ has limited violation across all subintervals), the authors again show that a modified version of OGD, similar in spirit to their earlier method, ensures that the resulting sequence $x_t$ has low violation in the aforementioned strong sense.

Strengths

OCO with unknown constraints has attracted significant interest in recent years, amidst a general rise of interest in multiobjective online learning. I think that the paper makes a valuable contribution to this subfield by removing technical assumptions present in prior work, and by presenting an elegant algorithm with a slick and surprisingly simple analysis for the same. I further find the OCS problem interesting, and the results towards this quite powerful and elegant. I think that this paper will certainly be of interest to the online learning community at neurips.

Weaknesses

My only real grouse with the paper is the lower bound of Theorem 3, which I find to be overstated. The theorem is presented as "under assumptions 1, 2, and 3, the regret and CCV are $\Omega(\sqrt{T}),$ but the proof only defines a single instance where this occurs, and this further requires the strange assumption that the dimension of the domain $d$, exceeds $T$. I would much prefer that this is made explicit, e.g., to say something like _for any $d, T$ and algorithm, there exists an instance with a single time-varying constraint such that the method suffers $\min(\mathrm{regret}\_T, \mathrm{CCV}\_T) = \Omega(\sqrt{\min(T,d)}$._ This still makes the main point of the statement, but is explicit about the strength of the bound.

Questions

A suggestion: Definition 1 mixes the definition of the concept of $P_T$ with a bunch of editorialising, which just makes it hard to see what the object being defined is. I would suggest that the definition simply states that $P_T = \frac1F \min \max \cdots,$ and all of these comments are moved appropriately to either before or after it, but certainly not within the definition itself.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

This is fine

Thank you for your response

Thank you for the response. I do not have additional concerns and maintain my evaluation of the paper.