{"id":"c110dca6-1f1a-47e6-96e0-e50d04e34264","arxiv_id":"2412.14431","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Random subspace derivative-free optimization is shown to reach second-order critical points in O~(n^4.5 epsilon^-3) evaluations, and a new subspace quadratic-model solver handles n ~ 1000 problems.","lead":"This paper proves the first worst-case complexity bound for randomized subspace derivative-free optimization methods that reach approximate second-order optimal points, improving the dimension scaling from O(n^9) to O~(n^4.5) iterations when seeking low-accuracy solutions or when the objective has low effective rank.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised O~(n^{4.5} ε^{-3}) bound is not uniform in ε: θ>0 forces α=O(√(ε/r)), so the JLT subspace dimension is p=O(ε^{-1} r log r), which enters κ_d and changes the claimed complexity.","rationale":"The reader's weakest assumption already identifies the well-aligned condition and θ>0 as the load-bearing premise, and I agree. My stress-test sharpens that concern: the consequence is not only a practical limitation but a mismatch between the formal theorem and the advertised complexity. When α is chosen to make θ>0 for a given ε, the JLT dimension p=O(ε^{-1} r log r) is forced, and this p enters κ_d; the final complexity then has a different ε-exponent, O(ε^{-15/2}) rather than O(ε^{-3}), unless ε is treated as a fixed constant and only the n-dependence is quoted. The paper is transparent about the qualitative limitation in Remark 2, but the theorem statement and Table 1 still present the complexity as O(κ_d^3 ε^{-3}) with κ_d independent of ε, which is the kind of statement that should be corrected or qualified. I did not find a separate flaw in the trust-region accounting: the apparent issue in Lemma 3.10 about successful iterations lacking Δ≤||g||/κ_H is absorbed by an extra factor μ/κ_H in the constants, so it does not change the ε-dependence. No machine-checked proof or released code is provided, so the algebraic details remain unverified; however, the core proof structure follows established full-space and random-embedding arguments. The numerical experiments are suggestive but not independently reproducible, since no code is released and no confidence intervals are given. These are fixable issues, so the correct disposition remains the reader's conditional acceptance rather than rejection or full acceptance.","tokens_in":21773,"tokens_out":20272,"duration_ms":168907,"concrete_test":"Re-derive the complexity summary in Section 3 with α chosen as a function of ε to satisfy (24), and substitute p=O(α^{-2} log r) and P_max=Θ(√(n/p)) into κ_d=O(p^3 P_max^3) and ψ(ε). If the resulting iteration count is O(n^{9/2} r^{9/2} ε^{-15/2} polylog), or otherwise has ε-dependence through κ_d, then the O~(n^{4.5} ε^{-3}) statement in Table 1 and the abstract must be restricted to a fixed-ε low-accuracy regime or to r=O(ε). This is purely analytical: track the α and p dependencies through Lemma 3.13's ψ(ε), c1, and κ_d, and verify that with p=O(log r) no α satisfies (24) for ε below Θ(r/(M log r)) in the Gaussian case (84).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing issue is the compatibility of the well-aligned subspace condition (Definition 3.6) with the claimed complexity, not any single algebraic step in Lemmas 3.8–3.15. Condition (23d) plus θ>0 in Eq. (24) requires (1-α)^2 > 4M(r-1)α^2 / (ε(1-α)^2), i.e. α^2 = O(ε/r) when M=O(1). The JLT construction in Section 3.1 then requires p=O(α^{-2} log r)=O(ε^{-1} r log r), not the p=O(log r) used in Table 1 and in the sentence 'using a complexity of O(κ_d^3 ε^{-3})... the dependency on n decreases from O(n^9) to O(n^{4.5})'. Since κ_d=O(p^3 P_max^3)=O(p^{3/2} n^{3/2}) for P_max=Θ(√(n/p)), inserting p(ε) gives κ_d^3 ε^{-3}=O(n^{9/2} r^{9/2} ε^{-15/2} polylog) iterations. Thus Theorem 3.15, as stated for any ε>0, does not yield the claimed n^{4.5} ε^{-3} law; it yields an n^{4.5} dependence only in a fixed-ε low-accuracy regime, or when r is so small that r log r = O(ε). The paper explicitly flags this in Remark 2, but leaves Theorem 3.15 and Table 1 in a form that suggests a uniform ε^{-3} complexity. This is a scope-and-statement issue rather than a contradiction internal to the lemmas, but it directly affects the main contribution.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a randomized subspace model-based derivative-free optimization (DFO) framework with convergence guarantees to approximate second-order critical points. After recalling the first-order random-subspace framework, it introduces a second-order variant (Algorithm 2) equipped with a notion of well-aligned random subspaces (Definition 3.6) and a probabilistic alignment assumption (Assumption 3.7). The main theoretical result, Theorem 3.15, gives a high-probability worst-case complexity bound for reaching σ_k ≤ ε under a positivity condition θ>0 in Eq. (24). The authors then interpret this as O(κ_d^3 ε^{-3}) iterations and O(p^2 κ_d^3 ε^{-3}) evaluations, and, using Johnson–Lindenstrauss subspaces of dimension O(log r), advertise an O~(n^{4.5} ε^{-3}) iteration and evaluation complexity versus O(n^9 ε^{-3}) and O(n^{11} ε^{-3}) for full-space methods. The second half of the paper introduces a practical subspace quadratic-model algorithm, RSDFO-Q, and demonstrates numerically that it scales to problems with n≈1000 where full-space Py-BOBYQA variants fail.","tokens_in":22145,"tokens_out":8597,"duration_ms":71518,"significance":"If the claimed complexity result were valid uniformly in ε, the paper would make a substantial contribution: it appears to be the first worst-case second-order convergence analysis for random subspace model-based DFO, and it identifies a realistic regime (low-accuracy solutions or low-effective-rank problems) in which random subspaces improve dimension dependence. The proof chain from Lemma 3.8 through Theorem 3.15 is coherent and follows standard trust-region arguments, and the numerical study of RSDFO-Q is a useful practical contribution with a credible benchmark against Py-BOBYQA. The paper is also honest in Remark 2 about the restrictiveness of θ>0. However, the central advertised O~(n^{4.5} ε^{-3}) law is not uniform in ε: the positivity condition forces the alignment parameter α to shrink with ε, which in turn forces the subspace dimension p to grow like ε^{-1} in the JLT construction. This directly affects the main complexity claim and requires a substantial re-statement of the result's scope.","major_comments":[{"comment":"The advertised complexity O~(n^{4.5} ε^{-3}) is not a uniform consequence of Theorem 3.15. For θ>0 in Eq. (24) to hold with M=O(1), the alignment parameter α must satisfy α² = O(ε/r). The JLT construction in Section 3.1 then requires p = O(α^{-2} log r) = O(r ε^{-1} log r), not p = O(log r). Since κ_d = O(p³ P_max³) and P_max = Θ(sqrt(n/p)), substituting p(ε) gives an iteration bound of O~(n^{9/2} r^{9/2} ε^{-15/2}) and an evaluation bound of O~(n^{9/2} r^{13/2} ε^{-21/2}) rather than the displayed ε^{-3} laws. Table 1 and the sentence 'the dependency on n decreases from O(n^9) to O(n^{4.5})' are therefore only valid in a fixed-ε low-accuracy regime, or when r log r = O(ε); the abstract's branch 'and/or the problem has low effective rank' is also misleading if r is merely small but ε is driven to zero. Theorem 3.15, the complexity summary, and Table 1 need to be restated so that κ_d and p are explicitly allowed to depend on ε, or the theorem should be restricted to the regime in which the p=O(log r) choice is compatible with θ>0.","section":"Section 3.1, Table 1, Remark 2; Lemma 3.8, Eq. (24)"},{"comment":"The practical algorithm RSDFO-Q is not covered by the second-order theory developed in Section 3. Algorithm 3 is run numerically with q=2p+1 interpolation points, and the paper itself notes that fully quadratic models in the sense of Definition 3.1 generically require q=(p+1)(p+2)/2. Thus the experiments in Section 5 do not demonstrate the complexity guarantee of Theorem 3.15, and the claim that RSDFO-Q is a 'practical implementation of the ideas in Algorithms 1 and 2' needs a clear caveat that the implemented model construction is not fully quadratic and hence the second-order convergence theory does not apply to the numerical results as presented.","section":"Section 4 and Section 5"}],"minor_comments":[{"comment":"The text says 'using a complexity of O(κ5_d ε^{-3}) from above'; this should be O(κ_d^3 ε^{-3}) to be consistent with the complexity summary and with Eq. (14) in the trust-region argument.","section":"Section 3.1"},{"comment":"The theorem statement contains a typographical artifact in the lower bound on k: '− 1, ,' has an extra comma, and the notation δ_s is used inconsistently with δ_S elsewhere in the statement and proof.","section":"Theorem 3.15"},{"comment":"The text says RSDFO-Q with p=n achieves 'broadly comparable performance' to Py-BOBYQA, but Figure 1 shows it is worse than Py-BOBYQA with q=2n+1 in the data profile; the wording should be adjusted to reflect the actual comparison.","section":"Section 5.2"},{"comment":"No code or data availability statement is provided for the numerical experiments; the authors should state whether code is available and describe problem/data sources beyond the CUTEst references.","section":"Section 5 and References"}],"recommendation":"major_revision","confidential_remarks":"The non-uniformity issue is the core concern. The proof chain internal to Theorem 3.15 is not the problem; the problem is the interpretation of κ_d and p as ε-independent constants when θ>0 couples α to ε. This is fixable in the manuscript by re-stating the complexity bounds with explicit dependence on p(ε) and by marking Table 1 as applicable only in the low-accuracy or low-rank regime. The paper's heavy reliance on the authors' own prior work ([9], [11], [31]) is acceptable in context, but the novelty should be stated more crisply relative to those works."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is the first second-order worst-case complexity bound for random subspace model-based DFO, and it comes with a practical solver that actually works at n≈1000. The proof chain from the well-aligned subspace definition through Lemmas 3.8–3.13 to Theorem 3.15 is coherent and uses standard trust-region machinery. Credit where due: the alignment conditions (23c)–(23d) extend the derivative-based analysis of [11,31] to the DFO setting, and the high-probability bound with the Chernoff argument is clean. The practical RSDFO-Q algorithm is a sensible generalization of DFBGN to general objectives via two-set underdetermined quadratic interpolation, and the numerical section shows a real advantage over Py-BOBYQA on the large CUTEst collection.\n\nThe main soft spot is the advertised dimension-dependence. As the authors themselves flag in Remark 2, θ>0 forces α^2 = O(ε/r) for the JLT construction, which forces p = O(ε^{-1} r log r). Plugging that into κ_d = O(p^3 P_max^3) means the stated O~(n^4.5 ε^{-3}) law is not uniform in ε; it holds for fixed low-accuracy ε or for low effective rank r. The abstract and introduction do qualify the result as applying to low-accuracy/low-rank regimes, so this is a scope-and-statement issue rather than a contradiction in the lemmas. But Theorem 3.15 as written says 'for any ε>0' with Assumption 3.7, and Table 1 hides the ε-dependence of p. The authors should either state the bound with explicit dependence on α and r, or clearly state that p must scale with ε^{-1}. The scaled-Gaussian alternative in (84) weakens the α constraint but still requires ε > O(r/p). This is fixable.\n\nMinor issues: no code is released, and the numerical profiles show only averages over 10 runs without error bars. There is also a typo in Theorem 3.15 where δ_s appears in the denominator instead of δ_S.\n\nWho it's for: anyone working on large-scale DFO or randomized subspace methods. The theory is a genuine first, and the numerics suggest RSDFO-Q is a useful addition to the toolbox. It deserves a serious referee. I'd take it to the reading group.","headline":"First second-order complexity bound for random subspace model-based DFO, with a practical solver that scales to n≈1000; the n^4.5 bound is real but its ε-dependence is less clean than the presentation suggests.","tokens_in":22738,"tokens_out":2897,"would_cite":true,"duration_ms":24309,"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":"Random-subspace derivative-free optimization can reach approximate second-order critical points with complexity $\\widetilde{O}(n^{4.5}\\epsilon^{-3})$.","keywords":["derivative-free optimization","random subspaces","second-order convergence","worst-case complexity","quadratic interpolation models","Johnson-Lindenstrauss transforms","low effective rank","trust-region methods"],"falsifier":"Construct a smooth nonconvex function in $\\mathbb{R}^n$ whose Hessian at every relevant iterate has $r\\approx n$ eigenvectors with nearly identical, strictly negative eigenvalues, so no single dominant negative direction exists. Draw Gaussian Johnson-Lindenstrauss subspaces of dimension $p=O(\\log n)$ as prescribed, and compute the empirical probability that $\\theta>0$: it should decay to zero as $n$ grows. Then run RSDFO-Q on that function; if it still reaches the predicted $\\epsilon$-second-order critical complexity with uniformly good probability, the $\\theta>0$ mechanism is not actually needed, whereas if it fails, the low-rank caveat in Remark 2 is confirmed.","tokens_in":21470,"feed_emoji":"🧮","tokens_out":7759,"duration_ms":62716,"temperature":0.7,"pith_summary":"This paper extends random-subspace model-based derivative-free optimization (DFO) from first-order to second-order convergence. It proves the first high-probability worst-case complexity bound for such methods at approximate second-order critical points: $\\widetilde{O}(n^{4.5}\\epsilon^{-3})$ iterations and objective evaluations for an $n$-dimensional problem, versus $O(n^{9})$ iterations and $O(n^{11})$ evaluations for full-space model-based DFO. The improvement applies when the target accuracy $\\epsilon$ is modest or the Hessian has low effective rank. The paper also introduces RSDFO-Q, a practical quadratic-interpolation subspace method, and shows numerically that it solves problems of dimension roughly 1000 where full-space quadratic DFO fails.","feed_headline":"Random-subspace DFO reaches second order in O~(n^4.5)","feed_subtitle":"New complexity bound cuts dimension dependence from O(n^9) to O~(n^4.5) for low-accuracy or low-rank objectives.","key_machinery":"The load-bearing object is the well-aligned subspace condition (Definition 3.6). A subspace $P$ is well-aligned when it satisfies $\\|P\\|\\le P_{\\max}$, captures a $(1-\\alpha)$ fraction of the gradient via $\\|P^T\\nabla f(x_k)\\|\\ge(1-\\alpha)\\|\\nabla f(x_k)\\|$, captures a $(1-\\alpha)$ fraction of the most negative Hessian eigenvector $v_r$, and keeps every other eigenvector $v_i$ nearly orthogonal to $v_r$ in the subspace via $(\\hat v_i^T\\hat v_r)^2\\le 4\\alpha^2$. Combined with the condition $\\theta>0$ in (24), this implies the subspace criticality measure is at least $\\min((1-\\alpha)^2,\\theta)\\sigma_k$ (Lemma 3.8), which lets the trust-region analysis in Lemmas 3.10--3.13 run entirely in the low-dimensional space. Johnson-Lindenstrauss random matrices are shown to satisfy the alignment conditions with $p=O(\\log r)$ and $P_{\\max}=O(\\sqrt{n/p})$, which is the source of the improved dimension dependence.","core_discovery":"The central claim, Theorem 3.15, is that under boundedness and smoothness assumptions, fully quadratic subspace models, and a well-aligned random subspace condition, the iterate sequence satisfies $P[\\min_{j\\le k}\\sigma_j \\le \\epsilon] \\ge 1-\\exp(-c(k+1))$ after $k=O(\\kappa_d^3\\epsilon^{-3})$ iterations, where $\\sigma_k=\\max(\\|\\nabla f(x_k)\\|, -\\lambda_{\\min}(\\nabla^2 f(x_k)))$ is the second-order criticality measure and $\\kappa_d$ collects the fully quadratic model constants. With Johnson-Lindenstrauss subspaces of dimension $p=O(\\log r)$, where $r$ is the rank of the Hessian, $\\kappa_d=\\widetilde{O}(n^{3/2})$ and the bound becomes $\\widetilde{O}(n^{4.5}\\epsilon^{-3})$ iterations and evaluations. The mechanism is to show that a well-aligned subspace preserves a constant fraction of the full-space criticality measure, so that trust-region progress in the subspace certifies progress for the original problem.","pith_inferences":["The $\\theta>0$ requirement means the advertised advantage is really a statement about detecting one dominant negative-curvature direction: when the Hessian has many comparable negative directions at once, the needed subspace dimension grows like $O(r\\epsilon^{-1})$, so the $n^{4.5}$ bound should not be expected to hold at high accuracy without low effective rank.","A direct testable extension is to apply RSDFO-Q to large-scale neural-network fine-tuning, where Hessian low-rank structure has been reported; one would predict evaluation counts that track the effective rank rather than the ambient dimension.","The primary/secondary interpolation-set device could be extracted and reused in other derivative-free trust-region solvers as a cheap way to build underdetermined quadratic models in subspaces.","Combining the subspace second-order analysis with stochastic objective values, as has been done for the first-order case, would give a route to stochastic derivative-free second-order complexity bounds."],"forward_implications":["Second-order convergence theory now exists for random-subspace model-based DFO, matching the full-space $\\epsilon^{-3}$ rate while improving the dimension dependence.","For problems with low effective rank $r\\ll n$, the subspace dimension needs only $p=O(\\log r)$, so values of $n$ near 1000 or larger become practical for derivative-free optimization.","RSDFO-Q with full-dimensional subspaces is broadly competitive with a state-of-the-art full-space quadratic-interpolation solver on medium-scale problems, while low-dimensional variants solve large-scale problems where the full-space solver hits runtime limits.","The high-probability complexity bound implies, by standard arguments the paper outlines, almost-sure convergence of a subsequence of criticality measures to zero and complexity bounds in expectation."],"supporting_citations":[{"why":"Supplies the random-subspace model-based DFO framework and first-order complexity theory that this paper extends.","marker":"[9]"},{"why":"Source of the well-aligned subspace condition and the curvature-alignment lemma used to prove Lemma 3.8.","marker":"[11]"},{"why":"Provides the random embedding results and Johnson-Lindenstrauss subspace constructions used to satisfy the well-aligned condition with p=O(log r).","marker":"[31]"},{"why":"Gives fully quadratic interpolation theory, trust-region second-order convergence machinery, and Lemma 10.15 used to relate model and true criticality measures.","marker":"[13]"},{"why":"Provides the full-space second-order model-based DFO complexity bound that the paper compares against.","marker":"[19]"},{"why":"The state-of-the-art full-space quadratic-interpolation solver used as numerical baseline for RSDFO-Q.","marker":"[4]"},{"why":"Shows how to build fully quadratic interpolation models in random subspaces, a prerequisite for the second-order theory.","marker":"[12]"},{"why":"Minimum Frobenius norm quadratic interpolation used in RSDFO-Q model construction.","marker":"[28]"},{"why":"Trust-region radius management and interpolation-set maintenance ideas used in RSDFO-Q.","marker":"[29]"},{"why":"Johnson-Lindenstrauss transform theory that guarantees norm preservation and alignment with p=O(alpha^{-2} log r).","marker":"[34]"}],"fun_headline_variants":["Random-subspace DFO hits second order with O~(n^4.5) iteration bound","Subspace DFO: second-order criticality in O~(n^4.5) evaluations","Random projections give DFO second-order complexity O~(n^4.5)","Quadratic-model DFO in random subspaces proves O~(n^4.5) bound","Random subspaces cut DFO complexity from O(n^9) to O~(n^4.5)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the well-aligned subspace condition together with $\\theta>0$ (Equation 24): a random low-dimensional subspace must retain a fixed fraction of the gradient and of the most negative Hessian eigenvector, with all other eigenvectors nearly orthogonal to it inside the subspace. If $\\theta\\le 0$, the subspace criticality measure can vanish even when the full-space problem is far from second-order critical, and the complexity bound no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["Random-subspace DFO hits second order with O~(n^4.5) iteration bound","Subspace DFO: second-order criticality in O~(n^4.5) evaluations","Random projections give DFO second-order complexity O~(n^4.5)","Quadratic-model DFO in random subspaces proves O~(n^4.5) bound","Random subspaces cut DFO complexity from O(n^9) to O~(n^4.5)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001269,"raw_usage":{"total_tokens":5172,"prompt_tokens":900,"completion_tokens":4272,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":516,"completion_tokens_details":{"reasoning_tokens":4153}},"tokens_in":516,"tokens_out":4272,"duration_ms":27835,"temperature":1.0,"reasoning_tokens":4153,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:15:43.989378+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a smooth nonconvex function in $\\mathbb{R}^n$ whose Hessian at every relevant iterate has $r\\approx n$ eigenvectors with nearly identical, strictly negative eigenvalues, so no single dominant negative direction exists. Draw Gaussian Johnson-Lindenstrauss subspaces of dimension $p=O(\\log n)$ as prescribed, and compute the empirical probability that $\\theta>0$: it should decay to zero as $n$ grows. Then run RSDFO-Q on that function; if it still reaches the predicted $\\epsilon$-second-order critical complexity with uniformly good probability, the $\\theta>0$ mechanism is not actually needed, whereas if it fails, the low-rank caveat in Remark 2 is confirmed.","supporting_citations":[{"cited_title":"Cartis and L","cited_arxiv_id":null,"evidence_quote":"Supplies the random-subspace model-based DFO framework and first-order complexity theory that this paper extends."},{"cited_title":"Cartis, Z","cited_arxiv_id":null,"evidence_quote":"Source of the well-aligned subspace condition and the curvature-alignment lemma used to prove Lemma 3.8."},{"cited_title":"Shao, On random embeddings and their application to optimisation , Ph.D","cited_arxiv_id":null,"evidence_quote":"Provides the random embedding results and Johnson-Lindenstrauss subspace constructions used to satisfy the well-aligned condition with p=O(log r)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives fully quadratic interpolation theory, trust-region second-order convergence machinery, and Lemma 10.15 used to relate model and true criticality measures."},{"cited_title":"Garmanjani, Trust-region methods without using derivatives: Worst case complexity and the nonsmooth case , Ph.D","cited_arxiv_id":null,"evidence_quote":"Provides the full-space second-order model-based DFO complexity bound that the paper compares against."},{"cited_title":"Cartis, J","cited_arxiv_id":null,"evidence_quote":"The state-of-the-art full-space quadratic-interpolation solver used as numerical baseline for RSDFO-Q."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows how to build fully quadratic interpolation models in random subspaces, a prerequisite for the second-order theory."},{"cited_title":"Powell, Least Frobenius norm updating of quadratic models that satisfy interpola- tion conditions, Mathematical Programming 100 (2004), pp","cited_arxiv_id":null,"evidence_quote":"Minimum Frobenius norm quadratic interpolation used in RSDFO-Q model construction."},{"cited_title":"Powell, The BOBYQA algorithm for bound constrained optimization without derivatives, Tech","cited_arxiv_id":null,"evidence_quote":"Trust-region radius management and interpolation-set maintenance ideas used in RSDFO-Q."},{"cited_title":"Woodruff, Sketching as a tool for numerical linear algebra, Foundations and Trends® in Theoretical Computer Science 10 (2014), pp","cited_arxiv_id":null,"evidence_quote":"Johnson-Lindenstrauss transform theory that guarantees norm preservation and alignment with p=O(alpha^{-2} log r)."}],"review_version":1}