Efficiency of higher-order algorithms for minimizing composite functions

DOI10.1007/S10589-023-00533-9arXiv2203.13367MaRDI QIDQ6155068FDOQ6155068

Authors: Yassine Nabou, Ion Necoara 

Publication date: 16 February 2024

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: Composite minimization involves a collection of functions which are aggregated in a nonsmooth manner. It covers, as a particular case, optimization problems with functional constraints, minimization of max-type functions, and simple composite minimization problems, where the objective function has a nonsmooth component. We design a higher-order majorization algorithmic framework for fully composite problems (possibly nonconvex). Our framework replaces each component with a higher-order surrogate such that the corresponding error function has a higher-order Lipschitz continuous derivative. We present convergence guarantees for our method for composite optimization problems with (non)convex and (non)smooth objective function. In particular, we prove stationary point convergence guarantees for general nonconvex (possibly nonsmooth) problems and under Kurdyka-Lojasiewicz (KL) property of the objective function we derive improved rates depending on the KL parameter. For convex (possibly nonsmooth) problems we also provide sublinear convergence rates.

Full work available at URL: https://arxiv.org/abs/2203.13367

Recommendations

• High-order optimization methods for fully composite problems
• Convergence analysis of stochastic higher-order majorization–minimization algorithms
• Efficiency of minimizing compositions of convex functions and smooth maps
• Local properties of algorithms for minimizing nonsmooth composite functions
• The evaluation complexity of finding high-order minimizers of nonconvex optimization

zbMATH Keywords

convergence rateshigher-order methodscomposite optimizationKurdyka-Lojasiewicz property(non)convex minimization

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Testing Unconstrained Optimization Software
• Title not available (Why is that?)
• Smooth minimization of non-smooth functions
• Gradient methods for minimizing composite functions
• Incremental majorization-minimization optimization with application to large-scale machine learning
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Clarke Subgradients of Stratifiable Functions
• Conditions for convergence of trust region algorithms for nonsmooth optimization
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Majorizing Functions and Convergence of the Gauss–Newton Method for Convex Composite Optimization
• Cubic regularization of Newton method and its global performance
• Title not available (Why is that?)
• A model algorithm for composite nondifferentiable optimization problems
• Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
• Linear convergence of first order methods for non-strongly convex optimization
• A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
• Convergence and evaluation-complexity analysis of a regularized tensor-Newton method for solving nonlinear least-squares problems
• Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives
• The multiproximal linearization method for convex composite problems
• The value function approach to convergence analysis in composite optimization
• Efficiency of minimizing compositions of convex functions and smooth maps
• Implementable tensor methods in unconstrained convex optimization
• On the use of third-order models with fourth-order regularization for unconstrained optimization
• Inexact basic tensor methods for some classes of convex optimization problems
• High-order optimization methods for fully composite problems

Cited In (1)

• Convergence analysis of stochastic higher-order majorization–minimization algorithms

This page was built for publication: Efficiency of higher-order algorithms for minimizing composite functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155068)