Escaping Saddle-Points Faster under Interpolation-like Conditions

Abhishek Roy; Krishnakumar Balasubramanian; Prasant Mohapatra; Saeed Ghadimi

REVIEW 2 major objections 3 minor 52 references

Escaping Saddle-Points Faster under Interpolation-like Conditions

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

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

Pith's one-line read Under a strong growth condition on stochastic gradients, perturbed SGD finds an $\epsilon$-local minimizer with $\tilde{O}(1/\epsilon^2)$ first-order oracle calls—the same rate as deterministic gradient descent—and stochastic…

desk verdict New conditional rates for saddle escape under SGC, but the assumption's reach at saddle points is over-sold and a key zeroth-order lemma is missing its proof. read the letter →

arxiv 2009.13016 v1 pith:RJD6P2XN submitted 2020-09-28 stat.ML cs.LGmath.OCmath.STstat.TH

Abhishek Roy , Krishnakumar Balasubramanian , Saeed Ghadimi , Prasant Mohapatra This is my paper · ORCID

classification stat.MLcs.LGmath.OCmath.STstat.TH MSC 90C2690C1568Q2562L20

keywords interpolation-likeconditionsstronggrowthconditionsaddle-pointescapeoraclecomplexityperturbedstochasticgradientdescentcubic-regularizedNewtonover-parametrizationnonconvexoptimization

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 claims that when an over-parametrized model interpolates its training data, the stochastic noise obeys a strong growth condition: the variance of the sample gradient at any point is proportional to the squared norm of the true gradient. Under this condition, the perturbed stochastic gradient method (PSGD) escapes saddle points and reaches an $\epsilon$-local minimizer with $\tilde{O}(1/\epsilon^2)$ stochastic gradient calls, matching the deterministic rate. The stochastic cubic-regularized Newton method (SCRN) improves from $\tilde{O}(1/\epsilon^{3.5})$ to $\tilde{O}(1/\epsilon^{2.5})$ calls, though it still falls short of the deterministic cubic-regularized rate of $\tilde{O}(1/\epsilon^{1.5})$. The same mechanism also yields improved zeroth-order complexities, where only function values are available.

What carries the argument

The load-bearing object is the Strong Growth Condition (SGC), Assumption 2.4: $\mathbb{E}_\xi\|\nabla F(x,\xi)\|^2 \le \rho \|\nabla f(x)\|^2$ for $\rho>1$. Its key consequence is Lemma 2.1, which bounds the variance of the averaged stochastic gradient by $((\rho-1)/n_1)\|\nabla f(x)\|^2$. Because the noise scales with the squared gradient norm, the noise automatically disappears near stationary points and shrinks proportionally whenever the gradient is large, letting the standard PSGD descent and saddle-escape argument proceed as in the deterministic case; the same variance control, applied to the gradient estimator inside the cubic-regularized Newton update, yields the improved SCRN rate.

What would settle it

Take a finite-sum nonconvex objective with two or more data terms where the average has a strict saddle at $x^*$ but each individual sample has nonzero gradient at $x^*$, so SGC fails there; run PSGD with the paper's parameter choices and check whether the number of iterations to reach an $\epsilon$-local minimizer scales as $1/\epsilon^2$ or degrades toward $1/\epsilon^4$.

Watch

Extended reading notes

Core claim

Under the Strong Growth Condition (Assumption 2.4), the variance of the stochastic gradient estimator at $x$ is at most $((\rho-1)/n_1)\|\nabla f(x)\|^2$ (Lemma 2.1). Consequently, at every stationary point of the expected loss the sample gradients vanish almost surely, so stochastic noise cannot mask the signal that drives descent or saddle escape. Exploiting this, the paper proves that PSGD requires $\tilde{O}(1/\epsilon^2)$ first-order oracle calls to reach an $\epsilon$-local minimizer with high probability, and SCRN requires $\tilde{O}(1/\epsilon^{2.5})$ calls in expectation; the latter is better than the interpolation-free stochastic rate but does not match the deterministic cubic-regularized rate, and the authors argue that a Hessian-level interpolation assumption would be needed to close that gap.

Load-bearing premise

The strong growth condition, Assumption 2.4, must hold at every point: the sample gradient must have zero variance whenever the true gradient is zero, which for finite-sum models means every sample's loss shares every stationary point of the average loss.

