Efficiency of minimizing compositions of convex functions and smooth maps

DOI10.1007/s10107-018-1311-3zbMath1431.90111arXiv1605.00125OpenAlexW2963534244WikidataQ129506423 ScholiaQ129506423MaRDI QIDQ2330660

Dmitriy Drusvyatskiy, Courtney Paquette

Publication date: 22 October 2019

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

complexitysmoothingaccelerationincremental methodsGauss-Newtonfast gradient methodsinexactnesscomposite minimizationprox-gradient

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)

Related Items (42)

A Unified Analysis of Descent Sequences in Weakly Convex Optimization, Including Convergence Rates for Bundle Methods ⋮ Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization ⋮ Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning ⋮ Proximal methods avoid active strict saddles of weakly convex functions ⋮ Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints ⋮ Accelerated inexact composite gradient methods for nonconvex spectral optimization problems ⋮ Global convergence of model function based Bregman proximal minimization algorithms ⋮ Graphical Convergence of Subgradients in Nonconvex Optimization and Learning ⋮ An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems ⋮ A Zeroth-Order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization ⋮ Learning with risks based on M-location ⋮ The multiproximal linearization method for convex composite problems ⋮ Linearly-convergent FISTA variant for composite optimization with duality ⋮ Stochastic Gauss-Newton algorithms for online PCA ⋮ Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates ⋮ Unnamed Item ⋮ Efficiency of higher-order algorithms for minimizing composite functions ⋮ Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems ⋮ Consistent approximations in composite optimization ⋮ Average curvature FISTA for nonconvex smooth composite optimization problems ⋮ Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems ⋮ Majorization-minimization-based Levenberg-Marquardt method for constrained nonlinear least squares ⋮ Relax-and-split method for nonconvex inverse problems ⋮ Variable smoothing for convex optimization problems using stochastic gradients ⋮ Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria ⋮ An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems ⋮ An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems ⋮ Variable smoothing for weakly convex composite functions ⋮ A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems ⋮ Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods ⋮ Strong Metric (Sub)regularity of Karush–Kuhn–Tucker Mappings for Piecewise Linear-Quadratic Convex-Composite Optimization and the Quadratic Convergence of Newton’s Method ⋮ An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization ⋮ A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs ⋮ Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence ⋮ Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs ⋮ Efficiency of minimizing compositions of convex functions and smooth maps ⋮ Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods ⋮ Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization ⋮ Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems ⋮ Distributed Stochastic Inertial-Accelerated Methods with Delayed Derivatives for Nonconvex Problems ⋮ High-Order Optimization Methods for Fully Composite Problems ⋮ A Study of Convex Convex-Composite Functions via Infimal Convolution with Applications

Uses Software

• KNITRO
• NESUN

Cites Work

• Smooth minimization of non-smooth functions
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• A proximal method for composite minimization
• Gradient methods for minimizing composite functions
• First-order methods of smooth convex optimization with inexact oracle
• Universal gradient methods for convex optimization problems
• Introductory lectures on convex optimization. A basic course.
• Generalized Kalman smoothing: modeling and algorithms
• The value function approach to convergence analysis in composite optimization
• A Gauss-Newton method for convex composite optimization
• Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
• Efficiency of minimizing compositions of convex functions and smooth maps
• Techniques of variational analysis
• Majorization-Minimization Procedures and Convergence of SQP Methods for Semi-Algebraic and Tame Programs
• Accelerated and Inexact Forward-Backward Algorithms
• Iterative Reweighted Linear Least Squares for Exact Penalty Subproblems on Product Sets
• On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming
• The Mathematical Structure of Huber’s M-Estimator
• Convergence of an Inexact Algorithm for Composite Nonsmooth Optimization
• Introduction to Derivative-Free Optimization
• On the global convergence of trust region algorithms for unconstrained minimization
• On the superlinear convergence of a trust region algorithm for nonsmooth optimization
• Descent methods for composite nondifferentiable optimization problems
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• Numerical methods for the nonlinear robust regression problem
• A model algorithm for composite nondifferentiable optimization problems
• The Minimum Sum of Absolute Errors Regression: A State of the Art Survey
• Nonlinear programming via an exact penalty function: Global analysis
• An Exact Penalization Viewpoint of Constrained Optimization
• Variational Analysis
• The Linear l₁ Estimator and the Huber M-Estimator
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Exact Penalty Functions in Constrained Optimization
• Prox-regular functions in variational analysis
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
• Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
• Modified Gauss–Newton scheme with worst case guarantees for global performance
• Convex Analysis
• A method for the solution of certain non-linear problems in least squares
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficiency of minimizing compositions of convex functions and smooth maps