ItsOPT: An Inexact Two-Level Smoothing Framework for Nonconvex Optimization via High-Order Moreau Envelope

Abstract. This paper introduces ItsOPT, an 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 [Formula: see text] of the original cost, setting the regularization order [Formula: see text] 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.