Pith. sign in

REVIEW 2 major objections 4 minor 57 references

Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A two-step method using negative curvature directions reaches second-order stationary points even when gradients and Hessians are only noisy estimates.

desk verdict Solid extension of Curtis-Robinson to inexact oracles, with a genuinely new stochastic theorem that rests on a Hessian condition so strong it becomes exact at degenerate points. read the letter →

arxiv 2411.10378 v1 pith:JF4RSQXU submitted 2024-11-15 math.OC

Albert S. Berahas , Raghu Bollapragada , Wanping Dong This is my paper · ORCID
classification math.OC MSC 90C2690C3090C1590C53
keywords nonconvexoptimizationnegativecurvaturesecond-orderstationarypointsadaptivesamplingstochasticNewton-CGinexactHessianlinesearch
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

Unconstrained nonconvex optimization problems whose gradients and Hessians are only available as noisy or sampled estimates are common in machine learning, yet most stochastic methods can only promise first-order stationarity. This paper claims that a two-step update, one step along a direction of negative curvature and one descent step, restores second-order guarantees in both a deterministic-inexact and a stochastic setting. Under accuracy conditions that tie the approximate-Hessian error to the true smallest eigenvalue, the iterates converge to points where the gradient vanishes and the Hessian is positive semidefinite, with iteration complexity $O(\epsilon_g^{-2}+\epsilon_H^{-3})$. The paper also designs a practical matrix-free Newton-CG variant with adaptive sample sizes, negative-curvature detection inside CG iterations, and a backtracking line search, and reports experiments on two nonconvex regression problems.

What carries the argument

The load-bearing object is the negative-curvature direction $q_k$, computed from the approximate Hessian $H_k$; it must satisfy $q_k^T H_k q_k \le \gamma \lambda_k \|q_k\|_2^2$ with $\lambda_k$ the leftmost eigenvalue of $H_k$ and $\|q_k\|_2=\delta|\lambda_k|$, and its sign is chosen so that the final direction $p_k$ is also a descent direction for the approximate gradient. The analysis needs the Hessian approximation to be accurate only along this direction, not in full norm, so the negative-curvature step guarantees a model decrease proportional to $|\lambda_{\min,k}^-|^3$ while the descent step contributes decrease proportional to $\|\nabla f(\hat{x}_k)\|_2^2$. Summing these two decrease mechanisms yields the convergence and complexity theorems; in the stochastic setting the same mechanism is packaged into the expectation inequality of Lemma 3.8, whose two extra error terms determine whether second-order convergence survives.

What would settle it

On a function with a known saddle whose Hessian has smallest eigenvalue $-\delta$ for a tunable small $\delta$, run the stochastic algorithm from a start near the saddle and record whether the iterates reach a point with $E\|\nabla f(x_k)\|$ small and $E\lambda_{\min}(\nabla^2 f(x_k)) \ge -\epsilon_H$; the central claim fails if a non-vanishing fraction of runs stalls with $\lambda_{\min}$ below $-\epsilon_H$, or if the sample size needed to satisfy the Hessian accuracy condition grows without bound as $\delta \to 0$. One can also compute the left-hand side and right-hand side of Condition 3.3 on the actual computed directions to check the assumption directly.

Watch

Extended reading notes

Core claim

The central claim is that the two-step descent-plus-negative-curvature framework extends to inexact deterministic and stochastic settings without losing its second-order convergence order. In the deterministic setting (Theorem 2.10), if the approximate Hessian $H_k$ satisfies the directional error bound $\|(H_k-\nabla^2 f(x_k))p_k\|_2 \le \gamma_H |\lambda_k^-| \|p_k\|_2$ and the eigenvalue-gap bound $|\lambda_k^- - \lambda_{\min,k}^-| \le \gamma_\lambda |\lambda_k^-|$, then choosing constant step sizes $\alpha \le (1-\hat\theta)^2/(L_g(1+\hat\theta))$ and $\beta \le (\gamma-\gamma_H)/(\delta L_H)$ makes the iterates either stop at a second-order stationary point or satisfy $\lim_k \|\nabla f(x_k)\|_2=0$ and $\liminf_k \lambda_{\min}(\nabla^2 f(x_k)) \ge 0$. In the stochastic setting with vanishing variance and constant step size, Theorem 3.12 gives the same conclusion in expectation, while with constant variance and diminishing step size Theorem 3.10 only gives $\liminf_k E[\|\nabla f(x_k)\|_2]=0$. The accompanying corollaries bound the number of iterations needed to reach gradient test $\epsilon_g$ and curvature test $\epsilon_H$ by $O(\epsilon_g^{-2})$ and $O(\epsilon_H^{-3})$, respectively.

