{"id":"408b73d3-0726-421b-9c99-dcbc4321609c","arxiv_id":"2506.20630","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New first-order methods compute surely feasible approximate solutions to constrained stochastic convex problems with optimal or near-optimal oracle complexity.","lead":"This paper develops stochastic optimization algorithms that guarantee hard constraints are nearly satisfied on every run, not just on average. It proves these methods match the best-known speed limits for unconstrained stochastic convex optimization while adding this stronger safety guarantee.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Surely feasible guarantee for infinite sample spaces rests on Assumption 2's uniform almost-sure gradient bound; without it Algorithm 1 only gives in-expectation or high-probability feasibility.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing point: the deterministic (surely feasible) constraint-violation guarantee depends critically on Assumption 2's uniform almost-sure gradient bound. My independent read of the proof confirms that Lemma 3's pathwise bound on delta_k (eq. (56)) is the step that converts noise into a deterministic constraint guarantee, and without it the epsilon-SFSO claim for Algorithm 1 degrades. I found no internal error in the main theorems: the complexity calculations balance correctly, and minor algebraic slips (e.g., the factor 2/6 in the proof of Theorem 1) are conservative and do not affect the order. The SAA section does have a small gap where E[|F_bar^* - F^*|] is bounded by a pointwise deviation bound rather than a uniform one, but that is a byproduct, not the central claim. Since the reader's CONDITIONAL verdict already accounts for the three concrete issues it lists, and the Assumption 2 concern is captured in the reader's weak_assumption field, the verdict should remain UNCHANGED.","tokens_in":47634,"tokens_out":28774,"duration_ms":283148,"concrete_test":"Analytically: attempt to re-derive Lemma 3's deterministic bound on F_rho(x_k) - F*_rho using only the variance bound E[||delta_k||^2] <= sigma^2 instead of Assumption 2. If the best possible bound is in-expectation rather than almost sure, then inequality (10) has no deterministic counterpart and the epsilon-SFSO claim for Algorithm 1 fails without the uniform max-norm assumption. Computationally: run Algorithm 1 on a problem with unbounded gradients, e.g., min_x E[(xi^T x - 1)^2] with xi ~ N(0, I) and a deterministic constraint, and measure the maximum constraint violation over 10^4 independent runs; if positive violation occurs with non-negligible frequency for the predicted iteration count, the pathwise bound is essential.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline contribution for infinite sample spaces is the O(epsilon^{-2}) complexity of Algorithm 1 for an epsilon-SFSO solution, where the constraint violation is deterministically bounded by epsilon. The proof of this deterministic guarantee relies essentially on Assumption 2's uniform, almost-sure bound max_{xi in Xi} ||grad f~(x, xi)|| <= G for all x in X. This enters Lemma 3 through the pathwise inequality ||delta_k|| <= 2G (eq. (56)), which converts the stochastic noise in the recursion for F_rho(x_k) - F*_rho into a deterministic bound. That deterministic bound is the only mechanism that makes the constraint violation small with certainty: via Lemma 1, inequality (46) turns F_rho(x_K) - F*_rho into ||[c(x_K)]_+|| <= ... and if the noise is only bounded in variance, the pathwise terms gamma_i ||delta_i|| are uncontrolled, so the proof yields no nearly-sure feasibility guarantee. Since Assumption 2 excludes many natural stochastic optimization models (e.g., unbounded or heavy-tailed gradients), the infinite-sample 'surely feasible' result is conditional on a strong, undiscussed restriction. This is a scope limitation rather than an internal contradiction: the theorem is true as stated, but the central claim would be materially weaker if Assumption 2 were relaxed. The finite-sum Algorithm 2 avoids this issue by using deterministic smoothness bounds on the SVRG noise, but the infinite-sample half of the abstract does not.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes first-order methods for convex stochastic or finite-sum optimization with deterministic convex constraints, targeting ε-surely feasible stochastic optimal (ε-SFSO) solutions, i.e., deterministic constraint violation at most ε and expected optimality gap at most ε. For infinite sample spaces, Algorithm 1 applies an accelerated stochastic gradient scheme once to a sequence of quadratic penalty problems; under Assumptions 1–2 it is claimed to compute an ε-SFSO solution with FO complexity O(ε^{-2}) for constant penalty parameters and Õ(ε^{-2}) for dynamic ones. For finite-sum problems, Algorithm 2 uses a modified variance-reduced accelerated scheme with exact penalty gradients, obtaining O(s log s + √s ε^{-3/2}) for ε-SFSO and O(s log s + √s ε^{-1}) for ε-EFSO when m=O(1). Section 4 analyzes SAA, yielding O(ε^{-2}) for ε-EFSO and O(ε^{-5/2}) for ε-SFSO. The proofs are detailed, with explicit constants and lemmas leading to Theorems 1–4.","tokens_in":47878,"tokens_out":13112,"duration_ms":138607,"significance":"The deterministic feasibility guarantee is stronger than the commonly studied expected-feasibility notion, and the claimed infinite-sample complexity O(ε^{-2}) matches the unconstrained stochastic oracle bound. The finite-sum analysis with separation of stochastic and deterministic gradient contributions is a meaningful technical contribution, and the SAA byproduct gives concrete complexity comparisons. The paper is self-contained: it proves its own Lemmas 3–10 rather than importing the central recursion, and the main rates are internally consistent. The principal caveats are the strong uniform almost-sure gradient bound required for the infinite-sample deterministic feasibility claim, and the unsupported deterministic s=1 optimal-complexity remarks.","major_comments":[{"comment":"The ε-SFSO guarantee of Algorithm 1 for infinite sample spaces rests essentially on the uniform almost-sure bound in Assumption 2. In Lemma 3, inequality (56) bounds the noise pathwise as ∥δ_i∥ ≤ 2G, which is the only mechanism converting the recursion for F_ρ(x_K) − F*_ρ into a deterministic bound; Lemma 1(46) then yields the deterministic constraint violation in Theorem 1. If Assumption 2 is weakened to a variance bound only, the pathwise terms γ_i∥δ_i∥ are uncontrolled, and only an in-expectation or high-probability feasibility statement follows. The abstract and Remark 1 state the O(ε^{-2}) 'surely feasible' result without flagging this restriction. I recommend adding an explicit scope-limitation statement and, if possible, a companion in-expectation feasibility result under weaker noise assumptions.","section":"Assumption 2; Lemma 3; Theorem 1"},{"comment":"The special-case deterministic O(ε^{-1}) claims are not consequences of the stated theorems. For s=1, Theorem 3(ii) with ρ = √s K = K gives the bound ∥[c(˜x_K)]_+∥ ≤ 8 L_{∇ḟ}^{1/2} D_X K^{-1/2} + ... (first displayed bound after Theorem 3(ii)), so the theorem yields O(ε^{-2}) rather than O(ε^{-1}); the K^{-1/2} term originates from the K-independent term 16 L_{∇ḟ} D_X² in Lemma 8 (80), which decays only through division by ρ. Similarly, Theorem 4(ii) bound (35) has first term 60 L_{∇ḟ}^{1/2} D_X s^{-1/4}k^{-1/2}, giving O(k^{-1/2}) for s=1. If the intended argument is that δ_t=0 in the deterministic case and the noise term vanishes, that analysis must be supplied; otherwise Remarks 3(iii) and 4(iii) should be corrected.","section":"Remarks 3(iii), 4(iii); Theorem 3(ii); Theorem 4(ii)"}],"minor_comments":[{"comment":"There is a typo: 'togther' should be 'together'.","section":"Section 6.2, after eq. (110)"},{"comment":"In Assumption 2, the variance bound E∥∇f~(x,ξ)−∇f(x)∥² ≤ σ² is implied by the uniform almost-sure bound G via σ ≤ 2G; stating both is fine, but the redundancy could be noted.","section":"Notation, Section 1.1"},{"comment":"The equality O(s log s + √s ε^{-3/2}) = O(ε^{-5/2}) suppresses the logarithmic factor in s; writing O(ε^{-5/2} log(1/ε)) would be more precise.","section":"Section 4, Approach 2"},{"comment":"The notation ˜x_{k+1} = Σ_{t=1}^{T_k} θ_t x_t / Σ_{t=1}^{T_k} θ_t is clear, but the dependence of θ_t on k is implicit; a subscript θ_{k,t} would aid readability.","section":"Algorithm 2, line 11"}],"recommendation":"major_revision","confidential_remarks":"The main theorems appear internally consistent and the assumptions are explicit, so I see no grounds for rejection. However, the Assumption 2 restriction is load-bearing for the central infinite-sample 'surely feasible' claim and should be prominently disclosed, and the deterministic s=1 optimal-complexity remarks are not supported by the displayed bounds. Both issues are fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zhaosong and Yifeng introduce the epsilon-SFSO notion—deterministic constraint violation plus expected optimality gap—and show that first-order methods can achieve it with the same oracle complexity as unconstrained stochastic optimization: O(epsilon^{-2}) for infinite sample spaces, O(s log s + sqrt(s) epsilon^{-3/2}) for finite sums. That is a real contribution. The proofs are detailed and, as far as I can tell on close reading, internally consistent. The penalty parameter choices in Theorems 1 and 3 balance the objective and violation terms correctly, and the paper properly separates the variance-reduced estimator for the finite-sum objective from the exact gradient of the penalty term. The complexity claims for epsilon-SFSO are new, and matching the unconstrained rate for a stronger feasibility guarantee is worth having.\n\nThe main soft spot is the infinite-sample result. Algorithm 1's deterministic violation bound relies on Assumption 2's uniform almost-sure gradient bound max_xi ||grad f~(x,xi)|| <= G. That is a strong condition; it excludes heavy-tailed or unbounded stochastic gradients, which are common in practice. The stress-test note is right: without it, the proof only gives in-expectation or high-probability feasibility. This is a scope limitation, not an internal contradiction—the theorem is true as stated—but the abstract's \"with certainty\" framing should be clearer about the assumption's cost.\n\nTwo smaller issues. First, the intro claims this is the first work to give a complexity bound for an epsilon-EFSO solution, but [5] already gives O(epsilon^{-2}) for an expected-violation guarantee of exactly that kind. The authors should soften the novelty claim. Second, the numerical experiments are single runs with no error bars and no released code; they are illustrative only, and the text should say so.\n\nNone of this undermines the central results. The finite-sum algorithm's guarantee does not need the uniform bound, and the deterministic penalty analysis is solid. This paper deserves a serious referee; the comments above are the ones I would want the authors to answer in revision.","headline":"A genuinely useful strengthening of the feasibility guarantee, with careful proofs; the infinite-sample result is conditional on a strong uniform gradient bound, and the numerical section is light.","tokens_in":48448,"tokens_out":2495,"would_cite":false,"duration_ms":25796,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C25","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stochastic solutions can meet hard constraints surely at no extra cost","keywords":["stochastic convex optimization","finite-sum optimization","deterministic constraints","surely feasible stochastic optimal solution","quadratic penalty","accelerated stochastic gradient","variance reduction","sample average approximation"],"falsifier":"Run Algorithm 1 on a constrained stochastic convex problem satisfying all assumptions except the uniform bound $\\max_{\\xi\\in\\Xi}\\|\\nabla\\tilde f(x,\\xi)\\|\\le G$, for example $\\tilde f(x,\\xi)=\\xi^\\top x$ with $\\xi$ standard normal so the stochastic gradient is unbounded, and check whether $\\|[c(x_K)]_+\\|\\le\\epsilon$ holds with probability one at the claimed $O(\\epsilon^{-2})$ gradient budget; a single output with positive-probability violation above $\\epsilon$ falsifies the SFSO claim.","tokens_in":1823,"feed_emoji":"🎯","tokens_out":4337,"duration_ms":157785,"temperature":0.7,"pith_summary":"Stochastic convex optimization with deterministic hard constraints usually settles for expected constraint violation. This paper asks for a certificate that the violation is at most epsilon with certainty, and shows it can be obtained by running an accelerated stochastic gradient scheme just once on a sequence of quadratic penalty subproblems. For infinite sample spaces the first-order oracle complexity is $O(\\epsilon^{-2})$ gradient evaluations, the same order as for unconstrained stochastic optimization. For finite sums with a bounded number of constraints the complexity is $O(s\\log s + \\sqrt{s}\\,\\epsilon^{-3/2})$ for a surely feasible solution, or $O(s\\log s + \\sqrt{s}\\,\\epsilon^{-1})$ for the weaker expected-feasibility notion. The analysis also yields sample average approximation complexities under the same guarantees.","feed_headline":"Stochastic solutions can meet hard constraints surely at no extra cost","feed_subtitle":"A single pass over quadratic penalties bounds constraint violation and expected gap by epsilon.","key_machinery":"The load-bearing object is the quadratic penalty subproblem $F_\\rho(x)=F(x)+\\tfrac{\\rho}{2}\\|[c(x)]_+\\|^2$ together with Lemma 1's bound $\\|[c(x)]_+\\| \\le 2\\Lambda/\\rho + \\sqrt{2(F_\\rho(x)-F^*_\\rho)/\\rho}$. This inequality shows that controlling the penalty suboptimality $F_\\rho(x)-F^*_\\rho$ and choosing a large enough $\\rho$ yields a deterministic bound on the original constraint violation, and the paper selects $\\rho$ as a power of the horizon $K$ so that the two terms balance. Algorithm 1 applies an accelerated stochastic gradient scheme once to a sequence of these penalty problems, while Algorithm 2 runs a modified variance-reduced accelerated scheme in which the stochastic estimator approximates only the finite-sum objective and the penalty gradient is computed exactly, keeping the noise confined to the objective component.","core_discovery":"The paper establishes that an $\\epsilon$-surely feasible stochastic optimal ($\\epsilon$-SFSO) solution, meaning a point $x$ with $\\|[c(x)]_+\\| \\le \\epsilon$ and $E[|F(x)-F^*|] \\le \\epsilon$, can be computed by a single loop of accelerated stochastic gradient steps applied to the quadratic penalty problems $F_\\rho(x)=E[\\tilde f(x,\\xi)]+\\psi(x)+\\tfrac{\\rho}{2}\\|[c(x)]_+\\|^2$ with suitably chosen penalty parameters $\\rho$. For infinite sample spaces, Algorithm 1 achieves first-order oracle complexity $O(\\epsilon^{-2})$ with constant penalty $\\rho=K^{3/2}$ and $\\tilde O(\\epsilon^{-2})$ with dynamic penalties, where the oracle counts gradient evaluations during a single pass. For finite sums of size $s$, Algorithm 2 uses a variance-reduced estimator for the average of the $f_i$ and an exact gradient for the penalty term, and under $m=O(1)$ finds an $\\epsilon$-SFSO solution in $O(s\\log s + \\sqrt{s}\\,\\epsilon^{-3/2})$ gradient evaluations, with the weaker $\\epsilon$-expectedly feasible variant at $O(s\\log s + \\sqrt{s}\\,\\epsilon^{-1})$. The proof transfers stochastic suboptimality of the penalty problem into a deterministic feasibility bound through Lemma 1, so the noise only enters the optimality gap while the constraint violation stays deterministic.","pith_inferences":["One can infer that the deterministic certificate depends on the uniform almost-sure gradient bound in Assumption 2; under heavy-tailed or unbounded noise, the randomness would leak into the constraint violation, and recovering a usable certificate would require a probabilistic analogue of that assumption.","The penalty parameter recipes $\\rho=K^{3/2}$ and $\\rho=s^{2/3}K^{4/3}$ instantiate a general balance between constraint violation and objective gap, and the same trade-off could govern penalty-based stochastic and augmented Lagrangian methods beyond the two algorithms analyzed here.","A direct stress test is to replace the uniform bound with a bounded-variance or sub-Gaussian assumption and measure how the deterministic feasibility certificate degrades, which would show when 'surely feasible' claims are genuinely available."],"forward_implications":["Infinite-sample stochastic convex problems with deterministic constraints admit $\\epsilon$-SFSO solutions at $O(\\epsilon^{-2})$ gradient evaluations, the same order as the unconstrained case, so the constraints cost nothing in the epsilon-dependence.","For finite sums with $m=O(1)$, Algorithm 2 finds $\\epsilon$-SFSO solutions in $O(s\\log s + \\sqrt{s}\\,\\epsilon^{-3/2})$ evaluations and $\\epsilon$-EFSO solutions in $O(s\\log s + \\sqrt{s}\\,\\epsilon^{-1})$.","Combined with sample average approximation, the proposed solvers yield $O(\\epsilon^{-2})$ for $\\epsilon$-EFSO and either $O(\\epsilon^{-3})$ or $O(\\epsilon^{-5/2})$ for $\\epsilon$-SFSO solutions of the original infinite-sample problem.","In the deterministic special case $s=1$, Algorithm 2 becomes a single-loop first-order penalty method with optimal $O(\\epsilon^{-1})$ or nearly optimal $\\tilde O(\\epsilon^{-1})$ complexity.","The framework extends directly to affine equality constraints and to convex conic constraints $c(x)\\in-K$ with an exactly computable projection, covering conic programs beyond ordinary inequalities."],"supporting_citations":[{"why":"Supplies the accelerated stochastic gradient scheme that Algorithm 1 applies once to each penalty subproblem, together with its convergence estimates.","marker":"[18]"},{"why":"Provides the variance-reduced accelerated gradient loop that Algorithm 2 modifies, and the lemmas its analysis borrows.","marker":"[19]"},{"why":"Supplies the concentration inequality used to bound the gap between the sample average objective and the true expectation in the sample average approximation analysis.","marker":"[13]"},{"why":"Provides the extra anchored gradient method used as the nearly optimal deterministic solver in the sample average approach and as the comparison baseline in the experiments.","marker":"[17]"},{"why":"Provides a nearly optimal deterministic first-order solver for the sample average problem in the complexity comparison.","marker":"[23]"},{"why":"Provides another nearly optimal deterministic first-order solver whose iteration complexity feeds the sample average SFSO bound.","marker":"[37]"}],"fun_headline_variants":["Single-pass method ensures constraints hold within epsilon","Stochastic optimality with deterministic feasibility bounds","Hard constraints, no risk: epsilon-surely feasible solutions","Quadratic penalty trick yields sure feasibility in one loop","Finite-sum and stochastic: constraints satisfied with certainty"],"cache_read_input_tokens":50560,"weakest_assumption_plain":"The deterministic constraint-violation guarantee depends on a uniform almost-sure bound on the norm of the stochastic gradient over the whole feasible domain; without that bound the method's output can only be certified in expectation or with high probability, not surely.","fun_headline_variants_meta":{"raw":{"variants":["Single-pass method ensures constraints hold within epsilon","Stochastic optimality with deterministic feasibility bounds","Hard constraints, no risk: epsilon-surely feasible solutions","Quadratic penalty trick yields sure feasibility in one loop","Finite-sum and stochastic: constraints satisfied with certainty"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1578,"prompt_tokens":1068,"completion_tokens":510,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":437}},"tokens_in":684,"tokens_out":510,"duration_ms":6737,"temperature":1.0,"reasoning_tokens":437,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:43:57.787981+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a constrained stochastic convex problem satisfying all assumptions except the uniform bound $\\max_{\\xi\\in\\Xi}\\|\\nabla\\tilde f(x,\\xi)\\|\\le G$, for example $\\tilde f(x,\\xi)=\\xi^\\top x$ with $\\xi$ standard normal so the stochastic gradient is unbounded, and check whether $\\|[c(x_K)]_+\\|\\le\\epsilon$ holds with probability one at the claimed $O(\\epsilon^{-2})$ gradient budget; a single output with positive-probability violation above $\\epsilon$ falsifies the SFSO claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the variance-reduced accelerated gradient loop that Algorithm 2 modifies, and the lemmas its analysis borrows."},{"cited_title":"Hoeffding","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration inequality used to bound the gap between the sample average objective and the true expectation in the sample average approximation analysis."},{"cited_title":"Kovalev and A","cited_arxiv_id":null,"evidence_quote":"Provides the extra anchored gradient method used as the nearly optimal deterministic solver in the sample average approach and as the comparison baseline in the experiments."},{"cited_title":"Lu and Z","cited_arxiv_id":null,"evidence_quote":"Provides a nearly optimal deterministic first-order solver for the sample average problem in the complexity comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides another nearly optimal deterministic first-order solver whose iteration complexity feeds the sample average SFSO bound."}],"review_version":1}