ItsOPT: An inexact two-level smoothing framework for nonconvex optimization via high-order Moreau envelope

This paper introduces ItsOPT, an {\it inexact two-level smoothing optimization framework} designed to find first-order critical points of nonsmooth and nonconvex functions.

The framework consists of two levels of methodologies: at the upper level, a zeroth-, first-, or second-order method can be tailored to minimize a smooth approximation; at the lower level, the high-order proximal auxiliary problems are solved inexactly, generating an inexact oracle for the smooth function.

As a smoothing technique, we introduce the high-order Moreau envelope (HOME) and study its fundamental properties under standard assumptions.

Next, by combining a boosted high-order proximal-point algorithm (Boosted HiPPA) at the upper level with the inexact oracle from the lower level, we obtain a zeroth-order instance of ItsOPT.

Global convergence rates are established under the Kurdyka-Łojasiewicz (KL) property of the cost and envelope functions, together with reasonable conditions on the accuracy of the proximal terms.

Surprisingly, for any KL exponent $\theta\in (0,1)$ of the original cost, setting the regularization order $p=\frac{1}{1-\theta}$ ensures that Boosted HiPPA converges linearly to a proximal fixed point.

This is the first algorithm with this property for KL functions.

Preliminary numerical experiments on a robust low-rank matrix recovery problem demonstrate the promising performance of the proposed algorithm, supporting our theoretical foundations.