Inexact successive quadratic approximation for regularized optimization
From MaRDI portal
Abstract: Successive quadratic approximations, or second-order proximal methods, are useful for minimizing functions that are a sum of a smooth part and a convex, possibly nonsmooth part that promotes regularization. Most analyses of iteration complexity focus on the special case of proximal gradient method, or accelerated variants thereof. There have been only a few studies of methods that use a second-order approximation to the smooth part, due in part to the difficulty of obtaining closed-form solutions to the subproblems at each iteration. In fact, iterative algorithms may need to be used to find inexact solutions to these subproblems. In this work, we present global analysis of the iteration complexity of inexact successive quadratic approximation methods, showing that an inexact solution of the subproblem that is within a fixed multiplicative precision of optimality suffices to guarantee the same order of convergence rate as the exact version, with complexity related in an intuitive way to the measure of inexactness. Our result allows flexible choices of the second-order term, including Newton and quasi-Newton choices, and does not necessarily require increasing precision of the subproblem solution on later iterations. For problems exhibiting a property related to strong convexity, the algorithms converge at global linear rates. For general convex problems, the convergence rate is linear in early stages, while the overall rate is . For nonconvex problems, a first-order optimality criterion converges to zero at a rate of .
Recommendations
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- An inexact successive quadratic approximation method for L-1 regularized optimization
- Practical inexact proximal quasi-Newton method with global complexity analysis
- Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
Cites work
- A coordinate gradient descent method for nonsmooth separable minimization
- A general distributed dual coordinate optimization framework for regularized loss minimization
- A Limited Memory Algorithm for Bound Constrained Optimization
- Accelerated and inexact forward-backward algorithms
- An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP
- An inexact proximal path-following algorithm for constrained convex minimization
- An inexact successive quadratic approximation method for L-1 regularized optimization
- Catalyst acceleration for first-order convex optimization: from theory to practice
- Computing a Trust Region Step
- Convergence properties of trust region methods for linear and convex constraints
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- Duality between subgradient and conditional gradient methods
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Global Convergence of a Class of Trust Region Algorithms for Optimization with Simple Bounds
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 1243473 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Inexact proximal Newton methods for self-concordant functions
- Introductory lectures on convex optimization. A basic course.
- Linear convergence of first order methods for non-strongly convex optimization
- Newton's Method for Large Bound-Constrained Optimization Problems
- On the convergence of a linesearch based proximal-gradient method for nonconvex optimization
- On the global convergence of the BFGS method for nonconvex unconstrained optimization problems
- On the limited memory BFGS method for large scale optimization
- Practical inexact proximal quasi-Newton method with global complexity analysis
- Proximal Newton-type methods for minimizing composite functions
- Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates
- Signal Recovery by Proximal Forward-Backward Splitting
- Sparse Reconstruction by Separable Approximation
- Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
- Variable metric inexact line-search-based methods for nonsmooth optimization
Cited in
(37)- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates
- Inexact variable metric stochastic block-coordinate descent for regularized optimization
- Globalized inexact proximal Newton-type methods for nonconvex composite functions
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- Second order semi-smooth proximal Newton methods in Hilbert spaces
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- New convergence results for the inexact variable metric forward-backward method
- A globally convergent proximal Newton-type method in nonsmooth convex optimization
- An inexact successive quadratic approximation method for L-1 regularized optimization
- Practical inexact proximal quasi-Newton method with global complexity analysis
- Convergence of inexact forward-backward algorithms using the forward-backward envelope
- Inexact proximal stochastic second-order methods for nonconvex composite optimization
- scientific article; zbMATH DE number 7306888 (Why is no real title available?)
- On an iteratively reweighted linesearch based algorithm for nonconvex composite optimization
- Inexact proximal DC Newton-type method for nonconvex composite functions
- Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
- Minimizing oracle-structured composite functions
- Inexact proximal Newton methods in Hilbert spaces
- Analysis of a variable metric block coordinate method under proximal errors
- A new proximal heavy ball inexact line-search algorithm
- A VMiPG method for composite optimization with nonsmooth term having no closed-form proximal mapping
- Barzilai–Borwein-like rules in proximal gradient schemes for ℓ 1 -regularized problems
- A proximal-gradient method for problems with overlapping group-sparse regularization: support identification complexity
- An inexact regularized proximal Newton method without line search
- On global solvability of a class of possibly nonconvex QCQP problems in Hilbert spaces
- A proximal stochastic quasi-Newton algorithm with dynamical sampling and stochastic line search
- A proximal-gradient method for equality constrained optimization
- Fractional standalone backstepping control for nonlinear continuous stirred tank reactor
- A four-operator splitting algorithm for nonconvex and nonsmooth optimization
- An inexact variable metric variant of incremental aggregated Forward-Backward method for the large-scale composite optimization problem
- A nested primal-dual iterated Tikhonov method for regularized convex optimization
- A preconditioned version of a nested primal-dual algorithm for image deblurring
- An inexact proximal Newton method for nonconvex composite minimization
- A linesearch-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
- Multilevel Preconditioning Strategies for Convex Optimization Methods in Image Deblurring
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
This page was built for publication: Inexact successive quadratic approximation for regularized optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419525)
