Pith. sign in

REVIEW 3 major objections 3 minor 57 references

The Adaptive Complexity of Finding a Stationary Point

T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.09045 v1 pith:NICHBE5T submitted 2025-05-14 math.OC cs.CCcs.DC

Huanjian Zhou , Andi Han , Akiko Takeda , Masashi Sugiyama This is my paper · ORCID
classification math.OCcs.CCcs.DC MSC 90C2668Q2568W2090C60
keywords adaptivecomplexitynon-convexoptimizationstationarypointparallelquerieslowerboundsrandompartitiongradientflowtrappingcubicregularization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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.

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 (3)
  1. [Theorem 4 and Appendix B.4] 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.
  2. [Section 2, Oracle paragraph] 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.
  3. [Appendix B.3, proof of Lemma 8] 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.
minor comments (3)
  1. [Theorem 10] 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.
  2. [Lemma 8 and Lemma 9] 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'.
  3. [Section 1.2.1] The subsection heading 'Prior arguement fails under polynomial queries' contains a typo: 'arguement' should be 'argument'.

Circularity Check

0 steps flagged · score 1.0 of 10

No materially circular derivation: the lower bounds are adversarial constructions, and the self-citations are not load-bearing.

full rationale

Walking the derivation chain, the main high-dimensional lower bound (Theorem 4) is an adversarial construction rather than a fit: the hard function f_P is built from random partitions, the chain length r is chosen from Delta and the target epsilon only to set the scale of the instance, and Lemmas 8 and 9 establish that after fewer than r/2 rounds the output cannot satisfy the gradient condition. The proof does not use the claimed lower bound as an input; the constants (0.08, 1857, etc.) arise from explicit calculations. The random-partition idea is attributed to the authors' own earlier work (Zhou et al., 2024), but the paper re-proves the needed concentration via Theorem 12 (Polaczyk, 2023) and does not assume the conclusion of that prior work. The constant-dimensional lower bound is a round-preserving reduction to external local-search lower bounds (Vavasis, 1993; Branzei and Li, 2022), so it is independent. I therefore find no circular step. Two non-circular caveats are worth recording. First, Section 2 asserts without proof that higher-order oracles can be simulated by poly(d, 1/epsilon) zeroth-order queries in one round; this is the bridge from the zero-order lower bound to the claimed optimality of p-th order methods. That is an unsupported transfer or omitted proof, not circularity. Second, the proof of Theorem 4 sets r = floor(Delta / (1857 (L_p/l_p)^{1/p} epsilon^{-(1+p)/p})) and requires 162 * 230^2 (r+1)^2 log^2 d <= d, so the stated dimension condition d/log^2 d >= c2 (L_p/l_p)^{2/p} epsilon^{-(2+2p)/p} appears to omit a Delta^2 factor; this is an internal correctness or consistency issue, not circularity. The qualitative conclusion for bounded Delta is not affected by this observation.

Assumptions & free parameters 3 free parameters · 4 assumptions · 2 invented entities

No constants are fitted to empirical data. The proof uses several hand-chosen parameters (R, d0, alpha) that affect only constant factors and failure probabilities. The central claims rest on two external black boxes: the Boolean-slice concentration inequality and the Brânzei-Li local search lower bound, plus the asserted zero-order simulation of higher-order oracles.

free parameters (3)
  • R = 230*sqrt(r+1)
    Radius of the nonlinear map rho in the hard function f_P; chosen to control smoothness and gradient bounds. It affects only constants in the lower bound.
  • part size d0 = >= log^2 d
    Fixed part size of the random partition; choosing it logarithmic in d is what makes the Boolean-slice concentration argument work and sets the dimension condition.
  • alpha = omega(1), e.g. log log d
    Appears in Lemma 8 as the slack that makes the failure probability d^{-omega(1)}; any slowly growing choice works.
assumptions (4)
  • standard math Concentration for linear functions over a Boolean slice (Theorem 12, Polaczyk 2023)
    Used in Lemma 8 to show a parallel query cannot detect hidden future partition parts; if this concentration fails, the information-hiding lemma fails.
  • standard math Smooth lifting of monotone path functions to gradient-stationary functions (Vavasis 1993, Lemma 19)
    Bridges grid-graph local search to smooth stationary points for the constant-dimensional lower bound.
  • standard math Round-preserving reduction and local-search lower bound of Brânzei and Li (2022), Lemma 22
    Provides the query-per-round lower bound for monotone path functions; the paper cites this rather than reproving it.
  • domain assumption Zeroth-order oracle simulates p-th order oracles in one round (Section 2)
    Asserted without proof; needed to apply zero-order lower bounds to gradient and higher-order algorithms, including the claim that GD and cubic Newton are adaptively optimal.
