{"id":"9952e494-69c9-4c1c-b3de-f6209451c050","arxiv_id":"2412.02338","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A stochastic halfspace projection method with flexible linearization point achieves O(1/sqrt(k)) optimality and feasibility violation for convex smooth objectives with nonsmooth constraints, and O(1/k) under strong convexity.","lead":"This paper introduces SHAM, an algorithm that solves convex optimization problems with many nonsmooth constraints by alternating gradient steps with projections onto random halfspace approximations of the constraints. It proves convergence rates of O(1/sqrt(k)) for convex objectives and O(1/k) for strongly convex ones, and shows practical speedups over a standard solver on large random problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Feasibility-rate proof rests on linear regularity (Assumption 2.3); this can fail for tangential constraints such as h(x)=x^2, so the advertised O(1/sqrt k)/O(1/k) guarantee is not as general as claimed.","rationale":"The proofs of Theorems 4.5-4.8 are internally coherent: Lemmas 4.1-4.4 check out under the stated assumptions, and the averaging arguments in Theorems 4.6 and 4.8 are standard. The only place where a nontrivial global geometric condition enters is Lemma 2.4. That lemma is genuinely load-bearing: it is the sole bridge from the computable halfspace-projection error to dist(.,X), and it is used in Lemma 4.2, Lemma 4.4, and therefore in the main recurrence (19). I agree with the reader's identification of Assumption 2.3 as the weakest assumption. I did not find a fatal algebraic error in the recurrences; the strongly convex rate constants in Theorem 4.8 are loose, and the strict O(1/sqrt k) claim in the convex case carries a logarithmic factor for the standard stepsize choice, but the O(1/k) order survives. Thus the verdict should remain conditional: the mathematical contribution is real under Assumption 2.3, but the scope of the advertised guarantees is narrower than the title and abstract suggest. The numerical comparison to CVX is also not a reliable demonstration of practical advantage because it uses a general-purpose interior-point solver on small random instances with early stopping, and no code or data are provided. The proposed concrete test isolates whether Assumption 2.3 is a proof-only restriction or an actual algorithmic limitation.","tokens_in":15935,"tokens_out":27448,"duration_ms":295774,"concrete_test":"Analytical check: for h(x)=x^2 on Y=[-1,1], verify that Assumptions 2.1(ii), 2.2, and 3.1 hold but (6) fails, because sup_{x != 0} |x| / x^2 = infinity; hence Lemma 2.4 has infinite constant and Theorem 4.6's feasibility bound is inapplicable. To see whether this is only a proof obstruction rather than an algorithmic failure, run SHAM (Algorithm 1 with beta = 0.96, alpha_k = alpha_0 / sqrt(k), uniform j_k) on min 0.5 x^2 subject to x^2 <= 0 and record dist^2(hat x_k, {0}). If the empirical rate is O(1/sqrt k) or better, the assumption is sufficient but not necessary, and the stated theorem still does not certify the example; if it degrades or stalls, the assumption is also necessary in practice. Either outcome clarifies the scope of the central claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The convergence argument converts random halfspace projection error into distance to the feasible set exclusively through Lemma 2.4, which uses Assumption 2.3 (linear regularity). Lemma 4.2 then bounds dist^2(tilde x_k, X) by E[||v_k - Pi_{L_{j_k}}(v_k)||^2] with factor m c^2 B_h^2 / rho; this factor enters the main recurrence (19) and both Theorem 4.6 and Theorem 4.8. If (6) fails, the proof has no quantitative link between the halfspace-projection term and feasibility, so the stated O(1/sqrt k) and O(1/k) feasibility bounds do not follow. This is not a merely technical gap: the condition can fail while the paper's other assumptions hold. Example: Y = [-1,1], h(x) = x^2, X = {0}. Here h is smooth and convex, subgradients are bounded on Y, but max_j [h_j(x)]_+ = x^2 while dist(x,X) = |x|, so no finite c satisfies (6) near x=0. The paper's own justification (nonempty interior or polyhedral X) does not cover this case. Since the claimed rates are the central contribution, the practical scope is narrower than the title and abstract suggest; moreover, the rate constants depend on c^2 and B_h^2, which are generally unknown, so even when (6) holds the bounds can be vacuous for finite k.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers problem (1): minimize a smooth convex or strongly convex objective f over a simple set Y subject to convex, possibly nonsmooth functional constraints h_j(x) <= 0. It introduces Stochastic Halfspace Approximation Method (SHAM), Algorithm 1, in which each iteration performs a gradient step on f, projects onto Y, and then moves the iterate toward the projection of v_k onto a random halfspace approximation of one constraint. The linearization point is chosen as tilde x_k = gamma v_k + (1-gamma) x_k for gamma in [0,1], which unifies several previously studied and new strategies. Section IV proves a general recurrence (Theorem 4.5) and then derives rates O(1/sqrt(k)) for convex f and O(1/k) for strongly convex f, for both optimality gap and squared feasibility violation at weighted average points. Section V reports CPU-time comparisons with CVX on SOC-constrained quadratic problems.","tokens_in":16251,"tokens_out":25275,"duration_ms":241577,"significance":"If the results are correct, the main contribution is a unified convergence analysis for infinitely many halfspace linearization strategies, including the previously studied tilde x_k = v_k and the new tilde x_k = x_k, with state-of-the-art rates and no fitted constants in the proof. The derivation is first-principles given the explicit Assumptions 2.1-2.3 and 3.1, and the main recurrence (19) is internally consistent. The numerical experiments illustrate the algorithm on nontrivial second-order cone problems. The principal caveat is that the feasibility rates are proved only under the linear regularity condition (6), a restriction that is not advertised in the abstract or introduction.","major_comments":[{"comment":"The feasibility-rate claims are conditional on the linear regularity assumption (6), and this restriction should be stated in the abstract and introduction. Equation (6) is used in Lemma 2.4 to convert halfspace-projection distance into dist(x,X), and that lemma enters Lemma 4.2, Lemma 4.4, and hence the main recurrence (19). The assumption is not implied by the other assumptions: take Y=[-1,1], h(x)=x^2, and X={0}; then dist(x,X)=|x| while max_j[h_j(x)]_+ = x^2, so no finite c satisfies (6). The sufficient conditions mentioned in the text (nonempty interior or polyhedrality) do not cover this example. As written, the paper's title and abstract suggest the rates hold for the general class of convex nonsmooth functional constraints, but the proof does not establish that. Please either qualify the claims or discuss whether a weaker error-bound condition can replace (6).","section":"Section II, Assumption 2.3; Lemmas 2.4 and 4.2; Theorems 4.6-4.8"},{"comment":"The key inequality E[||tilde x_k - Pi_{L_{j_k}}(tilde x_k)||^2 | F[k]] >= (rho/m) min_Delta dist^2(tilde x_k, L(h_j; tilde x_k; Delta)) is imported without proof from Lemma 4 of [25]. This step is load-bearing: it is exactly how Lemma 2.4 is combined with Assumption 3.1 to produce the expected halfspace-projection bound used in the recurrence (19). The paper claims 'distinct proofs under basic assumptions,' so the needed lemma should be stated and proved in the appendix. Under Assumption 2.2 it can be proved directly from dist(x, L(h;x;g)) = (h(x))_+/||g|| for g != 0, and the derivation should be included for self-containedness.","section":"Appendix, proof of Lemma 4.2"}],"minor_comments":[{"comment":"The notation x in Y in R^n should read x in Y subseteq R^n; the current expression 'x in Y in R^n' appears to be a typo.","section":"Equation (1)"},{"comment":"Lemma 4.4 is stated as holding 'under the assumption of Lemma 4.2 with beta in (0,2)', but Lemma 4.2 contains no beta; the beta condition belongs to Lemma 4.3. Please correct the cross-reference.","section":"Lemma 4.4"},{"comment":"The displayed feasibility bound in Theorem 4.8 is O(1/(k^2 + k k0 + k0^2)), which is O(1/k^2) asymptotically, while the text after the theorem and the abstract state the strongly convex rates as O(1/k). The stronger statement should be presented consistently.","section":"Theorem 4.8 and abstract"},{"comment":"The sentence that SHAM 'consistently outperforms CVX by a factor ranging from 3 to 10' is not supported by the first row of Table I, where CVX times (2.4 and 1.9 seconds) are below the SHAM averages (about 11-13 seconds). Please qualify the claim as applying to larger instances or revise the wording.","section":"Section V, Table I"},{"comment":"The bound sum_{t=1}^{k+1} alpha_t^2 <= alpha_0^2/ln(3) for alpha_t = alpha_0/(sqrt(t+2) ln(t+2)) appears too strong; the infinite sum is numerically larger than 1/ln(3). Since only the order O(alpha_0^2) is needed for the stated rate, this does not change the conclusion, but the inequality should be corrected.","section":"Section IV-A, Choice (1)"},{"comment":"The rate constants involve c^2, B_h^2, and 1/rho, which are generally unknown; a brief discussion of the practical meaning of these constants for finite k would be helpful for users of the algorithm.","section":"Theorems 4.6 and 4.8"}],"recommendation":"major_revision","confidential_remarks":"The core recurrence appears coherent and the paper is within scope for an optimization journal. I would not reject: the central issue is not an internal contradiction but a mismatch between the advertised generality and the explicit linear regularity assumption, plus a reliance on an unproved external lemma in a load-bearing step. Both are fixable. The numerical section is illustrative rather than a definitive benchmark; the small-instance comparison should be softened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the quick read: this is a real but incremental contribution. The new degree of freedom—linearizing a randomly chosen constraint at any point on the segment between the current iterate and the gradient-projection point—is a genuinely useful unification, and the analysis is honest, with no hidden fitting. The convergence rates match the best earlier results; they are not new. The main thing to watch is the feasibility guarantee: it depends on Assumption 2.3 (linear regularity), and that assumption can fail for simple smooth constraints like h(x)=x^2 with X={0}. The optimality rates survive without it, but the advertised O(1/sqrt k) and O(1/k) feasibility rates do not.\n\nWhat the paper does well: the unified analysis covers infinitely many halfspace choices through the parameter gamma, and it removes the compactness assumption used in earlier work by relying on bounded subgradients and gradients. The proofs are first-principles and the main recurrence (19) checks out under the stated assumptions. The switching stepsize for the strongly convex case is a useful practical detail. I couldn't find a fatal flaw in the derivations.\n\nThe soft spots are proportionate. First, Assumption 2.3 is load-bearing for the feasibility rates, not for the optimality rates. The stress-test example is correct: for h(x)=x^2 on Y=[-1,1], no finite c satisfies the linear regularity bound near x=0, so the feasibility O(1/k) guarantee does not follow. The assumption is stated explicitly and is standard in error-bound literature, but the abstract and title oversell the generality. Second, the rate constants depend on c^2 and Bh^2, which are typically unknown and can be huge, so the bounds can be vacuous for finite k. That's a known caveat, but it belongs in the paper's discussion. Third, the numerical section only compares against CVX, omits the closest prior methods (e.g., the stochastic subgradient method of [11] and the minibatch variant of [19]), and reports CPU times from 5 runs with no code or data. The claim of a 3-10x speedup is contradicted by the smallest instance, where CVX is actually faster; the overclaim should be tempered.\n\nWho is this for? Researchers working on stochastic projection methods for constrained convex optimization. It deserves a serious referee: the analysis is careful and the extension is meaningful, even if the rates are not new. I would recommend major revision, focusing on the numerical section and on a precise statement of the scope of the feasibility rates. Send it to review.","headline":"A genuine but incremental extension of stochastic halfspace methods; the optimality rates are sound, but the advertised feasibility rates rest on a linear regularity assumption that can fail, and the numerics overstate the case.","tokens_in":16758,"tokens_out":4077,"would_cite":true,"duration_ms":41229,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The Stochastic Halfspace Approximation Method projects each iterate onto a random linear halfspace approximation of one nonsmooth constraint, and its unified analysis yields O(1/√k) rates for convex objectives and O(1/k) for strongly…","keywords":["convex optimization","nonsmooth functional constraints","stochastic gradient method","halfspace approximation","random projection","linear regularity","convergence rates","strongly convex"],"falsifier":"Compute the linear-regularity ratio for the feasible set X = {(x,y): $x^{4}$ - y ≤ 0, y ≤ 0} on Y = [-1,1]^2, whose only feasible point is (0,0). At (t,0), max_j [h_j]_+ = $t^{4}$ while dist((t,0),X) = |t|, so the ratio |t|/$t^{4}$ = 1/|t|^3 is unbounded and no finite c satisfies (6); all other assumptions (bounded subgradients, smooth convex objective) can be met. Running SHAM on this two-constraint problem with the stated α_k and β and checking whether E[$dist^{2}$(\\hat x_k,X)] still decays as O(1/√k) would show whether linear regularity is a proof artifact or a genuine requirement.","tokens_in":15726,"feed_emoji":"🎯","tokens_out":12174,"duration_ms":115311,"temperature":0.7,"pith_summary":"This paper proposes SHAM, a stochastic algorithm for minimizing a smooth convex function over a set defined by many nonsmooth convex constraints. At each step SHAM takes a gradient step, projects the result onto the simple set Y, then projects onto a halfspace that linearizes one randomly chosen constraint at any point on the segment between the current iterate and the projected point. The central claim is a unified convergence analysis: for any such choice of linearization point, the averaged iterates have expected optimality gap and expected squared feasibility violation of order O(1/√k) when f is convex, and O(1/k) when f is strongly convex. If correct, these are the best known rates for stochastic subgradient methods, and one analysis covers infinitely many algorithmic variants, including the two extremes where the halfspace is built at the current iterate or at the projected point. The practical interest is that per iteration only one constraint is touched, so the method scales to problems with very many constraints and no easy full projections.","feed_headline":"Halfspace projection: O(1/√k) rates for constrained convex problems","feed_subtitle":"One random constraint projection per step matches the best known rates on optimality and feasibility.","key_machinery":"The load-bearing object is the random halfspace L(h_j; \\tilde x; Δ) = { y : h_j(\\tilde x) + ⟨Δ, y-\\tilde x⟩ ≤ 0 }, the linearization of a single constraint at \\tilde x_k, together with the relaxed projection z_k = v_k - β (l_{h_j}(v_k;\\tilde x_k))_+ / ‖Δ‖^2 Δ. The chain that carries the argument is: Lemma 2.4 converts the linear-regularity inequality dist(x,X) ≤ c max_j [h_j(x)]_+ into a bound on dist(x,X) in terms of the distance from x to the best linearization halfspace; Lemma 4.2 turns the expected squared distance from v_k to the random halfspace into a bound on $dist^{2}$(\\tilde x_k, X); Lemma 4.4 feeds this into the main recurrence, which couples the contraction of ‖x_k - \\bar x_k‖^2, the optimality gap f(x_{k+1}) - f(\\bar x_k), and the feasibility term $dist^{2}$(x_{k+1}, X). The parameter γ controls where the halfspace is anchored and enters only through the constant $B^{2}$, so the proof handles all γ ∈ [0,1] simultaneously.","core_discovery":"SHAM is the update x_{k+1} = Proj_Y((1-β)v_k + β Proj_{L_{j_k}}(v_k)), where v_k = Proj_Y(x_k - α_k ∇f(x_k)) and L_{j_k} is the halfspace { y : h_{j_k}(\\tilde x_k) + ⟨Δ, y - \\tilde x_k⟩ ≤ 0 } with \\tilde x_k = γ v_k + (1-γ)x_k and Δ ∈ ∂h_{j_k}(\\tilde x_k). The paper proves, under bounded subgradients, linear regularity, and a positive uniform sampling probability, that the expected squared distance to the optimal set obeys the recurrence (19). Summing this recurrence yields, for the weighted averages \\hat x_k, E[f(\\hat x_k)-f(\\hat x^*_k)] = O(1/√k) and E[$dist^{2}$(\\hat x_k, X)] = O(1/√k) in the convex case, and O(1/k) for both criteria in the strongly convex case, with explicit constants depending on c, B_h, ρ, m, L_f, and μ. The novelty is that the linearization point \\tilde x_k may be any convex combination of x_k and v_k, so the result unifies and extends earlier algorithms that fixed \\tilde x_k = v_k.","pith_inferences":["The unified treatment of γ ∈ [0,1] suggests an intermediate γ might be tuned to balance the cheaper anchor \\tilde x_k = x_k against the more robust anchor \\tilde x_k = v_k observed in the numerical experiments; the theory does not single out an optimal γ.","Because c appears squared in the feasibility rate, constraint sets with a large linear-regularity constant will require many more iterations; estimating c (or a Slater constant) before running the algorithm could guide the choice of β and the stopping criterion.","The rates hold for weighted average points, not the last iterate; deriving last-iterate or high-probability guarantees would require additional machinery and is not addressed.","For finite-sum objectives, pairing the halfspace projection with variance-reduced gradient estimators (as in the reference [25] does for a similar method) may remove the logarithmic factor, but SHAM's analysis does not cover variance reduction."],"forward_implications":["Both extremes γ=0 (\\tilde x_k = x_k) and γ=1 (\\tilde x_k = v_k) carry the same worst-case rates, so a practitioner can choose the cheaper or more stable anchor without sacrificing the O(1/√k) or O(1/k) guarantee.","For a strongly convex objective, the switching stepsize \\alpha_k = min(1/L_f, 2/(μ(k+1))) is fully specified after k0 = floor(2L_f/μ - 1), so the algorithm needs no stepsize tuning beyond the Lipschitz and strong-convexity constants.","The per-iteration cost is one gradient evaluation, one projection onto Y, and one halfspace projection for a single constraint, independent of m; the feasibility guarantee is nevertheless for the full constraint set X = Y ∩ ⋂_j X_j.","Feasibility violation at the average point is controlled by the same sum that bounds the optimality gap, so both quality measures improve in lockstep at the same rate.","Under the α_k = α_0/√k choice the logarithmic factor disappears from the leading term, giving clean O(1/√k) rates for convex f."],"supporting_citations":[{"why":"Earlier algorithm analyzed asymptotically for the same problem class; SHAM generalizes its halfspace update and supplies rates where [9] had none.","marker":"[9]"},{"why":"Previous stochastic subgradient method for composite convex optimization with functional constraints; supplies projection inequalities and the O(1/√k) baseline SHAM matches and extends.","marker":"[11]"},{"why":"Variance-reduced random relaxed projection method whose Proposition 1(ii) is adapted in Lemma 2.4; SHAM's feasibility-distance argument builds on this proof.","marker":"[25]"},{"why":"Establishes the linear-regularity condition (Assumption 2.3) and describes classes of sets (polyhedral, Slater, Robinson) where it holds.","marker":"[8]"},{"why":"Source of the uniform sampling condition (Assumption 3.1) and of the stochastic random-constraint-projection framework SHAM fits into.","marker":"[22]"},{"why":"Primal-dual stochastic gradient method for many functional constraints, the main alternative stochastic approach compared in the introduction.","marker":"[24]"},{"why":"Polyak's stepsize for minimizing unsmooth functionals; the halfspace projection in (12) reduces to a Polyak-type step when \\tilde x_k = v_k.","marker":"[15]"},{"why":"Supplies the Lipschitz-gradient smoothness property (Assumption 2.1(ii)) used in Lemma 4.1 and the descent bound.","marker":"[14]"},{"why":"CVX solver used in the numerical experiments as the baseline against which SHAM's CPU times are reported.","marker":"[6]"}],"fun_headline_variants":["Stochastic halfspace method matches best-known rates with one constraint per step","One random halfspace projection per step achieves O(1/√k) convergence","SHAM: stochastic halfspace approximation with O(1/k) rates for strong convexity","New stochastic projection method: O(1/√k) on optimality and feasibility","Random halfspace projection: O(1/√k) for constrained convex optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the distance to the feasible set can be bounded by a fixed constant times the largest constraint violation (Assumption 2.3); if this linear regularity fails, the chain from halfspace errors to feasibility distances breaks and the stated rates do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic halfspace method matches best-known rates with one constraint per step","One random halfspace projection per step achieves O(1/√k) convergence","SHAM: stochastic halfspace approximation with O(1/k) rates for strong convexity","New stochastic projection method: O(1/√k) on optimality and feasibility","Random halfspace projection: O(1/√k) for constrained convex optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000995,"raw_usage":{"total_tokens":4230,"prompt_tokens":978,"completion_tokens":3252,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":3145}},"tokens_in":594,"tokens_out":3252,"duration_ms":23153,"temperature":1.0,"reasoning_tokens":3145,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:35:07.130789+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the linear-regularity ratio for the feasible set X = {(x,y): $x^{4}$ - y ≤ 0, y ≤ 0} on Y = [-1,1]^2, whose only feasible point is (0,0). At (t,0), max_j [h_j]_+ = $t^{4}$ while dist((t,0),X) = |t|, so the ratio |t|/$t^{4}$ = 1/|t|^3 is unbounded and no finite c satisfies (6); all other assumptions (bounded subgradients, smooth convex objective) can be met. Running SHAM on this two-constraint problem with the stated α_k and β and checking whether E[$dist^{2}$(\\hat x_k,X)] still decays as O(1/√k) would show whether linear regularity is a proof artifact or a genuine requirement.","supporting_citations":[{"cited_title":"Nedich, ”Random algorithms for convex minimization prob lems,” Mathematical Programming, vol","cited_arxiv_id":null,"evidence_quote":"Earlier algorithm analyzed asymptotically for the same problem class; SHAM generalizes its halfspace update and supplies rates where [9] had none."},{"cited_title":"Necoara and N.K","cited_arxiv_id":null,"evidence_quote":"Previous stochastic subgradient method for composite convex optimization with functional constraints; supplies projection inequalities and the O(1/√k) baseline SHAM matches and extends."},{"cited_title":"Y ang, F","cited_arxiv_id":null,"evidence_quote":"Variance-reduced random relaxed projection method whose Proposition 1(ii) is adapted in Lemma 2.4; SHAM's feasibility-distance argument builds on this proof."},{"cited_title":"Lewis and J.S","cited_arxiv_id":null,"evidence_quote":"Establishes the linear-regularity condition (Assumption 2.3) and describes classes of sets (polyhedral, Slater, Robinson) where it holds."},{"cited_title":"Wang and D.P","cited_arxiv_id":null,"evidence_quote":"Source of the uniform sampling condition (Assumption 3.1) and of the stochastic random-constraint-projection framework SHAM fits into."},{"cited_title":"Xu, ”Primal-dual stochastic gradient method for convex p rograms with many functional constraints,” SIAM Journal on Optimization , vol","cited_arxiv_id":null,"evidence_quote":"Primal-dual stochastic gradient method for many functional constraints, the main alternative stochastic approach compared in the introduction."},{"cited_title":"Polyak, ”Minimization of unsmooth functionals,” USSR Com- putational Mathematics and Mathematical Physics , vol","cited_arxiv_id":null,"evidence_quote":"Polyak's stepsize for minimizing unsmooth functionals; the halfspace projection in (12) reduces to a Polyak-type step when \\tilde x_k = v_k."},{"cited_title":"Nesterov, ”Lectures on Convex Optimization,” Springer Opti- mization and Its Applications , vol","cited_arxiv_id":null,"evidence_quote":"Supplies the Lipschitz-gradient smoothness property (Assumption 2.1(ii)) used in Lemma 4.1 and the descent bound."},{"cited_title":"Grant and S","cited_arxiv_id":null,"evidence_quote":"CVX solver used in the numerical experiments as the baseline against which SHAM's CPU times are reported."}],"review_version":1}