EUVIMEDOpdag EUVIMED
Crossref

Screening for a Reweighted Penalized Conditional Gradient Method

Yifan Sun, Francis Bach

Open Journal of Mathematical Optimization · 2022

DOI: 10.5802/ojmo.14 ↗

At a glance

Journal article in Open Journal of Mathematical Optimization, 2022. Written by Yifan Sun and 1 co-authors. 72 references.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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 for 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.

Cite

APA

Sun, Y., & Bach, F. (2022). Screening for a Reweighted Penalized Conditional Gradient Method. Open Journal of Mathematical Optimization. https://doi.org/10.5802/ojmo.14

Vancouver

Sun Y, Bach F. Screening for a Reweighted Penalized Conditional Gradient Method. Open Journal of Mathematical Optimization. 2022. doi:10.5802/ojmo.14

BibTeX
@article{Sun2022,
  author = {Sun, Yifan and Bach, Francis},
  title = {Screening for a Reweighted Penalized Conditional Gradient Method},
  journal = {Open Journal of Mathematical Optimization},
  year = {2022},
  doi = {10.5802/ojmo.14}
}
Start for free →