{"id":"8409f1ff-f97d-4818-b0a9-d359aa130b86","arxiv_id":"2412.08060","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"An optimistic meta-algorithm achieves O(sqrt(E_T(f))) regret and O(sqrt(E_T(g+)) log T) constraint violation for online convex optimization with adversarial constraints, where E_T measures cumulative prediction error.","lead":"This paper proposes an online learning algorithm that handles both loss minimization and adversarial constraints, with regret bounds that shrink when the learner has good predictions of future losses and constraints. It shows the same idea extends to contextual bandits with safety constraints.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Nondifferentiability of g+ is load-bearing: Eq. (39) uses undefined subgradients of max(0,g), and a valid choice can make E_T(g+) = T even when gradient predictions of g are perfect, so Theorem 7's optimistic CCV bound is not established.","rationale":"The reader's weakest assumption is precisely the nondifferentiability of g+ and the lack of subgradient selection; I agree. The concern is load-bearing because the central theorem's proof uses epsilon_t(g+) as if it were a well-defined, small prediction error, but it can be large even under perfect gradient predictions of g. I do not think this makes the algorithmic idea hopeless: a careful treatment with a fixed subgradient rule, predictions of g+ (not just g), and possibly a smooth approximation could repair the proof. However, as written the advertised O(sqrt(E_T(g+))) bound is not established, and the issue propagates to the dynamic and bandit corollaries. The paper also contains secondary gaps (bandit E_T(g+) mismatch, omitted dynamic proof), but the g+/subgradient issue is the single most load-bearing one. Since the reader already conditions the verdict on repairing exactly this point, my stress-test does not change the conditional verdict.","tokens_in":30019,"tokens_out":14639,"duration_ms":145681,"concrete_test":"Run a one-dimensional numerical check of the proof's key inequality (Eq. 39). Set X = [-1,1], f_t = 0, g_t(x) = x - 1, x_t = 0, Q_t = 0, and use the prediction g_hat_t(x) = x + 1. Compute the constraint-part prediction error using the paper's definition epsilon_t(g+) = ||s_t - s_hat_t||^2 with the natural subgradient selection s_t in partial max(0,g_t)(0) and s_hat_t = nabla max(0,g_hat_t)(0); both are uniquely 0 and 1 respectively, so epsilon_t(g+) = 1 while epsilon_t(g) = 0. Then check whether Theorem 7's proof can be rerun with this example: the RHS of Eq. (39) is 2 and the LHS is 1, so the inequality itself holds, but the subsequent identification of E_T(g+) with prediction quality of the original constraint functions fails; summing over T copies gives E_T(g+) = T.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix A derives epsilon_t(L) <= 2 epsilon_t(f) + 2 Phi'(Q_t)^2 epsilon_t(g+) (Eq. 39) and Theorem 7 then states an O(sqrt(E_T(g+)) log T) CCV bound. The step requires treating nabla g+_t(x_t) and nabla g+_t(x_t) as well-defined prediction errors. But g+_t = max(0,g_t) is nondifferentiable on {x : g_t(x) = 0}; the paper gives no subgradient selection for the algorithm, for the predictor, or for the definition of epsilon_t(g+). This is not a footnote-level gap. At a kink the subdifferential is an interval: for g_t(x) = x at x = 0, partial g+ = [0,1], so the algorithm may use s_t = 0 while the predictor uses s_hat_t = 1, giving epsilon_t(g+) = 1 even though epsilon_t(g) = 0. The same happens away from kinks when predictions have correct gradients but wrong signs: with g_t(x) = x - 1 and g_hat_t(x) = x + 1 at x_t = 0, nabla g_t = nabla g_hat_t = 1 so epsilon_t(g) = 0, while the g+-subgradient is 0 and the predicted subgradient is 1. Repeating this for T rounds gives E_T(g+) = T with E_T(g) = 0, making the advertised optimistic bound meaningless. If epsilon_t(g+) is instead defined relative to an explicitly chosen selection rule, that rule is absent from Assumptions 1-6 and from Algorithm 1, and the bound is not expressed in terms of the prediction errors claimed in the abstract. Corollaries 11, 16, 18, and 23 inherit this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1941,"tokens_out":2083,"duration_ms":89579,"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":[{"comment":"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.","section":"Appendix A, Eq. (39)"},{"comment":"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":"Theorem 7, item d"},{"comment":"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.","section":"Section 8, after Eq. (35)"}],"minor_comments":[{"comment":"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.","section":"Lemma 5, proof"},{"comment":"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.","section":"Theorem 10, Eq. (17) and Appendix C"},{"comment":"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.","section":"Table 1"},{"comment":"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.","section":"Assumption 6"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and relevant problem, and the high-level approach is promising. However, the central theorem is not yet proven because of the undefined subgradient of g^+ in Appendix A, and the bandit section has a mismatch between the prediction error used in the guarantee and the prediction error that actually enters the surrogate. Both issues are technical and appear fixable within the scope of a major revision: the first by smoothing or by fixing and proving a subgradient calculus for g^+, and the second by restating the bandit bounds in terms of the shifted positive constraint. I would not reject the paper on the basis of these gaps, but I would not accept it in the current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jordan, quick take on arXiv:2412.08060 (Lekeufack & Jordan). The paper has a good idea: wrap an optimistic OCO algorithm in the Sinha-Vaze Lyapunov/Lagrangian queue, so regret and constraint violation scale with prediction error E_T(f) and E_T(g+) instead of T. As far as I know, that combination for adversarial time-varying constraints is new, and the static regret analysis (modulo the issue below) is clean. The related-work table is genuinely useful, and the paper is honest about several caveats, including the nonsmoothness problem in its own conclusion.\n\nThe soft spot is load-bearing. The proof of Theorem 7 (Appendix A) defines epsilon_t(g+) = ||grad g+_t(x_t) - grad ghat_t(x_t)||^2, but g+ = max(0,g) is nondifferentiable on the set {g=0}. The paper never specifies a subgradient selection or a smoothing, for either the algorithm or the predictor. This isn't a footnote gap: at a kink the subdifferential is an interval, and the algorithm and predictor can pick different elements with E_T(g+) = T even when gradient predictions of g are perfect. So the advertised optimistic bound is not defined, let alone proven, and Corollaries 11, 16, 18, and 23 inherit the gap. The stress-test note is right, and it doesn't go away on reading.\n\nOther issues are smaller but real: the dynamic regret proof is omitted ('We omit the proof' for Theorem 14), and the bandit section defines E_T(g+) as sum ||c_t - chat_t||^2, while the error that actually enters the surrogate loss is the infinity-norm error on the clipped positive-part vector. The doubling trick for bandits is also left incomplete, since epsilon_t(g) is not observed. The paper acknowledges some of this, which I credit.\n\nConceptually the paper isn't sunk. I think the core argument can be repaired by either smoothing g+ or explicitly choosing and tracking subgradients, and then restating the bounds in terms of the prediction error of those selections. But as written, the main theorem is not established. This deserves a serious referee, not a desk reject; a careful referee could push the authors to fix the nonsmoothness and provide the missing dynamic proof. I wouldn't cite it yet.","headline":"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.","tokens_in":30939,"tokens_out":2551,"would_cite":false,"duration_ms":24951,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An optimistic projection algorithm converts accurate loss and constraint predictions into O(√E_T) regret and violation bounds, matching O(√T) when forecasts fail.","keywords":["online convex optimization","adversarial constraints","optimistic algorithms","prediction errors","cumulative constraint violation","regret bounds","contextual bandits","online mirror descent"],"falsifier":"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.","tokens_in":29763,"feed_emoji":"📉","tokens_out":16731,"duration_ms":144284,"temperature":0.7,"pith_summary":"The paper studies online convex optimization with adversarial constraints: at each round a learner chooses a point, then sees both a convex loss and a convex constraint, and is judged by static regret against any feasible comparator and by cumulative constraint violation. The paper's central claim is that, when the learner is given predictions of the next loss and constraint functions, a projection-based meta-algorithm achieves regret $O(\\sqrt{E_T(f)})$ and cumulative violation $O(\\sqrt{E_T(g^+)} \\log T)$, where $E_T(f)$ and $E_T(g^+)$ are cumulative squared prediction errors of the loss and constraint gradients. These rates match the best known worst-case $O(\\sqrt{T})$ bounds when predictions are uninformative, and improve as predictions get better. The same machinery yields dynamic regret guarantees and an application to adversarial contextual bandits with sequential risk constraints.","feed_headline":"Forecasts shrink regret and violations in constrained online learning","feed_subtitle":"Good loss and constraint forecasts yield O(√E) regret and violations; bad forecasts fall back to O(√T).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The best prior algorithm for adversarial constraints; the meta-algorithm adapts its surrogate-loss/queue design and matches its O(√T) bounds in the worst case.","marker":"(Sinha and Vaze, 2024)"},{"why":"Supplies the optimistic online mirror descent/AdaGrad subroutine (Algorithm 2) whose regret bound in terms of prediction error is used as Assumption 6.","marker":"(Rakhlin and Sridharan, 2013b)"},{"why":"Establishes optimistic OMD with gradual variations; the paper extends its techniques to functional predictions and Lipschitz coefficients of the predicted functions.","marker":"(Chiang et al., 2012)"},{"why":"Gives the EXP4.OVAR contextual bandit algorithm with prediction-dependent regret; the paper's bandit application modifies its learning rate to handle time-varying loss bounds.","marker":"(Wei et al., 2020)"},{"why":"Introduces adversarial contextual bandits with sequential risk constraints, the baseline whose O(√T) regret / O(T^{3/4}) violation the bandit result improves.","marker":"(Sun et al., 2017)"},{"why":"Provides the dynamic-regret bound for OMD with comparator path length, used for the paper's dynamic regret theorem and doubling trick.","marker":"(Jadbabaie et al., 2015)"}],"fun_headline_variants":["Forecasts cut regret and violations in adversarial-constraint OCO","Optimistic algorithm: prediction errors dictate regret bounds in OCO","Better forecasts yield smaller regret and violations in constrained OCO","Prediction-aware optimization for adversarial constraints: tighter bounds","Using forecast quality to beat O(√T) regret in constrained OCO"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Forecasts cut regret and violations in adversarial-constraint OCO","Optimistic algorithm: prediction errors dictate regret bounds in OCO","Better forecasts yield smaller regret and violations in constrained OCO","Prediction-aware optimization for adversarial constraints: tighter bounds","Using forecast quality to beat O(√T) regret in constrained OCO"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00158,"raw_usage":{"total_tokens":6345,"prompt_tokens":1031,"completion_tokens":5314,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":5227}},"tokens_in":647,"tokens_out":5314,"duration_ms":40108,"temperature":1.0,"reasoning_tokens":5227,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:17:37.226625+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Online primal-dual mirror descent under stochastic constraints","cited_arxiv_id":null,"evidence_quote":"Gives the EXP4.OVAR contextual bandit algorithm with prediction-dependent regret; the paper's bandit application modifies its learning rate to handle time-varying loss bounds."}],"review_version":1}