{"id":"2eb24189-f3a6-4de4-bf45-cceb9f5da74c","arxiv_id":"1908.11518","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An inexact proximal-point penalty algorithm finds ε-stationary points of non-convex constrained problems in O~(ε^{-5/2}) steps with convex constraints and O~(ε^{-3}) to O~(ε^{-4}) steps with non-convex constraints.","lead":"This paper designs and analyzes an algorithm for optimization problems where the objective and constraints may both be non-convex, combining proximal-point and penalty ideas. It proves worst-case complexity bounds for finding approximate stationary points, improving known rates in several settings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O~(ε^-3) non-convex-constraint rate hinges on Assumption 4, a global LICQ-type error bound that is not verified for the paper's own K=7/10 experiments and fails for simple non-convex constraints.","rationale":"I reviewed the convex-constraint proof in Section 5 in detail, including Lemma 3's multiplier bounds, Lemma 4's feasibility bound, the averaging argument in Theorem 2, and the inner-iteration summation in Corollary 1. I found no algebraic error: the Cauchy-Schwarz steps, the telescoping penalty sums, and the growth of the AdapAPG iteration count T_k = O~((k+1)^{1/4}) are consistent, so the O~(ε^{-5/2}) claim appears internally sound. The non-convex-constraint result in Section 6.2 is also derived correctly from Assumption 4; the issue is that this assumption is global and restrictive. It is not merely a statement about feasible points, and it can fail for natural nonconvex constraints such as a smoothed sphere. The appendix only checks the assumption for a simplified K=2 version of the mNPC problem, while the numerical experiments use K=7 and K=10, so the experiments do not validate the O~(ε^{-3}) regime. This matches the reader's weakest_assumption. Since the paper presents the O~(ε^{-3}) result as conditional and provides a fallback O~(ε^{-4}) guarantee, the appropriate verdict remains conditional acceptance rather than rejection. The reader's caveats about the 'by far the best' overclaim and the absence of error bars in the numerics also support keeping the verdict unchanged.","tokens_in":29997,"tokens_out":28637,"duration_ms":275480,"concrete_test":"For the covtype and mnist instances of Section 7, compute or globally lower-bound the quantity inf_{x in X} dist(Jc(x)^T c(x)+Jf(x)^T[f(x)]_+, -N_X(x)) / sqrt(||[f(x)]_+||^2+||c(x)||^2), restricting to points where the denominator is nonzero. If the infimum is zero, Assumption 4 fails for the tested problems and the O~(ε^-3) guarantee of Corollary 2 does not apply to the reported experiments.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 4 (Eq. 55) is the load-bearing premise for the O~(ε^-3) result in Corollary 2. It requires a uniform lower bound on dist(Jc(x)^T c(x)+Jf(x)^T[f(x)]_+, -N_X(x)) divided by sqrt(||[f(x)]_+||^2+||c(x)||^2) over the whole compact domain X, including infeasible points. This is much stronger than a feasible-point LICQ: for the single nonconvex equality constraint c(x)=||x||^2-1 on X=B_2, Jc(x)^T c(x)=2x(||x||^2-1), so at x=0 the ratio is 0 and (55) fails. Hence the theorem excludes very simple nonconvex constraints. The appendix verifies (55) only for the K=2 mNPC model, not for the K=7 and K=10 datasets used in Section 7, so the numerical section does not demonstrate the O~(ε^-3) regime. If Assumption 4 fails, the paper's own fallback is only O~(ε^-4) weak stationarity under a feasible initial point (Corollary 3). This is a limitation rather than an internal inconsistency: Corollary 2 is conditional and its proof appears valid given (55). But it is the main point where the advertised non-convex-constraint rate is least secure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies an inexact proximal-point penalty (iPPP) method, Algorithm 4, for constrained nonconvex optimization problems of the form (1), where the objective and constraints may be nonconvex and a nonsmooth convex term g with compact domain is present. Each outer iteration adds a proximal term and quadratic penalty terms, making the subproblem strongly convex under weak-convexity assumptions, and the subproblems are solved by the adaptive accelerated proximal gradient method of Lin and Xiao. Complexity results are given in terms of the total number of proximal gradient steps needed to produce an ε-stationary or weak ε-stationary point. For convex constraints with a weakly convex objective and Slater's condition, the paper proves an O~(ε^{-5/2}) rate (Corollary 1). For nonconvex constraints, it proves O~(ε^{-3}) under a global nonsingularity/error-bound condition (Assumption 4, Corollary 2) and O~(ε^{-4}) for a weak ε-stationary point under a feasible initial point (Corollary 3). Numerical experiments compare iPPP with a trust-region penalty method on multi-class Neyman-Pearson classification problems.","tokens_in":30351,"tokens_out":8390,"duration_ms":75572,"significance":"If the results hold, the paper gives a meaningful improvement over prior first-order complexity bounds for constrained nonconvex optimization, particularly the O~(ε^{-5/2}) rate for convex constraints and the conditional O~(ε^{-3}) rate for nonconvex constraints under Assumption 4. The paper is commendably explicit about parameter choices and about the distinction between ε-stationarity and weak ε-stationarity, and the outer-loop analysis is self-contained and does not rely on circular reasoning: the AdapAPG subroutine is an externally proven component. The main limitation is that the flagship nonconvex-constraint rate rests on a strong global condition (Assumption 4) whose scope is not fully delineated in the numerical section; however, the theorems themselves are stated conditionally and their proofs appear essentially sound. The convex-case proof has a fixable but important technical error in the bound leading to the O~(ε^{-5/2}) rate.","major_comments":[{"comment":"As written, inequality (42) is not a valid consequence of (41). From (41) and β_k = β√(k+1), multiplying (β_k − β_{k−1}) through the right-hand side gives (√(k+1)−√k) · 4(D+M_y^2+M_λ^2)/β_k, not (√(k+1)−√k) β_k · 4(D+M_y^2+M_λ^2). The displayed version is dimensionally inconsistent and, if summed over k, would grow linearly in K, whereas the subsequent bound (43) is O(1/β). Since (43) is used to define C_1 and hence the O~(ε^{-5/2}) complexity in Corollary 1, this step must be corrected. The repair is local: insert the missing factor 1/β_k in the right-hand side of (42); the rest of the proof then goes through as written.","section":"Section 5.2, Eq. (42)"},{"comment":"The advertised O~(ε^{-3}) rate for nonconvex constraints is conditional on the global nonsingularity inequality (55). This condition is not verified for the K=7 and K=10 datasets used in the numerical experiments; the Appendix verifies only the K=2 model, and that verification itself requires additional conditions (origin feasibility and (87)). Moreover, Assumption 4 is substantially stronger than a feasible-point LICQ: for example, with c(x)=‖x‖²−1 and X=B_2, the ratio in (55) is zero at x=0, so the assumption fails for very simple nonconvex equality constraints. The theorem is correctly stated as conditional, but the paper should explicitly delimit the scope of Corollary 2 in the abstract and introduction, and should either verify (55) for the actual test problems or state that the numerical experiments do not exercise the O~(ε^{-3}) regime.","section":"Section 6.2, Assumption 4 and Corollary 2; Section 7 and Appendix"}],"minor_comments":[{"comment":"The contribution statement that the O~(ε^{-5/2}) convex-constraint complexity 'remains by far the best' is in tension with the discussion in Section 2, which cites [41] and [36] as also achieving the same O~(ε^{-5/2}) order under the same assumptions after the first draft of this paper. Please update the wording to acknowledge these contemporaneous results.","section":"Section 1.1 and Section 2"},{"comment":"The paragraph following Assumption 4 says that the condition is inspired by LICQ and can hold on int(X), but the global form (55) is much stronger. It would help readers to state explicitly that Assumption 4 is an error-bound condition over the whole compact domain, including infeasible points, and to give a one-line example showing the difference from feasible-point LICQ.","section":"Section 6.2, Assumption 4 discussion"},{"comment":"The numerical comparison reports that the initial iterate x(0)=0 is feasible for (83), but it does not state whether the conditions used in the Appendix to verify Assumption 4 for the K=2 model (nonzero data vectors, pairwise nonnegative inner products, and f(0)≤0) hold for the K=7 and K=10 datasets. Please clarify this in the experimental setup or state explicitly that the verification is not intended to cover those instances.","section":"Section 7, experimental setup"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is technically sound in its main conditional claims, and the proof strategy is clear. The main blocking issue is the incorrect inequality in Eq. (42), which is needed for the convex-case complexity; this is fixable but must be corrected before the central O~(ε^{-5/2}) claim can be accepted as proven. In addition, the scope of Assumption 4 should be carefully limited, especially in the abstract and introduction, so that the nonconvex-constraint rate is not presented as applying more broadly than the assumptions allow. The numerical section should also be reconciled with the fact that Assumption 4 is not verified for the larger datasets."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the main machinery is sound: the O~(ε^{-5/2}) complexity for nonconvex objectives with convex nonlinear constraints and affine equalities is a real improvement, and the proof, including bounded multipliers under Slater, checks out. Second, the paper's strongest nonconvex-constraint claim, O~(ε^{-3}), is only as good as Assumption 4, and Assumption 4 is stronger than ordinary LICQ. The stress-test example is correct: for c(x)=||x||^2-1 on a Euclidean ball, the ratio in (55) is zero at the center, so that simple constraint is excluded. The appendix verifies the assumption only for the K=2 version of the test problem; it does not cover the K=7 and K=10 datasets used in the experiments. That does not make the theorem false, but it narrows the advertised regime.\n\nWhat the paper does well: it gives explicit parameter settings, splits convex versus nonconvex constraints cleanly, uses the published AdapAPG theorem as an external input without circularity, and correctly identifies a proof error in Sahin et al. The fallback O~(ε^{-4}) weak-stationarity result under a feasible initial point is a useful safety net and is honestly labeled. The numerics are illustrative only: one run per setting, no error bars, and the stationarity measure is computed by a QP rather than the paper's Definition 1. That is fine for a theory paper, but it is not evidence for the nonconvex-constraint rate.\n\nSoft spots, in proportion. The contribution bullet saying the convex-case rate \"remains by far the best\" is an overclaim even on the paper's own references: reference [41] is cited as achieving the same O~(ε^{-5/2}) under the same convex-constraint assumptions. That claim needs rewording. Assumption 4 is the load-bearing item; the paper is open that it is global, but a reader will want a clearer statement of where it actually holds, and the appendix's K=2 verification does not cover the reported experiments. Since Corollary 2 is explicitly conditional, I see a scope limitation rather than an internal inconsistency. Corollary 3 returns only weak stationarity, and that weaker guarantee should stay prominent whenever Assumption 4 is dropped.\n\nBottom line: this deserves serious refereeing. The convex-constraint rate alone is a solid contribution, and the rest is a conditional result with an honest fallback. I would accept a review invitation and push for a revised version that fixes the overclaim and puts the non-singularity assumption front and center.","headline":"A sound and genuinely useful complexity paper; the headline nonconvex-constraint rate is real but narrower than advertised because it rests on a global error-bound assumption that simple constraints fail.","tokens_in":30842,"tokens_out":2786,"would_cite":true,"duration_ms":27213,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"An inexact proximal-point penalty method finds epsilon-stationary points of nonconvex constrained problems in O~(epsilon^-5/2) proximal-gradient steps under Slater's condition, and in O~(epsilon^-3) or O~(epsilon^-4) depending on…","keywords":["constrained nonconvex optimization","proximal-point method","quadratic penalty method","weak convexity","epsilon-stationary point","first-order complexity","adaptive accelerated proximal gradient"],"falsifier":"Compute, for the problem class in question, the infimum over the domain of the ratio dist(Jc(x)^T c(x)+Jf(x)^T[f(x)]_+, -N_X(x)) divided by $\\sqrt$(||[f(x)]_+||^2+||c(x)||^2). If that infimum is 0, for instance at an infeasible point where the gradient of a violated constraint vanishes, then Assumption 4 cannot hold, so the $epsilon^{{-3}}$ claim does not apply and one must check whether the feasible-initialization result degrades to $epsilon^{{-4}}$ as predicted.","tokens_in":29787,"feed_emoji":"📉","tokens_out":8483,"duration_ms":77684,"temperature":0.7,"pith_summary":"The paper proposes and analyzes a first-order method for constrained nonconvex optimization where both the objective and the constraints may be nonconvex. Each subproblem adds a proximal term and quadratic penalty terms to the original objective, which, under a weak-convexity assumption, makes the subproblem strongly convex and solvable by an adaptive accelerated proximal-gradient routine. The paper claims three complexity results measured in proximal-gradient steps: O~($epsilon^{{-5/2}}$) for weakly convex objectives with convex constraints under Slater's condition, O~($epsilon^{{-3}}$) for nonconvex constraints under a non-singularity condition, and O~($epsilon^{{-4}}$) for weak stationarity when only a feasible initial point is available. The convex-constraint rate is described as the best known first-order complexity for this problem class.","feed_headline":"Proximal-penalty method reaches ε-stationarity in O~(ε^-5/2) steps","feed_subtitle":"Proximal plus penalty terms make subproblems strongly convex, yielding ~ε^-5/2 complexity for convex constraints.","key_machinery":"The load-bearing object is the prox-penalty subproblem phi_k(x)=f_0(x)+g(x)+(gamma_k/2)||x-$xbar^{{(k)}}$||^2+(beta_k/2)(||c(x)||^2+||[f(x)]_+||^2), with g kept as the nonsmooth convex term. The proximal term gamma_k/2||x-$xbar^{{(k)}}$||^2 is chosen above the weak-convexity constant, which converts the possibly nonconvex objective-plus-penalty into a strongly convex composite; the quadratic penalties beta_k/2(||c(x)||^2+||[f(x)]_+||^2) drive the iterates toward feasibility. Inside each subproblem, the adaptive accelerated proximal-gradient routine supplies a complexity bound in terms of the condition number of phi_k, and the outer analysis averages the per-iteration stationarity, feasibility, and complementary-slackness residuals so that selecting the best iterate by maximum residual yields the reported epsilon-stationary rates.","core_discovery":"On the paper's own terms, the central discovery is that a proximal-point quadratic-penalty hybrid can be tuned so that every subproblem is strongly convex, even when the original objective and constraints are only weakly convex, and that approximate solutions to these subproblems, output by an adaptive accelerated proximal-gradient routine, carry enough information to certify an epsilon-stationary point of the original problem. The analysis gives matching bounds: feasibility violation shrinks like 1/beta_k and the stationarity of the best iterate is controlled by the subproblem tolerances plus the proximal displacement, so choosing beta_k, gamma_k, and epsilon_k appropriately makes the returned point satisfy the paper's Definition 1. The claimed rates are O~($epsilon^{{-5/2}}$) for convex constraints with Slater's condition, O~($epsilon^{{-3}}$) under a non-singularity condition for nonconvex constraints, and O~($epsilon^{{-4}}$) for weak stationarity when only a feasible initial point is available.","pith_inferences":["Editorial inference: the balancing of three averaged residuals, namely stationarity, feasibility, and complementarity, looks like a transferable template; stochastic or distributed variants of the method could inherit the same rates if the subsolver's complexity bound survives expectation.","Editorial inference: the epsilon^{-3}-to-epsilon^{-4} gap between the two nonconvex-constraint results suggests that the missing ingredient is a substitute for the uniform non-singularity margin; any constraint-error bound that controls infeasible directions from the normal cone, even a local or averaged one, might close the gap.","Editorial inference: the numerical experiment on Neyman-Pearson classification indicates that growing penalty parameters beat fixed ones; a testable extension is an adaptive schedule for beta_k driven by observed infeasibility, which the theory does not yet cover."],"forward_implications":["If the O~(epsilon^{-5/2}) result is correct, first-order methods for weakly convex objectives with convex nonlinear constraints and Slater's condition improve by a factor of about epsilon^{-1/2} over the previous linear-constraint quadratic-penalty result.","For problems with nonconvex constraints satisfying the non-singularity condition, the method certifies a full epsilon-stationary point, including approximate complementary slackness, in O~(epsilon^{-3}) proximal-gradient steps without requiring a feasible starting point.","When no non-singularity condition is known but a feasible starting point is available, the method still guarantees a weak epsilon-stationary point in O~(epsilon^{-4}) steps.","Because the inner subroutine adapts to unknown strong-convexity and smoothness constants, the complexity bounds do not require exact knowledge of those constants, only upper bounds sufficient to set gamma_k.","The stronger stationarity notion in Definition 1 means the returned point satisfies an exact complementarity condition for constraints with f_i(x)<0, not merely for f_i(x)<-epsilon."],"supporting_citations":[{"why":"Supplies the AdapAPG subroutine and the subproblem complexity theorem that turns subproblem condition numbers into proximal-gradient step counts.","marker":"[44]"},{"why":"Introduced the adaptive accelerated proximal-gradient framework whose estimates of unknown strong-convexity and smoothness constants Algorithm 3 inherits.","marker":"[53]"},{"why":"Provides the KKT existence and multiplier theory used to bound the Lagrangian multipliers of the auxiliary strongly convex subproblem under Slater's condition.","marker":"[58]"},{"why":"The quadratic-penalty accelerated inexact proximal-point method for linear constraints that this paper extends to nonlinear constraints and improves from O(epsilon^{-3}) to O~(epsilon^{-5/2}) in the convex-constraint case.","marker":"[35]"},{"why":"The inexact augmented Lagrangian baseline whose non-singularity assumption inspires Assumption 4 and whose claimed O~(epsilon^{-3}) rate is corrected to O~(epsilon^{-4}); this paper improves on it.","marker":"[59]"},{"why":"The proximal augmented Lagrangian analysis for nonlinear equality constraints that motivates the non-singularity condition and supplies the comparison rate.","marker":"[72]"},{"why":"The trust-region penalty method used as the numerical baseline in the multiclass Neyman-Pearson experiments.","marker":"[10]"}],"fun_headline_variants":["Proximal-penalty method: O~(ε^-5/2) for convex constraints","Inexact proximal-penalty: O~(ε^-3) for non-convex constraints","Proximal-penalty method: complexity for convex and non-convex constraints","Subproblems strongly convex: proximal-penalty for non-convex optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise for the best nonconvex-constraint rate is Assumption 4: a single uniform margin nu>0 must control every point's constraint violation by a constraint-gradient quantity, including points that are far from feasible; if no such margin exists, the $epsilon^{{-3}}$ guarantee is not claimed and the method's known guarantee drops to weak epsilon-stationarity in $epsilon^{{-4}}$ from a feasible start.","fun_headline_variants_meta":{"raw":{"variants":["Proximal-penalty method: O~(ε^-5/2) for convex constraints","Inexact proximal-penalty: O~(ε^-3) for non-convex constraints","Proximal-penalty method: complexity for convex and non-convex constraints","Subproblems strongly convex: proximal-penalty for non-convex optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000882,"raw_usage":{"total_tokens":3824,"prompt_tokens":972,"completion_tokens":2852,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":2761}},"tokens_in":588,"tokens_out":2852,"duration_ms":20050,"temperature":1.0,"reasoning_tokens":2761,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:14:06.175719+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for the problem class in question, the infimum over the domain of the ratio dist(Jc(x)^T c(x)+Jf(x)^T[f(x)]_+, -N_X(x)) divided by $\\sqrt$(||[f(x)]_+||^2+||c(x)||^2). If that infimum is 0, for instance at an infeasible point where the gradient of a violated constraint vanishes, then Assumption 4 cannot hold, so the $epsilon^{{-3}}$ claim does not apply and one must check whether the feasible-initialization result degrades to $epsilon^{{-4}}$ as predicted.","supporting_citations":[{"cited_title":"Computational Optimization & Applications 60(3) (2015)","cited_arxiv_id":null,"evidence_quote":"Supplies the AdapAPG subroutine and the subproblem complexity theorem that turns subproblem condition numbers into proximal-gradient step counts."},{"cited_title":"Mathematical Programming 140(1), 125–161 (2013)","cited_arxiv_id":null,"evidence_quote":"Introduced the adaptive accelerated proximal-gradient framework whose estimates of unknown strong-convexity and smoothness constants Algorithm 3 inherits."},{"cited_title":"Princeton mathematical series","cited_arxiv_id":null,"evidence_quote":"Provides the KKT existence and multiplier theory used to bound the Lagrangian multipliers of the auxiliary strongly convex subproblem under Slater's condition."},{"cited_title":"SIAM Journal on Optimization 29(4), 2566–2593 (2019)","cited_arxiv_id":null,"evidence_quote":"The quadratic-penalty accelerated inexact proximal-point method for linear constraints that this paper extends to nonlinear constraints and improves from O(epsilon^{-3}) to O~(epsilon^{-5/2}) in the convex-constraint case."},{"cited_title":"In: Advances in Neural Information Processing Systems (2019)","cited_arxiv_id":null,"evidence_quote":"The inexact augmented Lagrangian baseline whose non-singularity assumption inspires Assumption 4 and whose claimed O~(epsilon^{-3}) rate is corrected to O~(epsilon^{-4}); this paper improves on it."},{"cited_title":"Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints","cited_arxiv_id":"1908.00131","evidence_quote":"The proximal augmented Lagrangian analysis for nonlinear equality constraints that motivates the non-singularity condition and supplies the comparison rate."},{"cited_title":"SIAM Journal on Optimization 21(4), 1721–1739 (2011)","cited_arxiv_id":null,"evidence_quote":"The trust-region penalty method used as the numerical baseline in the multiclass Neyman-Pearson experiments."}],"review_version":1}