Inexact Two-Level Smoothing Framework for Nonconvex Optimization: Algorithms and Analysis

We introduce an inexact two-level optimization framework (ItsOPT) for finding first- or second-order critical points of nonsmooth and nonconvex functions. The framework includes two levels: In the upper level, a smoothing technique (e.g., High-order Moreau envelope, high-order forward-backward envelope, high-order tensor envelope) will be applied to generate a smooth approximation of the objective function with the same minimizers. Then, first- or second-order methods will be introduced for minimizing the smoothing function. In the lower level, the corresponding high-order proximal subproblems (e.g., High-order proximal, forward-backward, and tensor subproblems) will be solved inexactly using subgradient or Bregman proximal methods. This will provide an approximate solution for the subproblems, leading to inexact smoothing information for the upper-level methods. We note that the complexity of solving the considered optimization problems is the multiplication of the complexities of both levels. Applying accelerated first- or second-order methods at the upper level and solving the subproblems with negligible complexity (e.g., logarithmic rate) may lead to the superfast methods attaining complexity better than worst-case complexity bounds. We finally introduce some algorithms and report preliminary numerical results.

Join at imt.lu/conference