High-order methods beyond the classical complexity bounds: inexact high-order proximal-point methods.

Area of Science:

• Optimization Theory
• Convex Analysis
• Numerical Analysis

Background:

• Minimizing sums of convex functions is a fundamental problem in optimization.
• Existing methods may lack efficiency for complex objective functions.
• High-order methods offer potential for faster convergence but can be computationally intensive.

Purpose of the Study:

• Introduce a flexible Bi-level Optimization (BiOPT) framework.
• Develop an accelerated inexact high-order proximal-point method.
• Achieve a 2q-order method with a convergence rate of O(1/k^2q) for specific problems.

Main Methods:

• Regularizing the objective with a pth-order proximal term.
• Designing a generic inexact pth-order proximal-point scheme with acceleration.
• Solving the auxiliary problem using lower-level non-Euclidean methods, including composite gradient schemes.
• Employing the estimating sequence technique for acceleration.

Main Results:

• The BiOPT framework allows flexibility in choosing the proximal term order (p) and lower-level solvers.
• An accelerated inexact pth-order proximal-point method is developed for the upper level.
• Combining the accelerated upper-level method with a non-Euclidean composite gradient scheme for the lower level yields a 2q-order method.
• The derived convergence rate is O(1/k^2q), offering superfast convergence for certain problem classes.

Conclusions:

• The BiOPT framework provides a versatile and efficient approach to convex optimization.
• The proposed method achieves a high order of convergence, outperforming existing techniques for specific problems.
• This research opens avenues for developing faster optimization algorithms in various scientific domains.