# High-order methods beyond the classical complexity bounds, I: inexact high-order proximal-point methods

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

## Key facts

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

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

- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [The Hidden Cost of Approximation in Online Mirror Descent](https://mlsanity.com/paper/2511.22283/) (2025)
- [Beyond Conventional Federated Learning via High-Order Regularization](https://mlsanity.com/paper/2609.09904/) (2026)

## Abstract (arXiv)

In this paper, we introduce a textitBi-level OPTimization (BiOPT) framework for minimizing the sum of two convex functions, where both can be nonsmooth. The BiOPT framework involves two levels of methodologies. At the upper level of BiOPT, we first regularize the objective by a (p+1)th-order proximal term and then develop the generic inexact high-order proximal-point scheme and its acceleration using the standard estimation sequence technique. At the lower level, we solve the corresponding pth-order proximal auxiliary problem inexactly either by one iteration of the pth-order tensor method or by a lower-order non-Euclidean composite gradient scheme with the complexity O(log tfrac1varepsilon), for the accuracy parameter varepsilon>0. Ultimately, if the accelerated proximal-point method is applied at the upper level, and the auxiliary problem is handled by a non-Euclidean composite gradient scheme, then we end up with a 2q-order method with the convergence rate O(k-(p+1)), for q=lfloor p/2 rfloor, where k is the iteration counter.