Load-bearing premise

The load-bearing premise is that the approximate Hessian is accurate along the negative-curvature direction and in its leftmost eigenvalue, with both errors bounded by a fixed multiple of the true most-negative eigenvalue magnitude, which vanishes near second-order stationary points and therefore demands near-exact Hessian information exactly where the stopping decision is hardest.

Editorial extensions

If this is right

  • In the deterministic inexact setting, second-order convergence holds under constant step sizes, with the same $O(\epsilon_g^{-2}+\epsilon_H^{-3})$ iteration complexity as exact-information two-step methods.
  • In the stochastic setting with diminishing variance and constant step size, the expected gradient norm converges to zero and the expected minimum eigenvalue is asymptotically nonnegative, matching the deterministic complexity order in expectation.
  • With constant variance and diminishing step sizes, only first-order convergence is claimed; the paper does not assert second-order convergence in this regime.
  • The practical algorithm computes steps with conjugate-gradient iterations that detect negative curvature for free, uses adaptive sample sizes for gradient and Hessian, and sets step sizes by a backtracking line search, so no explicit Hessian or eigendecomposition is required.
  • Numerical comparisons against a stochastic-gradient adaptive-sampling method, a full-batch Newton-CG method, and a trust-region variant indicate that negative curvature and adaptive sampling reduce total function, gradient, and Hessian evaluations on the tested regression problems.

Reading between the lines

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

  • Because the analysis controls Hessian error only along the negative-curvature direction rather than in full norm, a natural extension is a Hessian sample-size rule that estimates accuracy along the current most-negative eigen-direction instead of the full matrix; the paper does not test this cheaper rule.
  • The theory's right-hand sides use the exact eigenvalue magnitude $|\lambda_{\min}^-|$, which the algorithm cannot observe; a practical certification would need a confidence interval for the smallest eigenvalue of the true Hessian, a gap the paper leaves open.
  • As $\lambda_{\min}^- \to 0$ the guaranteed decrease from a negative-curvature step is cubic in this small number, so near a nearly flat saddle the descent step carries the convergence burden; this suggests the adaptive-precision policy could stop growing the Hessian sample size once the negative-curvature contribution is negligible.
  • The $O(\epsilon_H^{-3})$ negative-curvature rate is the same order as in exact-information analysis, but faster subspace or accelerated methods might reduce it; testing that would require a different proof and is not addressed here.
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

2 major / 4 minor

Summary. The paper studies unconstrained nonconvex optimization with inexact gradient and Hessian information. It proposes a two-step algorithmic framework: a negative curvature step followed by a descent step, analyzed first with deterministic bounded errors and then with stochastic approximations. In the deterministic setting, Theorem 2.10 proves convergence to a second-order stationary point under Conditions 2.3, 2.5, and 2.7 with constant step sizes satisfying (2.8), and Corollary 2.11 gives an O(epsilon_g^{-2} + epsilon_H^{-3}) iteration complexity. In the stochastic setting, Lemma 3.8 provides an expected descent inequality, Theorem 3.10 gives a first-order convergence result under diminishing step sizes and constant variance, and Theorem 3.12 gives an expected second-order convergence result under constant step sizes and diminishing variance. Section 4 develops a practical algorithm, NCAS, combining adaptive sampling, CG with negative curvature detection, and a backtracking line search; Section 5 reports numerical comparisons on two nonconvex machine learning problems.

