6 papers
Accelerated Relax-and-Round for Concave Coverage Problems
Matthew Fahrbach, Mehraneh Liaee, Morteza Zadimoghaddam
We present an accelerated relax-and-round algorithm for concave coverage problems, which generalize the classic maximum coverage problem. Building on the relax-and-round framework…
Efficient Hyperparameter Search for Non-Stationary Model Training
Berivan Isik, Matthew Fahrbach, Dima Kuzmin +4
Online learning is the cornerstone of applications like recommendation and advertising systems, where models continuously adapt to shifting data distributions. Model training for s…
GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
Matthew Fahrbach, Srikumar Ramalingam, Morteza Zadimoghaddam +3
This work studies a novel subset selection problem called max-min diversification with monotone submodular utility (), which has a wide range of applications in mach…
Fast Tensor Completion via Approximate Richardson Iteration
Mehrdad Ghadiri, Matthew Fahrbach, Yunbum Kook +1
We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods to solve highly structured line…
A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
Matthew Fahrbach, Mehrdad Ghadiri
We prove that the classic approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight by constructing a tensor for which HOSVD achieves an approximat…
Practical Performance Guarantees for Pipelined DNN Inference
Aaron Archer, Matthew Fahrbach, Kuikui Liu +1
We optimize pipeline parallelism for deep neural network (DNN) inference by partitioning model graphs into stages and minimizing the running time of the bottleneck stage, inclu…