REVIEW 3 major objections 4 minor 1 cited by
An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints
T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read An optimistic projection algorithm converts accurate loss and constraint predictions into O(√E_T) regret and violation bounds, matching O(√T) when forecasts fail.
desk verdict Promising meta-algorithm for optimistic COCO, but the main proof uses an undefined subgradient of max(0,g), so the headline bounds are not yet established. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is a surrogate loss $L_t(x) = f_t(x) + \Phi'(Q_t) g^+_t(x)$ built from the true loss, the positive part of the constraint $g^+_t(x)=\max\{0,g_t(x)\}$, and a queue $Q_t = Q_{t-1} + g^+_t(x_t)$ that accumulates past violations, weighted by the derivative of the exponential Lyapunov potential $\Phi(Q)=\exp(\lambda Q)-1$. The proof runs on a regret decomposition (Lemma 5) relating $\Phi(Q_{t+1}) - \Phi(Q_1) + \mathrm{Regret}_t(u)$ to the regret of an underlying optimistic OCO algorithm on the surrogate, plus a penalty controlled by the variation of $\Phi'$. Because the surrogate's instantaneous prediction error decomposes as $\varepsilon_t(L) \le 2\varepsilon_t(f) + 2\Phi'(Q_t)^2 \varepsilon_t(g^+)$, the final regret inherits $E_t(f)$ and the violation bound inherits $E_T(g^+)$; choosing $\lambda = \lambda^\star/2$ cancels the exponential term and yields the logarithmic factor in the constraint-violation bound.
What would settle it
Take the one-dimensional instance $X=[0,2]$, $f_t(x)=(x-1)^2$, $g_t(x)=x-1$, and let the algorithm play $x_t=1$ at some round $t$. Since $g^+$ is nondifferentiable at $1$, define the subgradient used in the surrogate update as $0$ and the subgradient used in the prediction-error computation as $1$, with the predicted gradient equal to $1$. Then $\varepsilon_t(g^+)=0$ while the surrogate gradient differs from its prediction by $\Phi'(Q_t)$; check whether Theorem 7's bound still holds when this subgradient selection is made on every visit to the kink. If the bound fails, the missing subgradient rule is load-bearing.
Extended reading notes
Core claim
The paper claims to give the first optimistic algorithm for constrained online convex optimization with adversarial, time-varying constraints. Its core result (Theorem 7) states that, under standard assumptions and an optimistic OCO subroutine, Algorithm 1 achieves $\mathrm{Regret}_t(u) = O(\sqrt{E_t(f)})$ and $CCV_T = O(\sqrt{E_T(g^+)} \log T)$, where $E_T(f)$ and $E_T(g^+)$ are the cumulative squared prediction errors of the loss and constraint gradient sequences. When predictions are perfect the terms vanish, and when they are useless the bounds reduce to the prior $O(\sqrt{T})$ regret and $O(\sqrt{T}\log T)$ violation of the current best projection-based algorithm. The authors further derive the dynamic regret bound $\tilde{O}(\sqrt{P_T E_T(f)})$ with $\tilde{O}(\sqrt{P_T E_T(g^+)})$ violation and a contextual-bandit variant with $\tilde{O}(\sqrt{E_T(f)} T^{1/3})$ regret and $\tilde{O}(\sqrt{E_T(g^+)} T^{1/3})$ violation.
Load-bearing premise
The proof requires the positive part $g^+ = \max\{0,g\}$ to have gradients wherever the prediction-error quantities are evaluated, but $g^+$ is nondifferentiable at every point where $g(x)=0$; the paper never specifies a subgradient selection or a smooth surrogate, so the decomposition of $\varepsilon_t(g^+)$ is not guaranteed at those points.
Editorial extensions
If this is right
- With accurate loss and constraint predictions, regret and cumulative violations drop below the worst-case $\sqrt{T}$ rates; in the extreme of perfect predictions they shrink toward constant or logarithmic (up to the log term).
- The meta-algorithm needs only one projection onto the feasible set $X$ per round, avoiding per-round convex optimization, so the per-round cost stays that of the underlying optimistic OCO subroutine.
- Dynamic regret is bounded by $O(\sqrt{P_T E_T(f)})$ with $O(\sqrt{P_T E_T(g^+)} \log T)$ violation, so slowly moving comparators do not ruin the prediction-dependent gains.
- For adversarial contextual bandits with sequential risk constraints, the method achieves $\tilde{O}(\sqrt{E_T(f)} T^{1/3})$ regret and $\tilde{O}(\sqrt{E_T(g^+)} T^{1/3})$ violation, improving on prior $\sqrt{T}$ rates when prediction quality is sufficiently high (e.g., $E_T(f)=O(T^{1/3})$ and $E_T(g)=O(T^{5/12})$).
- The worst-case guarantee ($E_T = O(T)$) recovers the $O(\sqrt{T})$ regret and $O(\sqrt{T} \log T)$ violation of the prior best algorithm, so optimism never hurts asymptotically.
Reading between the lines
- A natural test of the framework is to replace $g^+$ by a smooth surrogate (e.g., a softplus or squared penalty) and check whether the $O(\sqrt{E_T(g^+)})$ bound survives; if yes, the kink gap is a proof artifact rather than a substantive obstruction.
- The same Lyapunov-queue decomposition could be imported into other constraint-sensitive settings, such as online allocation with soft capacity constraints, by treating each resource as a queue; the paper's multi-constraint remark already points that way.
- For practitioners, the doubling-trick version suggests an adaptive scheme that re-estimates $\lambda$ from observed constraint violations; the main obstacle is that $\varepsilon_t(g^+)$ is not directly observable, so an estimator based on $|g^+(x_t)|$ or the gradient difference at nearby points would be needed.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online convex optimization with adversarial, time-varying constraints, in a setting where the learner receives predictions of the loss and constraint functions. It proposes a meta-algorithm that wraps an optimistic OCO algorithm with a Lyapunov potential, and claims static regret O(sqrt(E_T(f))) and cumulative constraint violation O(sqrt(E_T(g+)) log T), with analogous dynamic-regret guarantees and an application to adversarial contextual bandits with sequential risk constraints. The main theorems are Theorem 7 and its corollaries, with proofs in the appendices. The high-level decomposition in Lemma 5 and the use of optimistic OMD are standard in spirit, and the claimed worst-case recovery of the Sinha and Vaze (2024) rates is attractive. However, the proof of the central bound is not currently complete: the prediction-error term for the positive part g+ = max(0,g) is used without a well-defined subgradient or smoothing, and the bandit section measures the wrong prediction error relative to the surrogate used by the algorithm.
Significance. If the main claims are established, this would be the first optimistic, prediction-dependent bound for adversarial time-varying constraints in COCO, and the projection-only nature of the algorithm makes the result practically appealing. The paper also supplies explicit algorithms for the experts setting and for contextual bandits with risk constraints, and the comparison with Sinha and Vaze (2024), Qiu et al. (2023), and Anderson et al. (2022) is informative. The detailed appendices and the explicit dependence of the bounds on prediction errors are strengths. That said, the central theorem is currently not established because Eq. (39) of Appendix A relies on a subgradient of the nondifferentiable function g+, and no selection rule or smoothing is given. This is a load-bearing technical gap rather than a presentation issue, and it propagates to the corollaries and to the bandit application.
major comments (3)
- [Appendix A, Eq. (39)] The proof of Theorem 7 uses the bound epsilon_t(L) <= 2 epsilon_t(f) + 2 Phi'(Q_t)^2 epsilon_t(g+), where epsilon_t(g+) is defined by Eq. (3) as ||nabla g_t^+(x_t) - nabla \hat g_t^+(x_t)||^2_*. However, g_t^+ = max(0,g_t) is not differentiable on the set {x : g_t(x)=0}, and the paper never specifies a subgradient selection for the learner, for the predictor, or for the definition of epsilon_t(g+). This is not a cosmetic issue: for g_t(x)=x at x_t=0, the subdifferential of g^+ is [0,1], so the learner could use subgradient s_t=0 while the predictor uses \hat s_t=1, giving epsilon_t(g+)=1 even though epsilon_t(g)=0. Repeating this for T rounds gives E_T(g+)=T with E_T(g)=0, so the advertised O(sqrt(E_T(g+))) CCV bound would be meaningless under an adversarial choice of subgradients. Since Corollaries 11, 16, 18, and Theorem 23 inherit this issue, the paper must either replace g^+ by a smooth surrogate with a controlled approximation error, or fix an explicit subgradient selection rule and prove the decomposition (39) for that rule. Assumption 4 cannot be applied to g^+ as written because the predicted gradient of g^+ is not defined at kinks.
- [Theorem 7, item d] The parameter lambda is set using E_T(g+) and psi_T(g+), which are cumulative quantities at the terminal time T. The paper is aware of this and Appendix B proposes a doubling trick, but Algorithm 4 updates E(N) by adding epsilon_t(g+), and epsilon_t(g+) is exactly the undefined quantity from the previous comment. Moreover, in the bandit setting the observation model does not reveal the full vector c_t - \hat c_t, so the doubling update is not implementable; the text in Section 8 acknowledges this by saying the method requires ET(g) or an upper bound to be known and only suggests a heuristic. As stated, Theorem 7 is therefore a bound conditional on oracle knowledge of the prediction error, not a fully specified online algorithm. The paper should either state the theorems with an adaptive schedule that is implemented in each setting, or explicitly formulate the oracle-knowledge assumption in the theorem statement.
- [Section 8, after Eq. (35)] The theorem statements in Section 8 advertise bounds in terms of ET(f) and ET(g), where ET(g+) is defined as sum_t ||c_t - \hat c_t||_infty^2, but the algorithm's surrogate loss uses the shifted positive part \tilde c_t[a] = (c_t[a]-alpha)_+ and the prediction \hat c_t. The actual prediction error entering Theorem 21 and the proof of Theorem 23 is of the form ||(ell_t + Phi'(Q_t) \tilde c_t) - (\hat ell_t + Phi'(Q_t) \hat c_t)||_infty^2, which contains ||\tilde c_t - \hat c_t||, not ||c_t - \hat c_t||. For actions with c_t[a] <= alpha, \tilde c_t[a]=0 while \hat c_t[a] may be nonzero, so the two quantities need not even be comparable. Theorem 23's bound in terms of ET(g) is therefore not derived, and the claimed improvement over Sun et al. (2017) when 'ET(g) is small' is not justified. The theorem must be stated in terms of the cumulative prediction error for \tilde c_t, with the threshold alpha explicitly entering that error, or the algorithm must predict \tilde c_t directly.
minor comments (4)
- [Lemma 5, proof] In the first displayed derivation after 'By convexity of Phi', the increment of the queue is written as g_t^+(x_tau), but the index should be tau, not t. The same typo appears in the displayed formula for S_t.
- [Theorem 10, Eq. (17) and Appendix C] The learning rate in Eq. (17) is displayed with a second term beta / \hat L^L_t, while the proof in Appendix C uses a rate whose second term is sqrt(beta)/\hat L^L_t up to a factor sqrt(B). The two displays should be aligned.
- [Table 1] The table entry for 'Ours' lists Regret O(sqrt(E_T(f))) and violation O(sqrt(E_T(g+)) log T), but Corollary 11 and Theorem 7 contain additional terms involving psi_T, e.g., \hat L^f and \hat L^{g+}. Please make the table consistent with the corollaries.
- [Assumption 6] Assumption 6 refers to a 'sublinear functional' psi without a precise definition. In particular, the proof of Theorem 7 uses sublinearity of psi with respect to the decomposition L = f + Phi'(Q) g^+, but the domain and subadditivity properties of psi are not stated. Please define psi explicitly or state the exact properties used.
Circularity Check
No significant circularity: the optimistic regret and CCV bounds are derived from the base algorithm's regret on a surrogate loss, not from fitted constants or self-citations.
full rationale
Theorem 7 is a meta-reduction: Assumption 6 is a regret guarantee for the inner OCO algorithm on the Lagrangian surrogate L (Eq. 5), and the proof in Appendix A algebraically converts that guarantee into regret on f and CCV via Lemma 5, the triangle inequality (Eq. 39), and the Lyapunov choice Phi(Q)=exp(lambda Q)-1. The terms E_T(f), E_T(g+), psi_T(f), and psi_T(g+) enter as inputs and conditions of the bound, through lambda and Assumption 6, not as quantities fitted to the outcomes being predicted; the doubling trick in Appendix B is the standard mechanism for removing a priori knowledge of these quantities. Algorithm-specific guarantees (Theorem 10, Theorem 17, Theorem 21) are proved in the appendices or adapted with proofs from external sources such as Rakhlin-Sridharan, Chiang et al., and Wei et al.; there is no load-bearing self-citation chain. The paper itself flags the main caveat: g+ = max(0,g) is nondifferentiable, so epsilon_t(g+) and the required Lipschitz condition on nabla g+ are not established under Assumption 1 (Remark 12: 'nabla g+_t does not satisfy Assumption 4 in the general case'; Conclusion: 'the non-smooth gradient of g+ prevents us from using itself as the prediction'). The bandit section also admits that E_T(g) must be known in advance. These are correctness and implementability caveats, not circular reductions; Eq. (39) is not identical to any input by construction, and no fitted parameter is renamed as a prediction.
Assumptions & free parameters
free parameters (1)
- lambda (Lyapunov rate) =
1/(2C(sqrt(2E_T(g+)) + psi_T(g+)) + 2G)
assumptions (7)
- domain assumption Assumption 1: X0 is closed, convex, bounded; f_t and g_t are convex and differentiable.
- domain assumption Assumption 2: f_t and g_t are bounded by F and G.
- domain assumption Assumption 3: The feasible set X = {x in X0 : g_t(x) <= 0 for all t} is nonempty.
- ad hoc to paper Assumption 4: The predicted gradients nabla f_hat and nabla g_hat are Lipschitz, and this is applied to g+ despite its nondifferentiability.
- domain assumption Assumption 6: The optimistic OCO algorithm A has regret O(sqrt(E_t(L)) + psi_t(L)).
- domain assumption Assumption 13: Lipschitz-like Bregman divergence for dynamic regret.
- domain assumption Corollary 16 requires predictions g_hat_t to be linear.
Cite this review
Pith. "Pith review of An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints." pith.science (2026). https://pith.science/paper/CR3AK2P6
@misc{pith2026241208060,
author = {Pith},
title = {Pith review of: An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/CR3AK2P6}},
note = {Machine review of arXiv:2412.08060}
}
abstract
We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make sequential decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of $ O(\sqrt{T}) $ regret and $ \tilde{O}(\sqrt{T}) $ cumulative constraint violations to $ O(\sqrt{E_T(f)}) $ and $ \tilde{O}(\sqrt{E_T(g^+)}) $, respectively, where $ E_T(f) $ and $E_T(g^+)$ represent the cumulative prediction errors of the loss and constraint functions. In the worst case, where $E_T(f) = O(T) $ and $ E_T(g^+) = O(T) $ (assuming bounded gradients of the loss and constraint functions), our rates match the prior $ O(\sqrt{T}) $ results. However, when the loss and constraint predictions are accurate, our approach yields significantly smaller regret and cumulative constraint violations. Finally, we apply this to the setting of adversarial contextual bandits with sequential risk constraints, obtaining optimistic bounds $O (\sqrt{E_T(f)} T^{1/3})$ regret and $O(\sqrt{E_T(g^+)} T^{1/3})$ constraints violation, yielding better performance than existing results when prediction quality is sufficiently high.
Forward citations
Cited by 1 Pith paper
-
An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
A primal-dual algorithm with optimistic mirror descent is claimed to achieve O~(sqrt K) regret and O~(sqrt K) strong constraint violation in episodic CMDPs with anytime adversarial constraints, without Slater's condition.
Reference graph
Works this paper leans on
-
[1]
Lazy Lagrangians with Predictions for Online Learning
Daron Anderson, George Iosifidis, and Douglas J Leith. Lazy L agrangians with predictions for online learning. arXiv preprint arXiv:2201.02890, 2022
work page Pith review arXiv 2022
-
[2]
Online optimization with gradual variations
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6--1. JMLR Workshop and Conference Proceedings, 2012
2012
-
[3]
Optimistic and Adaptive Lagrangian Hedging
Ryan D'Orazio and Ruitong Huang. Optimistic and adaptive L agrangian hedging. arXiv preprint arXiv:2101.09603, 2021
work page Pith review arXiv 2021
-
[4]
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12 0 (7), 2011
2011
-
[5]
Online convex optimization with hard constraints: towards the best of two worlds and beyond
Hengquan Guo, Xin Liu, Honghao Wei, and Lei Ying. Online convex optimization with hard constraints: towards the best of two worlds and beyond. Advances in Neural Information Processing Systems, 35: 0 36426--36439, 2022
work page 2022
-
[6]
Introduction to online convex optimization, 2023
Elad Hazan. Introduction to online convex optimization, 2023. URL https://arxiv.org/abs/1909.05207
arXiv 2023
-
[7]
Adaptive algorithms for online convex optimization with long-term constraints
Rodolphe Jenatton, Jim Huang, and Cedric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 402--411, New York, New York, USA, ...
work page 2016
-
[8]
Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints
Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints. ACM SIGMETRICS Performance Evaluation Review, 49 0 (3): 0 4--5, 2022
2022
Show all 20 references
-
[9]
Trading regret for efficiency: online convex optimization with long term constraints
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13 0 (1): 0 2503--2528, 2012
2012
-
[10]
Online learning with sample path constraints
Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10 0 (3), 2009
2009
-
[11]
Neely and Hao Yu
Michael J. Neely and Hao Yu. Online convex optimization with time-varying constraints, 2017. URL https://arxiv.org/abs/1702.04783
2017 arXiv
-
[12]
A modern introduction to online learning
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019
1912 arXiv
-
[13]
Gradient-variation bound for online convex optimization with constraints
Shuang Qiu, Xiaohan Wei, and Mladen Kolar. Gradient-variation bound for online convex optimization with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9534--9542, 2023
2023
-
[14]
Online learning with predictable sequences
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993--1019. PMLR, 2013 a
2013
-
[15]
Optimization, learning, and games with predictable sequences, 2013 b
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences, 2013 b . URL https://arxiv.org/abs/1311.1869
2013 arXiv
-
[16]
Optimal algorithms for online convex optimization with adversarial constraints, 2024
Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints, 2024. URL https://arxiv.org/abs/2310.18955
2024 arXiv
-
[17]
Online primal-dual mirror descent under stochastic constraints
Xiaohan Wei, Hao Yu, and Michael J Neely. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4 0 (2): 0 1--36, 2020
2020
-
[18]
Distributed online convex optimization with adversarial constraints: reduced cumulative constraint violation bounds under S later's condition
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou Chai, and Karl H Johansson. Distributed online convex optimization with adversarial constraints: reduced cumulative constraint violation bounds under S later's condition. arXiv preprint arXiv:2306.00149, 2023
2023 arXiv
-
[19]
A low complexity algorithm with o ( T ) regret and o (1) constraint violations for online convex optimization with long term constraints
Hao Yu and Michael J Neely. A low complexity algorithm with o ( T ) regret and o (1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21 0 (1): 0 1--24, 2020
2020
-
[20]
Online convex programming and generalized infinitesimal gradient ascent
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928--936, 2003
2003
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.