Editorial extensions

If this is right

PSGD with vanilla stochastic gradients reaches an $\epsilon$-local minimizer in $\tilde{O}(1/\epsilon^2)$ first-order oracle calls under SGC, matching deterministic perturbed gradient descent.
SCRN under SGC needs $\tilde{O}(1/\epsilon^{2.5})$ first- and second-order oracle calls, improving on the $\tilde{O}(1/\epsilon^{3.5})$ stochastic rate without interpolation.
In the zeroth-order (function-value-only) regime, PSGD under SGC requires $\tilde{O}(d^{1.5}/\epsilon^{4.5})$ function evaluations, a rate with no existing interpolation-free comparison.
The improved rates hold for the plain, unmodified versions of PSGD and SCRN, without variance-reduction machinery.
A Hessian-level interpolation assumption would likely be needed for SCRN to match the deterministic $\tilde{O}(1/\epsilon^{1.5})$ rate.

Reading between the lines

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

If SGC holds only in a neighborhood of the global minimum but not at saddle points, the deterministic PSGD rate would degrade; a local or approximate version of SGC may be the right testable condition for realistic over-parametrized models.
For finite-sum objectives, SGC at a saddle point says that every differentiable sample function shares that stationary point; this is a strong geometric constraint, and one can probe it directly by evaluating sample-gradient norms at known saddles of networks trained on duplicated data.
The SCRN gap suggests a natural analogue: a Hessian-SGC bounding $\mathbb{E}\|\nabla^2 F - \nabla^2 f\|^2$ by a function that vanishes at second-order stationary points; measuring whether this holds near saddles would decide whether the $\tilde{O}(1/\epsilon^{1.5})$ rate is achievable.
The dimension penalties in the zeroth-order results ($d^{1.5}$ for PSGD, $d^4$ for SCRN Hessian calls) are consequences of the Gaussian smoothing estimators; coordinate-wise smoothing might reduce them at the price of other assumptions.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this is a legitimate theoretical extension that gets new rates for PSGD and SCRN under SGC, but the assumption at saddle points is doing more work than the over-parametrization motivation acknowledges, and one zeroth-order lemma is missing a proof. I'd send it out, with a request for revision.

The genuinely new thing is the observation, Lemma 2.1, that under SGC the variance of the stochastic gradient is controlled by the squared norm of the full gradient. Applying that to the existing saddle-escape machinery from JNG+19 and TSJ+18 yields O~(1/eps^2) for PSGD and O~(1/eps^2.5) for SCRN. Those rates are not in the prior literature, and the paper is honest that SCRN does not reach the deterministic O~(1/eps^1.5). The zeroth-order analysis is also non-trivial: the gradient estimators have sub-exponential tails with exponent 2/3, and the authors work through the concentration carefully. No constants are fitted and no circular argument jumps out.

Now the soft spots. The big one, flagged in the stress-test, is that SGC forces zero stochastic gradient almost surely at every stationary point of f, not just at global minimizers. Interpolation in over-parametrized models gives you zero noise at the interpolating point, but it does not make individual sample gradients vanish at a strict saddle where the full gradient cancels. The paper asserts the phenomenon is observed in practice, but gives no model class or reference where SGC actually holds at saddles. That means the advertised 'over-parametrization' regime is not secured. The theorems themselves are conditional on SGC, so the math stands, but the motivation is over-sold.

Second, Lemma A.12(b), which is the load-bearing step for zeroth-order saddle escape, is stated and then the proof is omitted with 'the proof method is same.' That is not acceptable for a lemma of that importance; the non-sub-Gaussian tail makes it unlikely to be literally the same as JNG+19.

Third, Theorem 3.2 is presented as the 'without SGC' comparison, but its statement includes Assumption 2.4. The proof suggests a standard variance bound is really being used. The statement needs to be corrected to match the intended comparison.

None of these are fatal to the conditional rates, but they need fixing before the results are fully trusted. The paper deserves a serious referee; I would suggest major revision rather than rejection.

For you: if you work on stochastic nonconvex optimization, this is worth knowing about and citing once the presentation is cleaned up. I'd bring it to group meeting to discuss whether SGC at saddles is ever realistic.

