{"id":"0b25eef5-299d-41c1-900d-5f6451583b9c","arxiv_id":"2505.09045","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The adaptive round complexity of finding an epsilon-stationary point is Omega(epsilon^{-(p+1)/p}) in high dimension even with poly(d) parallel queries, and near-matching per-round query bounds are given in constant dimension.","lead":"This paper proves that in high dimension, running many parallel queries per round does not reduce the number of sequential rounds needed to find an approximate stationary point of a smooth nonconvex function. In constant dimension, it gives a constant-round algorithm whose per-round query count approaches the known gradient-flow-trapping bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's stated dimension condition omits a Δ^2 factor, so the lower bound as stated cannot hold for large Δ.","rationale":"The reader identified the zeroth-order to p-th order oracle simulation as the weakest assumption. That is a real gap, but the most load-bearing concern is more concrete and internal to Theorem 4: the statement's dimension condition does not match the proof's own use of r, which depends on Δ. This is not a matter of outside consensus or a missing citation; it is an algebraic inconsistency in the main theorem. If the theorem's statement is corrected to include Δ^2 in the dimension condition, the proof goes through for that corrected regime, which likely covers the paper's advertised Δ = O(1) claims. Hence the paper can be accepted conditional on fixing the theorem statement and providing the missing oracle-simulation justification. The verdict remains CONDITIONAL, matching the reader's overall assessment, but for a different primary reason.","tokens_in":28313,"tokens_out":34156,"duration_ms":316494,"concrete_test":"Set p=1, L_p=l_p=1, ε=10^{-2}, and choose d such that d/log^2 d = 10^8, satisfying Theorem 4's stated condition with c2=1. For Δ=10^4, the theorem predicts a lower bound c0 Δ ε^{-2} ≈ c0·10^8 rounds. But the proof's own requirement d ≥ C (r+1)^2 log^2 d forces the chain length r ≤ √(d/log^2 d) ≈ 10^4, so the maximum provable lower bound is r/2 ≈ 5×10^3. The discrepancy of five orders of magnitude shows the missing Δ^2 factor; re-deriving the dimension check with Δ inserted and comparing to the stated condition would settle the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4 asserts that for all Δ>0 and all d with d/log^2 d ≥ c2 (L_p/l_p)^{2/p} ε^{-(2+2p)/p}, the randomized complexity is at least c0 Δ (L_p/l_p)^{1/p} ε^{-(1+p)/p}. The proof, however, sets the chain length r = ⌊Δ / (1857 (L_p/l_p)^{1/p} ε^{-(1+p)/p})⌋ and then requires the dimension to satisfy '162·230^2 (r+1)^2 log^2 d ≤ d' (Appendix B.4, proof of Theorem 4). Substituting r yields d/log^2 d ≥ C Δ^2 (L_p/l_p)^{2/p} ε^{-2(1+p)/p}, with C a universal constant. Thus the theorem's condition is sufficient only when Δ is bounded by an absolute constant. For larger Δ, the claimed lower bound c0 Δ (L_p/l_p)^{1/p} ε^{-(1+p)/p} exceeds the maximum chain length r/2 ≈ (1/2)√(d/log^2 d) that the proof's own dimension check permits. No function in the constructed family can force more rounds than the chain length, so the formal statement is internally inconsistent for large Δ. The qualitative conclusion for Δ = O(1), which is the regime stated in the abstract, remains plausible, but the theorem as printed overclaims.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the adaptive (round) complexity of finding an ε-stationary point of a smooth nonconvex function when each round can issue poly(d) parallel queries. In the high-dimensional regime d = Ω~(ε^{-(2+2p)/p}) the authors construct a family of hard functions based on random coordinate partitions and prove an Ω(Δ (L_p/ℓ_p)^{1/p} ε^{-(p+1)/p}) lower bound on the number of rounds for every randomized algorithm (Theorem 4). They conclude that parallelization yields no acceleration and that gradient descent, cubic regularization, and AR_p are adaptively optimal. In the constant-dimensional case they propose an algorithm called Gradient Flow Grid Trapping (GFGT) that finds an ε-stationary point in k = Θ(1) rounds with per-round query count approaching ε^{-(d-1)/2} as k grows (Theorem 10), and they prove a matching lower bound for algorithms running in O(log(1/ε)) rounds (Theorem 11), answering an open question from Bubeck and Mikulincer.","tokens_in":28584,"tokens_out":11465,"duration_ms":105308,"significance":"If the results are correct, this is a substantial contribution to the theory of parallel nonconvex optimization. It provides the first tight adaptive-complexity characterization for stationary-point finding in both high and constant dimension, and it introduces a random-partition chaining construction that genuinely improves on the projection-based arguments of Carmon et al. (2020) in the presence of many parallel queries. The constant-dimensional GFGT algorithm is a concrete algorithmic contribution with a detailed correctness proof, and the lower bound for logarithmic-round algorithms matches the known upper bound up to log factors. The paper would be considerably strengthened by fixing the Δ-dependence in Theorem 4 and supplying the missing zeroth-order simulation argument.","major_comments":[{"comment":"The stated dimension condition in Theorem 4 is missing a Δ^2 factor. The proof sets r = floor(Δ / (1857 (L_p/l_p)^{1/p} ε^{-(1+p)/p})) and then requires 162·230^2 (r+1)^2 log^2 d ≤ d (Appendix B.4, proof of Theorem 4). Substituting r gives d/log^2 d ≥ C Δ^2 (L_p/l_p)^{2/p} ε^{-2(1+p)/p}, not the condition printed in the theorem. Consequently, for large Δ the claimed lower bound cannot be derived from the constructed family: the available chain length r/2 is bounded by roughly d^{1/2}/log d, while the theorem claims a lower bound proportional to Δ. The statement should either include the Δ^2 factor in the dimension condition, as the proof shows is necessary, or restrict Δ to an absolute constant, matching the abstract's regime.","section":"Theorem 4 and Appendix B.4"},{"comment":"The assertion that higher-order oracles can be constructed using poly(d) queries to the zeroth-order oracle is load-bearing and unproved. Theorem 4 is proved for zeroth-order queries only, but the conclusions about gradient descent, cubic-regularized Newton, and AR_p require that an algorithm with p-th-order oracle access can be simulated by zeroth-order queries within the same round. No finite-difference construction, accuracy analysis, or round-preservation argument is supplied. Without this, the lower bound applies only to zeroth-order algorithms, and the stated adaptive optimality of p-th-order methods is not established.","section":"Section 2, Oracle paragraph"},{"comment":"The concentration step invokes Theorem 12 with coefficients ρ_j(x), but Theorem 12 is stated for nonnegative coefficients α_i ≥ 0, whereas ρ_j(x) can be negative. The proof does not address this mismatch. The argument is likely repairable by splitting into positive and negative parts or by citing a signed-coefficient version, but as written the information-hiding step is not fully justified.","section":"Appendix B.3, proof of Lemma 8"}],"minor_comments":[{"comment":"The exponents in the two displayed query complexities are typeset without enough parentheses, making the claimed rates ambiguous; the cleaner expression in Appendix D.3, Lemma 31 should be used in the main text.","section":"Theorem 10"},{"comment":"Lemma 8 says 'up to addictive error' and should read 'additive error'; Lemma 9 says 'there exits a direction vector' and should read 'there exists'.","section":"Lemma 8 and Lemma 9"},{"comment":"The subsection heading 'Prior arguement fails under polynomial queries' contains a typo: 'arguement' should be 'argument'.","section":"Section 1.2.1"}],"recommendation":"major_revision","confidential_remarks":"The Δ-dependence error in Theorem 4 is the most serious issue and must be fixed before publication; if the result can only be proved for bounded Δ, the abstract, introduction, and Table 1 need corresponding adjustment. The missing zeroth-order simulation proof is also required because it underlies the claimed optimality of p-th-order methods. I do not see grounds for rejection: the construction and proof strategy are credible, and both gaps appear fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a serious look, but the headline theorem has a bug that needs fixing before the adaptive-optimality claims can stand. In Theorem 4 the proof chooses r proportional to Δ·ε^{-(p+1)/p}, then requires 162·230²(r+1)²log²d ≤ d. Substituting r gives a dimension condition that scales with Δ², not just ε^{-(2+2p)/p} as printed. The theorem as stated therefore cannot hold for large Δ: the claimed lower bound grows with Δ, but the constructed chain has only r links, so no function in the family can force more than ~r rounds. The abstract's message for Δ = O(1) survives, but the formal statement overreaches.\n\nWhat is genuinely new and good: the random-partition chaining construction is an elegant way to handle poly(d) queries per round in a noiseless lower bound, going beyond Carmon et al. (2020). The constant-dimensional GFGT algorithm neatly interpolates between grid search and Hollender–Zampetakis, and its query lower bound is tight up to log factors. If the Δ issue is patched, the conclusions about gradient descent, cubic-regularized Newton, and AR_p being adaptively optimal are plausible for bounded suboptimality gap.\n\nSoft spots, in proportion. The Δ issue is load-bearing and demands a correction to the theorem statement or proof. Two smaller gaps: the Preliminaries claim that higher-order oracles can be simulated by poly(d) zeroth-order queries in one round is asserted, not shown, and the transfer to first-order methods depends on it. Also, Appendix C extends the Brânzei–Li local-search bound to Θ(log(1/ε)) rounds by assertion; no proof is supplied for that extension. Both are likely fixable with standard arguments, but they are currently gaps.\n\nThis paper is for researchers in oracle complexity of nonconvex optimization; the technique will be reused. It deserves peer review, but I would make acceptance conditional on fixing the Δ-dependence and filling in the two asserted steps.","headline":"Strong paper with a real gap: Theorem 4's stated dimension condition is missing a Δ² factor, so the theorem overclaims as printed, but the core construction is solid and the result looks salvageable.","tokens_in":29129,"tokens_out":3501,"would_cite":true,"duration_ms":38173,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","68Q25","68W20","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Even large parallel query batches do not cut the worst-case sequential rounds needed to find a stationary point of a high-dimensional nonconvex function.","keywords":["adaptive complexity","non-convex optimization","stationary point","parallel queries","lower bounds","random partition","gradient flow trapping","cubic regularization"],"falsifier":"Run any candidate parallel algorithm on the paper's own hard family $f_P$ with $d/\\log^2 d \\ge c_2 (L_p/l_p)^{2/p}\\varepsilon^{-(2+2p)/p}$: succeeding with probability at least $3/4$ in fewer than $c_0\\Delta(L_p/l_p)^{1/p}\\varepsilon^{-(1+p)/p}$ rounds would refute the high-dimensional lower bound. A cheaper partial check is whether a first-order oracle can be assembled from $\\mathrm{poly}(d)$ zeroth-order queries in a single round; showing that any such simulation needs more than one round leaves the lower bound intact but undercuts the adaptive-optimality claim for the named methods.","tokens_in":28094,"feed_emoji":"🎯","tokens_out":15060,"duration_ms":130324,"temperature":0.7,"pith_summary":"The paper asks whether parallel computation can accelerate non-convex optimization, where in each round an algorithm may fire polynomially many queries at a black-box oracle in parallel. The main answer is negative in high dimensions: for every randomized algorithm there exists a function with Lipschitz $p$-th order derivatives on which at least $\\Omega(\\varepsilon^{-(p+1)/p})$ sequential rounds are required to reach an $\\varepsilon$-stationary point, no matter how many queries per round. That rate matches what the best one-query-per-round methods already achieve, so gradient descent, cubic-regularized Newton's method, and the $p$-th order adaptive regularization method are adaptively optimal and worst-case parallelization buys nothing. In constant dimension the paper obtains the other side of the tradeoff: a new algorithm finds an $\\varepsilon$-stationary point in a constant number of rounds with a query count that interpolates between full grid search and the known logarithmic-round method, and a matching lower bound shows $\\Theta(\\log(1/\\varepsilon))$-round algorithms must use $\\widetilde\\Omega(\\varepsilon^{-(d-1)/2})$ queries per round. The result matters because it is the first tight characterization of the round-versus-query tradeoff for finding stationary points.","feed_headline":"Parallel queries cannot speed up worst-case nonconvex optimization","feed_subtitle":"High-dimensional worst cases resist parallel speedup; low-dimensional cases get a matching round-query tradeoff.","key_machinery":"Two mechanisms carry the argument. In high dimension, the lower bound is driven by a family of hard functions $f_P(x) = g_P(\\rho(x)) + \\frac{1}{5}\\|x\\|^2$ parameterized by a uniformly random partition $P = (P_1,\\dots,P_{r+2})$ of the $d$ coordinates into equal blocks; the block sums $X_i(x)$ feed a chaining sum of bump-function products $\\Psi\\Phi$ that is radially damped by $\\rho$. The chain has two opposing properties: the gradient cannot drop below a fixed constant unless $|X_{r+1}-X_r| \\ge 1$, yet the answer to any query depends only on the first $2\\ell$ blocks unless some adjacent block sums exceed $1/2$ — and concentration of linear functions of conditioned Bernoulli variables keeps adjacent sums below $1/2$ with probability $1-d^{-\\omega(1)}$, so each round of parallel queries reveals at most two blocks. In constant dimension, the algorithmic mechanism is the Gradient Flow Grid Trapping (GFGT) method: place $\\ell_t$ equally spaced trap barriers in each coordinate, query a fine $\\delta_t$-net on every barrier, move the iterate only to the lowest reachable queried point, and compress each side of the box by a factor of $3/\\ell_t$ per round; unreachable boundaries guarantee the shrunken box still contains an $\\varepsilon$-stationary point, so $k=\\Theta(1)$ rounds suffice. The matching lower bound proceeds by a round-preserving reduction to finding the minimum of a random-staircase monotone path on a grid graph.","core_discovery":"The central claim of the paper is an impossibility result for the high-dimensional regime $d = \\widetilde\\Omega(\\varepsilon^{-(2+2p)/p})$: any randomized algorithm allowed $\\mathrm{poly}(d)$ oracle queries per round still needs at least $c_0 \\Delta (L_p/l_p)^{1/p} \\varepsilon^{-(1+p)/p}$ rounds to output a point with expected gradient norm at most $\\varepsilon$ for some function in $\\mathcal{F}_p(L_p)$. Because this matches the known sequential one-query-per-round lower bound, the extra parallelism cannot help in the worst case, and the established methods — gradient descent for $p=1$, cubic-regularized Newton for $p=2$, and the adaptive regularization method AR$_p$ for general $p$ — are adaptively optimal. For the constant-dimensional setting $d=\\Theta(1)$ on the cube $[0,1]^d$, the paper builds a deterministic algorithm that runs in $k=\\Theta(1)$ rounds with $\\varepsilon^{-(d-1)/2}(1+O(2^{-k}))$ queries per iteration, bridging the two previously known extremes, and proves that any randomized algorithm running in $k=\\Theta(\\log(1/\\varepsilon))$ rounds needs at least $\\widetilde\\Omega(\\varepsilon^{-(d-1)/2})$ queries per round, tight up to logarithmic factors and implying that the gradient-flow parallel trap is adaptively optimal.","pith_inferences":["Because the two regimes rest on different mechanisms — Boolean-slice concentration in high dimension, grid-graph staircase hardness in constant dimension — the intermediate dimension range the paper leaves open presumably contains the flip from 'parallelism useless' to 'parallelism helps'; testing whether the random-partition construction degrades gracefully as $d$ shrinks would locate that flip.","The paper pins down the round-query tradeoff only at the extremes ($k=\\Theta(1)$ and $k=\\Theta(\\log(1/\\varepsilon))$); a testable extension is whether intermediate values of $k$ can attain the interpolating exponent $\\frac{d-1}{2}(1+O(d^{-k}))$ that the lower bound predicts, which would fully settle the adaptivity hierarchy in fixed dimension.","A practical reading the authors only gesture at: parallel hardware still pays off inside a round, since per-round query loads such as the $\\delta_t$-nets of GFGT are exactly the parallelizable part — but the worst-case number of rounds is already achieved by sequential algorithms, so in high dimension more workers should not be expected to reduce iteration counts."],"forward_implications":["No amount of in-round parallelism improves worst-case round counts in high dimension: the $\\Omega(\\varepsilon^{-(p+1)/p})$ lower bound holds for algorithms making polynomially many queries per round, exactly as for one-query-per-round algorithms.","Gradient descent ($p=1$), cubic-regularized Newton ($p=2$), and AR$_p$ (general $p$) are adaptively optimal, so their known iteration counts cannot be beaten by parallel methods on this function class.","In constant dimension, an $\\varepsilon$-stationary point can be found in $k=\\Theta(1)$ rounds with $\\varepsilon^{-(d-1)/2}(1+O(2^{-k}))$ queries per iteration, interpolating between grid search at $k=1$ and the flow-trapping rate as $k$ grows.","Any $\\Theta(\\log(1/\\varepsilon))$-round algorithm in constant dimension must issue at least $\\widetilde\\Omega(\\varepsilon^{-(d-1)/2})$ queries per round, matching the gradient-flow parallel trap up to logarithmic factors and settling the open question about the low-depth region.","In the zero-variance limit of stochastic non-convex optimization the construction combines with the stochastic lower bound $\\Omega(\\sigma^2\\varepsilon^{-4})$ to give $\\Omega(\\varepsilon^{-2}+\\sigma^2\\varepsilon^{-4})$, matching the query complexity of SGD."],"supporting_citations":[{"why":"Supplies the one-query-per-round lower bound that this paper strengthens, along with the Psi/Phi component functions and smoothness estimates reused in the hard-function construction.","marker":"(Carmon et al., 2020)"},{"why":"Introduces cubic-regularized Newton's method, the p = 2 sequential algorithm the paper shows is adaptively optimal.","marker":"(Nesterov and Polyak, 2006)"},{"why":"Provides the high-order regularized method AR_p whose epsilon^{-(1+p)/p} rate is matched by the new parallel lower bound for general p.","marker":"(Birgin et al., 2017)"},{"why":"Supplies the gradient-flow parallel trap, the Theta(log(1/epsilon))-round epsilon^{-(d-1)/2}-query upper bound in constant dimension that the new lower bound matches.","marker":"(Hollender and Zampetakis, 2023)"},{"why":"Introduces the flow-trapping framework, the grid-graph reduction, and the open question about constant-dimension adaptivity that this paper partially resolves.","marker":"(Bubeck and Mikulincer, 2020)"},{"why":"Gives the random-staircase results on the adaptive query complexity of grid-graph local search used as the constant-dimension lower-bound engine.","marker":"(Brânzei and Li, 2022)"},{"why":"Establishes the reduction from finding stationary points to monotone-path local minimum search on grids that the constant-dimension lower bound is built on.","marker":"(Vavasis, 1993)"},{"why":"Provides the stochastic nonconvex lower bound the paper combines with its zero-variance construction to match SGD's query complexity; its hard instance is shown not to transfer to the noiseless parallel setting.","marker":"(Arjevani et al., 2023)"}],"fun_headline_variants":["Parallel queries can't beat sequential worst-case limits","Worst-case nonconvex optimization resists parallel speedup","Adaptive complexity: parallel queries don't help worst-case","Tight tradeoff: parallel fails in high dims, matches in low dims","Lower bound: parallel queries can't speed up high-dim stationarity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The transfer of the lower bound to gradient descent, cubic-regularized Newton, and AR$_p$ rests on the unproven premise, stated in the preliminaries, that a $p$-th order oracle can be simulated by $\\mathrm{poly}(d)$ zeroth-order queries within the same round; if that simulation costs extra rounds, the adaptive-optimality conclusions for those methods do not follow, though the zeroth-order lower bound itself stands.","fun_headline_variants_meta":{"raw":{"variants":["Parallel queries can't beat sequential worst-case limits","Worst-case nonconvex optimization resists parallel speedup","Adaptive complexity: parallel queries don't help worst-case","Tight tradeoff: parallel fails in high dims, matches in low dims","Lower bound: parallel queries can't speed up high-dim stationarity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000982,"raw_usage":{"total_tokens":4287,"prompt_tokens":1183,"completion_tokens":3104,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":799,"completion_tokens_details":{"reasoning_tokens":3016}},"tokens_in":799,"tokens_out":3104,"duration_ms":21887,"temperature":1.0,"reasoning_tokens":3016,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:42:32.419220+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run any candidate parallel algorithm on the paper's own hard family $f_P$ with $d/\\log^2 d \\ge c_2 (L_p/l_p)^{2/p}\\varepsilon^{-(2+2p)/p}$: succeeding with probability at least $3/4$ in fewer than $c_0\\Delta(L_p/l_p)^{1/p}\\varepsilon^{-(1+p)/p}$ rounds would refute the high-dimensional lower bound. A cheaper partial check is whether a first-order oracle can be assembled from $\\mathrm{poly}(d)$ zeroth-order queries in a single round; showing that any such simulation needs more than one round leaves the lower bound intact but undercuts the adaptive-optimality claim for the named methods.","supporting_citations":[{"cited_title":"Cubic regularization of newton method and its global performance","cited_arxiv_id":null,"evidence_quote":"Introduces cubic-regularized Newton's method, the p = 2 sequential algorithm the paper shows is adaptively optimal."},{"cited_title":"Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models","cited_arxiv_id":null,"evidence_quote":"Provides the high-order regularized method AR_p whose epsilon^{-(1+p)/p} rate is matched by the new parallel lower bound for general p."},{"cited_title":"The computational complexity of finding stationary points in non-convex optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the gradient-flow parallel trap, the Theta(log(1/epsilon))-round epsilon^{-(d-1)/2}-query upper bound in constant dimension that the new lower bound matches."},{"cited_title":"How to trap a gradient flow","cited_arxiv_id":null,"evidence_quote":"Introduces the flow-trapping framework, the grid-graph reduction, and the open question about constant-dimension adaptivity that this paper partially resolves."},{"cited_title":"Black-box complexity of local minimization","cited_arxiv_id":null,"evidence_quote":"Establishes the reduction from finding stationary points to monotone-path local minimum search on grids that the constant-dimension lower bound is built on."}],"review_version":1}