Blitz: A Principled Meta-Algorithm for Scaling Sparse Optimization.
Tyler Johnson, Carlos Guestrin

Citation
Tyler Johnson, Carlos Guestrin. "Blitz: A Principled Meta-Algorithm for Scaling Sparse Optimization.". International Conference on Machine Learning (ICML), 2015.

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

Electronic downloads


Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.
Citation formats  
  • HTML
    Tyler Johnson, Carlos Guestrin. <a
    href="http://www.terraswarm.org/pubs/602.html"
    >Blitz: A Principled Meta-Algorithm for Scaling Sparse
    Optimization.</a>, International Conference on Machine
    Learning (ICML), 2015.
  • Plain text
    Tyler Johnson, Carlos Guestrin. "Blitz: A Principled
    Meta-Algorithm for Scaling Sparse Optimization.".
    International Conference on Machine Learning (ICML), 2015.
  • BibTeX
    @inproceedings{JohnsonGuestrin15_BlitzPrincipledMetaAlgorithmForScalingSparseOptimization,
        author = {Tyler Johnson and Carlos Guestrin},
        title = {Blitz: A Principled Meta-Algorithm for Scaling
                  Sparse Optimization.},
        booktitle = {International Conference on Machine Learning (ICML)},
        year = {2015},
        abstract = {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.},
        URL = {http://terraswarm.org/pubs/602.html}
    }
    

Posted by Carlos Guestrin on 10 Aug 2015.
Groups: services

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.