invented entities (2)
  • Random-partition chaining hard function f_P
    purpose: Adversarial lower-bound instance for high-dimensional adaptive algorithms
    It is an internal proof construction with no empirical or falsifiable external handle; its role is to hide future coordinates from parallel queries.
  • Gradient Flow Grid Trapping (GFGT) Algorithm 1
    purpose: Constant-round upper-bound algorithm for constant dimension
    A new algorithmic construction; no code is shipped, but the algorithm is fully specified enough for re-implementation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Adaptive Complexity of Finding a Stationary Point." pith.science (2026). https://pith.science/paper/NICHBE5T

@misc{pith2026250509045,
  author       = {Pith},
  title        = {Pith review of: The Adaptive Complexity of Finding a Stationary Point},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NICHBE5T}},
  note         = {Machine review of arXiv:2505.09045}
}
abstract

In large-scale applications, such as machine learning, it is desirable to design non-convex optimization algorithms with a high degree of parallelization. In this work, we study the adaptive complexity of finding a stationary point, which is the minimal number of sequential rounds required to achieve stationarity given polynomially many queries executed in parallel at each round. For the high-dimensional case, i.e., $d = \widetilde{\Omega}(\varepsilon^{-(2 + 2p)/p})$, we show that for any (potentially randomized) algorithm, there exists a function with Lipschitz $p$-th order derivatives such that the algorithm requires at least $\varepsilon^{-(p+1)/p}$ iterations to find an $\varepsilon$-stationary point. Our lower bounds are tight and show that even with $\mathrm{poly}(d)$ queries per iteration, no algorithm has better convergence rate than those achievable with one-query-per-round algorithms. In other words, gradient descent, the cubic-regularized Newton's method, and the $p$-th order adaptive regularization method are adaptively optimal. Our proof relies upon novel analysis with the characterization of the output for the hardness potentials based on a chain-like structure with random partition. For the constant-dimensional case, i.e., $d = \Theta(1)$, we propose an algorithm that bridges grid search and gradient flow trapping, finding an approximate stationary point in constant iterations. Its asymptotic tightness is verified by a new lower bound on the required queries per iteration. We show there exists a smooth function such that any algorithm running with $\Theta(\log (1/\varepsilon))$ rounds requires at least $\widetilde{\Omega}((1/\varepsilon)^{(d-1)/2})$ queries per round. This lower bound is tight up to a logarithmic factor, and implies that the gradient flow trapping is adaptively optimal.

Figures

Figures reproduced from arXiv: 2505.09045 by the authors.

Figure 1
Figure 1. Illustration of iterate update on 2-dimensional space. We plot trap barriers as black grids and queried points on the trap barrier as blue dots. (a) Current iterate location. (b) If all the queried points are εt-unreachable from xt , then x t+1 = x t . (c) If some queried points are εt-reachable, we select x t+1 as the point with smallest function value. probability. Furthermore, they effectively controlled the vari… view at source ↗
Figure 2
Figure 2. Illustration of domain compression on 2-dimensional space depending on the location of x t+1. The shaded areas represent the compressed domain for the next iteration. (a,b) If x t+1 is close to a boundary (in this case, the left boundary), the domain is extended only to the other directions (top, bottom, right). (c,d) If x t+1 is not close to any boundary, the domain is extended for to directions, depending on wheth… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 44 canonical work pages

  1. [1]

    Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons

    Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Conference on Learning Theory, pages 39--75. PMLR, 2017

    work page 2017

  2. [2]

    A convergence theory for deep learning via over-parameterization

    Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning, pages 242--252. PMLR, 2019

    work page 2019

  3. [3]

    Fast parallel sampling under isoperimetry

    Nima Anari, Sinho Chewi, and Thuy-Duong Vuong. Fast parallel sampling under isoperimetry. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 161--185. PMLR, 30 Jun--03 Jul 2024

    work page 2024

  4. [4]

    Lower bounds for non-convex stochastic optimization

    Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 0 (1): 0 165--214, 2023

    2023

  5. [5]

    The adaptive complexity of maximizing a submodular function

    Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 1138--1151, 2018 a

    work page 2018

  6. [6]

    Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization

    Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. arXiv preprint arXiv:1808.03880, 2018 b

    arXiv 2018

  7. [7]

    An elementary introduction to modern convex geometry

    Keith Ball et al. An elementary introduction to modern convex geometry. Flavors of geometry, 31 0 (1-58): 0 26, 1997

    work page 1997

  8. [8]

    Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

    Ernesto G Birgin, JL Gardenghi, Jos \'e Mario Mart \' nez, Sandra Augusta Santos, and Ph L Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Programming, 163: 0 359--368, 2017

    work page 2017

