CaltechAUTHORS
  A Caltech Library Service

Learning to Prune: Speeding up Repeated Computations

Alabi, Daniel and Kalai, Adam Tauman and Ligett, Katrina and Musco, Cameron and Tzamos, Christos and Vitercik, Ellen (2019) Learning to Prune: Speeding up Repeated Computations. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190626-145729225

[img] PDF - Submitted Version
See Usage Policy.

1973Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190626-145729225

Abstract

It is common to encounter situations where one must solve a sequence of similar computational problems. Running a standard algorithm with worst-case runtime guarantees on each instance will fail to take advantage of valuable structure shared across the problem instances. For example, when a commuter drives from work to home, there are typically only a handful of routes that will ever be the shortest path. A naive algorithm that does not exploit this common structure may spend most of its time checking roads that will never be in the shortest path. More generally, we can often ignore large swaths of the search space that will likely never contain an optimal solution. We present an algorithm that learns to maximally prune the search space on repeated computations, thereby reducing runtime while provably outputting the correct solution each period with high probability. Our algorithm employs a simple explore-exploit technique resembling those used in online algorithms, though our setting is quite different. We prove that, with respect to our model of pruning search spaces, our approach is optimal up to constant factors. Finally, we illustrate the applicability of our model and algorithm to three classic problems: shortest-path routing, string search, and linear programming. We present experiments confirming that our simple algorithm is effective at significantly reducing the runtime of solving repeated computations.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1904.11875arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
Additional Information:This work was supported in part by Israel Science Foundation (ISF) grant #1044/16, a subcontract on the DARPA Brandeis Project, and the Federmann Cyber Security Center in conjunction with the Israel national cyber directorate.
Funders:
Funding AgencyGrant Number
Israel Science Foundation1044/16
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Hebrew University of JerusalemUNSPECIFIED
Record Number:CaltechAUTHORS:20190626-145729225
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190626-145729225
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96752
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Jun 2019 22:04
Last Modified:03 Oct 2019 21:25

Repository Staff Only: item control page