{"id":"2f35b84f-f890-4214-a408-1fd40af55501","arxiv_id":"1908.03077","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"A stochastic feasible level-set method maintains a high-probability feasible solution path for convex optimization with expectation constraints, with iteration complexity comparable to stochastic subgradient methods.","lead":"The paper designs an algorithm that keeps every intermediate solution within the constraints while solving optimization problems where both the goal and the limits are defined by large data sets. It matters when an infeasible answer is unacceptable, for example in fairness, risk, or safety constrained systems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's union bound incorrectly sums δ(k)=δ/2^k to δ, so the claimed 1−δ feasibility guarantee is not actually proven.","rationale":"The paper's central claim is that SFLS maintains a high-probability feasible solution at every root-finding iteration and returns a relative ε-optimal feasible solution with probability at least 1−δ. The most load-bearing point in that argument is the union bound over oracle failures: if the per-iteration failure probabilities are δ/2^k, the total failure probability is 2δ, so the stated 1−δ guarantee is not proven. This is an internal inconsistency in the proof, not a disagreement with consensus or a stylistic concern. The reader's weakest-assumption pick, Assumption 2 on light-tailed stochastic subgradients, is a standard condition for high-probability concentration and is satisfied by the bounded or truncated distributions used in the experiments; it is not the weakest link in the argument. The reader's secondary concern about implementation tuning is practical and is explicitly addressed by Corollary 2, which analyzes a fixed inner-iteration limit T, even though the constants are not verified numerically. The union-bound normalization error, by contrast, directly undermines the stated probability guarantee and should be fixed before the theorem is accepted as stated. Because the fix is straightforward and does not change the method or its complexity, the appropriate verdict remains conditional acceptance rather than rejection.","tokens_in":40809,"tokens_out":12230,"duration_ms":135247,"concrete_test":"Recompute the union bound in the proof of Theorem 1: with line 3's δ(k)=δ/2^k, we have ∑_{k=0}^K δ(k)=δ(2−2^{-K}), which tends to 2δ as K grows, not δ. Verify whether any factor elsewhere in the proof compensates for this factor of two; none appears. Then change Algorithm 1 line 3 to δ(k)=δ/2^{k+1} and re-check that Theorem 1 and Corollary 2 hold verbatim with the original probability 1−δ.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Algorithm 1, line 3, the per-iteration failure probability is set to δ(k)=δ/2^k. The proof of Theorem 1 (in the e-companion, immediately after inequality (EC.5)) relies on 'the fact that ∑_{k=0}^∞ δ(k)=δ'. But ∑_{k=0}^∞ δ/2^k = 2δ, not δ. Since the stochastic oracle call at iteration k fails with probability at most δ(k), a union bound over the k=0,...,K iterations before termination gives a failure probability of at most ∑_{k=0}^K δ/2^k ≤ 2δ. Thus the proof establishes feasibility of the whole path with probability at least 1−2δ, not 1−δ as claimed in Theorem 1, Lemma 2, and the abstract. The same normalization issue propagates into Corollary 2, where the total failure probability is again double-counted. This is a real but localized proof error: the fix is to set δ(k)=δ/2^{k+1}, exactly as Algorithm 4 already does with δ(h)=δ/2^{h+1}; then the sum is δ and the stated 1−δ guarantee follows from the same argument. The algorithmic idea and the oracle analysis are not affected, but the central high-probability claim of the paper is not supported as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces SFLS, a stochastic feasible level-set method for stochastic convex optimization problems with expectation constraints (SOECs). The SOEC is reformulated as a root-finding problem for the level-set function H(r), and the authors propose a new stochastic oracle, OVSMD, which combines stochastic mirror descent with online validation to compute tractable high-probability upper and lower estimates of H(r). The main theoretical results state that SFLS maintains a high-probability feasible solution at every root-finding iteration and returns a relative epsilon-optimal feasible solution within a prescribed number of oracle calls and gradient iterations. The paper also provides implementation guidelines and numerical experiments on approximate linear programming, Neyman-Pearson classification, and fairness-constrained learning, comparing SFLS with a stochastic subgradient method (YNW) and a deterministic feasible level-set method (DFLS).","tokens_in":41090,"tokens_out":5276,"duration_ms":54903,"significance":"If the results are correct, this is a meaningful contribution: it is, to the authors' knowledge, the first fully stochastic level-set method for SOECs that maintains a feasible solution path before convergence, and it offers low data complexity relative to deterministic feasible level-set methods. The theoretical framework is built on published mirror-descent and level-set results rather than ad hoc assumptions, and the electronic companion contains detailed proofs of the key inequalities in Lemmas EC.1 and EC.5. The explicit light-tail assumptions in Assumption 2 are restrictive but clearly stated; they do not make the argument circular. The numerical study on three diverse applications supports the practical claims, especially the advantage of SFLS over YNW in maintaining feasibility and over DFLS in data efficiency. The main concerns are localized proof and statement errors, not the overall algorithmic idea.","major_comments":[{"comment":"Algorithm 1, line 3, sets the per-iteration failure probability to δ(k)=δ/2^k, but the proof of Theorem 1 relies on the claim that ∑_{k=0}^∞ δ(k)=δ. In fact, ∑_{k=0}^∞ δ/2^k = 2δ, so the union bound as written establishes the feasible-path and terminal-solution guarantees only with probability at least 1−2δ, not 1−δ as stated in Theorem 1, Corollary 2, and the abstract. This is a load-bearing error in the central high-probability guarantee, but it is localized and easily fixed: set δ(k)=δ/2^{k+1}, which is exactly the normalization already used for δ(h) in Algorithm 4. With that change, the sum is δ and the stated 1−δ guarantee follows from the same argument.","section":"Algorithm 1 and proof of Theorem 1 (e-companion, after inequality (EC.5))"},{"comment":"The OVSMD-call complexity in Theorem 3 is stated as O((θ^2/β) ln(θ^2/((1−θ)βǫ))). Since θ>1, 1−θ is negative and the logarithm's argument is negative, so the expression is undefined as written. The proof combines the OVSMD-call bounds from Lemma EC.7 and Corollary 1, but the combined logarithmic term must have a positive argument; presumably it should involve (θ−1), as in Lemma EC.7's O(ln(θ/((θ−1)β))). This needs to be corrected before the theorem can be used.","section":"Theorem 3"}],"minor_comments":[{"comment":"Equation (13) defines the stochastic lower-bound estimate \\hat l(t)_* using G_y(x(s), y(s), ξ(s))^T(x−x(s)); this should be G_x, consistently with the definition of the lower bound l(t)_* and the text following Algorithm 3.","section":"Equation (13)"},{"comment":"The implementation guidelines tune T, θ, and the step-size constant c rather than computing the theoretical thresholds T(δ, ε_A) and δ, and Corollary 2 is invoked to justify this practice. The paper is transparent about this, but the numerical experiments should explicitly note that they are not a direct empirical verification of the quantitative bounds in Theorems 1–3, since those bounds require the theoretical parameter settings.","section":"Section 5.2"},{"comment":"The proof of Corollary 2 again defines δ(k)=δ/2^k and inherits the same union-bound normalization problem as Theorem 1; after the fix in Algorithm 1 is applied, the proof of Corollary 2 should use the corrected definition consistently.","section":"Proof of Corollary 2"}],"recommendation":"major_revision","confidential_remarks":"The union-bound normalization error in Theorem 1 is real but clearly localized, and the paper already contains the correct pattern in Algorithm 4. The sign error in Theorem 3's logarithmic term is also easily fixed. I therefore view this as a major-revision rather than a reject: the algorithmic idea and the oracle analysis are sound, and the required corrections do not change the structure of the proofs. I would encourage the authors to also make the theory-experiment gap in Section 5.2 more explicit, since the tuned implementation does not automatically inherit the theorems' probability guarantees as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The core contribution is real: this is the first fully stochastic feasible level-set method for expectation-constrained convex optimization, and it combines mirror descent with online validation in a way that previous work didn't. But the central high-probability claim in Theorem 1 isn't proven as written: in the e-companion, δ(k)=δ/2^k is used, and the proof says ∑_{k=0}^∞ δ(k)=δ. That sum is 2δ. Union-bounding over iterations gives 1−2δ, not 1−δ. The fix is simple—set δ(k)=δ/2^{k+1}, as Algorithm 4 already does—so the method and the oracle analysis survive, but the stated guarantee and its corollaries need correcting.\n\nWhat the paper does well: it identifies a real gap in stochastic first-order methods, namely that previous methods guarantee feasibility only at convergence and can return infeasible solutions when stopped early. SFLS maintains an implementable feasible solution at every outer iteration. The OVSMD oracle is a clever extension of Lan et al.'s online validation to a saddle-point setting, and the complexity result is on par with Yu et al. (2017) up to the condition measure, which is a reasonable price for feasibility. The e-companion proofs are detailed; Lemmas EC.1 and EC.5 are the backbone and they check out. The citation pattern is honest, including the relationship to the authors' earlier deterministic level-set work. The experimental sections cover three genuinely different applications, and the comparisons with YNW and DFLS support the data-complexity argument.\n\nSoft spots, in order of severity. The union-bound error is real but localized; it should not sink the paper, and it has an obvious correction. The practical implementation tunes T, θ, and the step-size constant instead of computing the theoretical thresholds, so the reported experiments do not strictly inherit the theorem's guarantees. That is common in first-order optimization, but worth stating more candidly. There is no code or data and no error bars in the figures. Assumption 2's exponential tail bounds are standard but rule out heavy-tailed data; if they fail, the oracle may not be valid. These are limitations, not fatal flaws.\n\nWho it's for: researchers working on stochastic constrained optimization, especially with application-motivated feasibility requirements. It deserves a serious referee. I would engage with it, and I'd recommend accepting it conditional on fixing the probability normalization and being clearer about what the numerics do and don't prove.","headline":"Genuine contribution to stochastic feasible level-set methods, but Theorem 1's probability guarantee is off by a factor of two due to a union-bound error that is easy to fix.","tokens_in":41599,"tokens_out":2868,"would_cite":true,"duration_ms":32975,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C25","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"A stochastic level-set method keeps expectation-constrained convex optimization feasible before convergence, reaching a relative $\\epsilon$-optimal feasible solution in $O(\\theta^2/(\\beta\\epsilon^2))$ gradient iterations up to logarithmic…","keywords":["stochastic convex optimization","expectation constraints","feasible level-set method","stochastic mirror descent","online validation","data complexity","root-finding","high-probability feasibility"],"falsifier":"Run OVSMD on a small SOEC where the noise distribution is heavy-tailed (for example, Student's $t$ with two degrees of freedom) using the theoretical inner-iteration limit $T(\\delta,\\epsilon_A)$, and check whether $P(r,\\bar x^{(t)})-H(r)\\le\\epsilon_A$ holds at a frequency close to $1-\\delta$; a significant shortfall would falsify the oracle guarantee.","tokens_in":40643,"feed_emoji":"🎯","tokens_out":7428,"duration_ms":73034,"temperature":0.7,"pith_summary":"Stochastic convex optimization problems with expectation constraints (SOECs) arise whenever the objective and constraints are averages over large datasets, and existing stochastic first-order methods only guarantee near-feasibility at convergence, so early termination can produce infeasible solutions. This paper proposes a stochastic feasible level-set method (SFLS) that solves the problem by finding the root of a level-set function, using a stochastic oracle that computes upper and lower bounds on that function without evaluating expectations exactly. The central claim is that SFLS keeps a high-probability feasible solution at every root-finding iteration and finds a relative $\\epsilon$-optimal feasible solution in $O(\\theta^2/(\\beta\\epsilon^2))$ gradient iterations up to logarithmic factors, where $\\beta$ is a condition measure of the problem. If correct, this means feasibility can be guaranteed before convergence, at a data cost that does not grow with the dataset size, which matters for applications where constraint violations void the solution. The paper supports the claim with theory and experiments on approximate linear programs, Neyman-Pearson classification, and fairness-constrained learning.","feed_headline":"Stochastic level-set method keeps solutions feasible before convergence","feed_subtitle":"High-probability feasible solutions at every step, with gradient cost growing only inverse-quadratically in the target gap.","key_machinery":"The load-bearing object is the level-set function $H(r):=\\min_{x\\in X}\\max\\{f_0(x)-r,f_1(x)-r_1,\\dots,f_m(x)-r_m\\}$, whose root is the optimal value $f^*$; keeping the level parameter above $f^*$ guarantees that the minimizing point is feasible. SFLS solves $H(r)=0$ by root-finding, and each oracle call is executed by OVSMD, which solves the equivalent saddle-point reformulation $H(r)=\\min_{x\\in X}\\max_{y\\in Y}\\sum_{i=0}^m y_i(f_i(x)-r_i)$ via stochastic mirror descent. The online-validation step replaces exact expectations by weighted sums of stochastic function values and subgradients, which still upper- and lower-bound $H(r)$ with high probability; this is what converts an idealized but unimplementable oracle into a tractable one without sample-average bias. The complexity statements are governed by the condition measure $\\beta=-H(r^{(0)})/(r^{(0)}-f^*)$, the slope of the level-set function at the root.","core_discovery":"The paper's discovery is that a tractable stochastic oracle can be built for the nonsmooth level-set function by reformulating it as a saddle-point problem and applying mirror descent together with online validation. The oracle returns a stochastic upper bound $\\hat u^{(t)}_*$ and a primal solution $\\bar x^{(t)}$ such that, with probability at least $1-\\delta$, $P(r,\\bar x^{(t)})-H(r)\\le \\epsilon_A$ and $|\\hat u^{(t)}_*-H(r)|\\le \\epsilon_A$ after finitely many gradient iterations. Feeding this oracle into a root-finding scheme yields a feasible solution at each outer iteration, and the total complexity to reach a relative $\\epsilon$-optimal feasible solution is $O((\\theta^2/(\\beta\\epsilon^2))\\ln(\\theta^2/(\\beta\\epsilon))\\ln^2(1/\\delta)\\ln^2(1/\\epsilon))$ gradient iterations under the stated assumptions. This is a fully stochastic feasible level-set method for SOECs with generic expectation constraints, avoiding the bias and high data complexity of sample-average approximations inside the oracle.","pith_inferences":["Editorial inference: the same online-validation oracle could be plugged into other root-finding or cutting-plane frameworks for stochastic convex optimization, not just level-set methods, whenever a feasible iterate is required at every call.","Editorial inference: replacing the fixed step-size scaling with an adaptive estimate of subgradient magnitude is a testable extension that might soften the condition-measure $\\beta$ dependence on ill-conditioned instances.","Editorial inference: the heavy-tailed caveat suggests a concrete stress test, namely data with infinite variance, where the high-probability feasibility guarantee would likely degrade and would need truncation or robust gradient estimators.","Implementation caveat visible in the paper itself: Section 5.2 proposes choosing the inner-iteration limit $T$ by tuning rather than by the theoretical formula, so the numerical experiments should be read as validating practical behavior rather than as a direct confirmation of the high-probability oracle bound."],"forward_implications":["If the central claim is correct, stochastic first-order methods need not sacrifice feasibility: SFLS can be terminated after any outer iteration and still return a solution that is feasible with probability at least $1-\\delta$.","The gradient-iteration bound is comparable to the best stochastic subgradient methods that only guarantee feasibility at convergence, so feasibility comes at the price of a condition-measure dependence rather than a worse dependence on $\\epsilon$.","Because each stochastic gradient uses only a small sample batch, the number of data passes needed to reach a small optimality gap is independent of the dataset size, unlike deterministic feasible level-set methods built on sample-average approximations.","In the tested applications, the practical consequence is that SFLS produces implementable, feasible classifiers or value-function bounds with small optimality gaps before conservative theoretical stopping rules would trigger, while a stochastic subgradient benchmark can return superoptimal but infeasible solutions."],"supporting_citations":[{"why":"Provides the stochastic mirror descent framework and the concentration inequalities used to prove the oracle's complexity.","marker":"Nemirovski et al. 2009"},{"why":"Supplies the online validation technique that OVSMD extends from minimization problems to saddle-point problems.","marker":"Lan et al. 2012"},{"why":"Is the deterministic feasible level-set method that SFLS stochasticizes and whose condition-measure complexity is the baseline for comparison.","marker":"Lin et al. 2018b"},{"why":"Is the stochastic subgradient method for expectation-constrained problems that serves as the main benchmark and feasibility-at-convergence comparison.","marker":"Yu et al. 2017"},{"why":"Provides the properties of the level-set function $H(r)$ that justify the root-finding reformulation.","marker":"Nesterov 2004"},{"why":"Shows a variance-reduced level-set method for finite-sum problems that cannot handle generic expectations, motivating the fully stochastic oracle.","marker":"Lin et al. 2018a"}],"fun_headline_variants":["Stochastic level-set method keeps every iterate feasible","New oracle makes feasible solutions cheap and fast","Feasibility-first algorithm for expectation-constrained optimization","Data-efficient SFLS: feasible before convergence","Feasible solutions on every step with low gradient cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole high-probability guarantee rests on Assumption 2, which requires the stochastic subgradients and function values to have exponential tail bounds (light tails); if the data distribution is heavy-tailed, the oracle may fail to be a valid stochastic oracle and the feasible-path guarantee does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic level-set method keeps every iterate feasible","New oracle makes feasible solutions cheap and fast","Feasibility-first algorithm for expectation-constrained optimization","Data-efficient SFLS: feasible before convergence","Feasible solutions on every step with low gradient cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1350,"prompt_tokens":1056,"completion_tokens":294,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":221}},"tokens_in":672,"tokens_out":294,"duration_ms":3545,"temperature":1.0,"reasoning_tokens":221,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:40:01.315541+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OVSMD on a small SOEC where the noise distribution is heavy-tailed (for example, Student's $t$ with two degrees of freedom) using the theoretical inner-iteration limit $T(\\delta,\\epsilon_A)$, and check whether $P(r,\\bar x^{(t)})-H(r)\\le\\epsilon_A$ holds at a frequency close to $1-\\delta$; a significant shortfall would falsify the oracle guarantee.","supporting_citations":[{"cited_title":"SIAM Journal on Optimization 19(4):1574--1609","cited_arxiv_id":null,"evidence_quote":"Provides the stochastic mirror descent framework and the concentration inequalities used to prove the oracle's complexity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the properties of the level-set function $H(r)$ that justify the root-finding reformulation."}],"review_version":1}