Show all 57 references
  1. [9]

    Optimization methods for large-scale machine learning

    L \'e on Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60 0 (2): 0 223--311, 2018

    2018

  2. [10]

    The query complexity of local search and brouwer in rounds

    Simina Br \^a nzei and Jiawei Li. The query complexity of local search and brouwer in rounds. In Conference on Learning Theory, pages 5128--5145. PMLR, 2022

    2022

  3. [11]

    Parallel algorithms for select and partition with noisy comparisons

    Mark Braverman, Jieming Mao, and S Matthew Weinberg. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 851--862, 2016

    2016

  4. [12]

    How to trap a gradient flow

    S \'e bastien Bubeck and Dan Mikulincer. How to trap a gradient flow. In Conference on Learning Theory, pages 940--960. PMLR, 2020

    2020

  5. [13]

    Complexity of highly parallel non-smooth convex optimization

    S \'e bastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in neural information processing systems, 32, 2019

    2019

  6. [14]

    An adaptivity hierarchy theorem for property testing

    Cl \'e ment L Canonne and Tom Gur. An adaptivity hierarchy theorem for property testing. computational complexity, 27: 0 671--716, 2018

    2018

  7. [15]

    Lower bounds for finding stationary points i

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184 0 (1): 0 71--120, 2020

    2020

  8. [16]

    Lower bounds for finding stationary points ii: first-order methods

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185 0 (1): 0 315--355, 2021

    2021

  9. [17]

    Resqueing parallel and private stochastic convex optimization

    Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2031--2058. IEEE, 2023

    2023

  10. [18]

    Scalable subspace methods for derivative-free nonlinear least-squares optimization

    Coralia Cartis and Lindon Roberts. Scalable subspace methods for derivative-free nonlinear least-squares optimization. Mathematical Programming, 199 0 (1): 0 461--524, 2023

    2023

  11. [19]

    On the complexity of steepest descent, newton's and regularized newton's methods for nonconvex unconstrained optimization problems

    Coralia Cartis, Nicholas IM Gould, and Ph L Toint. On the complexity of steepest descent, newton's and regularized newton's methods for nonconvex unconstrained optimization problems. Siam journal on optimization, 20 0 (6): 0 2833--2852, 2010

    2010

  12. [20]

    Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

    Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints. SIAM Journal on Optimization, 30 0 (1): 0 513--541, 2020 a

    2020

  13. [21]

    A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

    Coralia Cartis, Nick IM Gould, and Ph L Toint. A concise second-order complexity analysis for unconstrained optimization using high-order regularized models. Optimization Methods and Software, 35 0 (2): 0 243--256, 2020 b

    2020

  14. [22]

    Improved lower bounds for submodular function minimization

    Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, and Aaron Sidford. Improved lower bounds for submodular function minimization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 245--254. IEEE, 2022

    2022

  15. [23]

    Parallel submodular function minimization

    Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, and Aaron Sidford. Parallel submodular function minimization. Advances in Neural Information Processing Systems, 36, 2024

    2024

  16. [24]

    Settling the query complexity of non-adaptive junta testing

    Xi Chen, Rocco A Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. Journal of the ACM (JACM), 65 0 (6): 0 1--18, 2018

    2018

  17. [25]

    The loss surfaces of multilayer networks

    Anna Choromanska, Mikael Henaff, Michael Mathieu, G \'e rard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pages 192--204. PMLR, 2015

    2015

  18. [26]

    Parallel merge sort

    Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17 0 (4): 0 770--785, 1988

    1988

  19. [27]

    Large scale distributed deep networks

    Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc'aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in Neural Information Processing Systems, 25, 2012

    2012

  20. [28]

    Lower bounds for parallel and randomized convex optimization

    Jelena Diakonikolas and Crist \'o bal Guzm \'a n. Lower bounds for parallel and randomized convex optimization. In Conference on Learning Theory, pages 1132--1157. PMLR, 2019

    2019

  21. [29]

    Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator

    Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018

    2018

  22. [30]

    Escaping from saddle points—online stochastic gradient for tensor decomposition

    Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points—online stochastic gradient for tensor decomposition. In Conference on learning theory, pages 797--842. PMLR, 2015

    2015

  23. [31]

    Matrix completion has no spurious local minimum

    Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in neural information processing systems, 29, 2016

    2016

  24. [32]

    The computational complexity of finding stationary points in non-convex optimization

    Alexandros Hollender and Emmanouil Zampetakis. The computational complexity of finding stationary points in non-convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 5571--5572. PMLR, 2023

    2023

  25. [33]

    Non-convex optimization for machine learning

    Prateek Jain, Purushottam Kar, et al. Non-convex optimization for machine learning. Foundations and Trends in Machine Learning , 10 0 (3-4): 0 142--363, 2017

    2017

  26. [34]

    How to escape saddle points efficiently

    Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724--1732. PMLR, 2017

    2017

  27. [35]

    Deep learning without poor local minima

    Kenji Kawaguchi. Deep learning without poor local minima. Advances in Neural Information Processing Systems, 29, 2016

    2016

  28. [36]

    Adam: A method for stochastic optimization

    Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  29. [37]

    On the complexity of first-order methods in stochastic bilevel optimization

    Jeongyeol Kwon, Dohyun Kwon, and Hanbaek Lyu. On the complexity of first-order methods in stochastic bilevel optimization. arXiv preprint arXiv:2402.07101, 2024

    2024 arXiv

  30. [38]

    A polynomial lower bound on adaptive complexity of submodular maximization

    Wenzheng Li, Paul Liu, and Jan Vondr \'a k. A polynomial lower bound on adaptive complexity of submodular maximization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 140--152, 2020

    2020

  31. [39]

    Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion

    Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345--3354. PMLR, 2018

    2018

  32. [40]

    Some np-complete problems in quadratic and nonlinear programming

    Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming. Technical report, 1985

    1985

  33. [41]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovi c Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  34. [42]

    How to make the gradients small

    Yurii Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, 0 (88): 0 10--11, 2012

    2012

  35. [43]

    Introductory lectures on convex optimization: A basic course, volume 87

    Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013

    2013

  36. [44]

    Cubic regularization of newton method and its global performance

    Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical programming, 108 0 (1): 0 177--205, 2006

    2006

  37. [45]

    Concentration of Measure and Functional Inequalities

    Bart omiej Polaczyk. Concentration of Measure and Functional Inequalities. PhD thesis, University of Warsaw, 2023

    2023

  38. [46]

    Hogwild!: A lock-free approach to parallelizing stochastic gradient descent

    Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011

    2011

  39. [47]

    A geometric analysis of phase retrieval

    Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18: 0 1131--1198, 2018

    2018

  40. [48]

    Parallelism in comparison problems

    Leslie G Valiant. Parallelism in comparison problems. SIAM Journal on Computing, 4 0 (3): 0 348--355, 1975

    1975

  41. [49]

    Black-box complexity of local minimization

    Stephen A Vavasis. Black-box complexity of local minimization. SIAM Journal on Optimization, 3 0 (1): 0 60--80, 1993

    1993

  42. [50]

    Lower bound for randomized first order convex optimization

    Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex optimization. arXiv preprint arXiv:1709.03594, 2017

    2017 arXiv

  43. [51]

    Large batch training of convolutional networks

    Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arXiv:1708.03888, 2017

    2017 arXiv

  44. [52]

    Large batch optimization for deep learning: Training BERT in 76 minutes

    Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In International Conference on Learning Representations, 2...

    2020

  45. [53]

    On the lower bound of minimizing polyak- ojasiewicz functions

    Pengyun Yue, Cong Fang, and Zhouchen Lin. On the lower bound of minimizing polyak- ojasiewicz functions. In The Thirty Sixth Annual Conference on Learning Theory, pages 2948--2968. PMLR, 2023

    2023

  46. [54]

    Adaptive methods for nonconvex optimization

    Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in Neural Information Processing systems, 31, 2018

    2018

  47. [55]

    On lower iteration complexity bounds for the convex concave saddle point problems

    Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194 0 (1): 0 901--935, 2022

    2022

  48. [56]

    Parallel simulation for sampling under isoperimetry and score-based diffusion models

    Huanjian Zhou and Masashi Sugiyama. Parallel simulation for sampling under isoperimetry and score-based diffusion models. arXiv preprint arXiv:2412.07435, 2024

    2024

  49. [57]

    Adaptive complexity of log-concave sampling

    Huanjian Zhou, Baoxiang Wang, and Masashi Sugiyama. Adaptive complexity of log-concave sampling. arXiv preprint arXiv:2408.13045, 2024

    2024 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.