Referee Report

2 major / 3 minor

Summary. The paper analyzes two stochastic algorithms, Perturbed Stochastic Gradient Descent (PSGD) and Stochastic Cubic-Regularized Newton (SCRN), under the Strong Growth Condition (Assumption 2.4). Its main claims are that PSGD reaches an epsilon-local minimizer with O~(1/epsilon^2) first-order oracle calls, matching the deterministic rate, and that SCRN reaches an epsilon-local minimizer with O~(1/epsilon^2.5) first- and second-order oracle calls, improving on the known stochastic rate of O~(1/epsilon^3.5) but not matching the deterministic cubic-regularized rate. Zeroth-order analogues are also stated, giving O~(d^1.5/epsilon^4.5) for PSGD and O~(d^4 log d / epsilon^2.5) for SCRN. The proofs follow the coupling framework of Jin et al. (2019), with the SGC used to replace constant stochastic gradient variance by variance proportional to the squared true gradient norm.

Significance. If the conditional statements are correct, the results are valuable: PSGD attains the deterministic saddle-escape rate without variance reduction, and SCRN improves the known stochastic second-order rate while leaving an explicitly identified gap to the deterministic cubic-regularized method. The first-order PSGD proof is laid out in detail with explicit parameter choices, and the paper honestly highlights that Hessian-level interpolation conditions may be needed for further SCRN improvements. The significance is tempered by two concerns: the motivating claim that SGC is satisfied in over-parametrized models is not established at saddle points, and the zeroth-order saddle-escape lemma is stated without proof. Both concerns bear directly on the advertised rates as statements about over-parametrized machine learning, rather than as purely conditional statements about functions satisfying SGC.

major comments (2)

[Section 2, Assumption 2.4; Lemmas 2.1, A.5, A.12] The Strong Growth Condition (Assumption 2.4) is the engine of the improved rates: Lemma 2.1 converts it into variance O(||grad f(x)||^2), and Lemmas A.5 and A.12 use this to shorten the saddle-escape phase from O~(epsilon^{-2.5}) to O~(epsilon^{-0.5}) in both Theorems 3.1 and 4.1. However, at any point with grad f(x)=0, the condition forces grad F(x,xi)=0 almost surely. In an over-parametrized finite-sum model, interpolation at a global minimizer x* only guarantees grad F_i(x*)=0 for each i; at a strict saddle x_bar where grad f(x_bar)=sum_i grad F_i(x_bar)=0 through cancellation, the individual gradients need not vanish, so SGC can fail exactly where the saddle-escape argument is applied. The paper asserts in Section 2 that this phenomenon is observed in practice, but it gives no model class, reference, or argument establishing SGC at saddle points. Consequently the central claim that interpolation accelerates saddle escape in over-parametrized models is not established; the theorems are conditional on SGC and should be framed as such, with the applicability claim either proved or removed.
[Appendix A, Lemma A.12(b); Lemmas A.10(b) and A.11(b)] The zeroth-order saddle-escape analysis is not complete as written. Lemma A.12(b) is stated for the zeroth-order setting, but its proof says 'we omit the proof here'; Lemmas A.10(b) and A.11(b) are asserted with 'the rest follows from [JNG+19]' without verifying that the 2/3-sub-exponential zeroth-order gradient noise satisfies the required coupling bounds. This is load-bearing because Lemma A.12(b) supplies the escape event used in the second half of the proof of Theorem 3.1(b) and in Theorem 3.2, and the zeroth-order rate O~(d^{1.5} epsilon^{-4.5}) depends on it. The authors should either provide the full proof or a complete reduction that states and proves the exact analogues of the Jin et al. (2019) claims for the zeroth-order estimator defined in equation (3).

minor comments (3)

