{"id":"55e2c2e7-db0a-49bd-b784-1694c4974d11","arxiv_id":"2511.20178","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Stochastic SQP with exact-penalty prox-linear updates attains O(1/ε²) convex and O(1/ε) strongly convex SFO complexity without bounded-gradient assumptions, and VARAS matches unconstrained accelerated finite-sum rates.","lead":"This paper proposes stochastic sequential quadratic programming algorithms for convex optimization with nonlinear functional constraints, achieving oracle-complexity bounds without bounded-gradient assumptions. A finite-sum accelerated variant matches unconstrained variance-reduced rates, which matters for constrained least-squares, filtering, and trajectory problems in signal processing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Constraint-violation bound in Theorem 1 divides by γ−B̃/ν while Algorithm 1 sets γ=B̃/ν; the Slater-data assumption is the weakest load-bearing point, though a strict-γ or direct-γ fix is straightforward.","rationale":"I read the manuscript in full and traced the main proof chain. The core ideas are coherent: the one-step inequality in Lemma 2 is internally consistent, the constraint handling via exact penalty and prox-linear subproblems is plausible, and the VARAS analysis in Lemma 5 follows the VARAG template with the expected parameter conditions. The numerical experiments, though single-run, support the practical claims. The weakest point is exactly the one the reader identified: the exact-penalty parameter γ is set to B̃/ν in Algorithm 1, yet Theorem 1's constraint-violation bound requires γ>B̃/ν. The manuscript itself flags the practical difficulty in Sec. II-A ('must be found by parameter tuning'), and Remark 1 admits the QMO cost. This is a genuine theorem-level gap in the stated guarantee, but it is not fatal to the central claim because a simple modification (strict γ or a direct bound from the objective gap) restores a nonzero constraint-violation rate. I therefore keep the verdict CONDITIONAL and do not recommend a change to the reader's assessment.","tokens_in":32003,"tokens_out":32633,"duration_ms":288822,"concrete_test":"Recompute the proof of Theorem 1 under γ=(1+δ)B̃/ν for a fixed δ>0, keeping the same η_t and L definitions. If the existing Lemmas 1–2 and inequality (64) hold without extra assumptions, the concern is purely a statement-level fix. Then, as a stronger check, prove directly from (62) that E[max_k[g_k(x̄_T)]_+] ≤ (ν/B̃)·(2/√T) max{2Lδ0, σ√δ0} by using γ E[w_T] ≤ E[F(x̄_T)]−F(x*). If this direct bound holds, the zero-denominator display in Theorem 1 can be amended without altering the algorithm or the main proof structure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 fixes γ=B̃/ν, and the paper's exact-penalty argument (Sec. II-B) shows this is enough for the reformulation to be exact. But Theorem 1's constraint-violation guarantee (17) is E[max_k[g_k(x̄_T)]_+] ≤ 2/((γ−B̃/ν)√T) max{2Lδ0, σ√δ0}. At the stated γ, the denominator is zero, so the displayed bound is undefined. The proof uses (64) after subtracting the dual bound (63); that step only yields a positive left-hand side if γ>B̃/ν. The assumption text in Sec. II-A also says ν and B̃ 'must be found by parameter tuning,' so an implementer with only a feasible point and unknown margin does not receive the theorem's stated constant. This is load-bearing because the constraint-violation criterion (2) is half of the ε-optimality definition, and the same γ appears in L=max{γLg,Lf}, so any tuning changes all complexity constants. The gap is repairable: choose γ=(1+δ)B̃/ν and pay the constant, or derive E[w_T] ≤ (E[F(x̄_T)]−F(x*))/γ from the already-proved objective gap, which gives a nonzero bound even at γ=B̃/ν. But as written, the theorem and algorithm do not match.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops stochastic sequential quadratic programming (SSQP) for convex optimization problems with nonlinear functional constraints. The method uses an exact l_infinity penalty reformulation and a prox-linear / stochastic proximal-gradient update, solving a diagonal QP at each iteration and avoiding projections onto the feasible set. The authors prove O(1/sqrt(T)) objective-gap and constraint-violation bounds for convex objectives, O(1/T) distance bounds for strongly convex objectives, a QP-skipping variant (SSQP-Skip), and an accelerated variance-reduced finite-sum variant (VARAS) with rates matching unconstrained accelerated methods. Numerical experiments on Zermelo trajectory generation and constrained regression compare favorably with APriD, GOCO, and PDSS.","tokens_in":32331,"tokens_out":10751,"duration_ms":105586,"significance":"If correct, this is a substantial contribution: it would be the first projection-free and bounded-gradient-free method achieving these oracle complexities for stochastic convex functional-constrained optimization. The proofs are largely self-contained, with explicit one-step inequalities (Lemmas 1, 2, and 5) and telescoping arguments in Appendices B-D. The VARAS extension is technically nontrivial and correctly leverages the VARAG framework. The numerical comparison against three published baselines on real datasets is a strength. However, the current statement has a mismatch between the theorem and the algorithm for the constraint-violation bound, and the violation metric in Theorem 1 is the max positive constraint value rather than the sum used in the epsilon-optimality definition; these issues need to be fixed before the result can be accepted.","major_comments":[{"comment":"Algorithm 1 sets gamma = B_tilde/nu, but Theorem 1's constraint-violation bound (17) divides by (gamma - B_tilde/nu). At the stated gamma the denominator is zero, and the proof step (64) only yields (gamma - B_tilde/nu) E[w_T] <= ..., which is vacuous at equality. Since constraint violation is half of the epsilon-optimality definition (2), this is load-bearing. The fix is straightforward: either set gamma = (1+delta) B_tilde/nu with delta>0 and restate the theorem, or derive E[w_T] <= (E[F(x_bar_T)]-F(x_star))/gamma from the already-proved objective gap. As written, the theorem and algorithm are inconsistent.","section":"Section III-A, Theorem 1, Eq. (17) and Eq. (64); Algorithm 1"},{"comment":"The epsilon-optimality criterion (2) is stated with the sum of positive parts, sum_k E[(g_k(x))_+]. However, Theorem 1 bounds only max_k E[(g_k(x_bar_T))_+] (Eq. (17)), and no conversion to the sum is provided. Since sum_k E[(g_k)_+] can be up to m times max_k E[(g_k)_+], the stated SFO complexity does not directly imply the claimed epsilon-optimality criterion unless an extra factor depending on m is introduced. Theorem 3 similarly gives objective-gap and distance bounds but does not state a constraint-violation bound, so the claim that VARAS solves (P) in the sense of (2) is not fully supported. The authors should either change the definition of constraint violation to the max metric or state the additional m-dependent factor in the complexity bounds.","section":"Section I, Eq. (2); Section III-A, Theorem 1; Section IV, Theorem 3"},{"comment":"The Slater data (nu, B_tilde) are assumed known in Algorithm 1 and in all complexity bounds, yet the text in Section II-A notes that these 'must be found by parameter tuning.' If only a feasible point with unknown margin is available, the stated gamma cannot be computed, and the constants in the theorem (through L = max{gamma L_g, L_f}) change. This is a limitation of the practical applicability of the stated guarantees. It should be explicitly listed as a limitation or an additional knowledge assumption at the start, rather than left as an aside.","section":"Section II-A, Assumption A1; Section II-B"}],"minor_comments":[{"comment":"The displayed SFO and QMO complexity formulas are garbled: 'O(σ2/µ2ǫ + κ2 κ√δ0+σ√ǫ)' and the QMO expression need proper parentheses and denominators. They should read, for example, O(σ^2/(µ^2 ε) + κ^2(κ√δ0+σ)/√ε) and correspondingly for the QMO bound.","section":"Theorem 2, display after Eq. (22)"},{"comment":"The crossover analysis in Figure 4 is described only in words. Since the paper already defines M as the per-QP cost relative to an SFO call, a short formula or table of the critical M values would make the claim more precise and reproducible.","section":"Section V-B and Figure 4"},{"comment":"The step size condition in Lemma 2 is stated as η_t ≤ 1/(2(L_f + max{γL_g,L_f})). The proof actually uses the slightly more transparent conditions η_t ≤ 1/(2(L_f+γL_g)) and η_t ≤ 1/(4L_f). Stating all three conditions or adding a one-line derivation would improve readability.","section":"Appendix B, proof of Lemma 2"},{"comment":"The sentence 'For γ = B̃/ν ≥ ||µ⋆||_1' should clarify that equality is allowed as a limiting case; if γ = ||µ⋆||_1 exactly, the argument still yields v⋆=0 but the accompanying text could be misread as requiring strict inequality.","section":"Section II-B, paragraph after Eq. (13)"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the core algorithmic ideas are sound. The main issue is the gamma mismatch in Theorem 1, which is easily fixable, and the unaddressed sum-vs-max violation metric. I do not see circularity or inappropriate self-citation; self-citations are used in context. Once the theorem/algorithm consistency and the violation-metric issue are resolved, the paper could be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is a real algorithmic contribution, not a routine extension. The authors combine an exact-penalty reformulation with stochastic prox-linear updates, add a ProxSkip-style skipping variant, and an accelerated variance-reduced version (VARAS) for finite-sum problems. The one-step inequalities in Lemmas 1–2 are checkable, the telescoping arguments mostly hold together, and the finite-sum rates matching unconstrained accelerated variance-reduced methods are new for functional-constrained problems. The experiments on trajectory generation and constrained regression show the methods work well in practice and beat the primal–dual baselines by a wide margin.\n\nThe soft spot is load-bearing. Theorem 1's constraint-violation bound divides by γ − B̃/ν, while Algorithm 1 is stated with γ = B̃/ν. At that setting the denominator is zero, so the displayed bound is undefined. The proof only yields a positive left-hand side if γ > B̃/ν, so the theorem and algorithm as written contradict each other. This matters because the constraint-violation criterion is half of the ε-optimality definition. The fix is simple — choose γ = (1+δ)B̃/ν and pay the constant, or derive a direct bound on E[w_T] from the already-proved objective gap — but the current version is not correct as stated. The same γ appears in L = max{γLg, Lf}, so any tuning changes all complexity constants. The paper acknowledges ν and B̃ must be found by parameter tuning, which is honest but does not patch the theorem.\n\nMinor issues: no released code, single-run curves without error bars, and Theorem 3 leans heavily on importing VARAG/ProxSkip analyses. Those are addressable and not fatal. The self-citations are used as building blocks, not to hide circularity.\n\nThe reader's report got this right. The paper is worth a serious referee; it is not ready as-is because of the γ issue, but it is close. I would accept it conditionally if the authors fix the constraint-violation proof and add the strict-γ setting, and I hope they do — the core idea is sound and the rates are a genuine step forward for the subfield.","headline":"Genuinely new stochastic SQP framework; the constraint-violation bound in Theorem 1 is vacuous at the stated parameter setting, but the fix is simple and the paper deserves refereeing.","tokens_in":32831,"tokens_out":2584,"would_cite":true,"duration_ms":25935,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","90C55"],"pacs":[],"model":"deepseek-v4-flash","headline":"A stochastic SQP framework solves convex problems with functional constraints without projections or bounded-gradient assumptions, at oracle rates matching unconstrained SGD.","keywords":["stochastic convex optimization","functional constraints","sequential quadratic programming","exact penalty method","projection-free methods","variance reduction","oracle complexity","bounded-gradient-free"],"falsifier":"Take a two-variable problem with a single constraint g(x)=x₁²−1 on x₁∈[−2,2] with a known Slater margin, run SSQP with γ set to exactly B̃/ν (the algorithm's stated setting), and check whether the constraint-violation bound (17) holds; the theorem requires γ > B̃/ν, so with equality the right-hand side is infinite and the bound must be adjusted. A sharper test: compute the empirical SFO complexity on a smooth but unbounded-gradient objective (e.g., f(x)=x² with stochastic samples) and check whether it follows the predicted O(1/ε²) in the convex case or O(1/ε) in the strongly convex case; any s","tokens_in":31857,"feed_emoji":"🎯","tokens_out":3547,"duration_ms":38274,"temperature":0.7,"pith_summary":"The paper claims that stochastic sequential quadratic programming—minimizing a linearized objective plus an exact penalty for constraint violations—solves convex problems with nonlinear functional constraints at the same oracle complexity as unconstrained SGD, while never projecting onto the feasible set and never assuming bounded gradients. The key is an exact-penalty reformulation that turns the constrained problem into an unconstrained composite problem, solved by stochastic prox-linear steps that reduce to diagonal quadratic programs. Two variants extend the idea: SSQP-Skip solves the quadratic subproblem only sporadically, and VARAS boosts the finite-sum case with variance reduction and acceleration to match unconstrained rates. If correct, this removes two common restrictions of projection-free constrained methods—gradient boundedness and repeated projections—and brings constrained stochastic optimization in line with unconstrained rates.","feed_headline":"Constraint solver matches unconstrained SGD rates, no projections","feed_subtitle":"Stochastic SQP handles functional constraints with no bounded-gradient assumption, reaching finite-sum rates on par with unconstrained metho","key_machinery":"The central objects are the exact-penalty reformulation and the stochastic prox-linear update. Reformulating (P) as min_x f(x)+h(x)+γ max_k[g_k(x)]_+ turns the functional constraints into a non-smooth composite objective. The prox-linear update linearizes f and each g_k around the current iterate but keeps h and the max operator intact, producing a strongly convex diagonal QP that can be solved without projection. The proof machinery is a one-step inequality (Lemma 2) that couples objective decrease with a Bregman-divergence control of gradient noise, bounding the noise only at the optimum x* rather than globally.","core_discovery":"Under standard smoothness and convexity, the exact-penalty reformulation F(x)=f(x)+h(x)+γ max_k[g_k(x)]_+ is equivalent to the constrained problem (P) once γ ≥ B̃/ν, where ν is the Slater margin and B̃ the objective gap at a Slater point. SSQP applies a stochastic prox-linear step to this F, solving at each iteration a diagonal quadratic program whose constraints are linearizations of the g_k. Theorem 1 gives E[F(x̄_T)]−F(x*) ≤ (2/√T) max{2Lδ0, σ√δ0} and a constraint-violation bound of order 1/√T, with no bounded-gradient assumption. Theorem 2 shows SSQP-Skip needs only O(1/√ε) calls to the quadratic-programming oracle for strongly convex objectives. Theorem 3 gives VARAS an SFO complexity o","pith_inferences":["The diagonal-QP structure suggests that a single-constraint variant, or a variant that samples one constraint per iteration, may inherit similar rates while reducing per-iteration cost from O(m³) to O(m); the paper leaves this as an open problem.","Because the guarantees hinge on γ ≥ B̃/ν, an adaptive rule that grows γ from the dual values of the per-iteration subproblem—standard in SQP practice—could make the method parameter-free in practice; the paper notes this as future work.","If the one-step inequality transports to nonconvex functional constraints, a prox-linear analysis could yield stationarity guarantees at similar oracle complexity, though global optimality would be lost.","The rates suggest that constrained and unconstrained stochastic optimization no longer have a first-order oracle gap when functional constraints are explicit; this could change practical algorithm selection for constrained least-squares and set-membership filtering."],"forward_implications":["SSQP attains O(1/ε²) SFO complexity for convex objectives and O(1/ε) for strongly convex objectives, matching known primal–dual and primal methods while avoiding projections and bounded-subgradient assumptions.","Constraint violation at the averaged iterate is bounded by O(1/√T) whenever γ > B̃/ν, so feasibility is approached at the same rate as optimality.","SSQP-Skip reduces quadratic-programming oracle calls to O(1/ε^{1/4}) in the strongly convex case while preserving SFO complexity, useful when solving QPs is expensive.","VARAS matches unconstrained accelerated variance-reduced rates—O(√(nD0)/ε) SFO complexity for convex objectives and O(n log n + √(nκ) log(1/ε)) for strongly convex objectives—for finite-sum problems with functional constraints.","The analysis framework extends naturally to streaming and real-time settings, where tracking performance can be studied with similar tools."],"fun_headline_variants":["Stochastic SQP removes projection and bounded-gradient limits","Constrained optimization without projections or bounded gradients","Stochastic SQP matches unconstrained finite-sum rates","Primal-only stochastic SQP skips projections and gradient bounds","SQP for constrained problems: no projections, no bounded gradients"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The equivalence of the penalty reformulation and the stated rates depend on knowing the Slater margin ν and the optimality gap B̃ at a Slater point in advance, so that γ can be set to at least B̃/ν; if the Slater data is unavailable and γ is chosen by guesswork, the stated constants and feasibility guarantees no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic SQP removes projection and bounded-gradient limits","Constrained optimization without projections or bounded gradients","Stochastic SQP matches unconstrained finite-sum rates","Primal-only stochastic SQP skips projections and gradient bounds","SQP for constrained problems: no projections, no bounded gradients"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000714,"raw_usage":{"total_tokens":3066,"prompt_tokens":779,"completion_tokens":2287,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":2218}},"tokens_in":523,"tokens_out":2287,"duration_ms":15788,"temperature":1.0,"reasoning_tokens":2218,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:21:04.615392+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-variable problem with a single constraint g(x)=x₁²−1 on x₁∈[−2,2] with a known Slater margin, run SSQP with γ set to exactly B̃/ν (the algorithm's stated setting), and check whether the constraint-violation bound (17) holds; the theorem requires γ > B̃/ν, so with equality the right-hand side is infinite and the bound must be adjusted. A sharper test: compute the empirical SFO complexity on a smooth but unbounded-gradient objective (e.g., f(x)=x² with stochastic samples) and check whether it follows the predicted O(1/ε²) in the convex case or O(1/ε) in the strongly convex case; any s","supporting_citations":[],"review_version":1}