Screening for a reweighted penalized conditional gradient method
From MaRDI portal
Publication:2165597
Abstract: The conditional gradient method (CGM) is widely used in large-scale sparse convex optimization, having a low per iteration computational cost for structured sparse regularizers and a greedy approach to collecting nonzeros. We explore the sparsity acquiring properties of a general penalized CGM (P-CGM) for convex regularizers and a reweighted penalized CGM (RP-CGM) for nonconvex regularizers, replacing the usual convex constraints with gauge-inspired penalties. This generalization does not increase the per-iteration complexity noticeably. Without assuming bounded iterates or using line search, we show convergence of the gap of each subproblem, which measures distance to a stationary point. We couple this with a screening rule which is safe in the convex case, converging to the true support at a rate where measures how close the problem is to degeneracy. In the nonconvex case the screening rule converges to the true support in a finite number of iterations, but is not necessarily safe in the intermediate iterates. In our experiments, we verify the consistency of the method and adjust the aggressiveness of the screening rule by tuning the concavity of the regularizer.
Recommendations
- Gap safe screening rules for sparsity enforcing penalties
- Generalized conditional gradient for sparse estimation
- Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods
- Screening rules and its complexity for active set identification
- A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
Cites work
- ``Active-set complexity of proximal gradient: how long does it take to find the sparsity pattern?
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A generalized conditional gradient method and its connection to an iterative shrinkage method
- An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
- Compressed sensing
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient algorithms with open loop step size rules
- Convex analysis and monotone operator theory in Hilbert spaces
- Convex analysis and nonlinear optimization. Theory and examples.
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
- Decoding by Linear Programming
- Dual gauge programs, with applications to quadratic programming and the minimum-norm problem
- Duality between subgradient and conditional gradient methods
- Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso
- Forward–Backward Greedy Algorithms for Atomic Norm Regularization
- Gauge optimization and duality
- Generalized conditional gradient for sparse estimation
- Generalized Gradients and Applications
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Identifying active manifolds in regularization problems
- Identifying activity
- Introductory lectures on convex optimization. A basic course.
- Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints
- Iteratively reweighted least squares minimization for sparse recovery
- Iteratively Reweighted Least Squares: Algorithms, Convergence Analysis, and Numerical Comparisons
- On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision
- On the Identification of Active Constraints
- On the Identification of Active Constraints II: The Nonconvex Case
- Optimization and nonsmooth analysis
- Practical sketching algorithms for low-rank matrix approximation
- Relatively smooth convex optimization by first-order methods, and applications
- Safe Feature Elimination in Sparse Supervised Learning
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Simplicial decomposition in nonlinear programming algorithms
- Simultaneous Regression Shrinkage, Variable Selection, and Supervised Clustering of Predictors with OSCAR
- Some comments on Wolfe's ‘away step’
- Sparse Approximate Solutions to Semidefinite Programs
- Sparse modeling for image and vision processing
- Sparse Reconstruction by Separable Approximation
- The convex geometry of linear inverse problems
Cited in
(4)- Generalized conditional gradient for sparse estimation
- Screening rules and its complexity for active set identification
- Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods
- Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and Lasso
This page was built for publication: Screening for a reweighted penalized conditional gradient method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2165597)
