BLITZ: a principled meta-algorithm for scaling sparse optimization. By reducing optimization to a sequence of small subproblems, working set methods achieve fast convergence times for many challenging problems. Despite excellent performance, theoretical understanding of working sets is limited, and implementations often resort to heuristics to determine subproblem size, makeup, and stopping criteria. We propose BLITZ, a fast working set algorithm accompanied by useful guarantees. Making no assumptions on data, our theory relates subproblem size to progress toward convergence. This result motivates methods for optimizing algorithmic parameters and discarding irrelevant variables as iterations progress. Applied to l1-regularized learning, BLITZ convincingly outperforms existing solvers in sequential, limited-memory, and distributed settings. BLITZ is not specific to l1-regularized learning, making the algorithm relevant to many applications involving sparsity or constraints.
Keywords for this software
References in zbMATH (referenced in 5 articles )
Showing results 1 to 5 of 5.
- Fercoq, Olivier; Qu, Zheng: Restarting the accelerated coordinate descent method with a rough strong convexity estimate (2020)
- Massias, Mathurin; Vaiter, Samuel; Gramfort, Alexandre; Salmon, Joseph: Dual extrapolation for sparse GLMs (2020)
- Pan, Xianli; Xu, Yitian: A safe reinforced feature screening strategy for Lasso based on feasible solutions (2019)
- Smith, Virginia; Forte, Simone; Ma, Chenxin; Takáč, Martin; Jordan, Michael I.; Jaggi, Martin: CoCoA: a general framework for communication-efficient distributed optimization (2018)
- Ndiaye, Eugene; Fercoq, Olivier; Gramfort, Alexandre; Salmon, Joseph: Gap safe screening rules for sparsity enforcing penalties (2017)