Research map / Optimization / Nonconvex and smooth optimization
Balancing Gradient and Hessian Queries in Non-Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a gradient/Hessian query trade-off for finding epsilon-critical points of functions with Lipschitz gradient and Hessian, using approximate Hessians with a carefully designed spectral-reweighting norm and restarts.
Problem
Computing an epsilon-critical point (small gradient norm) of a non-convex twice-differentiable function with Lipschitz Hessian, when gradient and (approximate) Hessian queries both have cost, and the trade-off between their counts.
Approach
Runs accelerated gradient descent in a norm induced by a spectrally reweighted approximate Hessian (phi applied to eigenvalues, with spectral gaps), combined with negative curvature descent, lazy Hessian recomputation via restarts, and a reduction removing the L1 smoothness dependence with one extra Hessian query.
Key results
- Achieves O~(L2^{1/4} n_H^{-1/2} Delta eps^{-9/4}) gradient queries with n_H Hessian queries (up to log factors), interpolating between gradient-only and Hessian-heavy regimes.
- With a single Hessian query, gradient complexity O~(L2^{3/4} Delta^{3/2} eps^{-9/4}), improving prior single-Hessian results by roughly Delta^{1/2} L2^{1/4} eps^{-3/4}.
- Dimension-dependent corollary gives O~(d^{1/3} L2^{1/2} Delta eps^{-3/2} + d) gradient queries, improving on Doikov et al. for d >= 7 (up to log factors).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed dimension-dependent method instead of the Doikov et al. bound | Critical point computation with bounded dimension d · Critical point computation, bounded dimension d | gradient queries: O(\sqrt{dL_2}Δε^{-3/2}+d) -> \tilde{O}(d^{1/3}L_2^{1/2}Δε^{-3/2}+d) | Helped |
| Use one exact Hessian query with the proposed method instead of the prior Doikov et al. bound | Critical point computation with unbounded smoothness · Critical point computation, single Hessian query | gradient queries: O(Δ^{2} L_2ε^{-3}) -> \tilde{O}(Δ^{3/2} L_2^{3/4}ε^{-9/4}) | Helped |
| Use the proposed dimension-dependent method instead of the Li & Lin bound | Critical point computation with bounded dimension d · Critical point computation, bounded dimension d | gradient queries: O(L_1^{1/2}L_2^{1/4}Δ ε^{-7/4}) -> \tilde{O}(d^{1/3}L_2^{1/2}Δε^{-3/2}+d) | Helped |
Limitations
- Purely theoretical; no implementation or experiments.
- Polylogarithmic factors, some of which depend on L1 and are only removed with one extra Hessian query.
- Tightness of the d^{1/3} dependence and the overall trade-off is unknown.
Experimental setup
Metrics: gradient oracle query complexity Hessian oracle query count
Baselines: Li and Lin O(L1^{1/2} L2^{1/4} Delta eps^{-7/4}) Doikov et al. O(sqrt(d L2) Delta eps^{-3/2} + d) Nesterov and Polyak Jiang et al. O(d^{1/4} L1^{1/4} L2^{3/8} Delta eps^{-13/8}) Vavasis
Builds on: Carmon et al. accelerated gradient with restarts for non-convex optimization Nesterov and Polyak cubic regularization Doikov et al. Hessian-based methods Li and Lin accelerated gradient for critical points
Closest papers by meaning
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.87)
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.87)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.87)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.87)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.87)
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.