{"id":"6cde2774-1814-4093-92ab-bb6db0baa627","arxiv_id":"2506.08506","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Convex majorization methods for nonconvex constrained problems achieve O(ε^{-(κ+1)/κ}) iteration complexity under Hölderian gradients, with a second-order variant reaching approximate second-order stationarity in O(1/ε1+1/ε2) subproblem solves.","lead":"This paper proves how many iterations a family of 'convex majorization' algorithms needs to approximately solve nonconvex optimization problems with constraints, including cases where gradients are only Hölder continuous. The results extend known complexity guarantees and add a second-order variant that targets stronger stationary solutions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof invokes Assumption 3 only at strictly feasible centers, but CMMA can hit the constraint boundary under Assumptions 1–2; the min-step selection may then land on a non-strictly-feasible iterate, leaving a gap in the proof.","rationale":"The reader's verdict of CONDITIONAL is well-founded, and I agree that the numerical section and novelty claims are weak. My stress-test focuses on the proof of Theorem 1, the central first-order complexity result. The paper is honest about Assumption 3 being unverifiable a priori, but I find a more specific proof-completeness issue: Assumption 3 is only stated for strictly feasible centers, while Algorithm CMMA does not maintain strict feasibility under Assumptions 1–2. The descent argument only gives c_i(x_{k+1}) ≤ 0. The strictness convention in Section 3.1 (choosing L_i strictly larger than minimal) is not part of Assumption 1. The one-dimensional example shows the min-step selection can land on a boundary iterate, so the proof of Theorem 1 cannot apply Assumption 3 at the chosen k*. This does not necessarily invalidate the theorem's conclusion (the example still gives a KKT point), but it means the theorem as stated is not proven. A patch would be to add an explicit strict-feasibility maintenance assumption or extend Assumption 3 to all feasible centers in Lev(x0). The FOSO theorem's stationarity notion is also nonstandard and the 'first result' claim is overstated, as the reader notes. Overall, the conditional verdict should stand, with these issues required for revision.","tokens_in":29562,"tokens_out":38044,"duration_ms":391256,"concrete_test":"Run Algorithm CMMA on the problem min -x s.t. c(x)=x^2-1≤0 using surrogates (4) with L=1, L_1=2, starting from x_0=0. Verify that x_1=1 (so c(x_1)=0) and that x_1 is a fixed point (d_1=0). For any ϱ<1, inequality (1) forces the k* selected in Theorem 1 to be k*=1, for which x_{k*} is not strictly feasible, so Assumption 3 cannot be invoked. If the proof is modified to handle boundary centers (e.g., by adding a strictness assumption or by extending Assumption 3), the computed KKT error at x_1 should still be certified; otherwise the theorem statement needs revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Assumption 3 is stated only for centers x that are strictly feasible to (P). In the proof of Theorem 1, the line 'By Assumption 3, there exist...' is applied to subproblem (P_{x_{k*}}) after selecting k* so that ||d_{k*}|| ≤ ϱ via (1). Nothing in Assumptions 1 and 2 or in Algorithm CMMA guarantees that the iterates remain strictly feasible: the subproblem constraints are \\tilde c_i(z|x_k) ≤ 0, and Assumption 1 gives c_i(z) ≤ \\tilde c_i(z|x_k), which only yields c_i(x_{k+1}) ≤ 0, not c_i(x_{k+1}) < 0. The strict-feasibility preservation noted in Section 3.1 relies on choosing L_i strictly larger than the minimal Hölder constants—a convention not contained in Assumption 1. A one-dimensional example exhibits the gap: min -x s.t. x^2-1≤0, surrogates (4) with L=1, L_1=2 (minimal), starting at x_0=0 gives x_1=1, so the only small step occurs at a boundary point, where Assumption 3 no longer applies. Thus Theorem 1's proof needs an additional strict-feasibility assumption (or an extension of Assumption 3 to all feasible centers) to be complete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a convex majorization framework (CMMA) for nonconvex constrained optimization, in which convex surrogate functions majorize the objective and the constraints and iterates are kept feasible. Under gradient-Hölderian surrogates, Slater's condition, bounded level sets, and a uniform multiplier bound (Assumption 3), Theorem 1 gives an O(K^{-κ_min/(κ+1)}) bound on the KKT error after K subproblem solves. Explicit surrogates are constructed for Hölderian, difference-of-convex, and nested composite problems. For convex problems, the paper derives an O(1/K^κ) function-value gap for Algorithm GHMA and linear convergence under strong convexity, discusses efficient dual solutions of the convex subproblems, proposes a two-tier second-order algorithm FOSO with claimed O(1/ε1 + 1/ε2) complexity, and analyzes barrier and Dikin-ellipsoid variants. Numerical experiments on copositive programming illustrate the behavior of the methods.","tokens_in":29805,"tokens_out":18541,"duration_ms":213570,"significance":"The proposed framework is attractive because it maintains feasible iterates and covers objective and constraint functions whose gradients are only Hölder continuous, a setting not handled by standard gradient-Lipschitz analyses. The first-order complexity estimates are derived from structural assumptions rather than fitted to data, and the convex-case analysis gives explicit constant dependence. If the proof gaps identified below are repaired, the main first-order results would be a valuable contribution to nonconvex constrained optimization under limited smoothness. The second-order result, if fully proved, would also be the first of its kind for nonconvex constraints, which makes the missing proof of Theorem 14 especially important.","major_comments":[{"comment":"The proof invokes Assumption 3 at x_{k*} without establishing that x_{k*} is strictly feasible. Assumption 3 is stated only for centers x that are strictly feasible, and under Assumptions 1–2 alone Algorithm CMMA can produce boundary iterates; the strict-feasibility preservation mentioned in §3.1 relies on taking L_i strictly larger than the minimal Hölder constant, which is not assumed in Theorem 1. Concretely, for min -x subject to x^2 - 1 ≤ 0 with surrogates (4), L = 1, L_1 = 2, and x_0 = 0, CMMA returns x_1 = 1, a boundary point, and after one more step d_1 = 0, so the small-step index selected by (1) can be a non-strictly-feasible center. The theorem needs either an explicit strict-feasibility preservation assumption or an extension of Assumption 3 to all feasible centers.","section":"§2.1, Theorem 1"},{"comment":"Theorem 14 is stated without proof. No argument is given that bounds the number of first-order subproblem solves (FP_k) or second-order solves (SP_k)', nor is the stopping condition connected to the defined (ε1, ε2)-approximate KKT solution. A proof can likely be supplied from the descent inequalities (each non-terminal first-order step decreases f by at least ε1 and each non-terminal second-order step by at least ε2), but the manuscript must actually provide it, since Theorem 14 is the paper's principal claim for second-order complexity with nonconvex constraints.","section":"§6, Theorem 14"},{"comment":"The telescoping argument for Algorithm CEB defines Δ = F(x_0) - F(x_*), where F(x) = f(x) + r(x) - μ Σ_i ln(-c_i(x)) and x_* is an optimal solution of (P). If x_* lies on the boundary c_i(x_*) = 0 for some i, then F(x_*) = +∞, so Δ is not a finite nonnegative quantity and the bound (29) is not justified. The analysis needs to define a finite reference value for the barrier objective, for example the infimum of F over the strict interior, or explicitly assume a strictly feasible optimal solution.","section":"§7.1, Theorem 16 and preceding display"},{"comment":"The proof of Theorem 17 uses LICQ in Branch 9: it states 'by LICQ, {∇c_i(x*)}_i∈A(x*) are linearly independent' and then defines the matrix inverse in (56). However, Theorem 17 and Algorithm CEAS do not state any constraint qualification. Without LICQ, equation (56) and the boundedness of λ_{k,A} are not established. The theorem should either assume LICQ explicitly or provide a separate argument for the degenerate case.","section":"Appendix, proof of Theorem 17"}],"minor_comments":[{"comment":"In the sum appearing in (7), the exponent should be κ_j rather than κ_i, since each term involves L_j ϱ^{κ_j} from the bound on ∥d∥^{κ_j}.","section":"§3.1, inequality (7)"},{"comment":"The threshold for the second-order stopping criterion is inconsistent: the text and Algorithm FOSO use v((SP_k)') < -2ε2 for the descent test, while the definition of an (ε1, ε2)-approximate KKT solution requires v((SP_k)') ≥ -ε2. Please choose one convention and use it consistently.","section":"§6, definition of approximate KKT solution"},{"comment":"The Dikin-ellipsoid constraint is written with d^T ∇²B_k(x_k) d ≤ δ < 1 in the derivation, but Algorithm FOSO uses d^T ∇²B_k(x_k) d ≤ 1. Clarify whether the boundary is included and how this affects feasibility of the update.","section":"§6, subproblem (SP_k)'"},{"comment":"The theorem statement says 'the iteration sequence {x_k}_{k≥0} generated by' but does not name the algorithm; it should say 'generated by GHMA'.","section":"§4, Theorem 11"},{"comment":"The result is called 'Brinkman's theorem' in the running text and 'Brickman's theorem' in the proposition; the standard attribution is Brickman's theorem, and the spelling should be unified.","section":"§6, Proposition 12"},{"comment":"The claim that dual iterates remain in a 2B neighborhood of an optimal dual solution assumes the non-increasing-distance property for 'many convex optimization algorithms'; this is not true for arbitrary algorithms, so the statement should specify which algorithm is used and verify the property.","section":"§5, dual subproblem analysis"}],"recommendation":"major_revision","confidential_remarks":"The strict-feasibility gap in Theorem 1 and the missing proof of Theorem 14 are fixable within the scope of the manuscript, but they are load-bearing for the main claims. The CEB telescoping issue and the unstated LICQ use in Theorem 17 also require attention. I do not see grounds for rejection, but the revision needs to be substantive rather than cosmetic."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper is a solid, mostly honest complexity analysis of convex majorization for nonconvex constrained problems. The genuinely new pieces are the Hölderian-smoothness complexity bounds—O(epsilon^{-(κ+1)/κ}) for nonconvex and O(epsilon^{-1/κ}) for convex—and the second-order FOSO scheme with a Dikin-ellipsoid subproblem. The CEAS counterexample showing constant stepsize can converge to a nonstationary boundary point is a nice touch. The convex analysis (Lemma 6, Lemma 7, Theorem 10) checks out; I verified the descent and multiplier-bound arguments.\n\nThe main soft spot is Theorem 1. The proof invokes Assumption 3 at x_{k*}, but Assumption 3 only covers strictly feasible centers, and CMMA under Assumptions 1–2 does not guarantee strict feasibility of the iterates. The paper's own Section 3.1 notes that strict preservation requires choosing L_i strictly larger than the minimal Hölder constant—a convention not in Assumption 1. The one-dimensional example in the stress test is real: min -x, x^2-1≤0, with minimal L values, moves to the boundary and the small step occurs there. So the proof as written has a hole. It is fixable: either add strict-feasibility preservation to the algorithm, or extend Assumption 3 to all level-set centers. But it should be flagged to the authors.\n\nOther soft spots are smaller. Assumption 3 is explicitly unverifiable a priori; the sufficient conditions (Propositions 2 and 3) are themselves hard to check. The numerical section reports no code, data, or error bars, and the \"all accurate stable set numbers\" claim is unquantified. The 'first result' for second-order stationarity under nonconvex constraints is plausible but they should soften it in light of [23,18,35].\n\nWho should read this: researchers working on feasible-iterate methods or complexity of constrained nonconvex optimization. The convex result (Theorem 10) is likely useful as a benchmark. The paper deserves a serious referee—the gap is real but localized, and the rest of the theory is worth vetting. Recommend: send to peer review with a request to fix the strict-feasibility handling and to either weaken or better support the novelty claims.","headline":"Useful complexity framework with a fixable gap in Theorem 1's strict-feasibility handling; the convex and second-order parts are worth the referee's time.","tokens_in":30436,"tokens_out":3843,"would_cite":true,"duration_ms":45538,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","65K05","68Q17","52A41"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that nonconvex constrained optimization — even with only Hölderian, non-Lipschitz gradients — is solvable by repeatedly solving convex surrogate subproblems, with $\\epsilon$-KKT complexity…","keywords":["nonconvex optimization","convex majorization","gradient Hölderian continuity","iteration complexity","KKT conditions","self-concordant barrier","Dikin ellipsoid","copositive programming"],"falsifier":"Build a two-constraint instance whose feasible region pinches to a cusp at the optimum so that the active constraint gradients become linearly dependent there; run CMMA while monitoring both the subproblem multipliers $\\|\\lambda_k\\|_\\infty$ and the KKT error $\\mathrm{dist}(0, \\partial L(x_{k+1},\\lambda) + N_X(x_{k+1}))$. If the multipliers grow without bound as the step $\\|x_{k+1}-x_k\\|$ shrinks to zero, Assumption 3 fails and the KKT error should stop decaying at the promised $O(K^{-\\kappa_{\\min}/(\\kappa+1)})$ rate, so a systematically slower exponent is a direct counterexample. A second check targets the second-order claim: because Brickman's theorem holds only for $n\\ge 3$, solving the FOSO direction subproblem on a two-dimensional problem tests whether the $O(1/\\epsilon_2)$ guarantee survives outside the SDP regime.","tokens_in":29302,"feed_emoji":"🎯","tokens_out":19684,"duration_ms":200670,"temperature":0.7,"pith_summary":"The paper tries to establish that nonconvex constrained minimization can be handled by a simple replacement rule: at every iteration, swap the objective and each constraint for a convex function that lies above it and touches it at the current point, solve the resulting convex subproblem, and repeat. Its central result is an iteration-complexity bound for this convex-majorization scheme: after $K$ steps the distance to a KKT point is $O(K^{-\\kappa_{\\min}/(\\kappa+1)})$, so an $\\epsilon$-KKT solution costs $O(\\epsilon^{-(\\kappa+1)/\\kappa})$ convex subproblem solves when all Hölder exponents equal some $\\kappa$. This matters because the framework needs neither convexity nor gradient Lipschitz continuity, only the weaker and more widely available gradient Hölderian property (gradients that vary like $\\|x-y\\|^\\kappa$ rather than like $\\|x-y\\|$), and because every iterate is feasible, so the output is never an infeasible artifact of a penalty or Lagrangian scheme. The same machinery yields $O(\\epsilon^{-1/\\kappa})$ optimality-gap convergence for convex problems, linear convergence under strong convexity, and what the authors put forward as the first complexity guarantee for reaching a second-order stationary point under nonconvex constraints.","feed_headline":"Convex surrogates crack nonconvex problems at proven speed","feed_subtitle":"Provable ε-KKT rates without convexity or Lipschitz gradients — and every iterate stays feasible.","key_machinery":"The load-bearing object is the Hölderian convex envelope: for a function with $(L,\\kappa)$-Hölderian gradient, $\\tilde f(x|y) = f(y) + \\langle\\nabla f(y), x-y\\rangle + \\frac{L}{1+\\kappa}\\|x-y\\|^{1+\\kappa}$ is a convex function that majorizes $f$ and touches it at $y$, and the same envelope is built for each constraint. This object does three jobs: it makes every subproblem convex, it keeps the iterates strictly feasible, and it yields the sufficient-descent inequality $F(x_{k+1}) \\le F(x_k) - \\frac{L}{\\kappa+1}\\|x_{k+1}-x_k\\|^{\\kappa+1}$, whose telescoping produces the $O(K^{-1/(\\kappa+1)})$ residual bound. The transfer from residual decay to KKT error is carried by the Hölder mismatch terms $2L\\|d_k\\|^\\kappa + 2\\sum_i \\lambda_i L_i \\|d_k\\|^{\\kappa_i}$, which are controlled only if Assumption 3 supplies a uniform multiplier bound. In the second-order variant the key machinery is Brickman's theorem, the statement that the set $\\{(x^\\top Q_1 x,\\, x^\\top Q_2 x): \\|x\\|=1\\}$ is convex for $n\\ge 3$, which yields an SDP representation of the Dikin-ellipsoid direction subproblem $\\min d^\\top Q d + \\|d\\|^3$ subject to $d^\\top P d \\le 1$; the Dikin ellipsoid, built from the self-concordant barrier of the surrogate constraints, guarantees the step stays feasible.","core_discovery":"The central claim is the convergence-rate theorem for the convex majorization framework: if the Lagrangian multipliers of every surrogate subproblem stay uniformly bounded near the solution (Assumption 3), then after $K \\ge (\\kappa+1)\\Delta/(L\\varrho^{\\kappa+1})$ iterations there is an iterate whose distance to a KKT point of the original problem is $O(K^{-\\kappa_{\\min}/(\\kappa+1)})$, and any constraint active at that iterate is violated by at most $O(K^{-1/(\\kappa+1)})$. On the paper's own terms this is a proof that nonconvex, non-Lipschitz constrained problems are solvable at a provable rate through convex surrogates alone. For the convex case, the same surrogate construction yields a feasible-sequence method that reaches an $\\epsilon$-optimal point in $O(\\epsilon^{-1/\\kappa})$ iterations, and a linear rate $O((L_B/\\alpha)\\log(1/\\epsilon))$ when the objective is strongly convex and $\\kappa=1$. The second-order extension, Algorithm FOSO, alternates first-order subproblems ($O(1/\\epsilon_1)$ solves) with second-order subproblems over a Dikin ellipsoid ($O(1/\\epsilon_2)$ solves), and the paper claims it as the first result of its kind for nonconvex constraints: an $(\\epsilon_1,\\epsilon_2)$-approximate KKT, i.e. second-order stationary, point is reached in $O(1/\\epsilon_1 + 1/\\epsilon_2)$ subproblem solves, with the internal cubic direction subproblem solvable exactly as a semidefinite program.","pith_inferences":["My inference: because Assumption 3 cannot be verified in advance, the theory doubles as a running diagnostic — monitor $\\sup_k\\|\\lambda_k\\|_\\infty$ while CMMA runs, and the promised $O(K^{-\\kappa_{\\min}/(\\kappa+1)})$ KKT rate should appear exactly while this running supremum stays bounded.","My inference: the complexity depends on the mismatch exponents of the convex envelope one can actually construct, not on the problem's intrinsic smoothness alone, so a problem endowed with a well-structured convex majorant converges provably faster than its raw gradient regularity would suggest.","My inference: the SDP reformulation of the second-order direction subproblem relies on Brickman's theorem and hence on $n\\ge 3$; whether the $O(1/\\epsilon_2)$ guarantee carries over to two-dimensional problems, where the ratio set is an ellipse rather than a spectrahedron, is a natural follow-up check.","My inference: the counterexample with constant steps converging to a non-stationary boundary point is a warning about the affine-scaling surrogate: the Dikin-ellipsoid variants, attractive when the number of constraints is very large, are less robust than the other variants, and the diminishing-step requirement is essential rather than a technicality."],"forward_implications":["Problems whose gradients are only Hölder continuous — such as regression with $\\ell_p$ losses for $1