mlsanityData to 7 Oct 2026

Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

arXiv 1705.07260 ↗First posted 20 May 2017math.OCcited by 23

Not on the map. Why?

Abstract (arXiv)

Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we prove tight bounds on the oracle complexity of such methods for smooth convex functions, or equivalently, the worst-case number of iterations required to optimize such functions to a given accuracy. In particular, these bounds indicate when such methods can or cannot improve on gradient-based methods, whose oracle complexity is much better understood. We also provide generalizations of our results to higher-order methods.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 3; 2024: 4; 2025: 3; 2026: 3.

23 papers.

Sort:

  1. 2024Challenges in Training PINNs: A Loss Landscape Perspectivecited by 109
  2. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  3. 2021Regularized Newton Method with Global O(1/k2) Convergencecited by 22
  4. 2022Super-Universal Regularized Newton Methodcited by 20
  5. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 19
  6. 2022Generalized Optimistic Methods for Convex-Concave Saddle Point Problemscited by 15
  7. 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
  8. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  9. 2024Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimizationcited by 8
  10. 2023Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Methodcited by 7
  11. 2021Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothnesscited by 6
  12. 2023First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessianscited by 6
11 more
  1. 2022Perseus: A Simple and Optimal High-Order Method for Variational Inequalitiescited by 5
  2. 2021Understanding Riemannian Acceleration via a Proximal Extragradient Frameworkcited by 3
  3. 2024Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexitycited by 3
  4. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  5. 2023A Hybrid Framework of Reinforcement Learning and Convex Optimization for UAV-Based Autonomous Metaverse Data Collectioncited by 2
  6. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  7. 2024Faster Acceleration for Steepest Descentcited by 1
  8. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  9. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 0
  10. 2026Primal Acceleration of Newton's Methodcited by 0
  11. 2026Optimal High-Order Methods for Solving Monotone Variational Inequalitiescited by 0