{"id":"b3325a1e-7644-4a2e-8a68-f05cace0d817","arxiv_id":"2411.14342","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Smoothing compositional gradient and prox-linear approximate gradient methods reach stationary points in O(1/(δε²)) and O(1/ε²) iterations for structured non-smooth non-convex compositions.","lead":"This note proves iteration bounds for two first-order methods that solve non-smooth, non-convex compositional optimization problems with special structure. The bounds improve on existing rates for similar problem classes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.7's inequality (11) uses the wrong weak-convexity modulus for G(x): the natural constant is βC_v/µ, not L_gC_v/µ, so the proof needs β≤L_g or a corrected constant.","rationale":"After reading the full text, the main claims are credible. Theorem 5.8's hidden constants C1 and C are actually implied by Assumption 5.1: bounded g_i and Lipschitz h_i make both h_i(g_i(x)) and f_{i,µ}(z) bounded, so no additional boundedness assumption is needed. The algebra from (27) and (30) to (31), while not tight, is valid because the derived left-hand side has larger coefficients than Σ(Δ_k+δ_k) and the right-hand side includes only nonnegative extra terms. The single genuine soft spot is the weak-convexity constant in Theorem 4.7. The proof uses C_v L_g/µ in (11), but the natural modulus is βC_v/µ, and L_g does not bound β. This is a proof gap in a constant, not a fatal flaw: replacing L_g by β (or adding β≤L_g to Assumption 4.1) preserves the O(1/(δε²)) rate and the downstream argument. Since the reader already flagged exactly this point and returned CONDITIONAL, no verdict change is needed. If the authors correct the constant, the theorem's stated complexity is supported.","tokens_in":16179,"tokens_out":31187,"duration_ms":258174,"concrete_test":"Analytically re-derive (11) for the active function at a maximizer: for any v with ‖v‖≤C_v, the map x↦v^T g(x) has a β‖v‖-Lipschitz gradient, giving a one-sided quadratic lower bound with modulus β‖v‖, not L_g‖v‖. To confirm the claimed constant fails, evaluate (11) with a bounded-below Lipschitz h, µ=1, and scalar g(x)=sin(kx)/k at x_k=π/(2k); the active curvature is ≈k(1−1/k), exceeding C_vL_g≈1 for k>2, while βC_v≈k works. If (11) fails, replace C_vL_g by C_vβ in Theorem 4.7 and in C; the O(1/(δε²)) rate is unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4, Theorem 4.7 and equation (11), the proof asserts that G(x) in (3) is C_v L_g/µ-weakly convex. For a maximizer v at x_k, the active function φ_v(x)=(1/µ)v^T g(x) has gradient (1/µ)∇g(x)^T v, whose Lipschitz modulus is β‖v‖/µ. Hence the uniform weak-convexity modulus of the max function is β C_v/µ, not L_g C_v/µ. L_g does not control β: for g(x)=sin(kx)/k one has L_g=1 and β=k. The constant C=L_g²+βC_g+C_vL_g should therefore read L_g²+βC_g+βC_v (or use max{L_g,β}). This does not change the O(1/(δε²)) order, but as written the stated K is not supported unless Assumption 4.1 additionally requires β≤L_g, which the paper does not state. The rest of the descent argument, equations (10), (12)–(15), and the conversion to a stochastic (δ,ε)-stationary point, is unaffected once this constant is corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the compositional optimization problem min_x h(g(x)) with Lipschitz, nonsmooth, and generally nonconvex h, and smooth g. In Section 4, assuming the proximal mapping of h is easy to compute, the authors propose a smoothing compositional gradient method (Algorithm 1) and prove that it finds a stochastic chain-rule (δ, ε)-stationary point in O(1/(δε^2)) iterations (Theorem 4.7). In Section 5, assuming h is a difference of two convex Lipschitz functions composed with smooth maps, the authors propose a prox-linear approximate gradient method (Algorithm 2) and prove that it finds a stochastic nearly 2ε-critical point in O(1/ε^2) iterations (Theorem 5.8). The analysis is based on Moreau-envelope smoothing, weak convexity of the smoothed objectives, and standard descent arguments.","tokens_in":16537,"tokens_out":31569,"duration_ms":262880,"significance":"If fully established, the claimed rates would improve on the O(1/(δε^3)) typical for Goldstein stationarity in nonsmooth nonconvex optimization and on the O(1/ε^4) of smoothing DC methods under the stated compositional structure. The paper is largely self-contained: the chain-rule stationarity notion is clearly motivated by the KKT conditions of the lifted constrained problem, Lemma 4.3 and Proposition 5.7 supply the needed technical bounds, and the proof skeletons are standard. The two structural settings are distinct and the algorithms are simple and practically motivated. However, two proof points are not currently supported as written; both are local and fixable without changing the claimed rates.","major_comments":[{"comment":"The proof asserts that G(x) in (3) is C_v L_g/µ-weakly convex. Under Assumption 4.1 the natural uniform modulus for each active function is β‖y‖/µ, because the gradient of y^T g(x) with respect to x is ∇g(x)^T y, whose Lipschitz constant is at most β‖y‖ and not L_g‖y‖. The constant β is not controlled by L_g (for example, g(x)=sin(kx)/k in one dimension has L_g=1 and β=k), so inequality (11) and the definition C := L_g^2 + βC_g + C_v L_g in Theorem 4.7 are not justified unless Assumption 4.1 is augmented with β ≤ L_g, which the paper does not state. The O(1/(δε^2)) rate survives if C is corrected to L_g^2 + βC_g + βC_v (or a max{L_g, β} variant), but the theorem as stated is not proven.","section":"§4, Theorem 4.7, Eq. (11)"},{"comment":"Equation (31) does not follow from the preceding combined inequality. Summing that inequality after multiplying by 32µ^2/γ gives Σ_{k=1}^K(Δ_k+δ_k) + 7Δ_K - 7Δ_0 + (49 - 147/θ^2)δ_0 + (147/θ^2 - 48)δ_K ≤ (32µ^2/γ)(f_µ(z_1)-f_µ(z_{K+1})). Since θ=tc<1, the terms -7Δ_K and -(147/θ^2-48)δ_K are nonpositive and can be dropped, leaving an upper bound with 7Δ_0 + (147/θ^2-49)δ_0; there is no 49Δ_K term. Consequently the subsequent bound Δ_K ≤ 8µC_1 does not enter the estimate, and the displayed K containing the 1568µC_1 term is not supported by the derivation. The proof and the constants in K should be corrected; the O(1/ε^2) rate remains plausible after this correction.","section":"§5, Theorem 5.8, Eq. (31)"}],"minor_comments":[{"comment":"The sentence defining f1 and f2 reads \"We define f1(x) := h1(g1(x)) and f1(x) := h2(g2(x))\", but the second definition should be f2(x) := h2(g2(x)).","section":"§5, after Eq. (2)"},{"comment":"The constants C1 and C are introduced in the proof by \"We assume that there exists...\" without being stated in Assumption 5.1 or in the theorem statement; they are finite under the assumptions because g_i is bounded, h_i is Lipschitz, and f_µ is bounded below, but this should be stated explicitly so that the explicit K in the theorem is well defined.","section":"§5, proof of Theorem 5.8"},{"comment":"The condition t^{-1} ≥ µ^{-1}+ρ implies tc < 1, which is used to ensure 1-t^2c^2 > 0 in the definition of γ and to justify sign choices in the proof of Theorem 5.8; this restriction should be stated explicitly where the constants are introduced.","section":"§5, Proposition 5.7 and Theorem 5.8"},{"comment":"In the introduction, \"similar to but different form that in [44,19]\" should be \"similar to but different from that in [44,19]\"; also reference [29] is incomplete, as it lacks venue and year information.","section":"§1 and references"}],"recommendation":"major_revision","confidential_remarks":"The two proof gaps are concentrated in a wrong weak-convexity modulus in Theorem 4.7 and a summation error in Theorem 5.8; both are local and do not suggest that the claimed rates are wrong. I recommend encouraging the authors to correct these points and resubmit. The paper is appropriate as a short note, but the explicit constants in the theorems should be made consistent with the corrected derivations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a useful note with two real complexity improvements for structured non-smooth non-convex compositional problems, but the proof of the first theorem (4.7) has a wrong constant in the weak-convexity claim that needs fixing. The second theorem (5.8) is more solid but has a few hidden boundedness constants.\n\nWhat's new: For h Lipschitz and non-convex with an easy proximal map, the smoothing compositional gradient method finds a stochastic (δ,ε)-stationary point (defined via the chain-rule subdifferential) in O(1/(δε²)) iterations, improving on the O(1/(δε³)) for Goldstein stationarity. For DC compositions h2(g2) − h1(g1) with easy prox-linear subproblems, the prox-linear approximate gradient method gets a stochastic nearly ε-critical point in O(1/ε²), beating the O(1/ε⁴) from Moreau-envelope smoothing. The comparison with prior work is careful, and the self-citations are used appropriately.\n\nWhere it's soft: The proof of Theorem 4.7 asserts that G(x) = max_y [(1/µ)yᵀg(x) − ...] is C_v L_g/µ-weakly convex. That's wrong: the natural modulus is β C_v/µ, where β is the Jacobian Lipschitz constant. L_g does not control β, as in g(x) = sin(kx)/k. Unless the paper adds β ≤ L_g to Assumption 4.1 (it does not), the stated constant C in the theorem is unsupported. The order O(1/(δε²)) survives because it only needs C to be a constant, but the theorem as written needs a corrected constant, e.g. C = L_g² + β C_g + β C_v or using max{L_g, β}. This is a genuine error, not a typo, but it's fixable.\n\nThe second theorem introduces constants C1 and C inside the proof (boundedness of h_i(g_i) and f_μ(z1) − f_μ(z_{K+1})) without stating them in the theorem. These are data-dependent and finite under the assumptions, so it's a minor presentation issue, not a load-bearing flaw. Proposition 5.7's contraction argument looks correct and is the cleanest part of the paper.\n\nVerdict: The paper deserves a serious referee. The central rates are new and likely correct after a constant fix. I'd suggest the authors correct the weak-convexity modulus in Section 4 and explicitly state the boundedness constants in Theorem 5.8. I'd be happy to see this in a journal after revision.\n\nRecommendation: send to peer review, but flag the constant issue.","headline":"Useful new rates for two structured non-smooth compositional problems, but Theorem 4.7's weak-convexity constant needs correction before the stated complexity is supported.","tokens_in":17046,"tokens_out":3829,"would_cite":true,"duration_ms":32340,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This note proves that for nonsmooth nonconvex compositional optimization with an easy-prox outer function, a smoothing gradient method finds a stochastic $(\\delta,\\epsilon)$-stationary point in $O(1/(\\delta\\epsilon^2))$ iterations, and…","keywords":["compositional optimization","non-smooth non-convex optimization","smoothing method","prox-linear method","difference-of-convex optimization","Goldstein stationary point","iteration complexity","Moreau envelope"],"falsifier":"Take a scalar example with $h(y)=|y|$ and $g(x)=\\sin(10x)$ on a bounded interval, and compute the finite-difference second quotient of $G(x)=\\max_y\\{ y g(x)-\\frac{1}{2}y^2-|y|\\}$; the lower bound will scale with $\\beta=100$ rather than $L_g=10$, showing inequality (11) cannot hold with the claimed $C_v L_g/\\mu$ modulus.","tokens_in":15989,"feed_emoji":"🧩","tokens_out":13488,"duration_ms":115162,"temperature":0.7,"pith_summary":"This note establishes iteration-complexity guarantees for first-order methods on compositional optimization problems $\\min_x h(g(x))$ where the inner map $g$ is smooth and the outer function $h$ is Lipschitz, nonsmooth, and nonconvex but has one of two exploitable structures. For an outer function with an easily solvable proximal mapping, the smoothing compositional gradient method (SCGM) returns a stochastic $(\\delta,\\epsilon)$-stationary point defined through the chain rule and a Goldstein-type enlargement of $\\partial h$ in $O(1/(\\delta\\epsilon^2))$ iterations, improving the known $O(1/(\\delta\\epsilon^3))$ bound for generic $(\\delta,\\epsilon)$-Goldstein stationarity by a factor of $1/\\epsilon$. For an outer function of the difference-of-convex form $h_2(g_2(x))-h_1(g_1(x))$ with easy prox-linear subproblems, the prox-linear approximate gradient method (PAGM) finds a stochastic nearly $2\\epsilon$-critical point in $O(1/\\epsilon^2)$ iterations. These results show that structure-aware stationarity notions let nonsmooth nonconvex compositions be solved at complexities comparable to smooth nonconvex optimization.","feed_headline":"Structured nonsmooth optimization hits O(1/ε²) iterations","feed_subtitle":"First-order methods reach stationary points of structured nonsmooth compositions in O(1/ε²) or O(1/(δε²)) steps.","key_machinery":"The Moreau envelope is the machinery common to both algorithms. In the first setting, $h_\\mu(g(x)) = \\frac{1}{2\\mu}\\|g(x)\\|^2 - G(x)$ with $G(x)=\\max_y\\{ \\frac{1}{\\mu}y^\\top g(x)-\\frac{1}{2\\mu}\\|y\\|^2 - h(y)\\}$, a DC decomposition; the proximal point $v(g(x_k))\\in\\mathrm{prox}_{\\mu h}(g(x_k))$ gives the subgradient $\\frac{1}{\\mu}\\nabla g(x_k)^\\top(g(x_k)-v(g(x_k)))$, and the smoothness and weak-convexity of the two pieces produce the descent inequality. In the second setting, the Moreau envelopes $f_{i,\\mu}(z)$ smooth each DC component, and Proposition 5.7 shows the prox-linear subproblem (20) contracts the error $\\|x_i^{k+1}-x_i^*(z_k)\\|$ by a factor $1-tc$, which drives the $O(1/\\epsilon^2)$ bound once the gradient step on $z_k$ is chosen suitably.","core_discovery":"The central claim is that the compositional structure of (1), rather than an obstacle, is an asset for nonsmooth nonconvex optimization. Theorem 4.7 shows that under Assumption 4.1 (Lipschitz outer function with easy prox, smooth inner map with bounded range), SCGM—a subgradient descent on the Moreau envelope $h_\\mu(g(x))$—finds a stochastic chain-rule $(\\delta,\\epsilon)$-stationary point in $O(1/(\\delta\\epsilon^2))$ iterations. Theorem 5.8 shows that under Assumption 5.1 (DC outer function with easy prox-linear subproblems), PAGM finds a stochastic nearly $2\\epsilon$-critical point of (2) in $O(1/\\epsilon^2)$ iterations. The proofs hinge on smoothing via Moreau envelopes and on measuring stationarity through the chain-rule subdifferential $\\nabla g(x)^\\top \\partial h(g(x)+\\delta B)$, a weaker target than the full Goldstein subdifferential yet still meaningful as an approximate KKT condition for the constrained reformulation.","pith_inferences":["A natural extension is stochastic or variance-reduced versions of both algorithms; the contraction structure in Proposition 5.7 suggests sample-average or SVRG-style updates could preserve the $O(1/\\epsilon^2)$ rate with finite-sample oracles under bounded-variance assumptions.","The chain-rule stationarity notion used in Theorem 4.7 is not the Goldstein condition; if the downstream task only needs KKT conditions of the lifted problem (9), then the cheaper $O(1/(\\delta\\epsilon^2))$ rate is the right measure, and optimal rates for structured nonsmooth problems should be defined relative to the structure, not the worst-case function class.","The DC structure visible in (3) connects the two settings: the same Moreau-envelope machinery that smooths an easy-prox outer function also underlies the DC prox-linear analysis, so one could expect a unified treatment or algorithms that interpolate between the two assumptions.","For DC compositional problems with strongly concave conjugates, the PAGM rate suggests that the bottleneck is the subproblem solver rather than the outer geometry; using inexact or stochastic prox-linear solves would likely trade the $O(1/\\epsilon^2)$ rate for higher complexity, so implementing exact solves for structured $h_i$ is the practical key."],"forward_implications":["For the first structure, SCGM finds a chain-rule $(\\delta,\\epsilon)$-stationary point in $O(1/(\\delta\\epsilon^2))$ iterations, a factor $1/\\epsilon$ better than the $O(1/(\\delta\\epsilon^3))$ rate known for generic $(\\delta,\\epsilon)$-Goldstein stationarity.","For compositional DC problems, PAGM finds a nearly $2\\epsilon$-critical point in $O(1/\\epsilon^2)$ iterations, improving on the $O(1/\\epsilon^4)$ rates of Moreau-envelope smoothing methods that solve subproblems inexactly.","Because each iteration uses only one proximal evaluation of the outer function and one gradient evaluation of the inner map, the iteration counts in Theorems 4.7 and 5.8 translate directly into first-order oracle complexity.","The stationarity targets carry algorithmic meaning: a chain-rule $(\\delta,\\epsilon)$-stationary point is an $\\epsilon$-KKT point of the constrained reformulation $h(v)$ subject to $g(x)=v$, and a nearly $\\epsilon$-critical point is a nearly $2\\epsilon$-KKT point of the consensus reformulation of (2)."],"supporting_citations":[{"why":"Supplies the proximal mapping inclusions and chain rule (Lemmas 4.2 and 4.4) that define the stationarity target and the subgradient update in SCGM.","marker":"[34]"},{"why":"Gives the weak convexity of $h\\circ g$ for Lipschitz convex $h$ and smooth $g$ (Lemma 5.2) and the model-error bound (Lemma 5.6) used by the prox-linear analysis.","marker":"[13]"},{"why":"Establishes the $O(1/(\\delta\\epsilon^3))$ complexity for generic $(\\delta,\\epsilon)$-Goldstein stationarity that Theorem 4.7 improves by a factor of $1/\\epsilon$.","marker":"[44]"},{"why":"Introduces the nearly $\\epsilon$-critical point and Moreau-envelope smoothing for DC programs, the target and machinery used in Section 5.","marker":"[35]"},{"why":"Provides the single-loop algorithm for difference of max-structured weakly convex functions with $O(1/\\epsilon^4)$ complexity that PAGM improves to $O(1/\\epsilon^2)$.","marker":"[17]"},{"why":"Is the source of the contraction proof technique (Theorem 2.3.4) adapted in Proposition 5.7.","marker":"[30]"},{"why":"Supplies the DC decomposition of the Moreau envelope (equation (3)) on which the SCGM descent analysis relies.","marker":"[27]"},{"why":"Gives the oracle lower bound showing finite-time $\\epsilon$-stationarity is impossible for generic nonsmooth nonconvex functions, motivating the weakened $(\\delta,\\epsilon)$-type targets.","marker":"[21]"}],"fun_headline_variants":["Prox-linear method hits O(1/ε²) for DC-structured nonsmooth objectives","Smoothing compositional gradient method achieves O(1/(δ ε²)) for easy prox","Two structures give first-order methods with O(1/ε²) and O(1/(δ ε²))","Structure is an asset: O(1/ε²) for nonsmooth nonconvex compositions","Nonsmooth nonconvex? Structure enables O(1/ε²) first-order methods"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Theorem 4.7 assumes that the term $G(x)$ in the Moreau-envelope decomposition (3) is $C_v L_g/\\mu$-weakly convex; the natural uniform weak-convexity modulus of this max function is $\\beta C_v/\\mu$, so the descent inequality (11) is only justified if $\\beta \\le L_g$, a condition not stated in Assumption 4.1.","fun_headline_variants_meta":{"raw":{"variants":["Prox-linear method hits O(1/ε²) for DC-structured nonsmooth objectives","Smoothing compositional gradient method achieves O(1/(δ ε²)) for easy prox","Two structures give first-order methods with O(1/ε²) and O(1/(δ ε²))","Structure is an asset: O(1/ε²) for nonsmooth nonconvex compositions","Nonsmooth nonconvex? Structure enables O(1/ε²) first-order methods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001746,"raw_usage":{"total_tokens":6897,"prompt_tokens":946,"completion_tokens":5951,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":562,"completion_tokens_details":{"reasoning_tokens":5828}},"tokens_in":562,"tokens_out":5951,"duration_ms":42340,"temperature":1.0,"reasoning_tokens":5828,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:18:21.732675+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a scalar example with $h(y)=|y|$ and $g(x)=\\sin(10x)$ on a bounded interval, and compute the finite-difference second quotient of $G(x)=\\max_y\\{ y g(x)-\\frac{1}{2}y^2-|y|\\}$; the lower bound will scale with $\\beta=100$ rather than $L_g=10$, showing inequality (11) cannot hold with the claimed $C_v L_g/\\mu$ modulus.","supporting_citations":[{"cited_title":"Tyrrell Rockafellar and Roger J.-B","cited_arxiv_id":null,"evidence_quote":"Supplies the proximal mapping inclusions and chain rule (Lemmas 4.2 and 4.4) that define the stationarity target and the subgradient update in SCGM."},{"cited_title":"Drusvyatskiy and C","cited_arxiv_id":null,"evidence_quote":"Gives the weak convexity of $h\\circ g$ for Lipschitz convex $h$ and smooth $g$ (Lemma 5.2) and the model-error bound (Lemma 5.6) used by the prox-linear analysis."},{"cited_title":"Complexity of finding stationary points of nonsmooth nonconvex functions","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(1/(\\delta\\epsilon^3))$ complexity for generic $(\\delta,\\epsilon)$-Goldstein stationarity that Theorem 4.7 improves by a factor of $1/\\epsilon$."},{"cited_title":"Algorithms for difference-of-con vex programs based on difference- of-moreau-envelopes smoothing","cited_arxiv_id":null,"evidence_quote":"Introduces the nearly $\\epsilon$-critical point and Moreau-envelope smoothing for DC programs, the target and machinery used in Section 5."},{"cited_title":"Single-loop st ochastic algorithms for differ- ence of max-structured weakly convex functions","cited_arxiv_id":null,"evidence_quote":"Provides the single-loop algorithm for difference of max-structured weakly convex functions with $O(1/\\epsilon^4)$ complexity that PAGM improves to $O(1/\\epsilon^2)$."},{"cited_title":"Lectures on Convex Optimization","cited_arxiv_id":null,"evidence_quote":"Is the source of the contraction proof technique (Theorem 2.3.4) adapted in Proposition 5.7."},{"cited_title":"A successive diffe rence-of-convex approxi- mation method for a class of nonconvex nonsmooth optimization pro blems","cited_arxiv_id":null,"evidence_quote":"Supplies the DC decomposition of the Moreau envelope (equation (3)) on which the SCGM descent analysis relies."},{"cited_title":"Oracle complexity in nonsmooth nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"Gives the oracle lower bound showing finite-time $\\epsilon$-stationarity is impossible for generic nonsmooth nonconvex functions, motivating the weakened $(\\delta,\\epsilon)$-type targets."}],"review_version":1}