[Section 3, Theorem 3.2] Theorem 3.2 is stated under Assumptions 2.1-2.4 and 3.1, although the surrounding paragraph says it treats the case 'when SGC does not hold'; the assumption list should replace Assumption 2.4 with the standard variance bound in equation (10), which is the condition actually used in the proof.
[Section 2, Lemma 2.1] Lemma 2.1 claims the variance bound holds for both the first-order and zeroth-order oracles, but the proof only treats the first-order oracle using grad F(x,xi); in the zeroth-order setting the estimator g_t defined in (3) is biased and Lemma B.6 contains an additional O(nu^2 L_G^2 (d+3)^3) term. The statement should be restricted to the first-order oracle, or a separate zeroth-order version should be proved explicitly.
[Theorems 3.1 and 4.1] Several parameter prescriptions are ambiguous or incomplete as printed: in Theorem 3.1(a) the formula for eta mixes log^{-2}(1/epsilon) with a0 log(...), and the constants kappa_i and mu_i in Theorems 3.1(b), 3.2, and 4.1 are declared absolute without giving the conditions they must satisfy. Please restate these parameter choices unambiguously so the claimed rates can be verified without reverse-engineering the proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the rates are derived from the explicit SGC premise and standard smoothness/tail assumptions; the self-citations are auxiliary technical bounds, not restatements of the target results.

full rationale

The derivation chain is self-contained in the relevant sense. The claimed rates are obtained by taking SGC (Assumption 2.4) as a premise, deriving Lemma 2.1 by direct variance algebra, and then following the JNG+19 framework for PSGD and the Nesterov-Polyak / TSJ+18 framework for SCRN. Nothing is fitted to reproduce the 1/epsilon^2 or 1/epsilon^2.5 rates: T, n1, n2, eta, r, nu, and M are chosen as explicit functions of rho, sigma_2, L_G, L_H, and epsilon, and the high-probability and expectation bounds are proved from those choices. There is no parameter fitted to a subset of data and then renamed as a prediction. The self-citations are auxiliary. Lemma A.18 [SBG19] supplies a concentration inequality for products of sub-Gaussian and sub-exponential random variables; Lemma B.5 [RBGM19] states variance and moment bounds for averaged Hessian estimators that follow from Assumption 2.6 and i.i.d. sampling. Neither lemma restates the paper's theorems, and neither is used to define the oracle complexity claims. The paper's own Remark 6 and Section 5 explicitly flag the absence of a Hessian-level interpolation assumption and the resulting SCRN gap to the deterministic rate, which is the opposite of concealing a circular dependence. The concern that SGC may fail at strict saddles under mere over-parametrization is an assumption-validity or modelling question, not a circularity, because the paper does not derive SGC from the escape-rate conclusions it uses SGC to prove.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No constants are fitted to data; the problem constants rho, L, and sigma are assumed inputs. The paper introduces no new particles, forces, or parameters. The largest burden is the SGC assumption, which is strong enough to imply that every stationary point of the expected loss is also a stationary point of almost every sample loss.

assumptions (4)

domain assumption Smoothness: F and f have L-Lipschitz values, L_G-Lipschitz gradients, and L_H-Lipschitz Hessians (Assumptions 2.1-2.3).
Standard regularity needed for descent and saddle-escape arguments; accepted as the problem class.
domain assumption Strong Growth Condition (Assumption 2.4): E_xi||grad F(x,xi)||^2 <= rho ||grad f(x)||^2 for all x.
Load-bearing interpolation model; forces stochastic gradient noise to vanish at stationary points. Stronger than mere zero training loss at a global minimizer.
domain assumption Light-tail deviations (Assumption 3.1): stochastic gradients have sub-Gaussian tails, used to obtain high-probability bounds in Theorem 3.1.
Common in stochastic optimization; needed for high-probability concentration of accumulated noise.
domain assumption Oracle assumptions: unbiased estimators with bounded fourth moments (Assumptions 2.5-2.6).
Standard for zeroth-order and Hessian estimators.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Escaping Saddle-Points Faster under Interpolation-like Conditions." pith.science (2026). https://pith.science/paper/RJD6P2XN

@misc{pith2026200913016,
  author       = {Pith},
  title        = {Pith review of: Escaping Saddle-Points Faster under Interpolation-like Conditions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RJD6P2XN}},
  note         = {Machine review of arXiv:2009.13016}
}

abstract

