SCIENCE@home

A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems

Tyler B. Johnson,Carlos Guestrin

Published 2018 in arXiv.org

ABSTRACT

By reducing optimization to a sequence of smaller subproblems, working set algorithms achieve fast convergence times for many machine learning problems. Despite such performance, working set implementations often resort to heuristics to determine subproblem size, makeup, and stopping criteria. We propose BlitzWS, a working set algorithm with useful theoretical guarantees. Our theory relates subproblem size and stopping criteria to the amount of progress during each iteration. This result motivates strategies for optimizing algorithmic parameters and discarding irrelevant components as BlitzWS progresses toward a solution. BlitzWS applies to many convex problems, including training L1-regularized models and support vector machines. We showcase this versatility with empirical comparisons, which demonstrate BlitzWS is indeed a fast algorithm.

PUBLICATION RECORD

  • Publication year

    2018

  • Venue

    arXiv.org

  • Publication date

    2018-07-20

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1807.08046
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-81 of 81 references · Page 1 of 1

CITED BY