{"id":"c59213a7-6e92-499d-b8f3-ba08bb41775a","arxiv_id":"1908.01871","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A proximally constrained subgradient method finds a nearly stationary point for weakly convex objectives with weakly convex constraints in O(1/epsilon^4) deterministic and O~(1/epsilon^6) stochastic iterations.","lead":"This paper designs a new class of optimization methods for problems where both the goal and the constraints are curved and non-smooth, by adding a quadratic term to each constraint in every subproblem. It proves convergence to an approximate solution in a number of steps that grows polynomially with the desired accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Uniform Slater constants σ_ε, ρ_ε may depend on ε; if they decay, the claimed O(1/ε^4) rate is not established.","rationale":"Good-faith reading: the paper's core contribution is a proximal-point scheme for weakly convex objectives and constraints, with subproblem oracles that yield O(1/ε^4) deterministic and O~(1/ε^6) stochastic rates under Assumption 1. The proofs are mostly displayed and the construction is plausible; Lemma 1 and Theorem 1 are the pillars. I looked hardest at Assumption 1B because it is the only assumption that gives the uniform dual bound. The reader's weakest_assumption also names Assumption 1B; I partly agree, but I think the more precise defect is that the paper does not pin down whether σ_ε and ρ_ε are constants in ε. If they may decay, the headline rates are conditional on hidden ε-dependence. The paper's own tests do not close this: the simple example fixes constants, and Remark 3's condition (small c and small ||a||) is not verified for the real data. The λ_t=0 division in A.1 is an additional rigor issue but is easily repaired; the in-expectation wording is a clarity issue. None of these makes the central idea false; they make the current formulation too conditional. Hence the reader's CONDITIONAL verdict is correct, but the conditions should include an explicit statement or verification that the uniform Slater margin is uniform in ε, not just in x. The concrete check re-deriving the complexity with σ_ε and ρ_ε explicit would settle whether the O(1/ε^4) claim is actually established; if it fails, the paper should either strengthen Assumption 1B or state the rate with ε-dependent constants.","tokens_in":20085,"tokens_out":20728,"duration_ms":201040,"concrete_test":"Recompute the proof of Theorem 2 (Appendix A.3) without hiding σ_ε and ρ_ε in the big-O: write the total iteration count T·K as an explicit function of ε, σ_ε, ρ_ε, M, D, and (ρ−ρ). If the expression contains 1/σ_ε or 1/ρ_ε and no assumption forces σ_ε, ρ_ε = Ω(1), then the claimed O(1/ε^4) rate is not valid as ε→0; if the expression simplifies to O(1/ε^4) with constants independent of ε, the concern is resolved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Assumption 1B is the keystone of the theory: Lemma 1 uses it to bound the dual multipliers λ_t of every subproblem, and Theorem 1's proof needs that bound (see (14)–(15) and the final display in A.2). The proof of Lemma 1 (A.1) also divides by λ_t, which is invalid if λ_t=0 (complementary slackness allows this); this gap is patchable but not present. The deeper issue is quantitative: Assumption 1B asserts the existence of positive σ_ε and ρ_ε for each ε, but the complexity bound in Theorem 2 is O( (f(x0)-f_lb)(M²+ρD²)/(ε^4(ρ−ρ)^3) (M+ρD)/sqrt(σ_ε(ρ−ρ)) + 1 ). If σ_ε→0 or ρ_ε→0 as ε→0, the rate is no longer O(1/ε^4) and may not be polynomial. The paper never states that σ_ε and ρ_ε are bounded below by constants independent of ε; the subscript ε suggests dependence. The only verification of Assumption 1B is a 2D toy example where σ_ε and ρ_ε are fixed constants, plus a conditional Remark 3 requiring 'c and ||a|| are small enough' — conditions not shown to hold for the bank, loan, and a9a datasets, whose features are unnormalized and c is 0.08–0.4. If Assumption 1B fails on these instances, the empirical demonstration does not instantiate the theoretical guarantee. This weakness is load-bearing because without a uniform-in-ε Slater margin the central polynomial-rate claim collapses to a statement with unspecified ε-dependent constants.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies constrained optimization of the form min_{x in X} f0(x) subject to fi(x) <= 0 for i=1,...,m, where all fi are weakly convex and possibly nonsmooth, and X is compact. The authors propose an inexact proximally constrained (IPC) method (Algorithm 1) that, at each outer iteration, approximately solves a strongly convex subproblem obtained by adding a quadratic proximal term to both the objective and each constraint function. The oracle subproblem is instantiated by a deterministic switching subgradient method (Algorithm 2) and by a stochastic online subgradient method (Algorithm 3) imported from Yu, Neely, and Wei. Under Assumption 1, which includes a uniform Slater-type condition, Theorem 1 gives O(1/epsilon^2) outer iterations to reach a point whose distance to the proximal solution is at most epsilon. Theorems 2 and 3 claim total complexity O(1/epsilon^4) for the deterministic oracle and O-tilde(1/epsilon^6) for the stochastic oracle. The paper also presents experiments on fairness-constrained classification with a truncated logistic loss, comparing IPC with an exact penalty method and with the method of Yu et al.","tokens_in":1775,"tokens_out":1857,"duration_ms":113311,"significance":"If the complexity claims hold, the paper would provide the first polynomial subgradient-method rates for weakly convex nonsmooth objective and constraint functions, a setting where previous proximal-point analyses were restricted to unconstrained or simply constrained problems. The potential-based proof of Theorem 1 and the adaptation of the switching subgradient method are useful contributions, and the paper is honest about its relationship to the concurrent work of Boob, Deng, and Lan. The main value is therefore conditional: the rates depend on the quantitative behavior of the uniform Slater parameters sigma_epsilon and rho_epsilon, and the paper does not currently establish that these constants are bounded away from zero uniformly in epsilon. The experiments are illustrative but do not verify the key assumption on the real datasets. With a clarified and strengthened Slater assumption, the paper could be a solid contribution; as written, the headline polynomial rates are not fully established.","major_comments":[{"comment":"The uniform Slater constants sigma_epsilon and rho_epsilon in Assumption 1B are allowed to depend on epsilon, but every complexity bound in the paper depends on them. Lemma 1 bounds lambda_t by (M+rho_hat D)/sqrt(2 sigma_epsilon (rho_hat-rho)); Theorem 1 defines epsilon_hat using sigma_epsilon; Theorem 2's complexity in A.3, and Theorem 3's Lambda in A.4, have sigma_epsilon and rho_epsilon in denominators. If sigma_epsilon or rho_epsilon tends to zero as epsilon tends to zero, the claimed O(1/epsilon^4), O-tilde(1/epsilon^6), and even polynomial-in-epsilon rates are not established. In addition, Lemma 1 requires rho_hat <= rho + rho_epsilon, whereas Algorithm 1 and Theorem 1 state only that rho_hat > rho; when rho_epsilon is epsilon-dependent this is a missing condition. The authors should either state explicitly that sigma_epsilon and rho_epsilon are bounded below by positive constants independent of epsilon, or provide the explicit epsilon-dependence and revise the complexity claims accordingly. The numerical section does not fill this gap, because Remark 3 only establishes Assumption 1B when c and ||a|| are small enough, while the real datasets use c between 0.08 and 0.4 with unnormalized features.","section":"Assumption 1B; Lemma 1; Theorems 1-3; Appendix A.3-A.4"},{"comment":"The proof of Lemma 1 divides by lambda_t twice: it uses zeta_hat_t / lambda_t in the strong-convexity inequality and then forms a ratio of norms to conclude the bound on lambda_t. The KKT conditions (7) permit lambda_t = 0 by complementary slackness, in which case these divisions are invalid. The desired bound is trivially true when lambda_t = 0, so the proof can be repaired by treating that case separately, but as written the argument is incomplete and this lemma is load-bearing for Theorem 1.","section":"Appendix A.1, proof of Lemma 1"},{"comment":"The proof of Theorem 2 uses M^2 + rho_hat D^2 as an upper bound on ||F'(z_k)||^2, and Algorithm 2 sets K = ceil(4(M^2 + rho_hat D^2)/((rho_hat-rho) epsilon_hat^2)). Under Assumption 1F, the valid bound is ||F'(z_k)|| <= M + rho_hat D, so the squared norm is at most (M + rho_hat D)^2, which can be substantially larger. Consequently, the specified number of iterations K may be too small, and the deterministic oracle guarantee in Theorem 2 is not proven as stated. The proof and the input of Algorithm 2 should be corrected to use (M + rho_hat D)^2 or another valid upper bound; the O(1/epsilon^4) rate would survive this correction, but the current statement is inaccurate.","section":"Appendix A.3, Eq. (16) and Algorithm 2"}],"minor_comments":[{"comment":"The abstract contains a duplicated word: 'the constraint functions are are weakly convex'.","section":"Abstract and Section 1"},{"comment":"In the statement of Theorem 3, the second displayed bound is written as B1(D, ... ) but should be B2(D, ... ), matching equations (22) and (27).","section":"Theorem 3"},{"comment":"The output xt+1 is defined as a weighted average over the index set I, but the algorithm does not state what to return if I is empty; nonemptiness follows from the choice of K in the proof, but this should be stated explicitly.","section":"Algorithm 2"},{"comment":"The proof uses g(x_t) <= epsilon_hat^2 for every t, including t = 0, but Assumption 1E only guarantees g(x_0) <= epsilon^2 and epsilon_hat can be much smaller than epsilon; the t = 0 term needs a separate argument or an explicit absorbed constant.","section":"Appendix A.2, proof of Theorem 1"},{"comment":"The experimental section says 'We assume rho_hat = 2 rho in our algorithm for all experiments' and then later says the best rho_hat was tuned to 10^{-2.5}; this is confusing because rho is unknown and the stated relationship is not used consistently.","section":"Section 5"},{"comment":"There are several typographical errors, including 'stochatsic', 'orcale', and 'anlaysis'; these should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The central algorithmic idea is interesting and the paper is generally well organized, but the epsilon-dependence of the uniform Slater constants is the main obstacle to accepting the claimed rates. If the authors can strengthen Assumption 1B or give explicit uniform constants for the applications, the paper would be a reasonable contribution for this journal. The concurrent work by Boob, Deng, and Lan is acknowledged in the text, so the novelty disclosure appears adequate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The paper does something genuinely new: it adds a quadratic proximal term to the constraint function as well as the objective, making each subproblem strongly convex, and it delivers the first polynomial iteration complexities for subgradient-type methods on weakly convex objectives with weakly convex functional constraints. Lemma 1's uniform bound on subproblem multipliers under a uniform Slater condition is the technical core, and the proof is coherent. Second, the main rate claim has a soft spot that needs attention before I would take O(1/ε^4) at face value. Assumption 1B defines σ_ε and ρ_ε as positive constants for each ε, but the complexity in Theorem 2 has σ_ε in the denominator. If σ_ε or ρ_ε decay as ε→0, the rate is no longer O(1/ε^4) and may not be polynomial. The paper never states that these constants are bounded below independent of ε, and the only verification is a 2D toy example plus a conditional Remark 3. The real datasets are not shown to satisfy the condition, so the ε-dependence of the Slater margin is a load-bearing issue, not a cosmetic one.\n\nThere are two smaller problems. The proof of Lemma 1 divides by the multiplier λ_t without treating the λ_t=0 case; complementary slackness allows that, so the argument needs a patch. And Theorem 1's guarantee mixes expectation over the random output index with high probability over the algorithm; that is a standard form, but the wording 'find a nearly stationary point' could be clearer about the in-expectation nature.\n\nTo be fair, the paper is honest. It explicitly compares itself to the simultaneous work by Boob et al., and the citation pattern is reasonable. The experiments are limited in that no code or error bars are provided, but the empirical part is not the main contribution.\n\nWho should read this: people working on nonconvex constrained optimization, and anyone applying fairness or Neyman-Pearson constraints with nonconvex losses. The paper deserves a serious referee. My recommendation: send it to peer review, and ask the authors to clarify whether σ_ε and ρ_ε can be chosen independent of ε, and to patch the λ_t=0 case in Lemma 1. If the Slater constants genuinely can be ε-independent, or if the rates are restated explicitly in terms of them, the main result stands.","headline":"First provable subgradient rates for weakly convex constrained problems, with an unresolved dependence of the uniform Slater constants on ε that could weaken the central rate claim.","tokens_in":20949,"tokens_out":2653,"would_cite":true,"duration_ms":26966,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","90C25","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that weakly convex constrained optimization with nonsmooth objective and constraints can be solved by subgradient methods at polynomial rates: $O(1/\\epsilon^4)$ deterministically and $\\tilde{O}(1/\\epsilon^6)$…","keywords":["weakly convex optimization","nonsmooth constraints","subgradient method","proximal point method","near-stationary point","complexity guarantee","fairness constraints","stochastic subgradient"],"falsifier":"Build a weakly convex constrained problem whose feasible region satisfies ordinary Slater's condition but has an $\\epsilon^2$-feasible path along which $\\min_{y\\in X}\\{g(y)+((\\rho+\\rho_\\epsilon)/2)\\|y-x\\|^2\\}$ approaches zero; run Algorithm 1 on this problem. If the subproblem Lagrange multipliers fail to stay bounded, or the promised $O(1/\\epsilon^4)$ rate does not appear, then the uniform Slater assumption is doing essential work rather than being a technical convenience.","tokens_in":19846,"feed_emoji":"🎯","tokens_out":10488,"duration_ms":91619,"temperature":0.7,"pith_summary":"This paper claims that a class of first-order subgradient methods can solve constrained optimization problems in which both the objective and the constraints are weakly convex and nonsmooth, and can do so with the first polynomial complexity guarantees for such problems. The method adds a quadratic proximal term to the objective and to every constraint, turning each step into a strongly convex subproblem that existing algorithms can solve. Provided a uniform Slater condition holds, the paper proves that a random iterate becomes a nearly stationary point within $O(1/\\epsilon^2)$ main iterations, and that deterministic and stochastic oracle implementations yield total complexities $O(1/\\epsilon^4)$ and $\\tilde{O}(1/\\epsilon^6)$, respectively. These rates matter because machine learning tasks such as fairness-constrained learning and classification with nonconvex losses are naturally of this form, and no subgradient method with such guarantees previously existed.","feed_headline":"Subgradient method hits near-stationarity in O(1/ε⁴)","feed_subtitle":"Adding a quadratic prox term to objective and constraints turns each step into a tractable strongly convex subproblem.","key_machinery":"The load-bearing object is the proximally regularized subproblem (9), in which the same quadratic term $\\frac{\\hat{\\rho}}{2}\\|y-x_t\\|^2$ is added to the objective $f$ and to the constraint $g$. Because $f$ and $g$ are $\\rho$-weakly convex, choosing $\\hat{\\rho}>\\rho$ makes the subproblem $(\\hat{\\rho}-\\rho)$-strongly convex in both the objective and the constraint, so its solution is unique and approximable by strongly convex optimization algorithms. The uniform Slater condition (Assumption 1B) supplies the critical uniform bound on the subproblem's Lagrange multiplier, $\\lambda_t \\le (M+\\hat{\\rho}D)/\\sqrt{2\\sigma_\\epsilon(\\hat{\\rho}-\\rho)}$, which is what keeps the descent recursion from blowing up. The deterministic oracle is a single-loop switching subgradient method that takes an objective subgradient step when the regularized constraint is $\\hat{\\epsilon}^2$-feasible and a constraint subgradient step otherwise, with a weighted average over feasible iterates as output; this oracle is deterministic and satisfies the required error bounds exactly.","core_discovery":"The central claim is that every iteration of the inexact proximally constrained method approximately solves $\\hat{x}_t = \\arg\\min_{y\\in X}\\{ f(y) + \\frac{\\hat{\\rho}}{2}\\|y-x_t\\|^2 : g(y) + \\frac{\\hat{\\rho}}{2}\\|y-x_t\\|^2 \\le 0\\}$, and that the distance $\\|x_t-\\hat{x}_t\\|$ is a valid measure of stationarity: when it is at most $\\epsilon$, the proximal solution $\\hat{x}_t$ is feasible and satisfies the KKT conditions of the original problem with $O(\\epsilon)$ precision. The paper proves that, under Assumption 1, $T \\ge 4(f(x_0)-f_{\\mathrm{lb}})/(\\epsilon^2(\\hat{\\rho}-\\rho))$ iterations suffice for $\\mathbb{E}_R[\\|x_R-\\hat{x}_R\\|^2] \\le \\epsilon^2$ with probability at least $1-\\delta$. Combined with a deterministic switching subgradient oracle, this yields total complexity $O(1/\\epsilon^4)$; combined with a stochastic subgradient oracle, it yields $\\tilde{O}(1/\\epsilon^6)$.","pith_inferences":["Editorial inference: the uniform Slater condition is the natural place to look for a weaker sufficient condition; if the multiplier bound can be obtained from a data-dependent quantity, the method would extend to problems where the feasible region is thin or only known approximately.","Editorial inference: because the deterministic and stochastic rates differ by $\\epsilon^{-2}$, a variance-reduced or mini-batch stochastic oracle could plausibly close the gap, giving a stochastic rate matching the deterministic one.","Editorial inference: the near-feasibility of every iterate suggests an online or safety-critical setting where an infeasible proposal is costly; one could test the method on such problems and monitor constraint violations at intermediate steps.","Editorial inference: a concrete numerical check of Assumption 1B on larger real datasets, computing $\\min_{y\\in X}\\{g(y)+((\\rho+\\rho_\\epsilon)/2)\\|y-x\\|^2\\}$ for several $\\epsilon^2$-feasible points, would show whether the assumption holds beyond the paper's small example."],"forward_implications":["Deterministic weakly convex nonsmooth constrained problems now have a first-order subgradient method with an explicit $O(1/\\epsilon^4)$ complexity guarantee.","Stochastic subgradient versions inherit the same framework at $\\tilde{O}(1/\\epsilon^6)$, covering learning problems where constraints are only available through samples.","Every intermediate iterate produced by the main algorithm is approximately feasible, so feasibility is maintained along the path, not only at the final output.","The same proximal treatment applies when the functions are smooth and strongly convex after regularization, where existing level-set or augmented Lagrangian oracles give total complexity $O(1/\\epsilon^3)$ as noted in Remark 2."],"supporting_citations":[{"why":"Provides the switching subgradient method that Algorithm 2 adapts to solve the strongly convex subproblem with deterministic guarantees.","marker":"[35]"},{"why":"Motivates the inexact proximal-point framework and the use of the gap $\\|x_t-\\hat{x}_t\\|$ as a stationarity measure.","marker":"[16]"},{"why":"Supplies the online stochastic subgradient method used as Algorithm 3, including the high-probability bounds that make it an oracle.","marker":"[53]"},{"why":"Gives the step-size and averaging analysis that Theorem 2 adapts from unconstrained subgradient descent to the constrained switching subgradient method.","marker":"[24]"},{"why":"Provides a prior switching-subgradient treatment for nonsmooth inequality constraints, which the paper extends to a single-loop strongly convex setting.","marker":"[3]"},{"why":"Establishes the weak-convexity stationarity framework and the stochastic subgradient rate that the paper builds on for its oracle analysis.","marker":"[15]"},{"why":"Used in Remark 2 as the level-set oracle that gives the smooth-case total complexity $O(1/\\epsilon^3)$.","marker":"[29]"},{"why":"Used in Remark 2 as the augmented Lagrangian oracle that gives the smooth-case total complexity $O(1/\\epsilon^3)$.","marker":"[48]"}],"fun_headline_variants":["Quadratic regularization tames weakly convex constraints","Subgradient method: O(1/ε⁴) for weakly convex constraints","Inexact prox steps for weakly convex constraints","O(1/ε⁴) for weakly convex constrained optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's rates depend on a uniform Slater condition: every point that is already $\\epsilon^2$-feasible must be separated from the constraint boundary by a fixed margin $\\sigma_\\epsilon$ after regularization, which is stronger than ordinary Slater's condition and is only verified in the paper on a small example.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic regularization tames weakly convex constraints","Subgradient method: O(1/ε⁴) for weakly convex constraints","Inexact prox steps for weakly convex constraints","O(1/ε⁴) for weakly convex constrained optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000809,"raw_usage":{"total_tokens":3554,"prompt_tokens":955,"completion_tokens":2599,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":2529}},"tokens_in":571,"tokens_out":2599,"duration_ms":17318,"temperature":1.0,"reasoning_tokens":2529,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:01:28.175896+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a weakly convex constrained problem whose feasible region satisfies ordinary Slater's condition but has an $\\epsilon^2$-feasible path along which $\\min_{y\\in X}\\{g(y)+((\\rho+\\rho_\\epsilon)/2)\\|y-x\\|^2\\}$ approaches zero; run Algorithm 1 on this problem. If the subproblem Lagrange multipliers fail to stay bounded, or the promised $O(1/\\epsilon^4)$ rate does not appear, then the uniform Slater assumption is doing essential work rather than being a technical convenience.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the switching subgradient method that Algorithm 2 adapts to solve the strongly convex subproblem with deterministic guarantees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the online stochastic subgradient method used as Algorithm 3, including the high-probability bounds that make it an oracle."},{"cited_title":"Bayandina, P","cited_arxiv_id":null,"evidence_quote":"Provides a prior switching-subgradient treatment for nonsmooth inequality constraints, which the paper extends to a single-loop strongly convex setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Used in Remark 2 as the level-set oracle that gives the smooth-case total complexity $O(1/\\epsilon^3)$."},{"cited_title":"Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming","cited_arxiv_id":"1711.05812","evidence_quote":"Used in Remark 2 as the augmented Lagrangian oracle that gives the smooth-case total complexity $O(1/\\epsilon^3)$."}],"review_version":1}