{"id":"18befa7f-8750-4d1f-b05c-5004de1ad97e","arxiv_id":"2501.04889","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A trust-region method for nonsmooth composite optimization gets worst-case complexity bounds matching the smooth case under unbounded Hessian growth, and a new projected proximal-gradient subproblem solver is introduced.","lead":"Researchers prove worst-case iteration counts for trust-region algorithms that minimize a smooth nonconvex function plus a convex nonsmooth penalty, even when the curvature of the quadratic models grows without bound. They also introduce a simple subproblem solver, projected proximal gradient, which can beat an existing solver on standard test problems when high accuracy is required.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The PPG sufficient-decrease guarantee is not linked to the implemented backtracking rule: positive model decrease does not imply the interval condition behind (88), so Assumption 3.3 is unverified as the algorithm is run.","rationale":"The reader's weakest assumption identifies the same load-bearing gap: the implemented positive-decrease acceptance rule is not shown to select a stepsize in the interval required by Corollary 4.4 / Lemma 4.3. My review sharpens this in two ways. First, Corollary 4.4 itself has an unstated condition: a geometric sequence gamma_j = alpha^j gamma0 with alpha in (0.1,1) only guarantees some gamma_j in [c*/(10L), c*/L] if gamma0 is at least the lower endpoint; otherwise every gamma_j is too small. Second, positive model decrease is a much weaker condition than the quantitative bound (88); the 1D quadratic example in concrete_test shows that the acceptance test can pass for a step whose model decrease is arbitrarily small relative to kappa_s pi(x,gamma_max) min{Delta, pi(x,gamma_max)/L}. Thus the paper's claim that the PPG solver 'meets the sufficient descent requirements' is not established for the algorithm as implemented. The first contribution, the O(epsilon^{-2/(1-t)}) and exp-type complexity bounds, is a careful adaptation of [DHO24] and appears internally sound under Assumptions 3.1-3.3; my concern does not attack that part. The numerical comparison is limited to one regularizer and one baseline, and no code is released, but those are secondary. Since the issue is a missing proof link rather than a demonstrated counterexample to the complexity theorem, the appropriate disposition is unchanged: CONDITIONAL, requiring either a modified acceptance test that verifies the interval condition or a proof that the current test implies the sufficient-decrease inequality.","tokens_in":52,"tokens_out":16160,"duration_ms":308610,"concrete_test":"Set h = 0, x = (1,0), model m(p) = p1 + 0.5||p||^2, so H = I, L = 1, and pi(x,gamma) = 1 for every gamma > 0. Run Algorithm 2 with N = 1 and gamma = 1e-6. The first proximal-gradient step gives u1 - x = -gamma e1; since ||u1 - x|| = gamma < Delta, the output is p* = -gamma e1, and m(0) - m(p*) = gamma - 0.5 gamma^2 > 0. The Remark 4.5 acceptance test therefore passes, but the required lower bound kappa_s * pi(x,gamma_max) * min{Delta, pi(x,gamma_max)/L} = kappa_s is not satisfied for any positive kappa_s larger than roughly gamma. This directly exhibits a step admitted by the implemented rule that violates the sufficient-decrease inequality (88).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central complexity result (Theorem 3.14) is credible conditional on Assumption 3.3, so the load-bearing question is whether the proposed PPG subproblem solver actually enforces Assumption 3.3. Corollary 4.4 establishes (88) only for a stepsize gamma_j in [c*/(10L), c*/L] via Lemma 4.3, and its proof implicitly requires gamma0 >= c*/(10L); this lower bound is not stated, so if the reused or initial gamma0 falls below the interval, the geometric sequence never enters it. More importantly, Remark 4.5 replaces the interval condition with a strictly weaker acceptance test: accept gamma_j whenever all computed model decreases are positive. Positive decrease holds for arbitrarily small gamma (the proximal-gradient steps merely become tiny), while the right-hand side of (88) can remain bounded away from zero, so the quantitative sufficient-decrease inequality can fail even though the implemented test passes. Consequently, the backtracking acceptance rule in Algorithm 2 is not proven to produce steps satisfying Assumption 3.3, and the complexity certificate of Theorem 3.14 does not formally apply to the algorithm as specified and tested. This does not invalidate the complexity analysis under Assumption 3.3, but it leaves the second contribution's theoretical guarantee unverified as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies trust-region methods for minimizing F = f + h, where f is smooth (possibly nonconvex) and h is convex and nonsmooth. The first contribution extends worst-case iteration complexity results for trust-region methods from the smooth setting to this composite setting when model Hessian norms may grow at rate O(k^t), t in [0,1]. The second contribution proposes a projected proximal gradient (PPG) subproblem solver that performs several proximal gradient steps and one final projection into the trust region, and claims that this solver satisfies the sufficient decrease condition required by the main trust-region algorithm. The paper proves an O(epsilon^{-2/(1-t)}) bound for t in [0,1) and a doubly exponential-type bound for t = 1, matching the smooth-case rates of Diouane et al. (2024). Numerical experiments on L1-regularized CUTEst problems compare PPG with the spectral proximal gradient (SPG) solver.","tokens_in":18837,"tokens_out":9437,"duration_ms":87647,"significance":"The paper's central complexity analysis appears internally consistent and provides a valuable extension of recent smooth-case results to composite nonsmooth optimization, with a clearly stated set of assumptions and a careful adaptation of the techniques of [DHO24]. The proposed PPG solver is simple and the numerical results are promising, especially at high accuracy. However, the theoretical guarantee that the subproblem solver enforces the required sufficient decrease (Assumption 3.3) is not fully linked to the implemented backtracking rule, and the statement of Corollary 4.4 contains a missing condition; these issues must be addressed before the results can be accepted as stated.","major_comments":[{"comment":"The proof of Corollary 4.4 asserts that for the geometric stepsize schedule gamma_j = alpha^j gamma_0 with alpha in (0.1,1), 'there must be at least one j for which gamma_j in [c*/(10L), c*/L]'. This is not true for arbitrary gamma_0 > 0, because the sequence is strictly decreasing and if gamma_0 < c*/(10L), all subsequent terms are below the interval. The corollary as stated is therefore false unless an additional lower bound such as gamma_0 >= c*/(10L) is imposed, or the backtracking procedure is allowed to increase the stepsize. Please add the missing condition or correct the claim.","section":"Section 4, Corollary 4.4"},{"comment":"The backtracking rule actually implemented (Remark 4.5) accepts gamma_j whenever all computed model decreases m(0)-m(u_i) and m(0)-m(p*) are positive. This test is strictly weaker than the interval condition gamma_j in [c*/(10L), c*/L] that underlies the sufficient-decrease inequality (88). For arbitrarily small gamma, the proximal gradient steps become tiny and the model decreases can remain positive, while the right-hand side of (83) or (88) can remain bounded away from zero at nonstationary points. Consequently, the paper does not prove that the implemented rule produces steps satisfying Assumption 3.3, so the complexity certificate of Theorem 3.14 does not formally apply to Algorithm 1 as implemented and tested in Section 5. To close this gap, the authors should either modify the acceptance test to check the interval condition (which is implementable since L is known) or prove that positive model decrease implies a quantitative decrease of the form (83).","section":"Section 4, Remark 4.5 and Lemma 4.3"}],"minor_comments":[{"comment":"The statement that the modified trust-region updating rule (89) 'does not affect the complexity theory' is not substantiated. The theory relies on the specific parameters gamma_dec, gamma_inc, eta and on the acceptance condition rho_k >= eta, whereas (89) uses different thresholds and an additional boundary condition on ||p_k||. Please provide a direct argument or soften the claim.","section":"Section 5"},{"comment":"The phrase 'for all in N' should read 'for all k in N' in both lemmas.","section":"Section 3, Lemma 3.5 and Lemma 3.7"},{"comment":"The displayed inequality in the proof of Lemma 3.9 contains typographical errors ('a2 + sqrt(a2^2 + 4a1)/2' is typeset incorrectly), and the statement 'k* = Theta(a1)' is not derived explicitly. Please clean up the proof.","section":"Section 3, Lemma 3.9"},{"comment":"The reference [Toi88] has a duplicated article in its title: 'a a of trust-region methods' should be 'a class of trust-region methods'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The core worst-case complexity analysis (Theorem 3.14) appears sound and is a meaningful contribution. The main concern is the mismatch between the theoretical sufficient-decrease guarantee for the PPG subproblem solver and the actual backtracking rule used in the experiments; this is a fixable issue but it is load-bearing for the paper's claim that the proposed solver meets Assumption 3.3. I recommend major revision rather than rejection. There is also a genuine missing condition in Corollary 4.4 that must be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about arXiv:2501.04889. The worst-case complexity result is sound and genuinely useful: for the composite problem min f + h with model Hessians growing at O(k^t), t in [0,1], the trust-region method finds an epsilon-approximate critical point in O(epsilon^{-2/(1-t)}) iterations, and O~(e^{c epsilon^{-2}}) for t = 1, matching the smooth-case bounds from Diouane, Habiboullah and Orban. I traced the proof chain through Lemmas 3.6, 3.7, 3.10 and 3.13 to Theorem 3.14; it is internally consistent and is a legitimate adaptation of the [DHO24] argument to the nonsmooth setting inside the [BK23b] framework. Second, the PPG subproblem solver is simple and the numerics are promising: on 154 l1-regularized CUTEst problems it beats SPG at high accuracy and scales better with the subproblem budget.\n\nThe soft spot is the link between the PPG theory and the backtracking that is actually run. Corollary 4.4 only certifies sufficient decrease (88) when a backtracking stepsize lands in [c*/(10L), c*/L], and its proof silently assumes gamma_0 >= c*/(10L); if the starting stepsize lies below that interval, the geometric sequence never enters it. The acceptance rule in Remark 4.5 is weaker still: it accepts gamma_j whenever the computed model decreases are positive. Positive decrease holds for arbitrarily small stepsizes, while the right-hand side of (88) stays bounded away from zero, so the implemented test can pass without the sufficient-decrease inequality holding. And c* is only defined by an existence argument, so the interval cannot be checked directly in practice. The paper is upfront that the initial stepsize is a heuristic, but the acceptance test is the load-bearing issue. The complexity theorem is untouched by this - under Assumption 3.3 it holds up. The claim that PPG as implemented satisfies the sufficient-decrease requirement is not established.\n\nSmaller issues: the numerics use exact Hessians, so the unbounded-Hessian regime motivating the theory is not tested; no code is released; and the practical trust-region update (89) shrinks Delta on some successful iterations, which the Lemma 3.6 proof does not permit, so the claim that the modification does not affect the complexity theory needs justification.\n\nThis paper is for people designing or analyzing nonsmooth trust-region methods. It deserves serious refereeing: the central complexity result is credible and the PPG idea is worth having, but the revision needs to close the gap between Corollary 4.4 and the implemented acceptance test - either by proving the positive-decrease test implies the needed decrease, or by changing the test to check the quantitative bound.","headline":"A credible complexity extension with a promising subproblem solver, but the PPG backtracking as implemented is not proven to satisfy the sufficient-decrease condition behind the theory.","tokens_in":19415,"tokens_out":13714,"would_cite":true,"duration_ms":117594,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["47H05","49M37","65K05","65K10","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A trust-region method for nonsmooth composite problems finds epsilon-critical points at the same worst-case rate as the smooth case, even when model Hessians grow unboundedly.","keywords":["trust-region methods","nonsmooth optimization","proximal gradient descent","weak convexity","worst-case complexity","unbounded Hessian growth","projected proximal gradient","composite optimization"],"falsifier":"Construct a model with $\\lambda = -L$ (the worst weak-convexity case) and a large $L$, run Algorithm 2 with the Remark 4.5 backtracking, and record the accepted $\\gamma$; if it systematically lands outside $[c_*/(10L), c_*/L]$ while the output $p^*$ still satisfies (83), the practical solver is not certified by the paper's Lemma 4.3. A direct counterexample would be a pair $(\\gamma, L, \\text{model})$ where all model decreases are positive but $m(0) - m(p^*) < \\kappa_s \\pi(x,\\gamma) \\min\\{\\Delta, \\pi(x,\\gamma)/L\\}$.","tokens_in":18356,"feed_emoji":"🎯","tokens_out":13741,"duration_ms":102375,"temperature":0.7,"pith_summary":"Trust-region methods are extended to composite objectives $F = f + h$, where $f$ is smooth but nonconvex and $h$ is convex and nonsmooth, and their worst-case iteration complexity is derived for the case where model Hessians can grow as $O(k^t)$ with $t \\in [0,1]$. The result matches the smooth case exactly: $O(\\epsilon^{-2/(1-t)})$ iterations to reach an $\\epsilon$-approximate first-order critical point when $0 \\le t < 1$, and $e^{O(\\epsilon^{-2})}$ iterations when $t = 1$. A new subproblem solver, the projected proximal gradient (PPG) method, performs several proximal-gradient steps on the local model and then projects the final step into the trust region; the paper proves this solver satisfies the sufficient-decrease condition required by the main algorithm. Numerical experiments on 154 $\\ell_1$-regularized CUTEst problems show PPG is competitive with the spectral proximal gradient solver and outperforms it when high-accuracy solutions are requested.","feed_headline":"Trust-region method hits smooth-case rates on nonsmooth problems","feed_subtitle":"Worst-case bounds now cover unbounded Hessian growth; a simple projected proximal gradient solver delivers the steps.","key_machinery":"The stationarity measure $\\pi(x,\\gamma) = \\frac{1}{\\gamma}\\|\\operatorname{Prox}_{\\gamma h}(x - \\gamma \\nabla f(x)) - x\\|$ (Equation 6), which vanishes exactly at first-order critical points of $F$ and is continuous in $x$ and $\\gamma$, is what the algorithm drives below $\\epsilon$. The sufficient-decrease condition (Assumption 3.3) links the model decrease to this measure and to the trust-region radius, and the quantity $a_k$ (Equation 24) tracks the interplay between radius, Hessian growth, and achieved decrease, providing the ratio-like bound used in the complexity proof. The PPG subproblem solver (Algorithm 2) is the central new object: starting from the current iterate, it runs up to $N$ proximal-gradient steps on the model $m(p)$, then projects the final point into the trust region via $p^* = \\frac{\\Delta}{\\max\\{\\Delta, \\|u_i - x\\|\\}}(u_i - x)$; its decrease guarantee comes from $\\lambda$-convexity of the model and nonexpansiveness of the proximity operator.","core_discovery":"The paper's central claim is that the trust-region algorithm for (1) retains the same worst-case complexity as smooth trust-region methods under Assumption 3.2: if model Hessians grow like $\\|H_k\\| = O(k^t)$, then for $t \\in [0,1)$ an $\\epsilon$-approximate first-order critical point is found in $O(\\epsilon^{-2/(1-t)})$ iterations, and for $t = 1$ in $\\widetilde{O}(e^{c \\epsilon^{-2}})$ iterations (Theorem 3.14, Corollary 3.15). This extends the global-convergence result of the proximal trust-region framework to quantitative rates. The second claim is that the new PPG subproblem solver (Algorithm 2) meets the sufficient-decrease requirement (Assumption 3.3) that drives these bounds, with the model decrease bounded below by $\\theta \\|u_1 - x\\| \\min\\{\\Delta, \\|u_1 - x\\|\\}$ (Theorem 4.2) and a backtracking argument (Corollary 4.4) that guarantees the needed decrease for stepsizes in $[c_*/(10L), c_*/L]$. Numerical results indicate PPG is a practical and often superior alternative to SPG, particularly for high-accuracy solutions.","pith_inferences":["If the backtracking rule actually forces $\\gamma$ into the certified interval $[c_*/(10L), c_*/L]$, then the implemented PPG solver is fully covered by Corollary 4.4; if not, the practical success is not explained by the paper's sufficient-decrease theorem, and a separate analysis of the positive-decrease test would close the gap.","Because only the final projection depends on the trust-region geometry, the same projected proximal gradient idea should extend to other convex trust regions (e.g. $\\ell_\\infty$ or simplex constraints) by replacing the Euclidean projection, provided the projected step remains in the region and the decrease bound adapts.","A natural stress test is to compare PPG and SPG on problems where the model Hessian is actually unbounded in practice (e.g. SR1 updates), since the theory allows $t = 1$ but the experiments here use exact Hessians."],"forward_implications":["When model Hessians are uniformly bounded ($t = 0$), the bound recovers the standard $O(\\epsilon^{-2})$ iteration count for smooth trust-region methods.","Quasi-Newton models whose Hessians grow linearly ($t = 1$, e.g. SR1) do not alter the asymptotic rate relative to the smooth case.","Any subproblem solver satisfying Assumption 3.3 inherits the same worst-case complexity, making the theory solver-agnostic.","The PPG solver's simple structure—proximal-gradient steps plus one final projection—makes it a drop-in replacement for existing subproblem solvers in nonsmooth trust-region implementations.","Numerical evidence shows PPG scales with subproblem iteration budget $N$ and beats SPG at high accuracy ($\\tau = 10^{-6}$), suggesting it is preferable when tight tolerances are needed."],"supporting_citations":[{"why":"Provides the proximal trust-region framework whose global convergence this paper extends to worst-case complexity.","marker":"[BK23b]"},{"why":"Supplies the smooth-case complexity bounds that the nonsmooth bounds are designed to match.","marker":"[DHO24]"},{"why":"Gives the sufficient-decrease framework and the SPG subproblem solver used as the numerical baseline.","marker":"[BK23a]"},{"why":"Establishes global convergence for smooth trust-region methods with linearly growing Hessians, motivating the t = 1 case.","marker":"[Pow84]"},{"why":"Shows the algorithm fails to converge for t > 1, justifying the restriction t in [0,1].","marker":"[Toi88]"},{"why":"Provides the proximal-gradient machinery and the nonexpansiveness and optimality properties of Prox used in the PPG decrease proof.","marker":"[Bec17]"},{"why":"Provides the CUTEst test set used in the numerical comparisons.","marker":"[GOT15]"},{"why":"Provides the Python implementation (PyCUTEst) used to run the 154 test problems.","marker":"[FRB22]"},{"why":"Reference for the standard O(epsilon^-2) smooth trust-region complexity recovered at t = 0.","marker":"[CGT22]"}],"fun_headline_variants":["PPG solver achieves smooth-case rates for nonsmooth optimization","Trust-region with proximal gradient steps reaches smooth-case rates","Worst-case bounds for nonsmooth trust-region with unbounded Hessians","Proximal gradient trust-region matches smooth-case complexity","New trust-region subproblem solver hits smooth-case iteration bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's convergence guarantee for the PPG subproblem solver assumes the backtracking rule chooses a stepsize in the interval $[c_*/(10L), c_*/L]$, but the rule actually implemented only checks that model decreases are positive, which is not shown to imply that interval.","fun_headline_variants_meta":{"raw":{"variants":["PPG solver achieves smooth-case rates for nonsmooth optimization","Trust-region with proximal gradient steps reaches smooth-case rates","Worst-case bounds for nonsmooth trust-region with unbounded Hessians","Proximal gradient trust-region matches smooth-case complexity","New trust-region subproblem solver hits smooth-case iteration bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000573,"raw_usage":{"total_tokens":2681,"prompt_tokens":895,"completion_tokens":1786,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":511,"completion_tokens_details":{"reasoning_tokens":1714}},"tokens_in":511,"tokens_out":1786,"duration_ms":12213,"temperature":1.0,"reasoning_tokens":1714,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:23:48.747057+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a model with $\\lambda = -L$ (the worst weak-convexity case) and a large $L$, run Algorithm 2 with the Remark 4.5 backtracking, and record the accepted $\\gamma$; if it systematically lands outside $[c_*/(10L), c_*/L]$ while the output $p^*$ still satisfies (83), the practical solver is not certified by the paper's Lemma 4.3. A direct counterexample would be a pair $(\\gamma, L, \\text{model})$ where all model decreases are positive but $m(0) - m(p^*) < \\kappa_s \\pi(x,\\gamma) \\min\\{\\Delta, \\pi(x,\\gamma)/L\\}$.","supporting_citations":[],"review_version":1}