{"id":"54e65ba2-8273-4c81-8716-f1cc5eec9b09","arxiv_id":"2412.03983","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"SELO combines Lyapunov-style virtual queues with pessimistic linear-bandit estimates to reach O(√T) regret and zero cumulative constraint violation under unknown linear budgets and partial constraint feedback.","lead":"This paper proposes SELO, an algorithm for online convex optimization with unknown linear budget constraints, where the learner sees only gradients of the cost and bandit feedback on resource use. SELO is designed to achieve square-root-in-time regret with zero cumulative budget violation, and the authors test it on a simulated data-center task scheduling problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's proof bounds f_{t-1}(x_{t-1})-f_{t-1}(x), but the lemma claims f_t(x_t)-f_t(x); with arbitrary losses no convexity step bridges this, so Theorem 1's regret and violation bounds rest on an unproved inequality.","rationale":"The paper's contribution is an O(sqrt T) regret and O(1) violation algorithm for linear budget constraints with bandit constraint feedback. The architecture—virtual queues plus pessimistic ridge estimates—is plausible and related to known Lyapunov/queueing analyses, so I do not claim the result is false. However, the written proof of the central Lemma 1 has an index mismatch: the surrogate loss is built from f_{t-1}, the algebra bounds f_{t-1}(x_{t-1})-f_{t-1}(x), and the final display silently changes the argument to f_t(x_t)-f_t(x). Because the loss sequence is arbitrary, no Lipschitz or convexity property allows this substitution. This is more load-bearing than the reader's specific concern about knowing the Slater constant beta in T0=log T/beta, although that concern is also valid. The same proof defect also affects the proximal term's indices and the claimed hard-budget regret. The right disposition is still conditional: the theorem might be repairable by a shifted-regret argument and movement-cost control, but the current manuscript does not contain that argument. A revision should either correct the proof or explicitly state and prove the shifted lemma, then carry the additional terms through the regret and violation bounds.","tokens_in":11649,"tokens_out":15423,"duration_ms":142967,"concrete_test":"Re-derive Lemma 1 with explicit indices: write \\hat f_t as the linearization of f_{t-1} at x_{t-1}, state the first-order optimality condition for x_t, and try to produce the claimed inequality for V(f_t(x_t)-f_t(x))+\\Delta_t using only convexity of f_t and feedback available before x_t is chosen. If the derivation requires a term involving \\nabla f_t(x_t) that is absent from Algorithm 1, the lemma fails. A minimal adversarial check: take X=[0,1], no constraints, f_1(x)=x, f_2(x)=-x, and verify whether SELO's x_2 (based on \\nabla f_1=1) can satisfy the claimed one-step regret bound against f_2; the algebra in Section VI cannot because \\hat f_2 is a lower bound of f_1, not f_2.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The key step for both regret and violation is Lemma 1 (Eq. 6). In the proof, \\hat f_t is defined in Eq. (3) as the first-order expansion of f_{t-1} at x_{t-1}, and Algorithm 1 line 6 minimizes V\\hat f_t(x)+\\langle Q_t,\\hat g_t(x)\\rangle+\\frac{1}{2\\eta}\\|x-x_{t-1}\\|^2. The displayed derivation therefore yields an inequality for V(f_{t-1}(x_{t-1})-f_{t-1}(x))+\\Delta_t, and the proximal term coming out of the algebra is D(x,x_{t-1},x_t)/(2\\eta), not D(x,x_t,x_{t+1})/(2\\eta). In the final display this is replaced, without justification, by V(f_t(x_t)-f_t(x))+\\Delta_t to match Eq. (6). Since the sequence \\{f_t\\} is arbitrary and f_t is observed only after x_t is chosen, convexity and Lipschitzness of each f_t do not relate f_t(x_t) to f_{t-1}(x_{t-1}); the two losses can be adversarially complementary. Hence Eq. (6) is not established as stated. The telescoping regret bound (7), the soft-violation O(1) claim, and the hard-budget regret claim all rely on Eq. (6), so the central theorem is currently unsupported. A correct proof would need to re-index the algorithm (bound a shifted regret and add movement costs) or use the current gradient \\nabla f_t(x_t) in the same step, but the model explicitly reveals \\nabla f_t(x_t) only after x_t is played.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online convex optimization with linear budget constraints in a partial-feedback model: after choosing x_t, the learner observes the gradient/value of the loss at x_t and the consumption A_t x_t, where the constraint matrices A_t are i.i.d. with unknown mean A. The proposed SELO algorithm first explores for T0 rounds, then at each round minimizes a strongly convex surrogate consisting of an estimated linearized loss, a pessimistic estimated consumption term multiplied by a virtual queue, and a proximal penalty; the virtual queue accumulates pessimistic estimated violations plus a slack xi. The main claims are O~(sqrt(T)) regret with O(1) (and in the abstract, zero) cumulative violation under soft budgets, and O~(sqrt(T)) regret under hard budgets, under convex Lipschitz losses and Slater's condition. A Lyapunov-drift proof sketch is provided, and a simulation on energy-efficient task processing in data centers is reported.","tokens_in":12005,"tokens_out":21617,"duration_ms":190232,"significance":"The claimed results, if fully proved, would be a useful contribution: optimal-order regret with bandit constraint feedback, no anytime projection, and a computationally simple primal-dual update, improving on the T^{2/3}-type rates of safe-projection methods. The algorithm's design--linearized loss, pessimistic least-squares constraint estimates, and a virtual queue with extra budget pacing--is natural, and the high-level parameter balance is plausible. However, the key lemma's proof has a time-index gap, and the anytime high-probability bound on the virtual queue is only cited, not derived; the significance is therefore conditional on a complete proof being supplied. The simulation alone does not validate the theoretical rates.","major_comments":[{"comment":"The proof derives an inequality for V(f_{t-1}(x_{t-1})-f_{t-1}(x)) with the proximal term D(x,x_{t-1},x_t)/(2eta), but Lemma 1 and Eq. (6) state the inequality for V(f_t(x_t)-f_t(x)) with D(x,x_t,x_{t+1})/(2eta). Since the loss sequence is adversarially chosen and f_t is revealed only after x_t is played, convexity and Lipschitzness of each f_t do not justify replacing f_{t-1}(x_{t-1})-f_{t-1}(x) by f_t(x_t)-f_t(x) or shifting the proximal index from (t-1,t) to (t,t+1). Eq. (6) is the step from which the regret telescope (7), the soft-violation O(1) claim, and the hard-budget regret claim all follow, so the central theorem is currently unsupported. A correct proof will require a re-indexed drift argument, for example using the t+1 update and paying for the movement cost, or a modified algorithm in which the gradient used in x_t is nabla f_t(x_t); the latter is not available in the stated feedback model.","section":"Section VI, Lemma 1 proof"},{"comment":"The anytime high-probability bound ||Q_t|| = O(sqrt(T) log T) for all t is asserted by invoking a Foster-Lyapunov lemma from [29] and [65], but the lemma is not stated, its hypotheses are not verified for the present process (Q_t, \\bar A_t, \\hat g_t), and the constants are not tracked. This bound is the bridge from the drift inequality to the O(1) soft violation and to the hard-budget regret; without a self-contained statement and verification, or at least a precise quotation of a theorem whose assumptions are checked, Theorem 1 is not established. In particular, the later step V(T) <= (E||Q_T||_1 - T xi)_+ requires an expectation bound, while Eq. (9) as written is only a probability bound.","section":"Section V, Eq. (9)"},{"comment":"The hard-budget regret argument is incomplete. The displayed inequality sum_t g_t(x_t) <= Q_{T+1} + sum_t(g_t(x_t) - \\hat g_t(x_t)) relates cumulative consumption to the queue, but it does not by itself bound the regret of an algorithm that may stop early relative to the T-round offline benchmark, and it does not account for the budget consumed during the pure exploration phase of length T0 = log T / beta. The paper needs a precise definition of regret under early termination, a proof that the probability of stopping before T is small, and a bound on the loss difference caused by the unplayed rounds.","section":"Section V, hard-budget analysis"},{"comment":"The regret is first bounded against the time-varying comparator x*_{epsilon_t} in the tightened feasible set X_{epsilon_t}, and then it is asserted that the original regret against x* is O~(sqrt(T)) because sum_t epsilon_t = O~(sqrt(T)). The paper does not prove a stability bound relating sum_t(f_t(x*_{epsilon_t}) - f_t(x*)) to sum_t epsilon_t under Assumptions 1-3; such a bound, for example via Slater's condition and Lipschitzness of f_t, is needed to justify the last step of the regret analysis. The telescoping of the D(x,x_t,x_{t+1}) terms leading to D^2/(V eta) in Eq. (7) should also be written out with the correct indices.","section":"Section V, regret comparison"},{"comment":"The algorithm as stated requires knowledge of the Slater constant beta to set T0 = log T / beta, and it presupposes beta >= log T / T so that T0 <= T; neither condition appears in Assumption 3. In addition, the exploration phase says to generate a scaled Gaussian random vector x_t in X, but for a general convex compact set X this is not well-defined unless X contains a ball or a projection is specified, and the lower bound on the least-squares covariance needed for the confidence bound in (5) is not established.","section":"Section IV, Algorithm 1"}],"minor_comments":[{"comment":"Theorem 1 sets eta = 1/T, but the regret-analysis paragraph in Section V says 'Recall V = sqrt(T), eta = T'; the proof requires eta = 1/T, so this is a typo to correct.","section":"Theorem 1 and Section V"},{"comment":"The displayed high-probability event has the inequality in the wrong direction: it should be P((\\bar A_t - A)x <= -(alpha ||x||_{Sigma_t^{-1}} + xi)1) <= T^{-3} rather than P((\\bar A_t - A)x >= (...)).","section":"Section VI, proof of Lemma 1"},{"comment":"The abstract claims zero cumulative constraint violation, while Theorem 1 states V(T) = O(1); the zero-violation conclusion is justified only for sufficiently large T and should be stated with that qualification in both places.","section":"Abstract and Theorem 1"},{"comment":"Figure 1 is referenced in Section VII but is not visible in the manuscript text supplied for review; please ensure the figure and its caption are present and specify the number of independent runs and the error bars.","section":"Section VII"},{"comment":"The notation for the budget dimension is inconsistent: the model uses vectors with xi 1 and beta 1, the violation bound uses ||Q_T||_1, and Eq. (9) is stated for the Euclidean norm ||Q_t||; the norm and dimension conventions should be made explicit.","section":"Model notation"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is attractive and the claimed rates would be interesting, but the current manuscript does not contain a complete proof of its main theorem. The time-index gap in Lemma 1 and the unproved anytime queue bound are the two decisive issues; both are fixable in principle but require substantial additional work. I recommend major revision rather than rejection, because the algorithm and high-level parameter choices are plausible and the missing steps appear to be within the scope of a careful rewrite. I would also ask the editor to ensure the revised version includes all theorem proofs and the referenced figure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper attacks a genuinely open-looking spot: online convex optimization with unknown linear budget constraints, where the learner sees gradients of the objective but only bandit feedback on the constraints. SELO combines Lyapunov queues, pessimistic ridge estimates, and a proximal step, and the authors correctly position it against anytime-safe projection methods. If the main theorem were true—O(√T) regret with O(1) (or zero) violation—it would improve on the T^{2/3} rate of [20] in a practically relevant partial-feedback setting.\n\nThe problem is that Lemma 1, the load-bearing step, is not proved as stated. The algorithm minimizes a surrogate built from f_{t-1}, and the proof's derivation yields an inequality for V(f_{t-1}(x_{t-1}) - f_{t-1}(x)). The final display swaps this to V(f_t(x_t) - f_t(x)) without justification. Since the f_t are arbitrary and f_t is revealed only after x_t is chosen, convexity and Lipschitzness of each f_t do not connect the two expressions. The telescoping regret bound, the soft-violation O(1) claim, and the hard-budget regret argument all rest on the stated Lemma. So the central theorem is unsupported. The stress-test note is right.\n\nSecondary but real issues: the abstract claims zero cumulative violation while Theorem 1 only proves O(1) for soft budgets; the violation analysis relies on an anytime high-probability queue bound cited from [29] and [65] without showing the conditions transfer or how the high-probability event is converted into an expectation bound; and the exploration phase T0 = log T/β requires exact knowledge of the Slater constant β, with no control for small β. The proof sketch also has parameter typos (η = 1/T in the theorem, η = T in the regret sketch). The self-citations are to standard tools, so the citation pattern is not a problem per se—the problem is the unverified leap from those tools to this setting.\n\nCredit where it is due: the formulation is clean, the algorithm is computationally friendly on simple sets, the experiment is reasonable, and the related work is honestly surveyed. The approach is worth pursuing. But this is a conditional-major-revision situation, not a desk reject. A serious referee should ask the authors to fix the index mismatch in Lemma 1 (or re-index the algorithm and pay the shifted-regret cost) and to make the violation argument self-contained. If they can do that, the paper could be a solid contribution.\n\nMy bottom line: send it to peer review, but with the expectation that the proof needs real work.","headline":"Nice problem setup and plausible algorithm, but Lemma 1 proves the wrong index (f_{t-1} vs f_t), leaving the √T regret and zero-violation claims unsupported.","tokens_in":12548,"tokens_out":8072,"would_cite":false,"duration_ms":70141,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Budget-safe online learning reaches the optimal regret rate while keeping constraint violation bounded.","keywords":["online convex optimization","linear budget constraints","bandit feedback","Lyapunov optimization","virtual queue","regret","constraint violation","primal-dual algorithm"],"falsifier":"Run SELO on a one-dimensional instance with $X=[0,1]$, $A_t=1$, and $b=\\beta=T^{-1}$, keeping all other assumptions satisfied, and record the cumulative violation over $T$; then $T_0=\\log T/\\beta=T\\log T$ exceeds the horizon, so the exploration phase alone can consume more than the total budget and an $O(1)$ violation bound would fail.","tokens_in":11404,"feed_emoji":"⚖️","tokens_out":6522,"duration_ms":66596,"temperature":0.7,"pith_summary":"This paper studies online convex optimization where each decision consumes resources through a fixed but unknown linear mapping, and the learner only observes the realized consumption after choosing. The authors propose SELO, a primal-dual algorithm driven by a virtual queue that tracks cumulative budget overuse, and they claim it attains $\\widetilde{O}(\\sqrt{T})$ regret with $O(1)$ cumulative constraint violation under soft budget constraints, and $\\widetilde{O}(\\sqrt{T})$ regret under hard budget constraints. The abstract states the stronger conclusion of zero cumulative constraint violation, while the formal theorem proves $O(1)$. These rates match the $\\Omega(\\sqrt{T})$ lower bound for unconstrained online convex optimization up to logarithmic factors, so the price of unknown constraints and bandit feedback would vanish asymptotically. The practical significance is that a learner with an energy or monetary budget can learn a good policy without a long conservative warm-up phase.","feed_headline":"Budget-safe online learning hits the optimal regret rate","feed_subtitle":"A virtual-queue algorithm keeps cumulative violation at O(1) while matching the sqrt-T regret lower bound.","key_machinery":"The machine is a virtual queue $Q_t$ updated by $Q_{t+1}=\\max(Q_t+\\hat{g}_t(x_t)+\\xi\\mathbf{1},0)$, where $\\hat{g}_t(x)=\\bar{A}_t x+\\alpha\\|x\\|_{\\Sigma_t^{-1}}-b$ is a pessimistic estimate of the unknown constraint built from regularized least squares and the confidence radius of linear bandits. The pessimistic term plus the extra $\\xi$ pacing pushes the algorithm to under-use the budget, and the queue acts as a dual variable so that the decision step minimizes $V\\hat{f}_t(x)+\\langle Q_t,\\hat{g}_t(x)\\rangle+\\frac{1}{2\\eta}\\|x-x_{t-1}\\|^2$, a strongly convex and smooth problem. The analysis introduces the $\\epsilon_t$-tight feasible set $X_{\\epsilon_t}=\\{x: Ax\\le b-\\epsilon_t\\mathbf{1}\\}$ and uses a one-step bound on 'regret plus Lyapunov drift' together with a Foster-Lyapunov multi-step argument to obtain the anytime high-probability queue bound that carries both the regret and violation conclusions.","core_discovery":"The central claim is Theorem 1: under convexity, boundedness, and Slater's condition, SELO with parameter choices $V=\\sqrt{T}$, $\\eta=1/T$, $\\xi=\\log^2 T/\\sqrt{T}$, and exploration length $T_0=\\log T/\\beta$ guarantees $R(T)=\\widetilde{O}(\\sqrt{T})$ and $V(T)=O(1)$ when the budget constraint is soft, and $R(T)=\\widetilde{O}(\\sqrt{T})$ when the budget is hard and violations are not allowed. The proof route is to show the virtual queue is bounded with high probability at every round via a multi-step Lyapunov drift argument, then translate the bounded queue into both the violation bound and the regret loss from early stopping under the hard budget. The paper presents SELO as improving on anytime-safe projection methods, which it claims incur $\\widetilde{O}(T^{2/3})$ regret.","pith_inferences":["If Theorem 1 is right, the virtual-queue-plus-pessimistic-estimator pattern is a template for other partial-feedback resource problems: estimation error is converted into an additive safety margin rather than into a separate feasibility phase, so the algorithm avoids the conservative warm-up of projection-based safe learning.","The zero-violation phrasing in the abstract is stronger than the proved $O(1)$ violation; a practitioner should read the guarantee as 'violation bounded by a constant independent of $T$' and check the constant's dependence on problem parameters such as $D$, $F$, and $\\beta$.","Because the exploration length $T_0=\\log T/\\beta$ depends on the Slater constant, an extension to unknown $\\beta$ would need adaptive exploration or a doubling schedule; the paper's guarantee does not cover that case.","In applications where budgets are quotas, such as fairness or carbon caps, the $O(1)$ violation bound would translate into asymptotically perfect quota satisfaction, making SELO a candidate for online fair allocation with unknown resource costs."],"forward_implications":["SELO achieves $\\widetilde{O}(\\sqrt{T})$ regret with $O(1)$ cumulative violation, so a learner can satisfy a long-run budget without paying an extra $\\sqrt{T}$ penalty in safety, closing the gap to the unconstrained lower bound.","Under hard budgets the same algorithm keeps regret at $\\widetilde{O}(\\sqrt{T})$, so an energy- or money-limited system can stop when the budget is exhausted without losing more than the asymptotically optimal amount of objective value.","Because the primal update is strongly convex and smooth, each round costs about the same as an unconstrained gradient step, removing the projection bottleneck of anytime-safe methods.","The regret/violation trade-off parameter $\\xi=\\log^2 T/\\sqrt{T}$ absorbs the optimistic estimation error, indicating that the unknown-constraint estimation cost only shows up in logarithmic factors.","The paper notes the same construction works when only the loss value, not its gradient, is observed, by swapping in two-point or one-point gradient estimators."],"supporting_citations":[{"why":"Defines the anytime-safe projection baseline whose $\\widetilde{O}(T^{2/3})$ regret SELO claims to improve.","marker":"[20]"},{"why":"Supplies the confidence-ellipsoid bound used to construct the pessimistic constraint estimate $\\hat{g}_t$ and the $\\epsilon_t$-tight feasible set.","marker":"[57]"},{"why":"Provides the Lyapunov optimization and virtual-queue framework that motivates the queue update and drift analysis.","marker":"[59]"},{"why":"Presents the primal-dual viewpoint of network optimization used to interpret the virtual queue as a dual variable.","marker":"[60]"},{"why":"Cited for the Forster-Lyapunov lemma used in the multi-step drift argument that gives the high-probability queue bound.","marker":"[29]"},{"why":"Establishes the $O(\\sqrt{T})$ regret and $O(1)$ violation template for long-term constraints that SELO extends to partial feedback.","marker":"[67]"},{"why":"Shows the best-known $O(1)$ violation result for full-information hard constraints, the benchmark SELO improves on under partial feedback.","marker":"[36]"}],"fun_headline_variants":["SELO: safe online optimization with sqrt-T regret and zero violation","Optimal regret without crossing budget: SELO algorithm","Virtual queue keeps online learning safe at sqrt-T regret","Hard-budget online convex optimization: optimal regret achieved","Lyapunov method proves O(sqrt T) regret under budget constraints"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The learner must know the Slater constant $\\beta$ in advance, because the exploration phase lasts $\\log T/\\beta$; if $\\beta$ is unknown or very small, the safety and regret guarantees are not delivered.","fun_headline_variants_meta":{"raw":{"variants":["SELO: safe online optimization with sqrt-T regret and zero violation","Optimal regret without crossing budget: SELO algorithm","Virtual queue keeps online learning safe at sqrt-T regret","Hard-budget online convex optimization: optimal regret achieved","Lyapunov method proves O(sqrt T) regret under budget constraints"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1240,"prompt_tokens":851,"completion_tokens":389,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":467,"completion_tokens_details":{"reasoning_tokens":305}},"tokens_in":467,"tokens_out":389,"duration_ms":5350,"temperature":1.0,"reasoning_tokens":305,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:53:42.958151+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SELO on a one-dimensional instance with $X=[0,1]$, $A_t=1$, and $b=\\beta=T^{-1}$, keeping all other assumptions satisfied, and record the cumulative violation over $T$; then $T_0=\\log T/\\beta=T\\log T$ exceeds the horizon, so the exploration phase alone can consume more than the total budget and an $O(1)$ violation bound would fail.","supporting_citations":[{"cited_title":"Safe online convex optimization with unknown linear safety constraints,","cited_arxiv_id":null,"evidence_quote":"Defines the anytime-safe projection baseline whose $\\widetilde{O}(T^{2/3})$ regret SELO claims to improve."},{"cited_title":"Improved algorithms for linear stochastic bandits,","cited_arxiv_id":null,"evidence_quote":"Supplies the confidence-ellipsoid bound used to construct the pessimistic constraint estimate $\\hat{g}_t$ and the $\\epsilon_t$-tight feasible set."},{"cited_title":"Stochastic network optimization with application to communication and queueing systems,","cited_arxiv_id":null,"evidence_quote":"Provides the Lyapunov optimization and virtual-queue framework that motivates the queue update and drift analysis."},{"cited_title":"Srikant and L","cited_arxiv_id":null,"evidence_quote":"Presents the primal-dual viewpoint of network optimization used to interpret the virtual queue as a dual variable."},{"cited_title":"A low complexity algorithm with O( √ T ) regret and O(1) constraint violations for online convex optimization with long term constraints,","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(\\sqrt{T})$ regret and $O(1)$ violation template for long-term constraints that SELO extends to partial feedback."},{"cited_title":"Online convex optimization with hard constraints: Towards the best of two worlds and beyond,","cited_arxiv_id":null,"evidence_quote":"Shows the best-known $O(1)$ violation result for full-information hard constraints, the benchmark SELO improves on under partial feedback."}],"review_version":1}