{"id":"527c8dd5-19b7-4eb5-ad9f-cbc4cdda063c","arxiv_id":"1908.02734","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"ConEx, a single-loop primal-dual method with constraint extrapolation, achieves best-known convergence rates for convex functional constrained problems, and a proximal point method achieves O(1/ε) complexity to approximate KKT points for nonconvex ones.","lead":"A new algorithm family called ConEx solves convex optimization problems with constraints, including stochastic ones, at the best-known speeds. The paper also converts nonconvex constrained problems into a sequence of easy convex subproblems and proves the number of steps needed to find a good solution.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inexact proximal-point theorem uses a squared-distance bound as the Theorem 3.17 δ tolerance, so Corollary 3.19's δ guarantee and total complexity do not follow as written.","rationale":"The ConEx portion of the paper is substantial and internally coherent; the reader's concern about the unknown B and unverifiable subproblem accuracy conditions is legitimate but is an assumption/tuning limitation rather than an internal inconsistency. The more load-bearing issue I find is the square-root mismatch in the inexact proximal point theorem: the proof bounds the expected squared distance, while Definition 3.2's delta is a distance bound. Since Corollary 3.19 uses this delta to state concrete total complexity rates, those rates are not currently supported. The issue is localized and likely fixable by either amending the stochastic KKT definition to squared distance or changing the subproblem tolerances and re-deriving the complexity, so the appropriate verdict remains conditional rather than a rejection. The exact proximal point O(1/epsilon) result for epsilon-KKT points under uniform dual boundedness is not affected by this concern, and the paper's detailed proofs and explicit complexity tables are valuable evidence for the portions that survive scrutiny.","tokens_in":50781,"tokens_out":17508,"duration_ms":197215,"concrete_test":"Re-derive Theorem 3.17's stochastic KKT guarantee by taking expectations in (3.3): check whether E||x_pk - x*_pk|| <= s_epsilon_K follows from the displayed bound E||x_pk - x*_pk||^2 <= 2*Omega_K/(mu_0*K). Then evaluate the numerical example mu_0 = 1, c1 = 1, epsilon = 10^{-6} in Corollary 3.19: the claimed delta is 2*10^{-6}, while the proof yields sqrt(2*Omega/(mu_0*K)) = sqrt(epsilon/(mu_0*c1)) = 10^{-3}. If the inequality fails, rerun the complexity calculation with s_delta = O(epsilon^2) and record the resulting T_epsilon for ConEx and the total iteration complexity.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the inexact proximal point half of the paper, the proof of Theorem 3.17 derives only a bound on the expected squared distance: E||x_pk - x*_pk||^2 <= 2*Omega_K/(mu_0*K) (display before (3.41)). The theorem then declares x_pk a stochastic (epsilon_K, s_epsilon_K)-KKT point with s_epsilon_K = 2*Omega_K/(mu_0*K). But Definition 3.2, equation (3.3), measures deviation by ||x - px||_2 <= delta, not by its square, and 'under expectation' is naturally read as E||x - px||_2 <= delta. By Jensen, the proof gives E||x_pk - x*_pk|| <= sqrt(2*Omega_K/(mu_0*K)), which is much larger than 2*Omega_K/(mu_0*K) when the tolerance is small. The same square-root discrepancy propagates to Corollary 3.19: with delta_k = c*s_delta_k and s_delta_k = epsilon/(2*c1*c2), one has Omega_K/K = epsilon/(2*c1), so the guaranteed distance is at best sqrt(epsilon/(mu_0*c1)), not 2*epsilon/(mu_0*c1). Therefore the claimed (epsilon, 2*epsilon/(mu_0*c1))-KKT output and the stated O(1/epsilon^{3/2}), O(1/epsilon^2), O(1/epsilon^3) total complexities for the inexact method are not established as written. If the intended stochastic criterion is E||x - px||^2 <= delta, that definitional change must be stated; if not, the subproblem tolerances need to be squared (s_delta = O(epsilon^2)) and the ConEx subproblem costs change. This concern does not touch the exact proximal point result Theorem 3.13, which appears coherent under its assumptions.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies convex and nonconvex functional constrained composite optimization. For the convex case it proposes ConEx, a single-loop primal-dual method using linearized constraint extrapolation, and proves complexity bounds for deterministic, semi-stochastic, and fully-stochastic settings, with smooth or nonsmooth objectives and constraints. For the nonconvex case it proposes exact and inexact proximal point methods that add quadratic proximal terms to both objective and constraints; under Slater-type, MFCQ, or strong-feasibility assumptions it claims asymptotic convergence and O(1/epsilon) rates to epsilon-KKT points, with ConEx used as the subproblem solver in the inexact variant.","tokens_in":51225,"tokens_out":13332,"duration_ms":137785,"significance":"If the results hold, the ConEx method is a valuable unified contribution: it attains several rates that appear to be new, especially for fully stochastic functional constraints, and it avoids projection of the dual iterates onto a known bounded set. The exact proximal point analysis for nonconvex functional constraints under a range of constraint qualifications is also a substantial contribution. The proofs are detailed and largely internally consistent, and the convex part of the paper is explicit about the role of the user-chosen constant B. However, two load-bearing issues in the inexact proximal point part—the mismatch between the squared-distance bound and the distance criterion in Definition 3.2, and the insufficient strict-feasibility conditions in Proposition 3.15—mean that the stated complexity guarantees for the inexact method are not currently established. These are fixable within the scope of the manuscript, but they affect central claims.","major_comments":[{"comment":"The proof of Theorem 3.17 bounds the expected squared distance, E||x_pk - x*_pk||^2 <= 2*Omega_K/(mu_0*K), but Definition 3.2 in (3.3) uses ||x - px||_2 <= delta as the deviation criterion, and a stochastic reading of that definition requires E||x - px||_2 <= delta. Jensen's inequality gives only E||x_pk - x*_pk||_2 <= sqrt(2*Omega_K/(mu_0*K)), which is much larger than 2*Omega_K/(mu_0*K) for small tolerances. Consequently, the claimed s_epsilon_K in (3.41), the (epsilon, 2*epsilon/(mu_0*c1))-KKT conclusion of Corollary 3.19, and the final O(1/epsilon^{3/2}), O(1/epsilon^2), and O(1/epsilon^3) complexities in Remark 3.20 are not established as written. The fix is either to state that the stochastic KKT criterion in Definition 3.2 uses squared distance, or to change the subproblem tolerances to s_delta_k = O(epsilon^2) and re-derive the ConEx subproblem costs accordingly.","section":"Section 3.2, Theorem 3.17 and display before (3.41)"},{"comment":"The strict-feasibility and descent conditions in Proposition 3.15 contain a similar square-root mismatch. The proof combines the Lipschitz bound psi_i(x_k;x_{k-1}) <= M_i*||x_k - x*_k|| with the lower bound sqrt(2*mu_i*W(x_k,x_{k-1})) > sqrt(M_i)*||x_k - x*_k||. This yields only 2*mu_i*W > M_i*||x_k - x*_k||^2, not 2*mu_i*W > M_i*||x_k - x*_k||, so strict feasibility of x_k does not follow; the same issue affects the descent inequality in part b). The correct condition would require a tolerance of the form sqrt(M_i/mu_i)*sqrt(||x_k - x*_k||) + ||x_k - x*_k|| < ||x_{k-1} - x*_k||, i.e., subproblem accuracy of order O(epsilon^2) rather than O(epsilon). Since Theorem 3.16 and the subsequent convergence analysis rely on these conditions, this is a load-bearing gap that needs to be repaired or the complexity statements adjusted.","section":"Proposition 3.15, conditions (3.28)-(3.29)"},{"comment":"The headline O(1/epsilon) complexity for smooth deterministic convex problems in Table 1 is conditional on the user choosing B >= ||y*||_2 + 1, where y* is an unknown optimal Lagrange multiplier. If B is smaller, the bound in (2.21)-(2.22) degrades to the nonsmooth O(1/epsilon^2) rate, and the manuscript proves that replacing H* by HB in the stepsize policy (2.19) fails for smooth deterministic problems. The suggested line search is not analyzed. Since this is one of the main claimed new rates, the paper should either provide an implementable adaptive procedure with a proven rate or explicitly state that the smooth deterministic row of Table 1 is conditional on knowledge of an upper bound on ||y*||_2.","section":"Section 2.1, Theorem 2.3 and discussion after (2.22)"}],"minor_comments":[{"comment":"The proof cites relation (3.39), which is defined only later in Section 3.2; the intended reference appears to be relation (3.16) of the exact proximal point analysis. Please correct the cross-reference.","section":"Proof of Theorem 3.13"},{"comment":"The section heading contains a typo: 'Porblems' should be 'Problems'.","section":"Section 3 heading"},{"comment":"The reference to Ma, Lin, and Yang is incomplete: it lacks a venue, year, or arXiv identifier.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The major issues are concentrated in the inexact proximal point analysis and in the parameter choice for the smooth deterministic ConEx rate; the exact proximal point results and the convex ConEx derivation appear sound modulo the B caveat. With squared-tolerance corrections and either an adaptive B procedure or an explicit conditionality statement for Table 1, the manuscript would be a solid contribution. I recommend major revision rather than rejection because the framework is novel and the necessary fixes are identifiable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the Constraint Extrapolation (ConEx) method is the real news and it largely holds up. Using linearized constraints to define the extrapolation step is a clean construction, and the unified rate table — deterministic, semi-, and fully-stochastic; smooth, nonsmooth; convex and strongly convex — is what the paper claims. The fully-stochastic bounds under bounded second moments were genuinely first. Second, the inexact proximal point half has a real gap that affects the headline complexity claims: the proof of Theorem 3.17 delivers only a bound on E||x_k - x*_k||^2, and the theorem then uses that same quantity as the delta-tolerance in the (epsilon,delta)-KKT definition. Definition 3.2 measures deviation by ||x - p x|| <= delta, not its square, so the stated s_epsilon_K does not follow. The stress-test note is right.\n\nCredit where due. The B >= ||y*||_2 + 1 caveat on the smooth deterministic O(1/epsilon) rate is real but honestly handled — the paper states plainly that a small B degrades the rate to O(1/epsilon^2) and that the HB substitution provably fails in exactly that case. The suggested line search is not analyzed; that is a minor gap. The exact proximal point results (Theorem 3.13, O(1/epsilon) to an epsilon-KKT point under uniform dual boundedness, with MFCQ-type sufficiency conditions) are coherent. The (3.28)-(3.29) criteria requiring the unknown x*_k are acknowledged as hard to verify, which softens but does not remove the practical limitation.\n\nThe problem shows up in Corollary 3.19. With s_delta_k = O(epsilon), the guaranteed distance is at best sqrt(2epsilon/(mu0 c1)) by Jensen, not 2epsilon/(mu0 c1), and the stated O(1/epsilon^{3/2}), O(1/epsilon^2), O(1/epsilon^3) totals for the inexact method do not follow as written. The repair is conceptually simple: either define the stochastic KKT notion with a squared-distance delta (consistent with the already-squared stationarity residual), or square the subproblem tolerances — in which case the final rates degrade, e.g., to O(1/epsilon^2) for the deterministic smooth case. Either way, the authors owe the reader a corrected statement.\n\nThe citation pattern is normal; the machinery is the authors' own three-point-lemma toolkit, but no rate is assumed as input. Who gets value: anyone working on constrained stochastic optimization or first-order primal-dual methods — the ConEx rate table is a reference point even if the prox half needs revision.\n\nRecommendation: send to a serious referee, with the inexact proximal point claims the focus of the revision. This is not a desk reject.","headline":"The ConEx half is genuinely new and mostly checks out, but the inexact proximal point rates have a squared-distance-versus-distance mismatch that breaks Corollary 3.19 as written.","tokens_in":51739,"tokens_out":9461,"would_cite":true,"duration_ms":89467,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C26","90C30","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"ConEx reaches the best-known convergence rates for convex functional constrained optimization, and a proximal point variant reaches ε-KKT points in O(1/ε) iterations.","keywords":["functional constrained optimization","constraint extrapolation","stochastic first-order methods","composite convex optimization","proximal point method","nonconvex optimization","KKT conditions","primal-dual methods"],"falsifier":"Take a smooth deterministic convex functional constrained problem with a known optimal dual multiplier y*, run ConEx with B set to half of (||y*||_2 + 1), and measure the iteration count needed to reach an (ε, ε)-approximate solution. The paper predicts the rate degrades from O(1/ε) to O(1/$ε^{2}$); if the observed count instead stays O(1/ε), the claimed threshold on B is wrong.","tokens_in":50598,"feed_emoji":"🧮","tokens_out":8996,"duration_ms":89055,"temperature":0.7,"pith_summary":"Functional constrained optimization—minimizing an objective subject to inequality constraints that are themselves general functions rather than simple boxes—shows up in risk-averse machine learning, semisupervised learning, and robust optimization. This paper claims that a single primal-dual algorithm, Constraint Extrapolation (ConEx), attains the best-known convergence rates across the whole convex spectrum: objective and constraints each convex or strongly convex, smooth or nonsmooth, and evaluated deterministically, with a stochastic objective, or with both stochastic. Several of these rates, notably the fully stochastic ones, are claimed to be new. The same paper gives a proximal point method that converts a nonconvex functional constrained problem into a sequence of strongly convex subproblems and proves an O(1/ε) iteration bound to an approximate KKT point when the subproblem dual variables are uniformly bounded. If these claims hold, a much wider class of constrained stochastic optimization problems can be solved with a simple loop that needs no penalty subproblems and no projection of dual variables onto an unknown bounded set.","feed_headline":"ConEx hits best-known rates for convex constrained problems","feed_subtitle":"A single-loop primal-dual method also gives nonconvex problems an O(1/ε) path to KKT points.","key_machinery":"Two mechanisms carry the argument. Constraint extrapolation is the step s_t = (1+θ_t)[χ(x_t)+ℓ_F(x_t)] − θ_t[χ(x_{t-1})+ℓ_F(x_{t-1})], with ℓ_F(x_t) the stochastic linear approximation of the constraint vector at the previous point; the dual update y_{t+1} = [y_t + s_t/τ_t]_+ then stays finite without any projection onto a bounded set. The primal update is a prox step using the Bregman divergence W associated with the prox-function ω. The proximal point machinery adds 2μ_i W(x, x_{k-1}) to each constraint function, forcing every subproblem to be strongly convex in both objective and constraints. A three-point inequality and the saddle-point gap function Q(z, z̄) = L(x, ȳ) − L(x̄, y) convert the algorithm's primal-dual gap into separate bounds on the optimality gap and the constraint violation.","core_discovery":"ConEx linearizes the constraint functions—replacing ψ(x_t) with χ(x_t) + ℓ_F(x_t), where ℓ_F is a stochastic linear approximation built from the previous iterate—and uses this linearized value inside the extrapolation step of a primal-dual iteration. This substitution makes the dual update well behaved even though the dual feasible set is unbounded, so the method never projects multipliers onto a ball whose radius depends on the unknown optimal multiplier. The paper proves unified iteration complexity bounds for strongly convex and convex, smooth and nonsmooth, deterministic, semi-stochastic, and fully stochastic cases, and identifies which of these rates are new. For nonconvex problems it introduces exact and inexact proximal point methods in which each subproblem is made strongly convex by adding quadratic terms to both the objective and the constraints; under constraint-qualification assumptions the exact scheme converges to KKT points, and under uniform boundedness of the dual sequence the same scheme needs O(1/ε) subproblem solves to produce an ε-KKT point.","pith_inferences":["The paper leaves implicit that the unknown B threshold could be handled in practice by a restarting line search on the measurable constraint violation ||[ψ(x)]_+||_2: if the violation plateaus above the target, double B and restart, which would preserve the smooth deterministic O(1/ε) rate without knowing the norm of the optimal multiplier in advance.","Because the key trick is replacing function values with linearized values inside the extrapolation, a natural extension is to other first-order primal-dual or extragradient schemes for variational inequalities where the operator norm or dual radius is unknown; the paper only demonstrates the device for functional constraints.","The fully stochastic rates suggest a direct testable application to the motivating example of risk-averse learning with a CVaR objective and an expectation constraint: such problems should exhibit sample complexity O(1/ε^2) without light-tail noise assumptions, unlike level-set methods that require stochastic lower bounds on the optimal value.","The nonconvex O(1/ε) result is conditional on uniform boundedness of the dual sequence; a practical algorithm would need a cheap check for this condition, for example by tracking the dual iterates during ConEx solves and restarting the proximal loop if they exceed a threshold, though the paper does not analyze such a restart rule."],"forward_implications":["For convex functional constrained problems, one single-loop algorithm now covers all combinations of strongly convex or convex, smooth or nonsmooth, and deterministic, semi-stochastic, or fully stochastic settings, at the best-known rates, with several fully stochastic rates claimed for the first time.","Users no longer need penalty subproblems or a projection of dual multipliers onto a bounded set whose radius is usually unknown; the price is a user-chosen parameter B, and too small a B degrades the smooth deterministic rate from O(1/ε) to O(1/ε^2).","For nonconvex functional constrained problems, the exact proximal point method gives an O(1/ε) guarantee to an ε-KKT point when the subproblem dual sequence is uniformly bounded.","The inexact proximal point method, with ConEx solving its subproblems, gives total complexities O(1/ε^{3/2}), O(1/ε^2), and O(1/ε^3) for smooth deterministic, semi-stochastic, and fully stochastic nonconvex settings, respectively.","Starting from a strictly feasible point, every iterate of the exact proximal point method remains strictly feasible, so each subproblem satisfies the constraint qualification needed for dual variables to exist."],"supporting_citations":[{"why":"Supplies the closest existing primal-dual method for general convex-concave saddle point problems; its deterministic O(1/ε) bound is the one ConEx attains with a different termination criterion.","marker":"[18]"},{"why":"Baseline prox-method for smooth saddle point problems whose required projection of dual multipliers onto a bounded set ConEx removes.","marker":"[33]"},{"why":"Existing stochastic expectation-constraint algorithm with constraint evaluation steps and light-tail assumptions; ConEx's fully stochastic rates improve on this setting.","marker":"[26]"},{"why":"Level-set method requiring stochastic lower bounds on the optimal value; ConEx avoids such lower bounds.","marker":"[4]"},{"why":"Stochastic constrained optimization algorithm requiring bounded stochastic constraint noise, a restriction ConEx replaces with bounded second moments.","marker":"[47]"},{"why":"Concurrent proximal point analysis for weakly convex functional constraints under a uniform Slater condition; the paper broadens the constraint qualifications and supplies a unified subproblem solver.","marker":"[30]"},{"why":"Provides the three-point lemma for Bregman divergence that is used throughout the ConEx convergence proof.","marker":"[20]"}],"fun_headline_variants":["ConEx achieves best-known rates for convex constrained problems","Single-loop ConEx unifies stochastic functional constraint rates","New proximal point method reaches KKT in O(1/ε) for nonconvex","Constraint extrapolation: no projection, faster convergence","ConEx: first best-known rates for nonsmooth convex constraints"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The fast rates depend on constants chosen before the run: ConEx needs the user-set B to be at least one plus the unknown norm of an optimal dual multiplier, and the nonconvex method needs the dual multipliers of all subproblems to stay uniformly bounded.","fun_headline_variants_meta":{"raw":{"variants":["ConEx achieves best-known rates for convex constrained problems","Single-loop ConEx unifies stochastic functional constraint rates","New proximal point method reaches KKT in O(1/ε) for nonconvex","Constraint extrapolation: no projection, faster convergence","ConEx: first best-known rates for nonsmooth convex constraints"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000752,"raw_usage":{"total_tokens":3408,"prompt_tokens":1067,"completion_tokens":2341,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":683,"completion_tokens_details":{"reasoning_tokens":2256}},"tokens_in":683,"tokens_out":2341,"duration_ms":19559,"temperature":1.0,"reasoning_tokens":2256,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:36:12.673362+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a smooth deterministic convex functional constrained problem with a known optimal dual multiplier y*, run ConEx with B set to half of (||y*||_2 + 1), and measure the iteration count needed to reach an (ε, ε)-approximate solution. The paper predicts the rate degrades from O(1/ε) to O(1/$ε^{2}$); if the observed count instead stays O(1/ε), the claimed threshold on B is wrong.","supporting_citations":[{"cited_title":"A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems","cited_arxiv_id":"1803.01401","evidence_quote":"Supplies the closest existing primal-dual method for general convex-concave saddle point problems; its deterministic O(1/ε) bound is the one ConEx attains with a different termination criterion."},{"cited_title":"Prox-method with rate of convergence o(1/t) for variational ine quali- ties with lipschitz continuous monotone operators and smooth conv ex-concave saddle point problems","cited_arxiv_id":null,"evidence_quote":"Baseline prox-method for smooth saddle point problems whose required projection of dual multipliers onto a bounded set ConEx removes."},{"cited_title":"Y., Burke, J","cited_arxiv_id":null,"evidence_quote":"Level-set method requiring stochastic lower bounds on the optimal value; ConEx avoids such lower bounds."},{"cited_title":"Online convex optimization with stochastic constraints","cited_arxiv_id":null,"evidence_quote":"Stochastic constrained optimization algorithm requiring bounded stochastic constraint noise, a restriction ConEx replaces with bounded second moments."},{"cited_title":"Proximally constrained methods for weakly convex optimization with weakly convex constraints","cited_arxiv_id":null,"evidence_quote":"Concurrent proximal point analysis for weakly convex functional constraints under a uniform Slater condition; the paper broadens the constraint qualifications and supplies a unified subproblem solver."},{"cited_title":"Lectures on Optimization Methods for Machine Learning","cited_arxiv_id":null,"evidence_quote":"Provides the three-point lemma for Bregman divergence that is used throughout the ConEx convergence proof."}],"review_version":1}