Significance. The deterministic part of the paper is a solid, clean extension of the two-step negative curvature framework to explicit inexact oracle conditions; the proofs are not circular and the complexity claims match known rates. The practical algorithm is sensible and the numerical study is reasonably thorough. However, the stochastic second-order guarantee rests on a Hessian accuracy condition that finite-sample subsampled Hessians cannot satisfy at exactly the degenerate points the theorem is meant to describe, and the practical algorithm is not shown to enforce the theoretical conditions. Thus Theorem 3.12 is best read as a conditional result for an oracle that is effectively exact near second-order stationary points, and the gap between theory and Algorithm 4.2 is substantial.

major comments (2)
  1. [Section 3.1, Condition 3.4; Theorem 3.12] At any iterate with lambda^-_min,k = 0, Condition 3.4 reduces to E_k[|lambda^-_k|] <= 0, so lambda^-_k = 0 almost surely. For a finite-sample subsampled Hessian H_k = (1/b_H) sum_i nabla^2 F(x_k, xi_i), this requires the random matrix to have no negative eigenvalue almost surely whenever the true Hessian is positive semidefinite. If the per-sample Hessians have negative curvature along any null-space direction of nabla^2 f(x_k), a finite subsample has positive probability of producing a negative smallest eigenvalue. Therefore Condition 3.4 is not satisfiable by finite-sample Hessians at exactly the second-order stationary points that Theorem 3.12 is intended to characterize. Moreover, near such points, with per-sample curvature variance sigma^2, the condition forces the Hessian sample size to grow at least on the order of sigma^2/(gamma_lambda^2 |lambda^-_min,k|^2), which diverges as lambda^-_min,k tends to zero. The deterministic analogue, Condition 2.5, has the same collapse at lambda^-_min,k = 0. This is load-bearing because the central stochastic second-order convergence claim depends on a Hessian oracle that becomes exact in the degenerate regime.
  2. [Section 4.1, Eqs. (4.3)-(4.4); Algorithm 4.2] The practical algorithm is not connected to the theoretical Conditions 3.3 and 3.4. The adaptive sampling rules (4.5)-(4.9) are designed to enforce (4.3)-(4.4), which control the gradient variance and the Hessian error only along the computed CG step d_k. They do not control the leftmost-eigenvalue gap E[|lambda^-_k - lambda^-_min,k|] appearing in (3.4) nor the Hessian error along the negative curvature direction q_k appearing in (3.3). Algorithm 4.2 never computes lambda_k or checks either condition, and the capped growth rate zeta described in Remark 4.1 explicitly forbids the unbounded sample-size growth that (3.4) demands near degenerate points. Consequently Theorem 3.12 does not apply to Algorithm 4.2, and the numerical results in Section 5, while informative, do not validate the stochastic convergence theorem.
minor comments (4)
  1. [Theorem 3.12] The hypotheses set hat_theta_k = hat_theta as a constant, but the proof writes hat_theta_k in the line involving (1 + L_g alpha (1 + hat_theta_k)); the notation should be unified. The summability hypotheses are imposed on sigma_k^2 and hat_sigma_k^2, not on hat_theta_k^2.
  2. [Corollary 3.14] In the proof of Corollary 3.14, the implications following the definitions of G(epsilon_g) and H(epsilon_H) mix indices k and k-1 for sigma_k, and the expression '1/4 C beta^2 epsilon_H^3' uses an undefined constant C; the argument is recoverable but should be rewritten for precision.
  3. [Section 4.1] The theoretical conditions (4.3)-(4.4) are stated with a sequence theta_k, while Algorithm 4.2 uses a single fixed theta; please clarify whether the analysis of the practical sampling tests is intended for a fixed or a varying accuracy parameter.
  4. [Section 5] The numerical experiments appear to report single runs; since SGAS, TRAS, and NCAS are stochastic methods, averaging over several random seeds would strengthen the claims of robustness and efficiency.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the convergence theorems are self-contained from explicit oracle conditions; only non-load-bearing self-citations appear.

full rationale