In this paper, we show that under over-parametrization several standard stochastic optimization algorithms escape saddle-points and converge to local-minimizers much faster. One of the fundamental aspects of over-parametrized models is that they are capable of interpolating the training data. We show that, under interpolation-like assumptions satisfied by the stochastic gradients in an over-parametrization setting, the first-order oracle complexity of Perturbed Stochastic Gradient Descent (PSGD) algorithm to reach an $\epsilon$-local-minimizer, matches the corresponding deterministic rate of $\tilde{\mathcal{O}}(1/\epsilon^{2})$. We next analyze Stochastic Cubic-Regularized Newton (SCRN) algorithm under interpolation-like conditions, and show that the oracle complexity to reach an $\epsilon$-local-minimizer under interpolation-like conditions, is $\tilde{\mathcal{O}}(1/\epsilon^{2.5})$. While this obtained complexity is better than the corresponding complexity of either PSGD, or SCRN without interpolation-like assumptions, it does not match the rate of $\tilde{\mathcal{O}}(1/\epsilon^{1.5})$ corresponding to deterministic Cubic-Regularized Newton method. It seems further Hessian-based interpolation-like assumptions are necessary to bridge this gap. We also discuss the corresponding improved complexities in the zeroth-order settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 50 canonical work pages

[1]

1, 8194--8244

Zeyuan Allen-Zhu, Katyusha: The first direct acceleration of stochastic gradient methods, The Journal of Machine Learning Research 18 (2017), no. 1, 8194--8244

work page 2017
[2]

3716--3726

Zeyuan Allen-Zhu and Yuanzhi Li, Neon2: Finding local minima via first-order oracles, Advances in Neural Information Processing Systems, 2018, pp. 3716--3726

work page 2018
[3]

242--252

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

work page 2019
[4]

Qinbo Bai, Mridul Agarwal, and Vaneet Aggarwal, Escaping saddle points for zeroth-order non-convex optimization using estimated gradient descent, 2020 54th Annual Conference on Information Sciences and Systems (CISS), IEEE, 2020, pp. 1--6

work page 2020
[5]

Raef Bassily, Mikhail Belkin, and Siyuan Ma, On exponential convergence of sgd in non-convex over-parametrized learning, arXiv preprint arXiv:1811.02564 (2018)

work page Pith review arXiv 2018
[6]

Krishnakumar Balasubramanian and Saeed Ghadimi, Zeroth-order nonconvex stochastic optimization: Handling constraints, high-dimensionality and saddle-points, arXiv preprint arXiv:1809.06474 (2018)

work page Pith review arXiv 2018
[7]

3036--3046

Lenaic Chizat and Francis Bach, On the global convergence of gradient descent for over-parameterized models using optimal transport, Advances in neural information processing systems, 2018, pp. 3036--3046

work page 2018
[8]

Yair Carmon and John C Duchi, Gradient descent efficiently finds the cubic-regularized non-convex newton step, arXiv preprint arXiv:1612.00547 (2016)

work page Pith review arXiv 2016

Show all 52 references

[9]

part II : worst-case function-and derivative-evaluation complexity , Mathematical programming 130 (2011), no

Coralia Cartis, Nicholas IM Gould, and Philippe L Toint, Adaptive cubic regularisation methods for unconstrained optimization. part II : worst-case function-and derivative-evaluation complexity , Mathematical programming 130 (2011), no. 2, 295--319

2011
[10]

2937--2947

Lenaic Chizat, Edouard Oyallon, and Francis Bach, On lazy training in differentiable programming, Advances in Neural Information Processing Systems, 2019, pp. 2937--2947

2019
[11]

1-2, 1--32

Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi, A trust region algorithm with a worst-case iteration complexity of ^ -3/2 for nonconvex optimization , Mathematical Programming 162 (2017), no. 1-2, 1--32

2017
[12]

1753--1763

Aaron Defazio and L \'e on Bottou, On the ineffectiveness of variance reduced optimization for deep learning, Advances in Neural Information Processing Systems, 2019, pp. 1753--1763

2019
[13]

1067--1077

Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos, Gradient descent can take exponential time to escape saddle points, Advances in neural information processing systems, 2017, pp. 1067--1077

2017
[14]

1675--1685

Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai, Gradient descent finds global minima of deep neural networks, International Conference on Machine Learning, 2019, pp. 1675--1685

2019
[15]

2933--2941

Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio, Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, Advances in neural information processing systems, 2014, pp. 2933--2941

2014
[16]

689--699

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, 2018, pp. 689--699

2018
[17]

1192--1234

