Hyperparameter tuning of multi-stage pipelines introduces a significant computational burden. Motivated by the observation that work can be reused across pipelines if the intermediate computations are the same, we propose a pipeline-aware approach to hyperparameter tuning. Our approach optimizes both the design and execution of pipelines to maximize reuse. We design pipelines amenable for reuse by (i) introducing a novel hybrid hyperparameter tuning method called gridded random search, and (ii) reducing the average training time in pipelines by adapting early-stopping hyperparameter tuning approaches. We then realize the potential for reuse during execution by introducing a novel caching problem for ML workloads which we pose as a mixed integer linear program (ILP), and subsequently evaluating various caching heuristics relative to the optimal solution of the ILP. We conduct experiments on simulated and real-world machine learning pipelines to show that a pipeline-aware approach to hyperparameter tuning can offer over an order-of-magnitude speedup over independently evaluating pipeline configurations.
One of the basic limitations of a digital computer is the size of its available memory. 1 In most cases, it is neither feasible nor economical for a user to insist that every problem program fit into memory. The number of words of information in a program often exceeds the number of cells (i.e., word locations) in memory. The only way to solve this problem is to assign more than one program word to a cell. Since a cell can hold only one word at a time, extra words assigned to the cell must be held in external storage. Conventionally, overlay techniques are employed to exchange memory words and external-storage words whenever needed; this, of course, places an additional planning and coding burden on the programmer. For several reasons, it would be advantageous to rid the programmer of this function by providing him with a “virtual” memory larger than his program. An approach that permits him to use a sufficiently large address range can accomplish this objective, assuming that means are provided for automatic execution of the memory-overlay functions.  We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k)-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O(log(k (k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k. Our solution is based on a two-step approach. We first obtain an O(log k)-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O(log N)-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.