{"id":"5566a2cc-f956-4bc8-9792-20cd85a85f75","arxiv_id":"2506.21948","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"UPOQA exploits partial separability by building individual quadratic models with per-element trust regions and an approximate 'Steinmetz projection', cutting function evaluations versus baselines in numerical tests.","lead":"This paper introduces UPOQA, a derivative-free optimization algorithm that splits an objective into smaller element functions and builds a quadratic model for each one inside a trust-region framework. It reports that UPOQA needs fewer function evaluations than standard solvers on 85 CUTEst problems and on quantum variational problems, with larger gains at high precision.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (13) defines convergence against the best solver value rather than a true optimum, so a common plateau would inflate UPOQA's reported success rates and evaluation savings.","rationale":"The reader's weakest assumption matches my main concern. I considered whether the element-evaluation accounting (t_wst versus full evaluations for baselines) is the bigger problem; I do not think it is decisive, because on the same problem a full evaluation and a set of element evaluations are linked by the same factor q for all solvers, so the evaluation-count ordering is not automatically distorted. The f*_p anchor, by contrast, directly determines which runs count as converged and therefore drives every success rate and data-profile comparison in Section 3.2. The authors' own Section 4 limitations, no convergence-rate theory and limited representativeness of CUTEst decompositions, weaken scope but not the specific empirical claim; the benchmark anchor is the concrete load-bearing point. A conditional verdict is therefore appropriate, so I recommend no change to the reader's verdict: the paper should be accepted only after the f*_p issue is resolved or the claims are restated in terms of best-known solver values.","tokens_in":27052,"tokens_out":11745,"duration_ms":132017,"concrete_test":"For a representative subset of the 85 problems in Table 2, use all problems with certified CUTEst optimal values plus a few convex or quadratic problems with analytic minima, replace f*_p in Eq. (13) by the certified optimum, and recompute the success rates, Table 1, and Figures 3-4. If UPOQA retains its >80% success rates and the evaluation-count ordering is unchanged, the concern is resolved; if success rates drop markedly or the ordering shifts, the reported advantage is an artifact of the self-referential target. A secondary check: run PSDFO on the same test set to see whether UPOQA beats the natural structure-aware baseline.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The empirical case in Section 3 rests on Eq. (13), where f*_p is the lowest value any solver in S achieved on problem p. This is a self-referential target: if all four solvers stall at the same local minimum or plateau, every solver is 'converged' at tolerance epsilon without being near a true solution, and UPOQA's success rates (97.6%, 88.2%, 84.7% quoted in Section 3.2) and 'fewest evaluations' counts are measured against a target that can be met by the weakest common denominator. The screening in Section 3.2.1 also discards problems where none of the solvers converges, removing the very cases that would reveal whether the best solver value is meaningful. Because the central claim is phrased as solving partially separable problems with fewer evaluations, the benchmark needs an absolute or independently verified target, or at least a certified lower bound, before the headline numbers can be interpreted. The lack of a direct comparison with PSDFO, the existing partially separable DFO solver, makes it harder to attribute the improvement to UPOQA's design rather than to structure exploitation in general.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes UPOQA, a trust-region derivative-free optimization algorithm for unconstrained partially separable problems. It maintains underdetermined quadratic interpolation models for each element function, solves the resulting structured trust-region subproblem by a modified projected gradient method built on a new approximate Steinmetz projection, and adjusts element-wise trust-region radii through a scoring scheme based on Shahabuddin's combined separation criterion. The manuscript also describes a starting-point search, an optional restart mechanism, and hybrid black-white-box support. Numerical experiments on 85 CUTEst problems and two quantum variational problems report that UPOQA reduces the number of function evaluations relative to UPOQA without structure exploitation, NEWUOA, and finite-difference L-BFGS-B, and a newly introduced speed-up profile is used to quantify the acceleration.","tokens_in":27267,"tokens_out":9651,"duration_ms":111686,"significance":"If the numerical claims withstand scrutiny, UPOQA is a useful contribution to structured derivative-free optimization. The paper ships an open-source Python implementation, provides a correctness proof for the SHRINK subroutine in Theorem 2.1, and introduces a speed-up profile that is a potentially useful diagnostic for structure exploitation. The main caveat is that the reported success rates and evaluation counts rest on a convergence target defined from the solvers' own achieved values rather than an absolute or independently certified optimum; this needs to be fixed before the empirical contribution can be accepted at face value.","major_comments":[{"comment":"The convergence criterion defines f*_p as the lowest function value achieved by any solver in S on problem p. If all solvers stall at the same local minimum or plateau, then every solver is declared converged without being close to a true solution, and the reported success rates and evaluation counts are measured against a self-referential target. This is not only a theoretical concern: in Table 1, for HYDC20LS at epsilon = 1e-5 and 1e-7, only UPOQA has finite evaluation counts, so f*_p is essentially UPOQA's own best value, and the criterion can be satisfied by a small improvement of one solver over itself. The screening in Section 3.2.1 that removes problems where no solver converges further removes exactly the cases that would reveal an unreliable common plateau. Please rerun the comparison with known CUTEst minima or another independently certified target, and report final function values for the converged cases; the headline numbers in Section 3.2.2 should be recomputed against an absolute target.","section":"Section 3.1, Eq. (13)"},{"comment":"The experimental comparison does not include PSDFO [14], the existing model-based derivative-free algorithm designed specifically for partially separable problems. Because UPOQA's distinguishing features, namely element-wise quadratic models and trust-region management, are precisely the aspects that PSDFO also addresses, the reported advantage over NEWUOA and L-BFGS-B may reflect the benefit of partial separability in general rather than UPOQA's specific mechanisms. Please either include PSDFO in the comparison or explain why a direct comparison is not feasible, and interpret the numerical claims with that limitation stated.","section":"Section 3.2.2"},{"comment":"The speed-up profile is presented as comparing the actual speed-up t_single/t_wst with a predicted speed-up ratio n/max_i n_i. The dimension ratio is motivated by a finite-difference gradient argument, but UPOQA uses interpolation models and trust regions, and no argument is given that n/max_i n_i is the relevant predicted speed-up for this algorithm. The quantity c_p is therefore a normalization of the measured speed-up rather than a tested prediction, so statements such as 'the results align well with theoretical predictions' in Section 3.3 are stronger than the derivation supports. Please state explicitly that c_p is a normalized speed-up and either justify the prediction language or weaken it.","section":"Section 3.1, Eq. (14) and Section 3.3"}],"minor_comments":[{"comment":"In Step 2 of Algorithm 2, the violation ratios are written using s_0, but they should be computed from the current iterate s_k; please fix this typo.","section":"Section 2.1, Algorithm 2"},{"comment":"The complexity statement says the algorithm iterates at most 'q - q' times; the overline notation is not defined in the text, and the reader cannot tell which quantity is being subtracted from q.","section":"Section 2.1, Algorithm 2"},{"comment":"The solver name 'NEWUOQA' appears once; it should be 'NEWUOA'.","section":"Section 3.2.2"},{"comment":"The condition 'F_GI_1,,...,F_GI_q' contains an extra comma; this is a typographical error.","section":"Algorithm 1, line 11"},{"comment":"The axis labels in Figures 3-5 are truncated in the manuscript, for example 'Number f Evaluati ns' and 'log2 ( )'; please regenerate the figures with complete labels.","section":"Figures 3-5"},{"comment":"The conclusion correctly acknowledges that theoretical analysis is incomplete and that the artificially constructed CUTEst structures may lack representativeness; these limitations should be stated in the abstract or introduction so that the empirical framing of the contribution is transparent from the outset.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this before reading the experiments: the algorithm is genuinely new, but the central empirical claim is measured against a moving target. Section 3.1, Eq. (13), defines f*_p as the lowest value any solver achieves on that problem, not a known optimum. Section 3.2.1 then screens out problems where no solver converges. So the success rates (97.6% at 1e-1, 88.2% at 1e-5, 84.7% at 1e-7) are \"success\" against the weakest common denominator. If all solvers plateau together, UPOQA just reaches the plateau faster. The relative comparison among solvers is still fair under the same target, but the absolute language in the abstract and Section 3.2 is overstated, and the screening removes exactly the cases that would reveal how meaningful f*_p is.\n\nThe algorithmic side is solid. Per-element quadratic models, per-element trust-region radii, the Steinmetz projection (with a real correctness proof), selective model updates, and the speed-up profile are all novel pieces. The Python code is on GitHub, and the authors are honest in Section 4 about incomplete theory, high runtime of the projected gradient method, and limited representativeness of the CUTEst groups. That matters. The speed-up profile is a useful diagnostic, and the comparison against UPOQA in single-element mode helps attribute gains to structure exploitation.\n\nThe main gap in the evaluation is the missing direct comparison with PSDFO, the closest existing partially separable DFO method. Without it, you cannot tell whether UPOQA's specific ideas (per-element radii, Steinmetz projection, selective updates) beat a simpler way of exploiting partial separability. The free parameters (thetas, xi, mu1, mu2) are fixed rather than systematically tuned, which is acceptable since they are not fitted to the results, but a sensitivity check would strengthen the paper.\n\nThis is not a desk reject. It deserves a serious referee, and I would send it out with three requests: (1) re-benchmark at least a subset of problems against known or certified minima, or do a sensitivity analysis on f*_p; (2) add a PSDFO comparison; (3) state whether the screening changes the conclusions. Address those and this is a solid contribution to structured derivative-free optimization.","headline":"A real algorithmic contribution whose headline success rates depend on a benchmark target that is the best solver value, so read the absolute numbers with care.","tokens_in":27770,"tokens_out":3596,"would_cite":true,"duration_ms":39022,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C30","65K05","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"UPOQA is a trust-region DFO method that models each element of a partially separable objective separately and thereby reaches target accuracy with far fewer function evaluations than treating the problem as a single black box.","keywords":["derivative-free optimization","partially separable problems","trust region methods","quadratic interpolation","structured trust regions","Steinmetz projection","speed-up profile","quantum variational algorithms"],"falsifier":"Re-run the 85 CUTEst problems with the reference value $f^*_p$ in Eq. (13) replaced by a certified or independently verified minimum for each problem, or with a much larger evaluation budget; if UPOQA's reported success rates fall below the competing solvers, or its evaluation counts approach those of the single-element variant, the claimed speed-up from partial separability is an artifact of the test reference.","tokens_in":26816,"feed_emoji":"🧩","tokens_out":14268,"duration_ms":132288,"temperature":0.7,"pith_summary":"UPOQA is a derivative-free optimization algorithm aimed at unconstrained problems that decompose into a sum of element functions. The paper's central claim is that by building a separate quadratic interpolation model for each element and giving each its own trust-region radius, the algorithm reaches a target accuracy with far fewer evaluations of the expensive objective than methods that treat the whole problem as one black box. On an 85-problem test set, UPOQA is reported to solve 97.6%, 88.2%, and 84.7% of problems at tolerances $\\varepsilon = 10^{-1}, 10^{-5}, 10^{-7}$, respectively, the highest success rates among the compared solvers, and to use the fewest evaluations on at least 80% of problems at every tolerance. The paper also introduces a speed-up profile showing that the advantage of exploiting partial separability is modest at low precision and grows when high precision is required, and it demonstrates the method on quantum variational problems where element functions are circuit expectation values.","feed_headline":"UPOQA cuts function evaluations by exploiting partial separability","feed_subtitle":"Giving each element its own interpolation model reaches high accuracy with fewer evaluations on 85 test problems.","key_machinery":"The load-bearing object is the structured trust region $\\mathcal{S}(\\mathbf{\\Delta}_k)=\\{s\\in\\mathbb{R}^n : \\|s_{\\mathcal{I}_i}\\|_2\\le \\Delta_{k,i},\\, i=1,\\dots,q\\}$, the intersection of one cylinder per element, together with the element models $m_{k,i}$ that it bounds. UPOQA maintains an underdetermined quadratic interpolation model per element, updated by the derivative-free symmetric Broyden update, so one full objective evaluation supplies every element value and refreshes all models. The structured subproblem is solved by a modified projected gradient method whose projection step is the Steinmetz projection, a fixed-iteration approximate projection onto this intersection of cylinders. Per-element radii are then adjusted by a combined separation score that separates global model agreement from element-level agreement and tolerates slight element deterioration when elements work against one another. These pieces together convert knowledge of which variables each element depends on into a lower per-iteration modeling cost and a larger per-step search space than a single spherical trust region would allow.","core_discovery":"The central claim is that a derivative-free trust-region method can exploit coordinate partial separability—where the objective is a sum of element functions, each depending on a small subset of variables—to reach the same accuracy with substantially fewer function evaluations than methods that query only the full objective. UPOQA assigns each element its own interpolation model and its own trust-region radius, so one evaluation of the full objective refreshes every element model at once, and steps are constrained only in the low-dimensional subspaces where each element actually varies. On the paper's 85-problem CUTEst suite, UPOQA solves 97.6%, 91.8%, 88.2%, and 84.7% of problems at tolerances $10^{-1}$, $10^{-3}$, $10^{-5}$, and $10^{-7}$, respectively; at three of the four tolerances this is the highest success rate among UPOQA, UPOQA treating the objective as a single element, NEWUOA, and L-BFGS-B with finite-difference gradients, and on successfully solved problems UPOQA uses the fewest evaluations on at least 80% of problems at every tolerance. The paper also reports that acceleration from structure is modest at low precision and grows at high precision, and that UPOQA escapes plateau regions faster on two quantum variational problems.","pith_inferences":["If the element-wise evaluation assumption holds, the same modelling strategy should transfer to overlapping-element problems beyond the test suite, such as objectives from PDE discretizations where each element touches few neighbours; the paper itself notes its CUTEst selection mostly has many small elements, so this is a natural next stress test.","The Steinmetz projection is a geometric primitive independent of derivative-free optimization: any trust-region or proximal method whose feasible set is an intersection of cylinders could reuse it in place of slower alternating or Dykstra projections, at the price of the approximation the paper accepts.","The speed-up profile, which divides actual evaluation savings by the predicted low-dimensionality ratio, could serve as a general benchmark for how efficiently any structured solver exploits problem structure, beyond partial separability.","A clean ablation test for the soft restart would be to run UPOQA with and without restart on noisy versions of the CUTEst problems, isolating whether the documented robustness comes from the restart or from the structured trust regions."],"forward_implications":["At tolerances $\\varepsilon = 10^{-1}$, $10^{-5}$, and $10^{-7}$, UPOQA achieves success rates of 97.6%, 88.2%, and 84.7% on the 85-problem test set, the highest among the compared solvers, and at every tolerance it uses the fewest evaluations on at least 80% of solved problems.","The speed-up profile shows that exploiting partial separability pays off mainly when high precision is demanded: predicted and actual speed-up agree poorly at coarse tolerance and the advantage strengthens as the tolerance tightens.","On quantum variational problems with $p$ parameterized circuits, reformulating each energy term and overlap penalty as an element yields the predicted speed-up ratio of about $p/2$ and faster escape from plateau regions.","Because a single full-objective evaluation supplies every element value, evaluation counts should grow with the largest element dimension rather than with the full dimension $n$ on problems whose elements can be evaluated independently.","The optional restart and hybrid black-white-box modes extend the method to noisy objectives and to objectives with known smooth parts, where element models only need to cover the black-box residuals."],"supporting_citations":[{"why":"Supplies the underdetermined quadratic interpolation update rule used to maintain each element model.","marker":"[49]"},{"why":"Provides the trust-region interpolation framework UPOQA's iteration follows and a baseline solver for comparison.","marker":"[51]"},{"why":"Supplies the truncated-CG subproblem machinery used in the unstructured-trust-region variant.","marker":"[53]"},{"why":"Provides the combined separation criterion for per-element trust-region radius adjustment.","marker":"[60]"},{"why":"Earlier interpolation-based element-model method that UPOQA builds on and contrasts with.","marker":"[14]"},{"why":"Provides the CUTEst problem collection from which the 85 test problems are drawn.","marker":"[24]"},{"why":"Parses SIF descriptions into Python partially separable element functions for the test runs.","marker":"[25]"},{"why":"Defines the performance and data profiles used to compare evaluation counts.","marker":"[43]"},{"why":"Defines the group partially separable form used to split CUTEst objectives into elements.","marker":"[17]"},{"why":"Shows how grid evaluations of elements can be reassembled into full objective values, an idea used by the starting point search.","marker":"[54]"}],"fun_headline_variants":["UPOQA exploits partial separability to slash function evaluations","Separable structure speeds derivative-free optimization to high precision","Element-level trust regions cut evaluations in derivative-free optimization","UPOQA: fewer evaluations via per-element interpolation models","Partial separability yields big gains at high precision for optimizer"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported success rates treat a problem as solved once a solver reaches a value within tolerance of the best value any solver in the test happened to find, rather than the true minimum of that problem; if all solvers stall at the same suboptimal plateau, UPOQA can be counted as converged without actually solving the problem.","fun_headline_variants_meta":{"raw":{"variants":["UPOQA exploits partial separability to slash function evaluations","Separable structure speeds derivative-free optimization to high precision","Element-level trust regions cut evaluations in derivative-free optimization","UPOQA: fewer evaluations via per-element interpolation models","Partial separability yields big gains at high precision for optimizer"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000159,"raw_usage":{"total_tokens":1243,"prompt_tokens":973,"completion_tokens":270,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":191}},"tokens_in":589,"tokens_out":270,"duration_ms":3162,"temperature":1.0,"reasoning_tokens":191,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:14:49.452260+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the 85 CUTEst problems with the reference value $f^*_p$ in Eq. (13) replaced by a certified or independently verified minimum for each problem, or with a much larger evaluation budget; if UPOQA's reported success rates fall below the competing solvers, or its evaluation counts approach those of the single-element variant, the claimed speed-up from partial separability is an artifact of the test reference.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the underdetermined quadratic interpolation update rule used to maintain each element model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the trust-region interpolation framework UPOQA's iteration follows and a baseline solver for comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the truncated-CG subproblem machinery used in the unstructured-trust-region variant."},{"cited_title":"Shahabuddin","cited_arxiv_id":null,"evidence_quote":"Provides the combined separation criterion for per-element trust-region radius adjustment."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier interpolation-based element-model method that UPOQA builds on and contrasts with."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the CUTEst problem collection from which the 85 test problems are drawn."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Parses SIF descriptions into Python partially separable element functions for the test runs."},{"cited_title":"Moré and Stefan M","cited_arxiv_id":null,"evidence_quote":"Defines the performance and data profiles used to compare evaluation counts."},{"cited_title":"Conn, Nicholas I","cited_arxiv_id":null,"evidence_quote":"Defines the group partially separable form used to split CUTEst objectives into elements."},{"cited_title":"Price and Philippe L","cited_arxiv_id":null,"evidence_quote":"Shows how grid evaluations of elements can be reassembled into full objective values, an idea used by the starting point search."}],"review_version":1}