{"id":"84db739f-3883-4d59-a806-9df2ec561ef2","arxiv_id":"2510.17366","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"TRFD-S reaches (L/σ ε)-approximate solutions in O(n(L/(σε))^-2), O(n(L/(σε))^-1), and O(n log((L/(σε))^-1)) function evaluations for nonconvex, convex, and P-L objectives respectively.","lead":"TRFD-S is a derivative-free trust-region method that uses finite-difference gradients and quadratic models to minimize smooth functions over convex sets, with worst-case evaluation counts of O(n ε^-2) for nonconvex, O(n ε^-1) for convex, and O(n log(1/ε)) for P-L objectives when the Lipschitz estimate is accurate. Benchmark tests show it competitive with NEWUOA, BOBYQA and NOMAD, and it avoids the extra stationarity-measure subproblem used by prior TRFD.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central sufficient-decrease hypothesis (4) is not shown to hold for the constrained subproblem solver FISTA; if violated, the evaluation-complexity bounds do not cover the tested implementation.","rationale":"The reader's CONDITIONAL verdict is well supported. The mathematical proof chain is internally coherent: given Assumptions A1–A3, A5/A7, and the sufficient-decrease condition (4), the complexity bounds in Theorem 3.9, Theorem 3.16, and Theorem 3.22 follow from the stated lemmas. I did not find a contradiction or a missing algebraic step in the core derivations. The load-bearing weakness is the relationship between the theorem's hypotheses and the actual algorithm used in the numerical experiments. In particular, condition (4) is an algorithmic requirement, not merely a problem assumption; every lower bound on objective decrease uses it. The paper acknowledges that η_{Δmax} is never computed and argues that a generalized Cauchy step would satisfy (4), but the bound-constrained implementation substitutes FISTA, an approximate convex solver, without proving that its finite output attains at least the generalized Cauchy decrease. For unconstrained problems, TRSgep's exact TRS solution likely satisfies (4), so the gap is concentrated in the constrained experiments. A second gap, the lack of a proven uniform bound on the safeguarded BFGS Hessian approximations, affects the constants but could be repaired by capping ||H_k||. The direct and decisive check is to instrument the code and test (4) empirically. I therefore do not recommend changing the reader's CONDITIONAL verdict: the concern is genuine but does not invalidate the theorems as conditional statements.","tokens_in":20619,"tokens_out":13387,"duration_ms":113587,"concrete_test":"Instrument the released GitHub implementation to verify (4) directly: at every iteration k on the 53 More-Wild bound-constrained problems, after FISTA returns d_k, compute η_{Δmax}(x_k) from (3) using the same g_k, and test whether m_k(0)-m_k(d_k) ≥ κ η_{Δmax}(x_k) min(Δ_k, η_{Δmax}(x_k)/||H_k||) holds with κ=1/2 and the actual ||H_k||. Report the first violation and the iteration count; also record max_k ||H_k|| to test A3. If (4) is violated before the Δ≤1e-13 stopping test, the tested FISTA-based solver does not implement Algorithm 1's Step 2, so the numerical claims fall outside the proven bounds. Running the same check with TRSgep on the unconstrained problems would identify whether the gap is specific to the constrained solver.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every complexity result (Theorem 3.9, Theorem 3.16, Theorem 3.22 and their corollaries) rests on Step 2 of Algorithm 1: the trial step d_k must satisfy (4), m_k(0)-m_k(d_k) ≥ κ η_{Δmax}(x_k) min(Δ_k, η_{Δmax}(x_k)/||H_k||). This inequality is used in the successful-iteration decrease bounds (Lemmas 3.7, 3.14, 3.20), and without it the proofs do not go through. The paper explicitly does not compute η_{Δmax}(x_k) (Remark 3.1) and instead relies on the subproblem solver to return a step at least as good as the generalized Cauchy step. For the unconstrained experiments, TRSgep returns an exact trust-region solution, so (4) plausibly holds with κ=1/2. But for the bound-constrained experiments, the subproblem is solved by FISTA with Dykstra projections; no proof is given that its finite output satisfies (4). FISTA is an approximate first-order method, not a construction of the generalized Cauchy step, so the numerical results on the More-Wild bound-constrained set are not formally covered by Corollaries 3.10 and 3.17. The A3 issue compounds this: the safeguarded BFGS update in §5.1.1 is not shown to keep ||H_k|| ≤ M, so the M-dependent constants in Δ_min, β, and γ are not guaranteed. The theorems themselves are conditional and internally coherent, but the gap between Algorithm 1's hypotheses and the implemented code is real and testable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TRFD-S, a derivative-free trust-region method that uses forward finite-difference gradient approximations and quadratic models for smooth optimization over closed convex sets. It proves worst-case evaluation-complexity bounds: for nonconvex objectives, O(n (L/(σ ε))^{-2}) evaluations to reach an (L/σ)ε-approximate stationary point; for convex objectives, O(n (L/(σ ε))^{-1}) evaluations to reach a Δmax(L/σ)ε-approximate minimizer; and for Polyak–Lojasiewicz objectives on R^n, O(n log(((L/(σ ε))^{-1}))) evaluations. The method avoids a separate stationarity-measure subproblem. An adaptation for unrelaxable box constraints is given, and numerical experiments compare TRFD-S with NEWUOA, DFQRM, TRFD, BOBYQA, and NOMAD.","tokens_in":21062,"tokens_out":15806,"duration_ms":126865,"significance":"If the theorems are correct, the paper extends finite-difference trust-region complexity guarantees from unconstrained to convexly constrained smooth problems without computing a stationarity measure, matching the best known finite-difference rates in the unconstrained case. The proof chain is explicit and the constants are tracked, and the manuscript ships a MATLAB implementation with benchmark data-profiling code, which strengthens reproducibility. The main contributions are valuable, but the theoretical guarantees are conditional on two assumptions that the implemented algorithm does not demonstrably enforce: the sufficient-decrease condition (4) for the subproblem solver and the Hessian bound A3 for the safeguarded BFGS update.","major_comments":[{"comment":"Condition (4) is load-bearing for every complexity result (Lemmas 3.7, 3.14, 3.20 and Theorems 3.9, 3.16, 3.22). The algorithm requires the subproblem solver to return a step satisfying (4), but the paper never computes η_Δmax(x_k) and gives no proof that the implemented solvers do so. For the unconstrained experiments TRSgep returns an exact trust-region solution, so (4) plausibly holds with κ=1/2. For the bound-constrained experiments in §5.1.2, the subproblem is solved by FISTA with Dykstra projections, an approximate first-order method, and no argument is given that its finite output satisfies (4). Since the generalized Cauchy step guarantee in Remark 3.1 is only asserted, the numerical results on the More–Wild bound-constrained set are not formally covered by Corollaries 3.10 and 3.17. Please provide a proof of (4) for the constrained subproblem solver, or modify the algorithm to co","section":"Algorithm 1, Step 2; Remark 3.1; §5.1.2"},{"comment":"The complexity bounds use the constant M through Δmin in Lemma 3.6, β in Lemma 3.13, and γ in Lemma 3.19. The safeguarded BFGS update in §5.1.1 is not shown to keep ∥H_k∥ ≤ M. The condition |⟨s_k,y_k⟩|>0 only avoids division by zero; it does not ensure positive curvature or boundedness of the Hessian approximation. If H_k becomes unbounded, all M-dependent constants in the proofs cease to be valid for the implementation. Please add an explicit safeguarding step (e.g., a projection or scaling of H_k to enforce ∥H_k∥≤M) in the algorithm, or prove that the stated BFGS update maintains boundedness under the algorithm's dynamics.","section":"Assumption A3; §5.1.1"}],"minor_comments":[{"comment":"The line 'Define x_{k+1}=x_k and Δ_{k+1}=...' is missing the 'Step 4' label; this is a typographical issue.","section":"Algorithm 1, Step 4"},{"comment":"The table heading says 'strongly convex problems', but A7 is the Polyak–Lojasiewicz condition, which is more general than strong convexity. Change the heading to 'P-L functions' for accuracy.","section":"Table 3"},{"comment":"The definition of the user parameter σ appears garbled: 'σ= ϵ√n√eps'. Please clarify whether it is ε√n/√eps or ε√n√eps, and state the corresponding units/scaling.","section":"§5.1.1"},{"comment":"After bounding 1−ρ_k, the proof says 'by (8) we get Δ_k < η_Δmax(x_k)/∥H_k∥'. Since the minimum in the denominator is then attained by Δ_k, it would be clearer to display this step explicitly, as the reader must otherwise reconstruct the min.","section":"Lemma 3.3, proof"},{"comment":"The asymptotic expression in (26) drops the M term that appears in the explicit bound (25). Please state that the O notation treats M as a constant, or include M in the displayed rate.","section":"Corollary 3.10"}],"recommendation":"major_revision","confidential_remarks":"The main proof chain appears internally consistent; my concerns are not about the conditional theory but about the gap between Algorithm 1's hypotheses and the actual implementation. The paper could be made publishable by (i) adding a formal proof or explicit execution of a generalized Cauchy step for the constrained case, and (ii) either proving boundedness of the BFGS update or adding a safeguarding step that enforces A3. The numerical section should then state explicitly which guarantees hold for the tested code."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look if you work on derivative-free methods or evaluation complexity. The new piece is TRFD-S, which combines quadratic models, finite-difference gradients, Cauchy-type decrease, and convex constraints in one trust-region subproblem per iteration, avoiding the second subproblem that TRFD needs for a stationarity measure. The complexity results are the expected targets: O(n ε^{-2}) for nonconvex, O(n ε^{-1}) for convex, O(n log ε^{-1}) for P-L functions on unconstrained domains, all matching the best finite-difference rates for unconstrained smooth problems while handling convex feasible sets. I checked the main proof chain—Lemmas 3.3 through 3.8, the convex and P-L analogues—and the inequalities are coherent. Constants track, the tolerance scaling with L/σ is explicit, and no fitted values are hidden in the bounds. That is a genuine and useful contribution to the DFO complexity literature.\n\nThe soft spots are real but not fatal to the theory. First, condition (4) in Step 2 requires the trial step to give a Cauchy-type decrease measured with η_{Δmax}(x_k), which is never computed. The paper cites the generalized Cauchy step as sufficient, and for unconstrained problems TRSgep plausibly returns something good enough. But the bound-constrained experiments use FISTA with Dykstra projections, and no proof is offered that FISTA's finite output satisfies (4). So those numerical results are not formally covered by Corollaries 3.10 and 3.17. This is an implementation-coverage gap, not a contradiction in the theorems. Second, Assumption A3 (uniformly bounded H_k) is assumed without an algorithmic safeguard; the \"safeguarded\" BFGS rule merely skips updates when ⟨s_k,y_k⟩≤0, which does not keep the norm bounded. The M-dependent constants in Δ_min and β are therefore not guaranteed for the code. Both issues are fixable, but they should be fixed before publication.\n\nWho gets value: anyone doing worst-case complexity analysis for derivative-free methods, and people using trust-region DFO solvers with constraints. The math is solid enough that I'd send it to peer review, but I'd ask the authors to close the gap between Algorithm 1's hypotheses and the tested implementation—either by proving the actual subproblem solver satisfies (4), or by modifying the algorithm to compute an explicit generalized Cauchy step, and by adding a genuine safeguard on H_k. My inclination is conditional acceptance with those revisions.","headline":"A solid, clean DFO trust-region result with honest proofs; the real soft spot is a gap between the theorem's sufficient-decrease condition and the FISTA-based implementation, plus an unenforced bounded-Hessian assumption.","tokens_in":21541,"tokens_out":2463,"would_cite":true,"duration_ms":23690,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"A derivative-free trust-region method matches known complexity bounds for convexly constrained smooth optimization.","keywords":["derivative-free optimization","trust-region methods","finite-difference approximations","worst-case complexity","convex constraints","Polyak-Lojasiewicz functions","function evaluation complexity","bound constraints"],"falsifier":"Run TRFD-S on a low-dimensional convex problem with a deliberately weak subproblem solver that stops at any feasible point without enforcing the Cauchy decrease; if the number of evaluations to reach the predicted functional residual exceeds the proven O(n(L/(σε))^{-1}) bound—or the trust-region radius keeps halving to machine precision—then condition (4) is not satisfied by that solver.","tokens_in":20487,"feed_emoji":"📉","tokens_out":5508,"duration_ms":44985,"temperature":0.7,"pith_summary":"The paper proposes TRFD-S, a derivative-free trust-region method that approximates gradients by forward finite differences, builds quadratic models with an approximate Hessian, and solves only one trust-region subproblem per iteration. Its central claim is that this single-subproblem design attains the best known finite-difference evaluation-complexity rates while handling convex constraints and without ever computing a separate stationarity measure. Specifically, it proves O(n (L/(σε))^{-2}) evaluations for nonconvex objectives to reach an (L/σ)ε-approximate stationary point, O(n (L/(σε))^{-1}) evaluations for convex objectives to reduce the functional residual below Δmax(L/σ)ε, and O(n log((L/(σε))^{-1})) evaluations for Polyak–Lojasiewicz functions on R^n. The bounds depend on a user-supplied estimate σ of the Lipschitz constant L, which creates an explicit accuracy–cost tradeoff. This matters because it shows that the simpler, cheaper-per-iteration design need not sacrifice the theoretical efficiency of finite-difference trust-region methods, extending those guarantees to convexly constrained black-box problems.","feed_headline":"One subproblem per step: derivative-free rates under convex constraints","feed_subtitle":"Matches unconstrained complexity rates for nonconvex, convex, and PL objectives, solving one subproblem per iteration.","key_machinery":"The central mechanism is the coupling between the finite-difference stepsize τ_k and the trust-region radius Δ_k: the update rules maintain τ_k√n ≤ Δ_k at every iteration, which forces the gradient approximation error to satisfy ∥∇f(x_k) − g_k∥ ≤ (L/2)Δ_k. This bound lets the method control the gap between the true stationarity measure ψ_{Δmax} and the approximate η_{Δmax}, and turns the standard trust-region acceptance test into a sufficient-decrease argument that uses η_{Δmax} only in proofs, not in computations. The user-supplied Lipschitz estimate σ sets the target tolerance (L/σ)ε and the initial stepsize τ0 = ε/(σ√n), producing the explicit tradeoff captured in the complexity bounds.","core_discovery":"The paper claims that TRFD-S—a trust-region method using finite-difference gradient approximations, quadratic models, and one subproblem solve per iteration—needs at most O(n (L/(σε))^{-2}) function evaluations to reach an (L/σ)ε-approximate stationary point on a closed convex set, O(n (L/(σε))^{-1}) evaluations when f is convex to drive the functional residual below Δmax(L/σ)ε, and O(n (L/µ) log((σ/L)(f(x0)−f*)/εf)) evaluations for Polyak–Lojasiewicz functions on R^n. These bounds hold even though the method never computes the approximate stationarity measure η; the only requirement is that each subproblem step delivers a Cauchy-type sufficient decrease (condition (4)). The paper also gives","pith_inferences":["The explicit σ-tradeoff suggests an online adaptation strategy—start with a modest overestimate of L and decrease it as the run progresses—which the paper does not explore but which could reduce average evaluation cost while preserving final accuracy.","The unrelaxable-bound construction uses one-sided differences near the boundary; a natural extension would be to general closed convex sets via projected finite-difference steps, though the paper only treats boxes.","The constants in the bounds depend on a uniform bound M on ∥H_k∥ that the safeguarded BFGS update does not explicitly enforce; proving boundedness of that update would close the gap between the theory and the tested implementation.","The single-subproblem design indicates that the earlier two-subproblem TRFD scheme can be simplified for smooth problems without losing the logarithmic rate for Polyak–Lojasiewicz functions."],"forward_implications":["For smooth nonconvex problems with convex constraints, derivative-free trust-region methods can match the O(n ε^{-2}) evaluation complexity of unconstrained finite-difference methods, up to a factor (σ/L)^2.","For convex objectives, the O(n ε^{-1}) rate provides a linear-in-budget accuracy guarantee without needing a separate stationarity measure computation.","The Polyak–Lojasiewicz logarithmic bound extends derivative-free fast rates to non-strongly-convex functions on unconstrained domains.","The unrelaxable-bound variant inherits the same worst-case guarantees, so box-constrained black-box problems enjoy the proven bounds.","The parameter σ acts as a dial: overestimating L gives stricter accuracy at higher worst-case cost, while underestimating L lowers cost but weakens the achievable accuracy guarantee."],"fun_headline_variants":["Finite-difference trust region hits optimal rates with one subproblem per step","Derivative-free trust region: matches unconstrained complexity on convex sets","One subproblem per step: optimal derivative-free rates under constraints","Trust-region without derivatives: tight bounds for constrained smooth optimization","Finite-difference trust region: one subproblem per step, optimal rates"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The complexity theorems assume every subproblem step satisfies a sufficient-decrease condition (4) involving a stationarity measure the algorithm never computes, and that the Hessian approximations stay uniformly bounded; if a practical solver violates (4) or H_k grows without bound, the proven evaluation counts do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Finite-difference trust region hits optimal rates with one subproblem per step","Derivative-free trust region: matches unconstrained complexity on convex sets","One subproblem per step: optimal derivative-free rates under constraints","Trust-region without derivatives: tight bounds for constrained smooth optimization","Finite-difference trust region: one subproblem per step, optimal rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000958,"raw_usage":{"total_tokens":3944,"prompt_tokens":795,"completion_tokens":3149,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":539,"completion_tokens_details":{"reasoning_tokens":3056}},"tokens_in":539,"tokens_out":3149,"duration_ms":18241,"temperature":1.0,"reasoning_tokens":3056,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T09:04:34.633255+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run TRFD-S on a low-dimensional convex problem with a deliberately weak subproblem solver that stops at any feasible point without enforcing the Cauchy decrease; if the number of evaluations to reach the predicted functional residual exceeds the proven O(n(L/(σε))^{-1}) bound—or the trust-region radius keeps halving to machine precision—then condition (4) is not satisfied by that solver.","supporting_citations":[],"review_version":1}