# High-order methods beyond the classical complexity bounds, II: inexact high-order proximal-point methods with segment search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2021.

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

- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)

## Abstract (arXiv)

A bi-level optimization framework (BiOPT) was proposed in [3] for convex composite optimization, which is a generalization of bi-level unconstrained minimization framework (BLUM) given in [20]. In this continuation paper, we introduce a pth-order proximal-point segment search operator which is used to develop novel accelerated methods. Our first algorithm combines the exact element of this operator with the estimating sequence technique to derive new iteration points, which are shown to attain the convergence rate O(k-(3p+1)/2), for the iteration counter k. We next consider inexact elements of the high-order proximal-point segment search operator to be employed in the BiOPT framework. We particularly apply the accelerated high-order proximal-point method at the upper level, while we find approximate solutions of the proximal-point segment search auxiliary problem by a combination of non-Euclidean composite gradient and bisection methods. For q=lfloor p/2 rfloor, this amounts to a 2qth-order method with the convergence rate O(k-(6q+1)/2) (the same as the optimal bound of 2qth-order methods) for even p (p=2q) and the superfast convergence rate O(k-(3q+1)) for odd p (p=2q+1).