High-order methods beyond the classical complexity bounds: inexact high-order proximal-point methods
提出一个双层优化框架，通过高阶近端项和加速技术，实现比经典方法更快的收敛速度，适用于求解两个凸函数之和的最小化问题。
Abstract We introduce a Bi-level OPTimization (BiOPT) framework for minimizing the sum of two convex functions, where one of them is smooth enough. The BiOPT framework offers three levels of freedom: (i) choosing the order p of the proximal term; (ii) designing an inexact p th-order proximal-point method in the upper level; (iii) solving the auxiliary problem with a lower-level non-Euclidean method in the lower level. We here regularize the objective by a $$(p+1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> th-order proximal term (for arbitrary integer $$p\ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> ) and then develop the generic inexact high-order proximal-point scheme and its acceleration using the standard estimating sequence technique at the upper level. This follows at the lower level with solving the corresponding p th-order proximal auxiliary problem inexactly either by one iteration of the p th-order tensor method or by a lower-order non-Euclidean composite gradient scheme. Ultimately, it is shown that applying the accelerated inexact p th-order proximal-point method at the upper level and handling the auxiliary problem by the non-Euclidean composite gradient scheme lead to a 2 q -order method with the convergence rate $${\mathcal {O}}(k^{-(p+1)})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> (for $$q=\lfloor p/2\rfloor $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>=</mml:mo> <mml:mo>⌊</mml:mo> <mml:mi>p</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>⌋</mml:mo> </mml:mrow> </mml:math> and the iteration counter k ), which can result to a superfast method for some specific class of problems.