High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
From MaRDI portal
(Redirected from Publication:2020600)
Abstract: This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a -th order Taylor model and show that the algorithm can produce an (epsilon,delta)-approximate q-th-order stationary point in at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of the objective function and its first p derivatives (whenever they exist). Our model uses the underlying rotational symmetry of the Euclidean norm function to build a Lipschitzian approximation for the non-Lipschitzian group sparsity terms, which are defined by the group ell_2-ell_a norm with a in (0,1). The new result shows that the partially-separable structure and non-Lipschitzian group sparsity terms in the objective function may not affect the worst-case evaluation complexity order.
Recommendations
- Sparse optimization for nonconvex group penalized estimation
- Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
- Sparsity in higher order methods for unconstrained optimization
- Optimality and complexity for constrained optimization problems with nonconvex regularization
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
- On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization
- Difference-of-Convex Algorithms for a Class of Sparse Group \ell₀ Regularized Optimization Problems
- Evaluation complexity of algorithms for nonconvex optimization. Theory, computation and perspectives
- Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities
- Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization
Cites work
- scientific article; zbMATH DE number 3898623 (Why is no real title available?)
- scientific article; zbMATH DE number 107545 (Why is no real title available?)
- A Modeling Language for Mathematical Programming
- A group bridge approach for variable selection
- Accuracy guaranties for \(\ell_{1}\) recovery of block-sparse signals
- Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
- An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity
- Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities
- Complexity of unconstrained \(L_2 - L_p\) minimization
- Convergence Properties of Minimization Algorithms for Convex Constraints Using a Structured Trust Region
- Distributed block coordinate descent for minimizing partially separable functions
- Error bounds for compressed sensing algorithms with group sparsity: A unified approach
- Group descent algorithms for nonconvex penalized linear and logistic regression models with grouped predictors
- Group-Sparse Model Selection: Hardness and Relaxations
- Isotropic sparse regularization for spherical harmonic representations of random fields on the sphere
- Lower bound theory of nonzero entries in solutions of _2-_p minimization
- Model Selection and Estimation in Regression with Grouped Variables
- Modified partial-update Newton-type algorithms for unary optimization
- Optimality conditions and a smoothing trust region Newton method for nonlipschitz optimization
- Optimization problems involving group sparsity terms
- Partial-Update Newton Methods for Unary, Factorable, and Partially Separable Optimization
- Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization
- Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
- Sparse optimization for nonconvex group penalized estimation
- Spherical designs and nonconvex minimization for recovery of sparse signals on the sphere
- Subspace Methods for Joint Sparse Recovery
- Support union recovery in high-dimensional multivariate regression
- The Group Lasso for Stable Recovery of Block-Sparse Signal Representations
- The benefit of group sparsity
- Trust Region Methods
- Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization
- Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
Cited in
(8)- Group sparse optimization for inpainting of random fields on the sphere
- Complexity of finite-sum optimization with nonsmooth composite functions and non-Lipschitz regularization
- An interior stochastic gradient method for a class of non-Lipschitz optimization problems
- The evaluation complexity of finding high-order minimizers of nonconvex optimization
- scientific article; zbMATH DE number 7594592 (Why is no real title available?)
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- An adaptive high order method for finding third-order critical points of nonconvex optimization
- Tensor methods for finding approximate stationary points of convex functions
This page was built for publication: High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020600)