Cong Fang, Zhouchen Lin, and Tong Zhang, Sharp analysis for nonconvex sgd escaping from saddle points, Conference on Learning Theory, 2019, pp. 1192--1234

2019
[18]

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Georgios Piliouras, Efficiently avoiding saddle points with zero order methods: No gradients required, arXiv preprint arXiv:1910.13021 (2019)

2019 arXiv
[19]

797--842

Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points: online stochastic gradient for tensor decomposition, Conference on Learning Theory, 2015, pp. 797--842

2015
[20]

4, 2341--2368

Saeed Ghadimi and Guanghui Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic programming, SIAM Journal on Optimization 23 (2013), no. 4, 2341--2368

2013
[21]

Benjamin D Haeffele and Ren \'e Vidal, Global optimality in tensor factorization, deep learning, and beyond, arXiv preprint arXiv:1506.07540 (2015)

2015 arXiv
[22]

2007--2015

Benjamin Haeffele, Eric Young, and Rene Vidal, Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing, International conference on machine learning, 2014, pp. 2007--2015

2014
[23]

8571--8580

Arthur Jacot, Franck Gabriel, and Cl \'e ment Hongler, Neural tangent kernel: Convergence and generalization in neural networks, Advances in neural information processing systems, 2018, pp. 8571--8580

2018
[24]

org, 2017, pp

Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan, How to escape saddle points efficiently, Proceedings of the 34th International Conference on Machine Learning-Volume 70, JMLR. org, 2017, pp. 1724--1732

2017
[25]

Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan, On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points, arXiv preprint arXiv:1902.04811 (2019)

2019 arXiv
[26]

1042--1085

Chi Jin, Praneeth Netrapalli, and Michael I Jordan, Accelerated gradient descent escapes saddle points faster than gradient descent, Conference On Learning Theory, 2018, pp. 1042--1085

2018
[27]

586--594

Kenji Kawaguchi, Deep learning without poor local minima, Advances in neural information processing systems, 2016, pp. 586--594

2016
[28]

853--863

Kenji Kawaguchi and Leslie Kaelbling, Elimination of all bad local minima in deep learning, International Conference on Artificial Intelligence and Statistics, 2020, pp. 853--863

2020
[29]

Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Benjamin Recht, First-order methods almost always avoid saddle points, arXiv preprint arXiv:1710.07406 (2017)

2017 arXiv
[30]

Songtao Lu, Meisam Razaviyayn, Bo Yang, Kejun Huang, and Mingyi Hong, Snap: Finding approximate second-order stationary solutions efficiently for non-convex linearly constrained problems, arXiv preprint arXiv:1907.04450 (2019)

2019 arXiv
[31]

1246--1257

Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht, Gradient descent only converges to minimizers, Conference on learning theory, 2016, pp. 1246--1257

2016
[32]

5356--5360

Songtao Lu, Ziping Zhao, Kejun Huang, and Mingyi Hong, Perturbed projected gradient descent converges to approximate second-order points for bound constrained nonconvex problems, ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)...

2019
[33]

3325--3334

Siyuan Ma, Raef Bassily, and Mikhail Belkin, The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning, International Conference on Machine Learning, 2018, pp. 3325--3334

2018
[34]

3629--3639

Aryan Mokhtari, Asuman Ozdaglar, and Ali Jadbabaie, Escaping saddle points in constrained optimization, Advances in Neural Information Processing Systems, 2018, pp. 3629--3639

2018
[35]

Si Yi Meng, Sharan Vaswani, Issam Laradji, Mark Schmidt, and Simon Lacoste-Julien, Fast and furious convergence: Stochastic second order methods under interpolation, arXiv preprint arXiv:1910.04920 (2020)

2020 arXiv
[36]

Quynh Nguyen and Matthias Hein, The loss surface of deep and wide neural networks, arXiv preprint arXiv:1704.08045 (2017)

2017 arXiv
[37]

1, 177--205

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

2006
[38]

Maher Nouiehed and Meisam Razaviyayn, A trust region method for finding second-order stationarity in linearly constrained non-convex optimization, arXiv preprint arXiv:1904.06784 (2019)

2019 arXiv
[39]

2, 527--566

Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions, Foundations of Computational Mathematics 17 (2017), no. 2, 527--566

2017
[40]

1017--1025

