{"id":"dd04363d-b9b8-4bce-9bed-cdb0bf262c30","arxiv_id":"2411.11574","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A distributed bandit primal-dual method achieves reduced cumulative constraint violation under Slater's condition, including O(log T) violation for known strongly convex losses.","lead":"This paper presents a distributed algorithm for online optimization with bandit feedback and time-varying constraints, and proves that cumulative constraint violation is reduced when a fixed strictly feasible point exists. The result closes a theoretical gap for distributed bandit constrained optimization.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 is not well-defined for μ<1: with α_t=1/(μt), the step ξ_1=α_1=1/μ exceeds 1, making the initialization set (1−ξ_1)X empty, so the claimed O(log T) bounds do not cover the full stated parameter range.","rationale":"The reader's verdict is CONDITIONAL, citing the Slater assumption as the weakest point and noting minor parameter-range inconsistencies. My stress-test agrees that the main proof structure is sound: inequality (106) correctly converts the Slater margin into a negative lower bound on h_T(x_s), which is then used via (44) and (67) to drop the violation bound from a square-root dependence to a direct one. I could not find a flaw in that central argument. The most load-bearing concern I identified is the μ<1 gap in Theorem 4: the algorithm is not well-defined for μ<1 because ξ_1=1/μ>1 makes the initialization set empty. This directly affects the stated scope of the flagship O(log T) result, though it is a fixable parameter-range issue rather than a breakdown of the asymptotic analysis. I therefore recommend keeping the reader's CONDITIONAL verdict unchanged, with the parameter-range restriction made explicit. The numerical section's lack of error bars and its use of γ0=0.15 (likely violating the bound in Lemma 5 for the stated p and G2) are additional verification concerns, but they do not alter the central theoretical claim.","tokens_in":29396,"tokens_out":29665,"duration_ms":247644,"concrete_test":"Set μ=0.5 in Theorem 4 and attempt to initialize Algorithm 1 with X=[-1,1] (r(X)=1): then ξ_1=2 and (1−ξ_1)X is empty, so no z_i,1 exists. Next, re-run the proof with α_t = 1/(μ(t+1)) (so ξ_1<1 for all μ>0) and verify that the summation identities (118)-(121) and the estimates (128)-(134) still produce E[Net-Reg(T)] = O(log T) and E[Net-CCV(T)] = O(log T). If the rates survive, the concern is a parameter-range oversight; if not, Theorem 4 must explicitly assume μ≥1 or a similar condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's flagship result for known strong-convexity parameters, Theorem 4, states O(log T) network regret and O(log T) network cumulative constraint violation under Slater's condition, with α_t = 1/(μt) and ξ_t = α_t. Assumption 6 allows any μ>0, and the theorem is stated without restriction on μ. However, Algorithm 1 initializes z_i,1 ∈ (1−ξ_1)X. For μ<1, α_1 = 1/μ > 1, so ξ_1 > 1 and the set (1−ξ_1)X is empty for typical X (e.g., a symmetric box about the origin), making the algorithm undefined. Even for μ=1, ξ_1=1 gives the degenerate set {0}, which is nonempty but outside the stated range ξ_t ∈ (0,1). This is a genuine parameter-range gap, not merely a cosmetic issue, because the proof's telescoping identities in (118) and the cancellation in (135) rely on the specific choice α_t = 1/(μt). The gap is likely fixable by reparameterizing α_t = 1/(μ(t+1)) or by shifting the time index, but as stated the theorem overclaims coverage. The rest of the proof, including the key Slater inequality (106), appears internally consistent; the issue is confined to the stepsize initialization range.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies distributed bandit convex optimization with time-varying inequality constraints under two-point bandit feedback for both losses and constraints. The authors propose a distributed primal-dual algorithm in which dual variables are updated by maximizing the regularized Lagrangian rather than by substituting the clipped constraint function, while primal variables are updated by projected gradient steps using two-point stochastic subgradient estimators and consensus mixing. The main theoretical results are: for convex losses, network regret O(T^{max{c,1-c}}) and network cumulative constraint violation O(T^{1-c/2}), reduced to O(T^{1-c}) under Slater's condition (Theorems 1 and 2); for strongly convex losses with unknown parameter, regret O(T^{1-c}) and violation O(T^{1-c/2}), reduced to O(T^{1-c}) under Slater's condition (Theorem 3); and for known strong convexity parameter, regret O(log T) and violation O(sqrt(T log T)), reduced to O(log T) under Slater's condition (Theorem 4). Detailed proofs with explicit constants are given in appendices, and a numerical example compares the proposed algorithm with prior work.","tokens_in":29637,"tokens_out":30862,"duration_ms":280435,"significance":"This is a potentially significant contribution. The paper identifies a real limitation of prior distributed bandit algorithms that use clipped constraint functions in the dual update, namely that Slater's condition cannot improve cumulative constraint violation bounds under that design. The proposed dual update via the regularized Lagrangian is a clean fix, and the key inequality (106) genuinely converts the uniform Slater margin into a linear lower bound on the dual objective, enabling the improved violation rates. The proof structure follows and extends known techniques from [28] and [29], with detailed appendix proofs and explicit constants. If the parameter-range issue in Theorem 4 is corrected, the results would be the first reduced cumulative constraint violation bounds under Slater's condition for distributed bandit convex optimization, matching the full-information rates of [29].","major_comments":[{"comment":"Theorem 4 as stated does not cover all mu>0 allowed by Assumption 6. With alpha_t = 1/(mu t), for any mu<1 we have alpha_1 = 1/mu > 1, so xi_1 > 1, contradicting the Algorithm 1 input condition xi_t in (0,1). Consequently the set (1 - xi_1)X is not contained in X, and for a general convex X the observation points x_i,1 + delta_1 u_i,1 need not lie in X, so Assumptions 2 and 3 cannot be applied at t=1. The proof's telescoping identities (118) and the cancellation in (135) rely on the exact choice alpha_t = 1/(mu t), so this is not merely a cosmetic issue. The theorem statement and proof must be revised, for example by restricting to mu >= 1 or by shifting the stepsize to alpha_t = 1/(mu(t + t0)) and reworking the affected estimates.","section":"Section III-C, Theorem 4, Eq. (25) and Algorithm 1"},{"comment":"Lemma 1 as stated is false for arbitrary b in R^p. Taking K = [0,1], b = 10, and a = 0 gives x_c = 1 and ||x_c - b|| = 9 > 0 = ||a||, violating (30). The proof invokes the optimality condition with b, which is valid only when b belongs to K. In all applications in the paper, including (42) and (64), b = x_i,t does belong to K = (1 - xi_{t+1})X because z_j,t in (1 - xi_t)X and xi_t is non-increasing, so the applications are sound. Nevertheless, the lemma statement should be corrected to include the hypothesis b in K, and the proof should be adjusted accordingly.","section":"Appendix A, Lemma 1"}],"minor_comments":[{"comment":"In Theorems 1 and 3, Eq. (16) gives xi_1 = alpha_1 = 1, and in Theorem 4, Eq. (25) gives xi_1 = 1 when mu = 1, both violating the stated condition xi_t in (0,1). Please either explicitly allow xi_1 = 1 or redefine the sequences for t >= 2.","section":"Algorithm 1 input and Theorems 1, 3, 4"},{"comment":"The strong convexity inequality in the proof of Lemma 1 is missing the square on ||b - x_c||; the displayed argument should be corrected. A simpler proof of (30), under the added hypothesis b in K, is to specialize (29) to y = b.","section":"Appendix A, Lemma 1 proof"},{"comment":"The notation 1/alpha_0 is used without defining alpha_0; please state the convention, presumably 1/alpha_0 = 0.","section":"Eqs. (78) and (118)"},{"comment":"The constant epsilon_1 is used in (65) and (85) but only tilde{epsilon}_1 is defined in Lemma 5; the notation should be aligned to avoid ambiguity.","section":"Lemma 6 and Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically strong and the main issue is a parameter-range gap in Theorem 4 that is likely fixable. The reliance on published lemmas from [28] and techniques from [29] is appropriate. I recommend major revision rather than rejection, contingent on correcting the Theorem 4 parameter range and the Lemma 1 statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the missing bandit analogue of the full-information reduced-violation result, and the core mechanism is sound. The authors replace the clipped constraint update with an explicit dual maximizer of the regularized Lagrangian, which lets Slater's margin survive in the analysis. Inequality (106) is the load-bearing step, and it checks out: with a uniform Slater point, the dual objective is bounded below by the cumulative violation itself, which converts a square-root bound into a direct one. The two-point estimator analysis is carried out with explicit constants, and the regret/violation rates match the full-information paper [29]. That is a genuine step forward for distributed bandit convex optimization with time-varying constraints.\n\nThe soft spots are real but localized. The stress-test concern about Theorem 4 is valid: with alpha_t = 1/(mu t) and mu < 1, xi_1 = 1/mu > 1, which violates the stated xi_t in (0,1) and can send the query points outside X, where the functions are not bounded. Even for mu = 1, xi_1 = 1 is at the boundary. The same boundary issue appears in Theorem 1 with xi_1 = 1^{-c} = 1. This does not break the asymptotic rates, and it is fixable by reindexing the stepsize, e.g., alpha_t = 1/(mu(t+1)) or starting the sequence at t=2, but as stated the theorems overclaim the parameter range. Also, the numerical section is a single illustrative run with no error bars; that is acceptable for an OCO paper, but do not cite it as empirical validation. The proof leans on self-cited lemmas from [28] and [29], but those are published and the dependence is legitimate, not circular. Assumption 5 is a strong uniform-in-time Slater condition; it is the standard assumption in this literature, just note it fails if the feasible set drifts so no fixed point stays strictly feasible.\n\nBottom line: worth a serious referee. The main technical claims are correct in spirit, and the issue is a parameter-range statement that a careful author can fix without changing the algorithm or rates. I would send it out.","headline":"Solid rate results for distributed bandit constrained optimization under Slater; the main theorems hold, but the stated parameter range for the known-strong-convexity result needs a small fix.","tokens_in":30243,"tokens_out":3575,"would_cite":true,"duration_ms":33736,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A distributed bandit algorithm with an unclipped dual update achieves O(log T) cumulative constraint violation under Slater's condition.","keywords":["bandit convex optimization","distributed optimization","cumulative constraint violation","Slater's condition","time-varying constraints","primal-dual algorithm","two-point feedback","network regret"],"falsifier":"Run Algorithm 1 on a network with known strongly convex quadratic losses and time-varying linear constraints for which a fixed x_s with g_t(x_s) ≤ -ς_s 1_m exists, using the step sizes of Theorem 4, and measure average Net-CCV(T) over many random seeds. If it grows faster than C log T for T up to $10^{5}$, Theorem 4's bound (28) is contradicted; an algebraic check of inequality (106) along a simulated trajectory would locate whether the margin inequality or the subsequent bound fails.","tokens_in":29117,"feed_emoji":"📉","tokens_out":5495,"duration_ms":53834,"temperature":0.7,"pith_summary":"The paper tackles distributed online decision-making in which networks of agents choose points, see only noisy function values (bandit feedback), and are penalized both for regret and for violating time-varying inequality constraints. Its central claim is that a primal–dual algorithm that updates dual variables by maximizing the regularized Lagrangian in closed form—rather than by plugging in the clipped constraint function—keeps Slater's condition effective. Under that condition, if local losses are strongly convex with known parameter, the algorithm attains O(log T) network regret and O(log T) network cumulative constraint violation; without Slater, the violation bound is only O($\\sqrt$(T log T)). For merely convex losses, the violation bound improves from O($T^{{1-c/2}}$) to O($T^{{1-c}}$) when Slater holds. This matters because earlier distributed bandit algorithms that clipped constraints could not exploit Slater's condition at all.","feed_headline":"Slater margin cuts bandit constraint violations from sqrt(T) to log T","feed_subtitle":"A dual update that skips clipping preserves Slater's condition, giving O(log T) regret and violations.","key_machinery":"The load-bearing object is the regularized Lagrangian dual update q_{i,t+1} = γ_t[g_{i,t}(x_{i,t})]_+, combined with two-point stochastic subgradient estimators and consensus mixing over a time-varying directed graph. Its role is to let Slater's fixed point x_s enter the analysis through inequality (106), converting a uniform feasibility margin into a linear lower bound on the dual objective; this is the step that turns square-root violation rates into direct rates.","core_discovery":"The paper's discovery is that the clipping operation [g_t(x)]_+, used by earlier algorithms to measure cumulative constraint violation, is what destroys Slater's condition: after clipping, a strictly feasible point x_s no longer gives a negative term in the dual update, and inequality (106) becomes nonnegative. Algorithm 1 instead keeps the original constraint function inside the regularized Lagrangian L_t(x,q) = (1/n)Σ f_{i,t}(x) + q^T g_t(x) - (1/(2γ_t))||q||^2, so the dual update has the closed form q_{i,t+1}=γ_t[g_{i,t}(x_{i,t})]_+. Slater's margin then yields inequality (106), Σ_{i,t} q_{i,t+1}^T g_{i,t}(x_s)/γ_t ≤ -ς_s Σ_{i,t} ||[g_{i,t}(x_{i,t})]_+||, which makes the cumulative violation linearly bounded by the regularized dual objective instead of by its square root. The theorems state the resulting rates: convex losses give Net-CCV O($T^{{1-c}}$) under Slater; strongly convex losses with known μ give Net-Reg O(log T) and Net-CCV O(log T) under Slater, versus O($\\sqrt$(T log T)) without.","pith_inferences":["Because the proof's key inequality depends on one fixed x_s common to all t, the reduction should fail exactly when the strictly feasible region moves over time; testing a shifting-feasibility instance would likely show the O(log T) violation bound reverting to the unimproved rate.","The same unclipped regularized-Lagrangian trick may transfer to other bandit settings with cumulative penalties, such as distributed online learning with communication compression, where clipping currently blocks Slater-type arguments.","The two-point estimator's smoothing bias introduces O(δ_t) error, so a one-point feedback version would face larger gaps; an analogous reduction under Slater may require different estimators or slower rates.","A practical reading is that the gap between O(log T) and O(sqrt(T log T)) is the quantitative price of not knowing a strictly feasible point, suggesting system designers could enforce Slater's margin as a safety requirement."],"forward_implications":["When a fixed strictly feasible point exists, distributed bandit networks with strongly convex known losses can achieve logarithmic regret and logarithmic cumulative constraint violation simultaneously, matching full-information rates in the prior work this paper builds on.","For convex losses, Slater's condition improves the cumulative constraint violation exponent by c/2, from O(T^{1-c/2}) to O(T^{1-c}), without worsening the regret bound.","The unclipped dual update also removes the need for uniformly bounded constraint functions, an assumption the prior clipped algorithm required.","In the strongly convex case with unknown parameter, the Slater improvement still holds for violations, giving O(T^{1-c}) instead of O(T^{1-c/2}) while regret improves to O(T^{1-c})."],"supporting_citations":[{"why":"This is the prior distributed bandit algorithm whose clipped constraint functions make Slater's condition ineffective, providing the baseline this paper improves.","marker":"[28]"},{"why":"This is the full-information distributed online algorithm that first established reduced cumulative constraint violation bounds under Slater's condition, and the source of the dual-update idea adapted here.","marker":"[29]"},{"why":"This supplies the two-point stochastic subgradient estimation technique used to approximate unavailable gradients.","marker":"[12]"},{"why":"This introduced the cumulative constraint violation metric and the regularized-Lagrangian dual update that the algorithm builds on.","marker":"[26]"},{"why":"This is the one-point bandit distributed algorithm with long-term constraints whose bounds the proposed two-point algorithm improves.","marker":"[27]"},{"why":"This provides the projection, smoothing, and consensus disagreement lemmas that the proof relies on.","marker":"[35]"}],"fun_headline_variants":["Avoid clipping to keep Slater: O(log T) constraint violation","Clipping was the culprit; unclipped dual hits O(log T) violations","Slater condition restored by skipping clip: violation drops to log T","New dual update preserves Slater, slashing violation to O(log T)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole reduction depends on one fixed decision that strictly satisfies every constraint at every time step with a positive margin; if the feasible region drifts so no such point exists, the improved violation bounds no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Avoid clipping to keep Slater: O(log T) constraint violation","Clipping was the culprit; unclipped dual hits O(log T) violations","Slater condition restored by skipping clip: violation drops to log T","New dual update preserves Slater, slashing violation to O(log T)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001158,"raw_usage":{"total_tokens":4856,"prompt_tokens":1063,"completion_tokens":3793,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":679,"completion_tokens_details":{"reasoning_tokens":3722}},"tokens_in":679,"tokens_out":3793,"duration_ms":68852,"temperature":1.0,"reasoning_tokens":3722,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:22:41.904775+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a network with known strongly convex quadratic losses and time-varying linear constraints for which a fixed x_s with g_t(x_s) ≤ -ς_s 1_m exists, using the step sizes of Theorem 4, and measure average Net-CCV(T) over many random seeds. If it grows faster than C log T for T up to $10^{5}$, Theorem 4's bound (28) is contradicted; an algebraic check of inequality (106) along a simulated trajectory would locate whether the margin inequality or the subsequent bound fails.","supporting_citations":[{"cited_title":"Regret and cumulative constraint violation analysis for distributed online constrained convex optimization,","cited_arxiv_id":null,"evidence_quote":"This is the prior distributed bandit algorithm whose clipped constraint functions make Slater's condition ineffective, providing the baseline this paper improves."},{"cited_title":"Optimal algorithms f or online convex optimization with multi-point bandit feed back,","cited_arxiv_id":null,"evidence_quote":"This supplies the two-point stochastic subgradient estimation technique used to approximate unavailable gradients."},{"cited_title":"Online convex optimization f or cumulative constraints,","cited_arxiv_id":null,"evidence_quote":"This introduced the cumulative constraint violation metric and the regularized-Lagrangian dual update that the algorithm builds on."},{"cited_title":"Distributed online o ptimization with long-term constraints,","cited_arxiv_id":null,"evidence_quote":"This is the one-point bandit distributed algorithm with long-term constraints whose bounds the proposed two-point algorithm improves."},{"cited_title":"Distributed bandit online convex optimization with time- varying coupled inequality constraints,","cited_arxiv_id":null,"evidence_quote":"This provides the projection, smoothing, and consensus disagreement lemmas that the proof relies on."}],"review_version":1}