Morteza Zadimoghaddam
I am a staff research scientist (L6) at Google Cambridge office in the US. Prior to moving to Cambridge, I spent two years (2018 and 2019) in the Zurich office and 4 years in the New York office where I started my career at Google in January 2014. Prior to Google, I did my PhD in computer science at MIT (CSAIL) under supervision of Professor Erik D. Demaine.
I work on applying optimization techniques to various practical problems in order to find provably efficient algorithms. In particular, I apply infrastructure optimization methods to save computational resources at scale. On the mathematical and research side, I am interested in Submodular Optimization and its applications in large scale data mining and machine learning problems.
Authored Publications
Sort By
Edge-Weighted Online Bipartite Matching
Runzhou Tao
Zhiyi Huang
Journal of the ACM, 69 (2022), 45:1-45:35
Preview abstract
Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) introduced an elegant algorithm for the unweighted problem that achieves an optimal competitive ratio of 1 - 1/e. Aggarwal et al. (SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, about the most general edge-weighted problem aside from the trivial 1/2-competitive greedy algorithm. In this paper, we present the first online algorithm that breaks the long standing 1/2 barrier and achieves a competitive ratio of at least 0.5086. In light of the hardness result of Kapralov, Post, and Vondrák (SODA 2013) that restricts beating a 1/2 competitive ratio for the more general problem of monotone submodular welfare maximization, our result can be seen as strong evidence that edge-weighted bipartite matching is strictly easier than submodular welfare maximization in the online setting.
The main ingredient in our online matching algorithm is a novel subroutine called online correlated selection (OCS), which takes a sequence of pairs of vertices as input and selects one vertex from each pair. Instead of using a fresh random bit to choose a vertex from each pair, the OCS negatively correlates decisions across different pairs and provides a quantitative measure on the level of correlation. We believe our OCS technique is of independent interest and will find further applications in other online optimization problems.
View details
Deletion Robust Submodular Maximization over Matroids
Ashkan Norouzi Fard
Federico Fusco
Paul Duetting
ICML'22 (2022)
Preview abstract
Maximizing a monotone submodular function is a fundamental task in machine learning. In this paper we study the deletion robust version of the problem under the classic matroids constraint. Here the goal is to extract a small size summary of the dataset that contains a high value independent set even after an adversary deleted some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank $k$ of the matroid and the number $d$ of deleted elements. In the centralized setting we present a $(3.582+O(\eps))$-approximation algorithm with summary size $O(k + \frac{d \log k}{\eps^2})$. In the streaming setting we provide a $(5.582+O(\eps))$-approximation algorithm with summary size and memory $O(k + \frac{d \log k}{\eps^2})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.
View details
Distributed load balancing: a new framework and improved guarantees
Allen Liu
Binghui Peng
Innovations in Theoretical Computer Science (2021)
Preview abstract
Inspired by applications on search engines and web servers, we consider a load balancing problem with a general \textit{convex} objective function. In this problem, we are given a bipartite graph on a set of sources $S$ and a set of workers $W$ and the goal is to distribute the load from each source among its neighboring workers such that the total load of workers are as balanced as possible.
We present a new distributed algorithm that works with \textit{any} symmetric non-decreasing convex function for evaluating the balancedness of the workers' load.
Our algorithm computes a nearly optimal allocation of loads in $O(\log n \log^2 d/\eps^3)$ rounds where $n$ is the number of nodes, $d$ is the maximum degree, and $\eps$ is the desired precision. If the objective is to minimize the maximum load, we modify the algorithm to obtain a nearly optimal solution in $O(\log n \log d/\eps^2)$ rounds. This improves a line of algorithms that require a polynomial number of rounds in $n$ and $d$ and appear to encounter a fundamental barrier that prevents them from obtaining poly-logarithmic runtime
\cite{berenbrink2005dynamic, berenbrink2009new, subramanian1994analysis, rabani1998local}. In our paper, we introduce a novel primal-dual approach with multiplicative weight updates that allows us to circumvent this barrier. Our algorithm is inspired by \cite{agrawal2018proportional} and other distributed algorithms for optimizing linear objectives but introduces several new twists to deal with general convex objectives.
View details
Fully Dynamic Algorithm for Constrained Submodular Optimization
Ashkan Norouzi Fard
Jakub Tarnawski
Slobodan Mitrović
NeurIPS 2020 (to appear)
Preview abstract
The task of maximizing a monotone submodular function under a cardinality constraint is at the core of many machine learning and data mining applications, including data summarization, sparse regression and coverage problems. We study this problem in the context of fully dynamic streams, where elements can be both inserted and removed.
Our main result is a randomized algorithm that maintains an efficient data structure with a poly-logarithmic ammortized update time and returns a (1/2 - \epsilon)-approximate solution.
We complement our theoretical analysis with an empirical study of the performance of our algorithm.
View details
Preview abstract
In this paper, we provide efficient approximation algorithms for finding the most likelihood configuration (MAP) of size $k$ for Determinantal Point Processes (DPP) in the online and streaming settings where the data points arrive in an arbitrary order. More specifically, in the online setting, where the algorithm cannot discard the selected elements from its local memory, our Online-DPP algorithm achieves an $O(k^{O(k)})$ multiplicative approximation with $\eta$ additive error, using memory independent of the number of points. In the streaming setting, where the algorithm is allowed to discard the previously selected elements, our Stream-DPP algorithm achieves an $O(k^{O(k)})$ multiplicative approximation (and no additive error), with similar memory bounds. We note that the exponential dependence on $k$ in the approximation factor is unavoidable even in the offline setting.
View details
Sliding Window Algorithms for k-Clustering Problems
Michele Borassi
Neurips 2020 (to appear)
Preview abstract
The sliding window model of computation captures scenarios in which data is arriving continuously, but only the latest $w$ elements should be used for analysis. The goal is to design algorithms that update the solution efficiently with each arrival rather than recomputing it from scratch. In this work, we focus on $k$-clustering problems such as $k$-means and $k$-median. In this setting, we give simple and practical algorithms that come with stronger performance guarantees than previously known results. Empirically, we show that our methods store only a small fraction of the data, are orders of magnitude faster, and find solutions with cost only slightly worse than those returned by algorithms that have access to the full dataset.
View details
Preview abstract
Any streaming algorithm is commonly judged
by the quality of its solution, the memory footprint, and its required amount of computations.
In this paper, we study the problem of maximizing a monotone submodular function subject to
a cardinality constraint k. We propose SIEVESTREAMING++, a streaming algorithm that with
one pass over the data, while keeping only O(k)
elements, achieves the tight 1/2 approximation
guarantee. The best previously known streaming
algorithms either achieve a suboptimal approximation ratio 1/4 with Θ(k) memory or the tight
approximation ratio 1/2 with O(k log k) memory.
We then show that by buffering a small fraction
of the data stream, and through a careful filtering
procedure, one can heavily reduce the rounds of
adaptive computations, thus can lower the computational complexity of SIEVE-STREAMING++
substantially. We then generalize our results to
the more challenging multi-source streaming setting. We show how one can achieve the tight
1/2 approximation guarantee with a O(k) shared
memory, while minimizing not only the rounds
of computations but also the total number of communicated bits. Finally, we demonstrate the efficiency of our algorithms on real-world applications including data summarization for multisource streams of tweets and of YouTube videos
View details
Preview abstract
This paper considers a traditional problem of resource allocation, scheduling jobs on
machines. One such recent application is cloud computing, where jobs arrive in an online fashion with capacity requirements and need to be immediately scheduled on physical machines in data centers.
It is often observed that the requested capacities are not fully utilized, hence offering an opportunity to employ an overcommitment policy, i.e., selling resources beyond capacity. Setting the right overcommitment level can induce a significant cost reduction for the cloud provider, while only inducing a very low risk of violating capacity constraints. We introduce and study a model that quantifies the value of overcommitment by modeling the problem as a bin packing with chance constraints. We then propose an alternative formulation that transforms each chance constraint into a submodular function. We show that our model captures the risk pooling effect and can guide scheduling and overcommitment decisions. We also develop a family of online algorithms that are intuitive, easy to implement and provide a constant factor guarantee from optimal. Finally, we calibrate our model using realistic workload data, and test our approach in a practical setting. Our analysis and experiments illustrate the benefit of overcommitment in cloud services, and suggest a cost reduction of 1.5% to 17% depending on
the provider's risk tolerance.
View details
Preview abstract
We propose online algorithms for Column Subset Selection (CSS) and Principal Component
Analysis (PCA), two methods that are widely employed for data analysis, summarization, and
visualization. Given a data matrix A that is revealed one column at a time, the online CSS
problems asks to keep a small set of columns, S, that best approximates the space spanned by
the columns of A. As each column arrives, the algorithm must irrevocably decide whether to
add it to S, or to ignore it. In the online PCA problem, the goal is to output a projection of
each column to a low dimensional subspace. In other words, the algorithm must provide an
embedding for each column as it arrives, which cannot be changed as new columns arrive.
While both of these problems have been studied in the online setting, only additive approximations were known prior to our work. The core of our approach is an adaptive sampling technique that gives a practical and efficient algorithm for both of these problems. We prove that by sampling columns using their “residual norm” (i.e. their norm orthogonal to directions sampled so far), we end up with a significantly better dependence between the number of columns sampled, and the desired error in the approximation.
We further show how to combine our algorithm “in series” with prior algorithms. In particular, using the results of Boutsidis et al. [4] and Frieze et al. [14] that have additive guarantees, we show how to improve the bounds on the error of our algorithm.
View details
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (2019), pp. 255-273
Preview abstract
Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization.
Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint k that achieves a (1 − 1/e − ε)-approximation in expectation. This algorithm runs in O(log(n)) adaptive rounds and makes O(n) calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. We also extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.
View details
