# Screening for a Reweighted Penalized Conditional Gradient Method

arXiv: https://arxiv.org/abs/2107.01106 · HTML: https://mlsanity.com/paper/2107.01106/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 74 references that are in the map.
- First posted on arXiv 2 Jul 2021.

## Builds on (most cited first, 25 of 25)

- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Sparse Modeling for Image and Vision Processing](https://mlsanity.com/paper/1411.3230/) (2014)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Mind the duality gap: safer rules for the Lasso](https://mlsanity.com/paper/1505.03410/) (2015)
- [A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems](https://mlsanity.com/paper/1303.4434/) (2013)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [GAP Safe screening rules for sparse multi-task and multi-class models](https://mlsanity.com/paper/1506.03736/) (2015)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Safe Screening With Variational Inequalities and Its Application to LASSO](https://mlsanity.com/paper/1307.7577/) (2013)
- [Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso](https://mlsanity.com/paper/1412.4080/) (2014)
- [Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage](https://mlsanity.com/paper/1702.06838/) (2017)
- [Deep Frank-Wolfe For Neural Network Optimization](https://mlsanity.com/paper/1811.07591/) (2018)
- [Screening Rules for Lasso with Non-Convex Sparse Regularizers](https://mlsanity.com/paper/1902.06125/) (2019)
- [Barrier Frank-Wolfe for Marginal Inference](https://mlsanity.com/paper/1511.02124/) (2015)
- [Forward - Backward Greedy Algorithms for Atomic Norm Regularization](https://mlsanity.com/paper/1404.5692/) (2014)
- [Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods](https://mlsanity.com/paper/1403.7588/) (2014)
- ["Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?](https://mlsanity.com/paper/1712.03577/) (2017)
- [Gauge optimization and duality](https://mlsanity.com/paper/1310.2639/) (2013)
- [Generalized Conditional Gradient for Sparse Estimation](https://mlsanity.com/paper/1410.4828/) (2014)
- [Nonsmooth Analysis and Optimization](https://mlsanity.com/paper/1708.04180/) (2017)
- [Learning Infinite RBMs with Frank-Wolfe](https://mlsanity.com/paper/1710.05270/) (2017)
- [Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives](https://mlsanity.com/paper/1807.07531/) (2018)

## Abstract (arXiv)

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 O(1/t) 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 O(1/(δ2)) where δ ≥ 0 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.