40 citations · 126 across the 27 of their papers we have counts for
27 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…
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…
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…
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…
PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses
Adel Javanmard, Matthew Fahrbach, Vahab Mirrokni
This work studies algorithms for learning from aggregate responses. We focus on the construction of aggregation sets (called bags in the literature) for event-level loss functions.…
Greedy PIG: Adaptive Integrated Gradients
Kyriakos Axiotis, Sami Abu-al-haija, Lin Chen +2
Deep learning has become the standard approach for most machine learning tasks. While its impact is undeniable, interpreting the predictions of deep learning models from a human pe…
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…
Unified Embedding: Battle-Tested Feature Representations for Web-Scale ML Systems
Benjamin Coleman, Wang-Cheng Kang, Matthew Fahrbach +4
Learning high-quality feature embeddings efficiently and effectively is critical for the performance of web-scale machine learning systems. A typical model ingests hundreds of feat…
Learning Rate Schedules in the Presence of Distribution Shift
Matthew Fahrbach, Adel Javanmard, Vahab Mirrokni +1
We design learning rate schedules that minimize regret for SGD-based online learning in the presence of a changing data distribution. We fully characterize the optimal learning rat…
Approximately Optimal Core Shapes for Tensor Decompositions
Mehrdad Ghadiri, Matthew Fahrbach, Gang Fu +1
This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give…
Sequential Attention for Feature Selection
Taisuke Yasuda, MohammadHossein Bateni, Lin Chen +3
Feature selection is the problem of selecting a subset of features for a machine learning model that maximizes model quality subject to a budget constraint. For neural networks, pr…
Subquadratic Kronecker Regression with Applications to Tensor Decomposition
Matthew Fahrbach, Thomas Fu, Mehrdad Ghadiri
Kronecker regression is a highly-structured least squares problem , where the design matrix $\mathbf{K} = \…
Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
Matthew Fahrbach, Mehrdad Ghadiri, Thomas Fu
Low-rank tensor decomposition generalizes low-rank matrix approximation and is a powerful technique for discovering low-dimensional structure in high-dimensional data. In this pape…
Faster Graph Embeddings via Coarsening
Matthew Fahrbach, Gramoz Goranci, Richard Peng +2
Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for…
Edge-Weighted Online Bipartite Matching
Matthew Fahrbach, Zhiyi Huang, Runzhou Tao +1
Online bipartite matching and its variants are among the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) introduced an elega…
A Fast Minimum Degree Algorithm and Matching Lower Bound
Robert Cummings, Matthew Fahrbach, Animesh Fatehpuria
The minimum degree algorithm is one of the most widely-used heuristics for reducing the cost of solving large sparse systems of linear equations. It has been studied for nearly hal…
Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases
Matthew Fahrbach, Dana Randall
The six-vertex model in statistical physics is a weighted generalization of the ice model on (i.e., Eulerian orientations) and the zero-temperature three-state Potts…
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity
Matthew Fahrbach, Vahab Mirrokni, Morteza Zadimoghaddam
Submodular maximization is a general optimization problem with a wide range of applications in machine learning (e.g., active learning, clustering, and feature selection). In large…
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
Matthew Fahrbach, Vahab Mirrokni, Morteza Zadimoghaddam
Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engin…
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides a…
On Computing Min-Degree Elimination Orderings
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
We study faster algorithms for producing the minimum degree ordering used to speed up Gaussian elimination. This ordering is based on viewing the non-zero elements of a symmetric p…
Analyzing Boltzmann Samplers for Bose-Einstein Condensates with Dirichlet Generating Functions
Megan Bernstein, Matthew Fahrbach, Dana Randall
Boltzmann sampling is commonly used to uniformly sample objects of a particular size from large combinatorial sets. For this technique to be effective, one needs to prove that (1)…
Online Weighted Matching: Breaking the Barrier
Matthew Fahrbach, Morteza Zadimoghaddam
Online matching and its variants are some of the most fundamental problems in the online algorithms literature. In this paper, we study the online weighted bipartite matching probl…