The central second-order convergence statements (Theorem 2.10 and Theorem 3.12, with Corollaries 2.11 and 3.14) are derived in the paper from explicit assumptions: smoothness and boundedness (Assumption 2.2), oracle conditions on the gradient and Hessian approximations and on the search directions (Conditions 2.3, 2.5, 2.7 and their stochastic counterparts 3.1, 3.3, 3.5), and step-size bounds. The proofs are self-contained Taylor-expansion descent arguments; they do not invoke any of the authors' prior convergence results as a premise. The Hessian accuracy conditions (2.5), (3.3), and (3.4) are strong; for example, at a point with λmin(∇2f(xk)) = 0, condition (3.4) forces λ^-_k = 0 almost surely. That makes the conditions demanding for finite-sample Hessians, but it does not make the theorem self-fulfilling. The practical Algorithm 4.2 uses sample-variance tests (4.5)-(4.9) and capped growth that are not proven to enforce those theoretical conditions, and its numerical results are reported as experiments; this is a proof gap rather than a circular reduction. The paper cites its authors' prior work [4]-[6], [9], [11], [15] for adaptive-sampling and line-search components, but those citations are motivational or support heuristics and do not carry the convergence proof. Score 2 reflects the presence of several self-citations, none load-bearing, not a genuinely circular argument.

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

The theoretical claims rest on standard smoothness assumptions plus strong oracle accuracy conditions that involve unknown true quantities (e.g., lambda_min^-). The practical algorithm depends on user-chosen hyperparameters and a heuristic sample-variance test. No fitted constants are used to manufacture the convergence results.

free parameters (5)
  • theta (adaptive sampling accuracy) = 0.9 (default in experiments)
    User-chosen accuracy parameter controlling the targeted gradient/Hessian sample variance; not fitted to data. It acts as a free parameter in the practical algorithm, though not in the convergence theory.
  • zeta (sample size increase cap) = 2 (default)
    User-chosen cap on how fast sample sizes grow; prevents runaway batch sizes. Not fitted.
  • epsilon_H (eigenvalue accuracy) = 1e-3 (default)
    Threshold for declaring negative curvature and for Hessian correction in CG. Sensitive in experiments: 1e-1 slows convergence.
  • epsilon_CG (CG residual tolerance) = 1e-6
    Stopping tolerance for the CG subroutine.
  • N_CG (max CG iterations) = 10
    Cap on CG iterations per outer step; N_CG=0 or 1 degrades performance as shown in Figure 1c.
assumptions (5)
  • domain assumption Assumption 2.2: f is twice continuously differentiable with L_g-Lipschitz gradients, L_H-Lipschitz Hessians, and bounded below.
    Standard smoothness assumption invoked throughout Sections 2 and 3.
  • domain assumption Deterministic oracle conditions 2.3, 2.5, 2.7: gradient error along the negative curvature direction is bounded relative to the approximate sign, Hessian error along the direction is bounded by gamma_H|lambda_k^-|, and the gradient norm error at x_hat satisfies a norm condition.
    These conditions define the deterministic inexactness model; they are strong and depend on unknown true quantities.
  • domain assumption Stochastic oracle conditions 3.1, 3.3, 3.5: unbiased gradient estimates, variance bounds with possibly diminishing sigma and theta_hat, and Hessian/eigenvalue accuracy in expectation relative to exact lambda_min^-
    Used to derive Lemma 3.8 and Theorems 3.10/3.12. Condition 3.3 uses exact lambda_min^- on the right, which is unverifiable in practice.
  • domain assumption Existence of a negative curvature vector q_k satisfying (2.2) with norm delta|lambda_k| and curvature ratio gamma, computed by a matrix-free method such as Lanczos or CG detection.
    The analysis assumes such a vector is available whenever lambda_k<0; practical methods only approximate this.
  • ad hoc to paper Sample variance tests (4.5)-(4.9) approximate the true variance conditions (4.3)-(4.4) and yield accurate gradient/Hessian estimates for Algorithm 4.2
    The practical algorithm relies on this heuristic; no convergence proof is given for Algorithm 4.2 and the approximation is not rigorously justified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm." pith.science (2026). https://pith.science/paper/JF4RSQXU

