{"id":"4f9acbe4-2c5b-4b46-8896-03b6e3d6d3e4","arxiv_id":"2501.04536","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A subspace-based derivative-free optimization framework is re-introduced with a sketched convergence analysis and preliminary numerical evidence for problems with up to 10^4 variables.","lead":"The paper re-introduces a derivative-free optimization framework that solves the problem in a low-dimensional subspace chosen from an approximate gradient, and reports good performance on problems with up to 10,000 variables using only imprecise function values. It is a draft: the convergence proofs are sketched, and the numerical results are preliminary.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 3.1 (Eq. 3.2) is not guaranteed under 3-significant-digit function values: finite-difference noise scales as ε_f/(τδ_k), violating the linear-in-δ_k error bound and undermining the O(n ε^{-2}) complexity claim.","rationale":"The central claim is that the subspace DFO framework achieves worst-case evaluation complexity O(n ε^{-2}) for smooth nonconvex problems with n ~ 10^4, even when function values are inaccurate. The proof is a chain: (3.2) ⇒ (3.4) ⇒ (3.5) ⇒ K_ε = O(ν^{-2}ε^{-2}) ⇒ K_f = O(n^{2-2p}ε^{-2}) with p = 1/2. Every link depends on Assumption 3.1. The paper only argues (3.2) for exact function values via the interpolation set (3.6); no argument is given for truncated 3-significant-digit values. In fact, under noise the finite-difference error has a component proportional to 1/(τδ_k), which cannot be controlled by a linear-in-δ_k bound at late iterations. Hence the experimental evidence, while showing practical promise, does not substantiate the theoretical complexity in the inaccurate-value regime. This does not invalidate the paper's core algorithmic idea, and the draft is explicitly self-described as incomplete, so a conditional acceptance remains appropriate. The reader's weakest_assumption captured the same point; my concern sharpens it by explaining why the provided justification in §3.2 does not extend to the experiments. The footnote's caveat that the theory is only sketched reinforces, rather than alleviates, the concern that (3.2) is not proven under the experimental conditions.","tokens_in":7205,"tokens_out":11702,"duration_ms":98822,"concrete_test":"Run NEWUOAs on the 12 large-scale CUTEst problems in Table 2 with function values truncated to 3 significant digits, and record δ_k and ĝ_k at each iteration. Using exact CUTEst values, compute the true gradient g_k. Test whether ||ĝ_k − g_k|| ≤ ζδ_k holds with ζ = τ√n L/2 and τ = n^{-1/2} at every iteration until the stopping criterion. If the ratio ||ĝ_k − g_k||/δ_k is unbounded as δ_k decreases (in particular exceeds any fixed ζ), then Assumption 3.1 is violated under the experiments' noise, so the complexity bound does not apply to the reported inaccurate-evaluation scenario.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 3.1 (Eq. 3.2) is the linchpin of the complexity analysis: it converts the sufficient-decrease condition (3.1) into the lower bound (3.5) and hence into K_ε = O(ν^{-2}ε^{-2}) and K_f = O(n^{2-2p}ε^{-2}) in §3.4. Section 3.2 justifies (3.2) only for exact evaluations, via the finite-difference/interpolation model (3.6), yielding ζ = τ√n L/2. But the abstract and experiments claim performance 'using only inaccurate function values', specifically truncation to 3 significant digits. Under a noise model with absolute error ε_f, the finite-difference quotient along coordinate i has an error component of order ε_f/(τδ_k) in addition to the truncation term L τδ_k/2. This noise term grows as δ_k → 0, so the inequality ||ĝ_k − g_k|| ≤ ζδ_k cannot hold uniformly with a constant ζ independent of k. In the claimed regime τ = O(n^{-1/2}) and n ~ 10^4, the sampling step h = τδ_k = δ_k/100 is so small that for reported function scales (e.g., f(x0) ≈ 10^4–10^11), the noise term dwarfs the truncation term at late iterations. Thus the worst-case evaluation complexity O(n ε^{-2}) is not established for the inaccurate-evaluation setting highlighted in the title and abstract; the experimental results, while encouraging, do not test (3.2) and cannot validate the theoretical bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper reintroduces a derivative-free subspace optimization framework originally developed in the author's 2012 PhD thesis. Algorithm 3.1 constructs an approximate gradient, builds a low-dimensional subspace containing it, performs a safeguarded subspace minimization, and adapts a step-size/trust parameter delta_k. The paper sketches global convergence and worst-case evaluation complexity results, claiming O(n epsilon^{-2}) evaluation complexity in the smooth nonconvex case when tau = O(n^{-1/2}), and presents numerical experiments on CUTEst problems with n = 200 and n = 10^4 using function values truncated to 3 significant digits. The manuscript is explicitly labeled as a draft with sketched proofs, and the final paper is promised to be substantially different.","tokens_in":7564,"tokens_out":6342,"duration_ms":65558,"significance":"If the claimed linear-in-n evaluation complexity were rigorously established, this would be a valuable contribution to derivative-free optimization at high dimensions, complementing recent scalable subspace DFO methods such as RSDFO. The framework is simple, flexible, and usefully separates the subspace choice from the convergence mechanism. The paper is honest about provenance, and it provides links to open-source implementations and a reproducible CUTEst benchmark, which are strengths. However, the central theoretical claim is not established in the current manuscript: the key Assumption 3.1 is incompatible with the inaccurate function evaluations used in the experiments, and the proof of the central implication (3.4) is left as a sketch. The numerical results are encouraging but preliminary and do not directly test the theory. The contribution is potentially significant, but the submission is not in publishable form.","major_comments":[{"comment":"Assumption 3.1 (Eq. (3.2)) cannot hold for the inaccurate function evaluations used in the experiments. For exact evaluations, the forward-difference model (3.6) gives ||g_k - g_k|| <= L*tau*delta_k*sqrt(n)/2, which is O(delta_k). If function values are truncated to 3 significant digits, the absolute error is bounded below by roughly 10^{a-3} when f is of order 10^a, and the coordinate difference quotient carries a noise term of order epsilon_f/(tau*delta_k), which grows as delta_k goes to zero. Thus no constant zeta independent of k can satisfy (3.2) uniformly as delta_k -> 0. With tau = O(n^{-1/2}) and n ~ 10^4, the sampling radius tau*delta_k is small enough that this noise likely dominates at late iterations. Since (3.2) is used to pass from (3.1) to (3.5) and hence to the claimed K_f^epsilon = O(n epsilon^{-2}) bound, the advertised worst-case evaluation complexity is not established for the inaccurate-evaluation setting highlighted in the abstract and used in Section 4.2.","section":"§3.2, Eq. (3.6) and §3.4"},{"comment":"The key implication (3.4) is asserted with the phrase \"we can establish\" but no proof is provided, and it is not a one-line consequence of the triangle inequality and Taylor expansion. One needs explicit conditions relating eta, zeta, L, and mu, and a verification that delta_k <= mu ||g_k|| implies both ||g_k|| >= eta*delta_k and the decrease inequality f(x_k - delta_k*g_k/||g_k||) <= f_k - eta*delta_k^2. This implication is the only bridge from Assumption 3.1 to the lower bound (3.5) and to the complexity statements in Section 3.4; leaving it as an exercise is not acceptable in a submission whose central contribution is the complexity result.","section":"§3.1, Eq. (3.4)"},{"comment":"The claim that Step 3 of Algorithm 3.1 costs O(1) function evaluations is not justified. Section 3.3 imposes no quality requirement on x_s^k, but it does not specify a fixed budget for the subspace subproblem solver; if (3.9) is solved by a DFO solver run to convergence, the per-iteration cost is not automatically O(1). The evaluation complexity K_f^epsilon = O(n^{2-2p} epsilon^{-2}) in Section 3.4 therefore requires an explicit rule (for example, at most one trial point in S_k besides the safeguarded point x_g^k) before the linear-in-n conclusion K_f^epsilon = O(n epsilon^{-2}) follows.","section":"§3.3–3.4"},{"comment":"The numerical study is not sufficient to support the theoretical claims. The experiments use only 3 significant digits, which, as discussed above, violates the model underlying Assumption 3.1, and no diagnostic is reported for whether ||g_k - g_k|| <= zeta*delta_k holds during the runs. Table 2 reports no accuracy measure such as final gradient norm or distance to a known solution, gives no stopping criteria for fminunc, and reports no repeated runs or variability information. The results are encouraging, but they cannot substitute for a direct test of the convergence theory.","section":"§4.2"}],"minor_comments":[{"comment":"Assumption 1.1 states \"The function f : R -> R\" but the problem is on R^n; this should read f : R^n -> R.","section":"§1"},{"comment":"The definition nu = min{delta_0/||g_0||, mu/2} is undefined when g_0 = 0; the degenerate case should be handled explicitly.","section":"§3.1"},{"comment":"The statement K_f^epsilon = O(n epsilon^{-2}) should specify the dependence of the constant on L, eta, zeta, delta_0, and f(x_0) - f_*; hiding all of these in the O notation makes the scalability claim difficult to compare with existing bounds.","section":"§3.4"},{"comment":"The performance profiles do not state the evaluation budget, the convergence test details, or clearly identify which curve corresponds to NEWUOAs and which to NEWUOA in the printed caption; please add this information.","section":"Figure 1"},{"comment":"Reference [9] is incomplete: it lacks a publication venue and year; if it is a preprint, the arXiv identifier should be given.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"This is explicitly a draft, and the theory is presented as a sketch; if the journal does not normally consider such submissions, a desk rejection may be warranted. The noise-floor issue in Assumption 3.1 is substantive, but it is fixable either by confining the theory to exact function evaluations or by adding a noise-aware analysis with a stopping/resolution scale. The other load-bearing gaps, especially the missing proof of (3.4) and the unspecified cost of the subspace subproblem, are also within reach of a revision. I therefore recommend major revision rather than rejection, provided the authors are willing to complete the proofs and clarify the scope of the claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zaikun's draft is exactly what it says on the tin: a quick set of notes on a subspace DFO framework that goes back to his 2012 thesis and to Conn et al.'s iterated-subspace work. The new material is the numerical study with NEWUOAs, not the algorithm or the convergence skeleton. That is fine if the paper is read as a research announcement, but the current form overclaims what is actually proved.\n\nThe framework itself is sensible and the paper explains it clearly. The observation that convergence is guaranteed by (3.1) and (3.2) regardless of the subspace choice is a useful unifying perspective. The numerical results at n=10^4 are encouraging, and the comparison with fminunc is fair enough as a first look. I also appreciate that the author flags this as a draft and says the final paper will be very different.\n\nThe soft spots are mostly in the complexity analysis. The stress test is right: Assumption 3.1, equation (3.2), is not justified when function values are truncated to 3 significant digits. With an absolute noise level ε_f, a forward-difference gradient has error O(ε_f/(τδ_k)) in addition to the truncation term O(Lτδ_k), so it cannot satisfy ||ĝ_k − g_k|| ≤ ζδ_k with a constant ζ as δ_k → 0. Since (3.2) is what converts sufficient decrease into the lower bound (3.5), the claimed O(n ε^{-2}) evaluation complexity is not established for the noisy setting emphasized in the abstract. This does not mean the bound is false; it means the draft has not supplied the machinery to handle noise. The paper also leaves the derivation of (3.4) to the reader, and the numerical experiments lack error bars, incomplete settings, and no reproducible code or data. Those are exactly the things a full version must fix.\n\nNovelty is genuinely limited: the algorithm is from the author's own thesis, and the complexity analysis is sketched as an application of prior techniques in [8,9]. The self-citation is not a problem per se; it is the absence of new proof content that matters.\n\nWho should read this? DFO researchers who want to know where subspace methods are headed, and anyone about to start high-dimensional DFO. It is a useful pointer to NEWUOAs and to the upcoming SPRIMA package. But it is not yet a self-contained paper.\n\nRecommendation: send it to peer review, but only after the author revises it into a full paper with detailed proofs, a rigorous treatment of noisy evaluations, and reproducible experiments. As it stands, it deserves a serious referee because the question matters and the author is credible, but the referee should insist on the missing analysis.","headline":"A honest draft that re-introduces a known subspace DFO framework; the linear-in-n complexity claim rests on an assumption that fails for the noisy function values advertised.","tokens_in":8070,"tokens_out":1317,"would_cite":false,"duration_ms":15771,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A low-dimensional subspace method scales derivative-free optimization to about 10,000 variables with linear-in-n evaluation cost.","keywords":["derivative-free optimization","subspace methods","approximate gradients","worst-case evaluation complexity","finite differences","nonconvex optimization","high-dimensional optimization","OptimIST"],"falsifier":"Run Algorithm 3.1 with $\\tau = n^{-1/2}$ on a family of smooth nonconvex problems of increasing dimension, and record the number of function evaluations needed to reach $\\|\\nabla f(x_k)\\|\\le\\epsilon$. If that count grows faster than $n\\epsilon^{-2}$ in either $n$ or $\\epsilon^{-1}$, the claimed worst-case bound is not realized; the same run should also track $\\sup_k \\|\\hat g_k-g_k\\|/\\delta_k$ to check whether Assumption 3.1 is actually satisfied.","tokens_in":6989,"feed_emoji":"📉","tokens_out":9660,"duration_ms":89004,"temperature":0.7,"pith_summary":"This paper claims that derivative-free optimization can be made scalable by never searching the full space. Its OptimIST algorithm builds, at each iteration, a low-dimensional subspace that contains an approximate gradient, then solves a cheap subproblem inside that subspace and takes a safeguarded step along the approximate-gradient direction. The analysis gives a worst-case function-evaluation complexity of $O(n\\epsilon^{-2})$ for smooth nonconvex objectives when the finite-difference step is chosen as $O(n^{-1/2})$, linear in the number of variables instead of the quadratic dependence of full-space derivative-free methods. Numerical experiments on problems with $10^4$ variables, using only three significant digits of the function values, support the claim that this scaling is real. A reader should care because the result would make derivative-free methods plausible for high-dimensional black-box optimization.","feed_headline":"Subspace search lifts derivative-free optimization to 10k variables","feed_subtitle":"Worst-case function evaluations drop from quadratic to linear in dimension for smooth problems.","key_machinery":"The load-bearing object is the pair $(\\hat g_k, \\delta_k)$: an approximate gradient whose error is controlled by the same step size that controls the decrease. Step size update doubles $\\delta_k$ whenever $\\|\\hat g_k\\|\\ge \\eta\\delta_k$ and the decrease $f_{k+1}\\le f_k-\\eta\\delta_k^2$ occurs, otherwise it halves $\\delta_k$. The implication (3.4) shows that whenever $\\delta_k\\le \\mu\\|g_k\\|$, the safeguarded step $x_k-\\delta_k\\hat g_k/\\|\\hat g_k\\|$ is guaranteed to achieve the required decrease, so $\\delta_k$ keeps growing relative to $\\|g_k\\|$; this yields the lower bound $f_k-f_{k+1}\\ge \\eta\\nu^2\\|\\tilde g_k\\|^2$ and hence the complexity counts. The stencil $Y_k = \\{x_k\\}\\cup\\{x_k+\\tau\\delta_k e_i\\}$ is the concrete derivative-free construction of $\\hat g_k$, and the subspace $S_k$ built around it is what keeps each subproblem cheap.","core_discovery":"The paper argues that Algorithm 3.1, derivative-free OptimIST, is globally convergent and has worst-case iteration complexity $K_\\epsilon = O(\\nu^{-2}\\epsilon^{-2})$ for nonconvex smooth objectives under Assumption 3.1, with $K_\\epsilon = O(\\nu^{-2}\\epsilon^{-1})$ for convex objectives and $O(\\nu^{-2}|\\log\\epsilon|)$ for strongly convex ones. The constant is $\\nu = \\min\\{\\delta_0/\\|g_0\\|, \\mu/2\\}$ with $\\mu = 2/(L+2\\eta+4\\zeta)$, so the complexity depends on the dimension only through the approximate-gradient error constant $\\zeta$. When $\\hat g_k$ comes from coordinate finite differences on the stencil $\\{x_k\\}\\cup\\{x_k+\\tau\\delta_k e_i\\}$, one has $\\zeta = \\tau\\sqrt n L/2$, and choosing $\\tau = O(n^{-1/2})$ balances the stencil cost against the error term, yielding $K_f^\\epsilon = O(n\\epsilon^{-2})$ function evaluations. The convergence argument does not require any particular choice of subspace: any $S_k$ containing $\\hat g_k$ works, so the subspace is a mechanism for cheap exploration rather than a condition for convergence.","pith_inferences":["If the linear-in-$n$ bound survives a polished proof, derivative-free optimization becomes a candidate for hyperparameter tuning and simulation-based design at scales where only noisy function values are available; the paper's own experiments stop at three significant digits and smooth test functions, so this is a forward inference.","The theory's indifference to the subspace suggests a testable extension: replacing the coordinate stencil by random subspace projections or sketched gradients should preserve the $O(n\\epsilon^{-2})$ rate whenever the error condition (3.2) holds with high probability; the probabilistic trust-region techniques cited by the paper are the natural tool for that analysis.","A practical diagnostic follows directly: record $\\|\\hat g_k-g_k\\|/\\delta_k$ during runs. If this ratio frequently exceeds the theoretical $\\zeta$, the algorithm has left the regime where the complexity guarantee applies, which would explain and predict stagnation on ill-conditioned problems."],"forward_implications":["In the smooth nonconvex case, the guarantee is a worst-case budget of $O(n\\epsilon^{-2})$ function evaluations to reach $\\|\\nabla f\\|\\le\\epsilon$, so dimensions of order $10^3$ to $10^4$ move into the range of derivative-free methods.","For convex objectives the same search needs $O(\\nu^{-2}\\epsilon^{-1})$ evaluations, and for strongly convex ones $O(\\nu^{-2}|\\log\\epsilon|)$, so the subspace framework inherits the usual acceleration for easier problems.","Because the convergence condition is only $\\hat g_k\\in S_k$, the subspace can be chosen freely to include conjugate-gradient directions, limited-memory quasi-Newton directions, or approximate-Newton and negative-curvature directions without changing the theory.","The subspace subproblem can be solved inexactly with only $O(1)$ function evaluations per outer iteration, so the per-iteration cost is dominated by forming the finite-difference stencil, which can be evaluated in parallel."],"supporting_citations":[{"why":"Supplies the probabilistic trust-region proof techniques that turn the sufficient-decrease condition into the global convergence and complexity bounds.","marker":"[8]"},{"why":"Provides the space-transformation and decomposition techniques used to derive the complexity rates in the convex and strongly convex cases.","marker":"[9]"},{"why":"Defines fully linear interpolation models and well-poised sets, the basis for ensuring the approximate-gradient condition (3.2).","marker":"[3]"},{"why":"Introduces the iterated-subspace minimization framework that Algorithm 2.1 and the convergence condition on dist(g_k, S_k) come from.","marker":"[4]"},{"why":"NEWUOA is the derivative-free solver used to solve the low-dimensional subspace subproblem in the implementation.","marker":"[15]"},{"why":"The RSDFO method is the full-space baseline whose quadratic-in-n evaluation complexity the paper contrasts with its linear-in-n result.","marker":"[2]"},{"why":"The author's thesis is the origin of the NEWUOAs implementation and of the subspace derivative-free framework being re-introduced.","marker":"[20]"},{"why":"CUTEst supplies the benchmark problems used in the moderate-dimensional comparison.","marker":"[7]"}],"fun_headline_variants":["Subspace method scales derivative-free optimization to 10k variables","Derivative-free optimization tames 10k variables with subspace tricks","Low-dim subspaces slash worst-case cost in derivative-free optimization","Derivative-free solver hits 10k dimensions via smart subspace choices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All convergence and complexity conclusions rely on Assumption 3.1, that the approximate gradient error is bounded by a constant times the current step size $\\delta_k$ at every iteration; if noisy or truncated function values break that bound, the guaranteed decrease and the $O(n\\epsilon^{-2})$ count no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Subspace method scales derivative-free optimization to 10k variables","Derivative-free optimization tames 10k variables with subspace tricks","Low-dim subspaces slash worst-case cost in derivative-free optimization","Derivative-free solver hits 10k dimensions via smart subspace choices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1467,"prompt_tokens":915,"completion_tokens":552,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":479}},"tokens_in":531,"tokens_out":552,"duration_ms":6032,"temperature":1.0,"reasoning_tokens":479,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:31:53.552715+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 3.1 with $\\tau = n^{-1/2}$ on a family of smooth nonconvex problems of increasing dimension, and record the number of function evaluations needed to reach $\\|\\nabla f(x_k)\\|\\le\\epsilon$. If that count grows faster than $n\\epsilon^{-2}$ in either $n$ or $\\epsilon^{-1}$, the claimed worst-case bound is not realized; the same run should also track $\\sup_k \\|\\hat g_k-g_k\\|/\\delta_k$ to check whether Assumption 3.1 is actually satisfied.","supporting_citations":[{"cited_title":"Gratton, C","cited_arxiv_id":null,"evidence_quote":"Supplies the probabilistic trust-region proof techniques that turn the sufficient-decrease condition into the global convergence and complexity bounds."},{"cited_title":"Gratton, L","cited_arxiv_id":null,"evidence_quote":"Provides the space-transformation and decomposition techniques used to derive the complexity rates in the convex and strongly convex cases."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines fully linear interpolation models and well-poised sets, the basis for ensuring the approximate-gradient condition (3.2)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the iterated-subspace minimization framework that Algorithm 2.1 and the convergence condition on dist(g_k, S_k) come from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"NEWUOA is the derivative-free solver used to solve the low-dimensional subspace subproblem in the implementation."},{"cited_title":"Cartis and L","cited_arxiv_id":null,"evidence_quote":"The RSDFO method is the full-space baseline whose quadratic-in-n evaluation complexity the paper contrasts with its linear-in-n result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The author's thesis is the origin of the NEWUOAs implementation and of the subspace derivative-free framework being re-introduced."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"CUTEst supplies the benchmark problems used in the moderate-dimensional comparison."}],"review_version":1}