Safe Screening for the Generalized Conditional Gradient Method

Abstract

The conditional gradient method (CGM) has been widely used for fast sparse approximation, having a low per iteration computational cost for structured sparse regularizers. We explore the sparsity acquiring properties of a generalized CGM (gCGM), where the constraint is replaced by a penalty function based on a gauge penalty; this can be done without significantly increasing the per-iteration computation, and applies to general notions of sparsity. Without assuming bounded iterates, we show $O(1/t)$ convergence of the function values and gap of gCGM. We couple this with a safe screening rule, and show that at a rate $O(1/(t{\delta }^2))$, the screened support matches the support at the solution, where $\delta \ge 0$ measures how close the problem is to being degenerate. In our experiments, we show that the gCGM for these modified penalties have similar feature selection properties as common penalties, but with potentially more stability over the choice of hyperparameter.

References in corpus (12)

• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Lasso Screening Rules via Dual Polytope Projection
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
• Mind the duality gap: safer rules for the Lasso
• A Safe Screening Rule for Sparse Logistic Regression
• Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering
• Deep Frank-Wolfe For Neural Network Optimization
• Barrier Frank-Wolfe for Marginal Inference
• Tight Bounds for Approximate Carathéodory and Beyond

Cited by in corpus (2)

• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
• Screening for Sparse Online Learning