# Higher-Order Newton Methods with Polynomial Work per Iteration

arXiv: https://arxiv.org/abs/2311.06374 · HTML: https://mlsanity.com/paper/2311.06374/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 10 Nov 2023.

## Builds on (most cited first, 18 of 18)

- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization](https://mlsanity.com/paper/1706.02586/) (2017)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics](https://mlsanity.com/paper/1908.05209/) (2019)
- [Lower Bounds for Higher-Order Convex Optimization](https://mlsanity.com/paper/1710.10329/) (2017)
- [An Optimal High-Order Tensor Method for Convex Optimization](https://mlsanity.com/paper/1812.06557/) (2018)
- [On the complexity of finding a local minimizer of a quadratic function over a polytope](https://mlsanity.com/paper/2008.05558/) (2020)
- [DC Decomposition of Nonconvex Polynomials with Algebraic Techniques](https://mlsanity.com/paper/1510.01518/) (2015)
- [Local convergence of tensor methods](https://mlsanity.com/paper/1912.02516/) (2019)
- [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints](https://mlsanity.com/paper/1811.01220/) (2018)
- [Universal regularization methods - varying the power, the smoothness and the accuracy](https://mlsanity.com/paper/1811.07057/) (2018)
- [Complexity aspects of local minima and related notions](https://mlsanity.com/paper/2008.06148/) (2020)
- [A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization](https://mlsanity.com/paper/1811.02427/) (2018)
- [Sums of Separable and Quadratic Polynomials](https://mlsanity.com/paper/2105.04766/) (2021)
- [Third-Order Newton Methods with Semidefinite Programming](https://mlsanity.com/paper/2209.10051/) (2022)
- [Tensor Methods for Finding Approximate Stationary Points of Convex Functions](https://mlsanity.com/paper/1907.07053/) (2019)
- [Second-order methods for quartically-regularised cubic polynomials, with applications to high-order tensor methods](https://mlsanity.com/paper/2308.15336/) (2023)

## Built on by (most cited first, 3 of 3)

- [SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers](https://mlsanity.com/paper/2502.20545/) (2025)
- [Non-Euclidean High-Order Smooth Convex Optimization](https://mlsanity.com/paper/2411.08987/) (2024)
- [On Approximate Computation of Critical Points](https://mlsanity.com/paper/2601.21917/) (2026)

## Abstract (arXiv)

We present generalizations of Newton's method that incorporate derivatives of an arbitrary order d but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our dth-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the dth-order Taylor expansion of the function we wish to minimize. We prove that our dth-order method has local convergence of order d. This results in lower oracle complexity compared to the classical Newton method. We show on numerical examples that basins of attraction around local minima can get larger as d increases. Under additional assumptions, we present a modified algorithm, again with polynomial cost per iteration, which is globally convergent and has local convergence of order d.