Deanna Needell, Rachel Ward, and Nati Srebro, Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm, Advances in neural information processing systems, 2014, pp. 1017--1025

2014
[41]

4, 643--653

Boris Teodorovich Polyak, Gradient methods for minimizing functionals, Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki 3 (1963), no. 4, 643--653

1963
[42]

Abhishek Roy, Krishnakumar Balasubramanian, Saeed Ghadimi, and Prasant Mohapatra, Multi-point bandit algorithms for nonstationary online nonconvex optimization, arXiv preprint arXiv:1907.13616 (2019)

2019 arXiv
[43]

Lingqing Shen, Krishnakumar Balasubramanian, and Saeed Ghadimi, Non-asymptotic results for langevin monte carlo: Coordinate-wise and black-box sampling, arXiv preprint arXiv:1902.01373 (2019)

2019 arXiv
[44]

Mark Schmidt, Faster algorithms for deep learning? (presentation in vector institute: https://www.cs.ubc.ca/ schmidtm/documents/2020\_vector\_smallresidual.pdf), 2020

2020
[45]

Ruoyu Sun, Optimization for deep learning: theory and algorithms, arXiv preprint arXiv:1912.08957 (2019)

2019 arXiv
[46]

Thomas Strohmer and Roman Vershynin, A randomized kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications 15 (2009), no. 2, 262

2009
[47]

2899--2908

Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I Jordan, Stochastic cubic regularization for fast nonconvex optimization, Advances in neural information processing systems, 2018, pp. 2899--2908

2018
[48]

Sharan Vaswani, Francis Bach, and Mark Schmidt, Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron, arXiv preprint arXiv:1810.07288 (2018)

2018 arXiv
[49]

Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan, Stochastic variance-reduced cubic regularization for nonconvex optimization, arXiv preprint arXiv:1802.07372 (2018)

2018 arXiv
[50]

3, 467--492

Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu, Gradient descent optimizes over-parameterized deep relu networks, Machine Learning 109 (2020), no. 3, 467--492

2020
[51]

Dongruo Zhou and Quanquan Gu, Stochastic recursive variance-reduced cubic regularization methods, arXiv preprint arXiv:1901.11518 (2019)

2019 arXiv
[52]

Junyu Zhang, Lin Xiao, and Shuzhong Zhang, Adaptive stochastic variance reduction for subsampled newton method with cubic regularization, arXiv preprint arXiv:1811.11637 (2018)

2018 arXiv

Pith tools

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

[1] [1]

1, 8194--8244

Zeyuan Allen-Zhu, Katyusha: The first direct acceleration of stochastic gradient methods, The Journal of Machine Learning Research 18 (2017), no. 1, 8194--8244

work page 2017

[2] [2]

3716--3726

Zeyuan Allen-Zhu and Yuanzhi Li, Neon2: Finding local minima via first-order oracles, Advances in Neural Information Processing Systems, 2018, pp. 3716--3726

work page 2018

[3] [3]

242--252

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

work page 2019

[4] [4]

Qinbo Bai, Mridul Agarwal, and Vaneet Aggarwal, Escaping saddle points for zeroth-order non-convex optimization using estimated gradient descent, 2020 54th Annual Conference on Information Sciences and Systems (CISS), IEEE, 2020, pp. 1--6

work page 2020

[5] [5]

Raef Bassily, Mikhail Belkin, and Siyuan Ma, On exponential convergence of sgd in non-convex over-parametrized learning, arXiv preprint arXiv:1811.02564 (2018)

work page Pith review arXiv 2018

[6] [6]

Krishnakumar Balasubramanian and Saeed Ghadimi, Zeroth-order nonconvex stochastic optimization: Handling constraints, high-dimensionality and saddle-points, arXiv preprint arXiv:1809.06474 (2018)

work page Pith review arXiv 2018

[7] [7]

3036--3046

Lenaic Chizat and Francis Bach, On the global convergence of gradient descent for over-parameterized models using optimal transport, Advances in neural information processing systems, 2018, pp. 3036--3046

work page 2018

[8] [8]

Yair Carmon and John C Duchi, Gradient descent efficiently finds the cubic-regularized non-convex newton step, arXiv preprint arXiv:1612.00547 (2016)

work page Pith review arXiv 2016