Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
From MaRDI portal
Abstract: For regularized optimization that minimizes the sum of a smooth term and a regularizer that promotes structured solutions, inexact proximal-Newton-type methods, or successive quadratic approximation (SQA) methods, are widely used for their superlinear convergence in terms of iterations. However, unlike the counter parts in smooth optimization, they suffer from lengthy running time in solving regularized subproblems because even approximate solutions cannot be computed easily, so their empirical time cost is not as impressive. In this work, we first show that for partly smooth regularizers, although general inexact solutions cannot identify the active manifold that makes the objective function smooth, approximate solutions generated by commonly-used subproblem solvers will identify this manifold, even with arbitrarily low solution precision. We then utilize this property to propose an improved SQA method, ISQA+, that switches to efficient smooth optimization methods after this manifold is identified. We show that for a wide class of degenerate solutions, ISQA+ possesses superlinear convergence not just only in iterations, but also in running time because the cost per iteration is bounded. In particular, our superlinear convergence result holds on problems satisfying a sharpness condition more general than that in existing literature. Experiments on real-world problems also confirm that ISQA+ greatly improves the state of the art for regularized optimization.
Recommendations
- Inexact successive quadratic approximation for regularized optimization
- 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
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- Newton acceleration on manifolds identified by proximal gradient methods
Cites work
- A \(\mathcal{VU}\)-algorithm for convex minimization
- A Broyden class of quasi-Newton methods for Riemannian optimization
- A coordinate gradient descent method for nonsmooth separable minimization
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- A proximal stochastic gradient method with progressive variance reduction
- Accelerated block-coordinate relaxation for regularized optimization
- Active Sets, Nonsmoothness, and Sensitivity
- Activity identification and local linear convergence of forward-backward-type methods
- An improved GLMNET for L1-regularized logistic regression
- An inexact successive quadratic approximation method for L-1 regularized optimization
- Convergence of inexact forward-backward algorithms using the forward-backward envelope
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Exact matrix completion via convex optimization
- Forward-backward quasi-Newton methods for nonsmooth optimization problems
- From error bounds to the complexity of first-order descent methods for convex functions
- Functions and sets of smooth substructure: relationships and examples
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 3857873 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 2155014 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- Identifying active manifolds in regularization problems
- Inexact proximal Newton methods for self-concordant functions
- Inexact successive quadratic approximation for regularized optimization
- Lectures on convex optimization
- Manifold identification in dual averaging for regularized stochastic online learning
- Newton methods for nonsmooth convex minimization: connections among \(\mathcal U\)-Lagrangian, Riemannian Newton and SQP methods
- On \(\mathcal{VU}\)-theory for functions with primal-dual gradient structure
- On gradients of functions definable in o-minimal structures
- On the convergence of a linesearch based proximal-gradient method for nonconvex optimization
- Partial Smoothness, Tilt Stability, and Generalized Hessians
- Practical inexact proximal quasi-Newton method with global complexity analysis
- Primal-Dual Gradient Structured Functions: Second-Order Results; Links to Epi-Derivatives and Partly Smooth Functions
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximal Newton-type methods for minimizing composite functions
- Sparse Reconstruction by Separable Approximation
- Stable signal recovery from incomplete and inaccurate measurements
- The 𝒰-Lagrangian of a convex function
- Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
- Variational Analysis
- Weak Sharp Minima in Mathematical Programming
Cited in
(7)- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- Inexact successive quadratic approximation for regularized optimization
- Global convergence and acceleration of projection methods for feasibility problems involving union convex sets
- Sampling-based methods for multi-block optimization problems over transport polytopes
- An inexact proximal Newton method for nonconvex composite minimization
- A normal map-based proximal stochastic gradient method: convergence and identification properties
This page was built for publication: Accelerating inexact successive quadratic approximation for regularized optimization through manifold identification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165598)