@misc{pith2026241110378,
  author       = {Pith},
  title        = {Pith review of: Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JF4RSQXU}},
  note         = {Machine review of arXiv:2411.10378}
}
read the original abstract

In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic and stochastic inexact settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees for both settings. To tackle large-scale problems, we develop a practical variant that utilizes the conjugate gradient method with negative curvature detection and early stopping to compute a step, a simple adaptive step size scheme, and a strategy for selecting the sample sizes of the gradient and Hessian approximations as the optimization progresses. Numerical results on two machine learning problems showcase the efficacy and efficiency of the practical method.

Figures

Figures reproduced from arXiv: 2411.10378 by the authors.

Figure 1
Figure 1. Sensitivity analysis of NCAS (Algorithm 4.2) on robust regression problem (australian dataset) with respect to the parameters associated with the CG subroutine (ϵH, ϵCG, and NCG) in terms of total evaluations. Algorithm 4.2 show significant slow-down, e.g., ϵH = 10−1 or NCG = 0, 1. The reason for this is that in the former setting, the Hessian approximations are perturbed too much and useful second-order information… view at source ↗
Figure 2
Figure 2. Sensitivity analysis of NCAS (Algorithm 4.2) on robust regression problem (australian dataset) with respect to the parameters associated with the adaptive sam￾pling scheme (θ, and ζ) in terms of total evaluations. 5.3 Comparative Analysis In this subsection, we compare the performance of NCAS with the methods described in Section 5.1 on the robust regression (Figures 3 and 4) and the Tukey Biweight (Figures 5 and 6)… view at source ↗
Figure 3
Figure 3. Performance of SGAS, NC, TRAS, and NCAS on robust regression problem (australian dataset) in terms of gradient norm, minimum eigenvalue, sample size, and step size/trust region radius. First row iterations; Second row total evaluations. 1 2 3 Total Evaluations #107 10-10 10-5 100 G r a die n t N o r m SGAS NC TRAS NCAS 105 Total Evaluations -0.01 -0.005 0 Minim u m Eig e n v alu e SGAS NC TRAS NCAS 105 Total Evaluat… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Performance of SGAS, NC, TRAS, and NCAS on robust regression problem in terms of gradient norm, minimum eigenvalue, sample size, and step size/trust region radius with respect to total evaluations. First row mushroom dataset; Second row splice dataset. 32 [PITH_FULL_I…
Figure 5
Figure 5. Figure 5: Performance of SGAS, NC, TRAS, and NCAS on Tukey Biweight problem (australian dataset) in terms of gradient norm, minimum eigenvalue, sample size, and step size/trust region radius. First row iterations; Second row total evaluations. Next, we illustrate the performance…
Figure 6
Figure 6. Figure 6: Performance of SGAS, NC, TRAS, and NCAS on Tukey Biweight problem in terms of gradient norm, minimum eigenvalue, sample size, and step size/trust region radius with respect to total evaluations. First row mushroom dataset; Second row splice dataset. 33 [PITH_FULL_IMAG…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 43 canonical work pages

  1. [1]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems

    Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences , 2(1):183–202, 2009

    2009

  2. [2]

    Adaptive Regularization for Nonconvex Optimization Using Inexact Function Values and Randomly Perturbed Derivatives

    Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, and Ph L Toint. High-order evaluation complexity of a stochastic adaptive regularization algorithm for nonconvex optimization using inexact function evaluations and randomly perturbed derivatives. arXiv preprint arXiv:2005.04639 , 2020

    work page Pith review arXiv 2005

  3. [3]

    Topology optimization: theory, methods, and applications

    Martin Philip Bendsoe and Ole Sigmund. Topology optimization: theory, methods, and applications. Springer Science & Business Media, 2013

    work page 2013

  4. [4]

    An investigation of newton-sketch and subsampled newton methods

    Albert S Berahas, Raghu Bollapragada, and Jorge Nocedal. An investigation of newton-sketch and subsampled newton methods. Optimization Methods and Software, 35(4):661–680, 2020

    work page 2020

  5. [5]

    An adaptive sampling sequential quadratic programming method for equality constrained stochastic opti- mization

    Albert S Berahas, Raghu Bollapragada, and Baoyu Zhou. An adaptive sampling sequential quadratic programming method for equality constrained stochastic opti- mization. arXiv preprint arXiv:2206.00712 , 2022

    arXiv 2022

  6. [6]

    Global convergence rate anal- ysis of a generic line search algorithm with noise

    Albert S Berahas, Liyuan Cao, and Katya Scheinberg. Global convergence rate anal- ysis of a generic line search algorithm with noise. SIAM Journal on Optimization , 31(2):1489–1518, 2021

    work page 2021

  7. [7]

    Nonlinear programming

    Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334–334, 1997

    work page 1997

  8. [8]

    Nonlinear programming: concepts, algorithms, and applications to chemical processes

    Lorenz T Biegler. Nonlinear programming: concepts, algorithms, and applications to chemical processes. SIAM, 2010

    2010

Show all 57 references
  1. [9]

    Adaptive sampling strategies for stochastic optimization

    Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Adaptive sampling strategies for stochastic optimization. SIAM Journal on Optimization , 28(4):3312–3343, 2018

    2018

  2. [10]

    Exact and inexact subsam- pled newton methods for optimization.IMA Journal of Numerical Analysis, 39(2):545– 578, 2019

    Raghu Bollapragada, Richard H Byrd, and Jorge Nocedal. Exact and inexact subsam- pled newton methods for optimization.IMA Journal of Numerical Analysis, 39(2):545– 578, 2019

    2019

  3. [11]

    A progressive batching l-bfgs method for machine learning

    Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching l-bfgs method for machine learning. In International Conference on Machine Learning , pages 620–629. PMLR, 2018

    2018

  4. [12]

    Optimization methods for large- scale machine learning

    L´ eon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large- scale machine learning. SIAM review, 60(2):223–311, 2018. 35

    2018

  5. [13]

    On the use of stochastic hessian information in unconstrained optimization

    R Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic hessian information in unconstrained optimization. SIAM Journal on Optimization , 21(3):977–995, 2011

    2011

  6. [14]

    Sample size se- lection in optimization methods for machine learning

    Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size se- lection in optimization methods for machine learning. Mathematical programming, 134(1):127–155, 2012

    2012

  7. [15]

    First-and second-order high probability complexity bounds for trust-region methods with noisy oracles

    Liyuan Cao, Albert S Berahas, and Katya Scheinberg. First-and second-order high probability complexity bounds for trust-region methods with noisy oracles. Mathe- matical Programming, 207(1):55–106, 2024

    2024

  8. [16]

    Accelerated methods for nonconvex optimization

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization , 28(2):1751–1772, 2018

    2018

  9. [17]

    On the global convergence of trust region algorithms using inexact gradient information

    Richard G Carter. On the global convergence of trust region algorithms using inexact gradient information. SIAM Journal on Numerical Analysis , 28(1):251–265, 1991

    1991

  10. [18]

    Global convergence rate analysis of uncon- strained optimization methods based on probabilistic models

    Coralia Cartis and Katya Scheinberg. Global convergence rate analysis of uncon- strained optimization methods based on probabilistic models. Mathematical Program- ming, 169:337–375, 2018

    2018

  11. [19]

    A nonlinear conjugate gradi- ent method with complexity guarantees and its application to nonconvex regression

    R´ emi Chan-Renous-Legoubin and Cl´ ement W Royer. A nonlinear conjugate gradi- ent method with complexity guarantees and its application to nonconvex regression. EURO Journal on Computational Optimization , 10:100044, 2022

    2022

  12. [20]

    Libsvm: a library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST) , 2(3):1–27, 2011

    2011

  13. [21]

    Exploiting negative curvature in deterministic and stochastic optimization

    Frank E Curtis and Daniel P Robinson. Exploiting negative curvature in deterministic and stochastic optimization. Mathematical Programming, 176(1):69–94, 2019

    2019

  14. [22]

    Trust- region newton-cg with strong second-order complexity guarantees for nonconvex opti- mization

    Frank E Curtis, Daniel P Robinson, Cl´ ement W Royer, and Stephen J Wright. Trust- region newton-cg with strong second-order complexity guarantees for nonconvex opti- mization. SIAM Journal on Optimization , 31(1):518–544, 2021

    2021

  15. [23]

    Optimization of energy systems

    Ibrahim Dincer, Marc A Rosen, and Pouria Ahmadi. Optimization of energy systems . John Wiley & Sons, 2017

    2017

  16. [24]

    Gradient descent can take exponential time to escape saddle points

    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 , 30, 2017

    2017

  17. [25]

    A modified newton method for mini- mization

    Roger Fletcher and Thomas Leonard Freeman. A modified newton method for mini- mization. Journal of Optimization Theory and Applications , 23:357–372, 1977. 36

    1977

  18. [26]

    Computing modified newton di- rections using a partial cholesky factorization

    Anders Forsgren, Philip E Gill, and Walter Murray. Computing modified newton di- rections using a partial cholesky factorization. SIAM Journal on Scientific Computing , 16(1):139–150, 1995

    1995

  19. [27]

    Hybrid deterministic-stochastic methods for data fitting

    Michael P Friedlander and Mark Schmidt. Hybrid deterministic-stochastic methods for data fitting. SIAM Journal on Scientific Computing , 34(3):A1380–A1405, 2012

    2012

  20. [28]

    Curvilinear path steplength algorithms for minimization which use directions of negative curvature

    Donald Goldfarb. Curvilinear path steplength algorithms for minimization which use directions of negative curvature. Mathematical programming, 18(1):31–40, 1980

    1980

  21. [29]

    Deep learning

    Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016

    2016

  22. [30]

    Complexity of zeroth-and first- order stochastic trust-region algorithms

    Yunsoo Ha, Sara Shashaani, and Raghu Pasupathy. Complexity of zeroth-and first- order stochastic trust-region algorithms. arXiv preprint arXiv:2405.20116 , 2024

    2024 arXiv

  23. [31]

    Adaptive filter theory

    Simon S Haykin. Adaptive filter theory . Pearson Education India, 2002

    2002

  24. [32]

    Methods of conjugate gradients for solving linear systems , volume 49

    Magnus Rudolph Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems , volume 49. NBS Washington, DC, 1952

    1952

  25. [33]

    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

  26. [34]

    Principal component analysis for special types of data

    Ian T Jolliffe. Principal component analysis for special types of data . Springer, 2002

    2002

  27. [35]

    An iteration method for the solution of the eigenvalue problem of linear differential and integral operators

    C Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of National Bureau of Standard , 45:255– 282, 1950

    1950

  28. [36]

    Planning algorithms

    Steven M LaValle. Planning algorithms . Cambridge university press, 2006

    2006

  29. [37]

    Gen- eration of whole-body optimal dynamic multi-contact motions

    S´ ebastien Lengagne, Joris Vaillant, Eiichi Yoshida, and Abderrahmane Kheddar. Gen- eration of whole-body optimal dynamic multi-contact motions. The International Journal of Robotics Research, 32(9-10):1104–1119, 2013

    2013

  30. [38]

    A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees.arXiv preprint arXiv:2310.18841, 2023

    Shuyao Li and Stephen J Wright. A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees.arXiv preprint arXiv:2310.18841, 2023

    2023 arXiv

  31. [39]

    Adaptive negative curvature descent with applications in non-convex optimization

    Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang. Adaptive negative curvature descent with applications in non-convex optimization. Advances in Neural Information Processing Systems, 31, 2018

    2018

  32. [40]

    On noisy negative curvature descent: Competing with gradient descent for faster non-convex optimization

    Mingrui Liu and Tianbao Yang. On noisy negative curvature descent: Competing with gradient descent for faster non-convex optimization. arXiv preprint arXiv:1709.08571, 2017. 37

    2017 arXiv

  33. [41]

    Statistical consistency and asymptotic normality for high-dimensional robust m-estimators

    Po-Ling Loh. Statistical consistency and asymptotic normality for high-dimensional robust m-estimators. The Annals of Statistics , 45(2):866, 2017

    2017

  34. [42]

    Deep learning via hessian-free optimization

    James Martens. Deep learning via hessian-free optimization. In Proceedings of the 27th International Conference on International Conference on Machine Learning , pages 735–742, 2010

    2010

  35. [43]

    On the use of directions of negative curvature in a modified newton method

    Jorge J Mor´ e and Danny C Sorensen. On the use of directions of negative curvature in a modified newton method. Mathematical Programming, 16:1–20, 1979

    1979

  36. [44]

    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. Mathematical Programming, 39:117–129, 1987

    1987

  37. [45]

    Numerical optimization

    Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999

    1999

  38. [46]

    Quadratic programming with one negative eigenvalue is np-hard

    Panos M Pardalos and Stephen A Vavasis. Quadratic programming with one negative eigenvalue is np-hard. Journal of Global optimization , 1(1):15–22, 1991

    1991

  39. [47]

    Digital signal processing: principles, algorithms, and applications, 4/E

    John G Proakis. Digital signal processing: principles, algorithms, and applications, 4/E. Pearson Education India, 2007

    2007

  40. [48]

    Engineering optimization: theory and practice

    Singiresu S Rao. Engineering optimization: theory and practice . John Wiley & Sons, 2019

    2019

  41. [49]

    A generic approach for escaping saddle points

    Sashank Reddi, Manzil Zaheer, Suvrit Sra, Barnabas Poczos, Francis Bach, Ruslan Salakhutdinov, and Alex Smola. A generic approach for escaping saddle points. In In- ternational conference on artificial intelligence and statistics, pages 1233–1242. PMLR, 2018

    2018

  42. [50]

    A newton-cg algorithm with complexity guarantees for smooth unconstrained optimization

    Cl´ ement W Royer, Michael O’Neill, and Stephen J Wright. A newton-cg algorithm with complexity guarantees for smooth unconstrained optimization. Mathematical Programming, 180:451–488, 2020

    2020

  43. [51]

    Complexity analysis of second-order line- search algorithms for smooth nonconvex optimization.SIAM Journal on Optimization, 28(2):1448–1477, 2018

    Cl´ ement W Royer and Stephen J Wright. Complexity analysis of second-order line- search algorithms for smooth nonconvex optimization.SIAM Journal on Optimization, 28(2):1448–1477, 2018

    2018

  44. [52]

    Chemical process: design and integration

    Robin Smith. Chemical process: design and integration . John Wiley & Sons, 2005

    2005

  45. [53]

    The conjugate gradient method and trust regions in large scale optimization

    Trond Steihaug. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis , 20(3):626–637, 1983

    1983

  46. [54]

    John Wiley & Sons, 2013

    Allen J Wood, Bruce F Wollenberg, and Gerald B Shebl´ e.Power generation, operation, and control. John Wiley & Sons, 2013. 38

    2013

  47. [55]

    Newton-type methods for non- convex optimization under inexact Hessian information

    Peng Xu, Fred Roosta, and Michael W Mahoney. Newton-type methods for non- convex optimization under inexact Hessian information. Mathematical Programming, 184(1):35–70, 2020

    2020

  48. [56]

    Robust linear regression: A review and comparison

    Chun Yu and Weixin Yao. Robust linear regression: A review and comparison. Com- munications in Statistics-Simulation and Computation , 46(8):6261–6282, 2017

    2017

  49. [57]

    From symmetry to geometry: Tractable nonconvex problems

    Yuqian Zhang, Qing Qu, and John Wright. From symmetry to geometry: Tractable nonconvex problems. arXiv preprint arXiv:2007.06753 , 2020. 39

    2007 arXiv

Pith tools

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