Efficiency of higher-order algorithms for minimizing composite functions

Composite minimization involves a collection of functions which areaggregated in a nonsmooth manner. It covers, as a particular case, smoothapproximation of minimax games, minimization of max-type functions, and simplecomposite minimization problems, where the objective function has a nonsmoothcomponent. We design a higher-order majorization algorithmic framework forfully composite problems (possibly nonconvex). Our framework replaces eachcomponent with a higher-order surrogate such that the corresponding errorfunction has a higher-order Lipschitz continuous derivative. We presentconvergence guarantees for our method for composite optimization problems with(non)convex and (non)smooth objective function. In particular, we provestationary point convergence guarantees for general nonconvex (possiblynonsmooth) problems and under Kurdyka-Lojasiewicz (KL) property of theobjective function we derive improved rates depending on the KL parameter. Forconvex (possibly nonsmooth) problems we also provide sublinear convergencerates.