Morteza Zadimoghaddam

JMLR Journal 2025 Journal Article

Deletion Robust Non-Monotone Submodular Maximization over Matroids

• Paul Dütting
• Federico Fusco
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

We study the deletion robust version of submodular maximization under matroid constraints. The goal is to extract a small-size summary of the data set that contains a high-value independent set even after an adversary deletes some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank $k$ of the matroid, the number $d$ of deleted elements, and the input precision $\varepsilon$. In the centralized setting we present a $(4.494+O(\varepsilon))$-approximation algorithm with summary size $O( \frac{k+d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ that improves to a $(3.582+O(\varepsilon))$-approximation with $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ summary size when the objective is monotone. In the streaming setting we provide a $(9.294 + O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$; the approximation factor is then improved to $(5.582+O(\varepsilon))$ in the monotone case. [abs] [ pdf ][ bib ] &copy JMLR 2025. ( edit, beta )

NeurIPS Conference 2025 Conference Paper

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility

• Matthew Fahrbach
• Srikumar Ramalingam
• Morteza Zadimoghaddam
• Sara Ahmadian
• Gui Citovsky
• Giulia DeSalvo

This work studies a novel subset selection problem called *max-min diversification with monotone submodular utility* (MDMS), which has a wide range of applications in machine learning, e. g. , data sampling and feature selection. Given a set of points in a metric space, the goal of MDMS is to maximize $f(S) = g(S) + \lambda \cdot \text{div}(S)$ subject to a cardinality constraint $|S| \le k$, where $g(S)$ is a monotone submodular function and $\text{div}(S) = \min_{u, v \in S: u \ne v} \text{dist}(u, v)$ is the *max-min diversity* objective. We propose the `GIST` algorithm, which gives a $\frac{1}{2}$-approximation guarantee for MDMS by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of $0. 5584$. Finally, we show in our empirical study that `GIST` outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet.

ICML Conference 2025 Conference Paper

Scalable Private Partition Selection via Adaptive Weighting

• Justin Y. Chen
• Vincent Cohen-Addad
• Alessandro Epasto
• Morteza Zadimoghaddam

In the differentially private partition selection problem (a. k. a. set union, key discovery), users hold subsets of items from an unbounded universe. The goal is to output as many items as possible from the union of the users’ sets while maintaining user-level differential privacy. Solutions to this problem are a core building block for many privacy-preserving ML applications including vocabulary extraction in a private corpus, computing statistics over categorical data and learning embeddings over user-provided items. We propose an algorithm for this problem, MaxAdaptiveDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight, thereby increasing the probability that less frequent items are output. Our algorithm can be efficiently implemented in massively parallel computation systems allowing scalability to very large datasets. We prove that our algorithm stochastically dominates the standard parallel algorithm for this problem. We also develop a two-round version of our algorithm, MAD2R, where results of the computation in the first round are used to bias the weighting in the second round to maximize the number of items output. In experiments, our algorithms provide the best results among parallel algorithms and scale to datasets with hundreds of billions of items, up to three orders of magnitude larger than those analyzed in prior works.

STOC Conference 2025 Conference Paper

The Cost of Consistency: Submodular Maximization with Constant Recourse

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Ola Svensson
• Morteza Zadimoghaddam

ICML Conference 2024 Conference Paper

Consistent Submodular Maximization

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper, we study this problem in a dynamic environment with consistency constraints: elements arrive in a streaming fashion, and the goal is maintaining a constant approximation to the optimal solution while having a stable solution (i. e. , the number of changes between two consecutive solutions is bounded). In this setting, we provide algorithms with different trade-offs between consistency and approximation quality. We also complement our theoretical results with an experimental analysis showing the effectiveness of our algorithms in real-world instances.

ICML Conference 2023 Conference Paper

Fully Dynamic Submodular Maximization over Matroids

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an $\tilde{O}(k^2)$ amortized update time (in the number of additions and deletions) and yields a $4$-approximate solution, where $k$ is the rank of the matroid.

ICML Conference 2022 Conference Paper

Deletion Robust Submodular Maximization over Matroids

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

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(\varepsilon))$-approximation algorithm with summary size $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. In the streaming setting we provide a $(5. 582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.

FOCS Conference 2020 Conference Paper

Edge-Weighted Online Bipartite Matching

• Matthew Fahrbach
• Zhiyi Huang 0002
• Runzhou Tao 0001
• Morteza Zadimoghaddam

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 bipartite matching 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.

NeurIPS Conference 2020 Conference Paper

Fully Dynamic Algorithm for Constrained Submodular Optimization

• Silvio Lattanzi
• Slobodan Mitrović
• Ashkan Norouzi-Fard
• Jakub M. Tarnawski
• Morteza Zadimoghaddam

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 classic problem in the fully dynamic setting, 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 amortized update time and yields a $(1/2-epsilon)$-approximate solution. We complement our theoretical analysis with an empirical study of the performance of our algorithm.

NeurIPS Conference 2020 Conference Paper

Online MAP Inference of Determinantal Point Processes

• Aditya Bhaskara
• Amin Karbasi
• Silvio Lattanzi
• Morteza Zadimoghaddam

In this paper, we provide an efficient approximation algorithm for finding the most likelihood configuration (MAP) of size $k$ for Determinantal Point Processes (DPP) in the online setting where the data points arrive in an arbitrary order and the algorithm cannot discard the selected elements from its local memory. Given a tolerance additive error $\eta$, our \online algorithm achieves a $k^{O(k)}$ multiplicative approximation guarantee with an additive error $\eta$, using a memory footprint independent of the size of the data stream. We note that the exponential dependence on $k$ in the approximation factor is unavoidable even in the offline setting. Our result readily implies a streaming algorithm with an improved memory bound compared to existing results.

NeurIPS Conference 2020 Conference Paper

Sliding Window Algorithms for k-Clustering Problems

• Michele Borassi
• Alessandro Epasto
• Silvio Lattanzi
• Sergei Vassilvitskii
• Morteza Zadimoghaddam

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 provide simple and practical algorithms that offer stronger performance guarantees than previous results. Empirically, we show that our methods store only a small fraction of the data, are orders of magnitude faster, and find solutions with costs only slightly higher than those returned by algorithms with access to the full dataset.

ICML Conference 2019 Conference Paper

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-scale optimization, the parallel running time of an algorithm is governed by its adaptivity, which measures the number of sequential rounds needed if the algorithm can execute polynomially-many independent oracle queries in parallel. While low adaptivity is ideal, it is not sufficient for an algorithm to be efficient in practice—there are many applications of distributed submodular optimization where the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of submodular maximization. In this paper, we give the first constant-factor approximation algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint $k$ that runs in $O(\log(n))$ adaptive rounds and makes $O(n \log(k))$ oracle queries in expectation. In our empirical study, we use three real-world applications to compare our algorithm with several benchmarks for non-monotone submodular maximization. The results demonstrate that our algorithm finds competitive solutions using significantly fewer rounds and queries.

FOCS Conference 2019 Conference Paper

Residual Based Sampling for Online Low Rank Approximation

• Aditya Bhaskara
• Silvio Lattanzi
• Sergei Vassilvitskii
• Morteza Zadimoghaddam

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. and Frieze et al. that have additive guarantees, we show how to improve the bounds on the error of our algorithm.

SODA Conference 2019 Conference Paper

Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

• Matthew Fahrbach
• Vahab Mirrokni
• Morteza Zadimoghaddam

ICML Conference 2019 Conference Paper

Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity

• Ehsan Kazemi 0001
• Marko Mitrovic
• Morteza Zadimoghaddam
• Silvio Lattanzi
• Amin Karbasi

Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study the problem of maximizing a monotone submodular function in the streaming setting with a cardinality constraint $k$. We first propose SIEVE-STREAMING++, which requires just one pass over the data, keeps only $O(k)$ elements and achieves the tight $\frac{1}{2}$-approximation guarantee. The best previously known streaming algorithms either achieve a suboptimal $\frac{1}{4}$-approximation with $\Theta(k)$ memory or the optimal $\frac{1}{2}$-approximation with $O(k\log k)$ memory. Next, we show that by buffering a small fraction of the stream and applying a careful filtering procedure, one can heavily reduce the number of adaptive computational rounds, thus substantially lowering the computational complexity of SIEVE-STREAMING++. We then generalize our results to the more challenging multi-source streaming setting. We show how one can achieve the tight $\frac{1}{2}$-approximation guarantee with $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 data summarization tasks for multi-source streams of tweets and of YouTube videos.

SODA Conference 2018 Conference Paper

Consistent Hashing with Bounded Loads

• Vahab Mirrokni
• Mikkel Thorup
• Morteza Zadimoghaddam

In dynamic load balancing, we wish to allocate a set of clients (balls) to a set of servers (bins) with the goal of minimizing the maximum load of any server and also minimizing the number of moves after adding or removing a server or a client. We want a hashing-style solution where we given the ID of a client can efficiently find its server in a distributed dynamic environment. In such a dynamic environment, both servers and clients may be added and/or removed from the system in any order. The most popular solutions for such dynamic settings are Consistent Hashing [KLL + 97, SML + 03] or Rendezvous Hashing [TR98]. However, the load balancing of these schemes is no better than a random assignment of clients to servers, so with n of each, we expect many servers to be overloaded with Φ(log n / log log n ) clients. In this paper, we aim to design hashing schemes that achieve any desirable level of load balancing, while minimizing the number of movements under any addition or removal of servers or clients. In particular, we consider a problem with m balls and n bins, and given a user-specified balancing parameter c = 1 + ε > 1, we aim to find a hashing scheme with no load above [ cm/n ], referred to as the capacity of the bins. Our algorithmic starting point is the consistent hashing scheme where current balls and bins are hashed to the unit cycle, and a ball is placed in the first bin succeeding it in clockwise order. In order to cope with given capacity constraints, we apply the idea of linear probing by forwarding the ball on the circle to the first non-full bin. We show that in our hashing scheme when a ball or bin is inserted or deleted, the expected number of balls that have to be moved is within a multiplicative factor of of the optimum for ε ≤ 1 (Theorem 1. 2) and within a factor of the optimum for ε ≥ 1 (Theorem 1. 1). Technically, the latter bound is the most challenging to prove. It implies that for superconstant c, we only pay a negligible cost in extra moves. We also get the same bounds for the simpler problem where, instead of a user specified balancing parameter, we have a fixed bin capacity C for all bins, and define c = 1 + ε = Cn/m.

ICML Conference 2018 Conference Paper

Data Summarization at Scale: A Two-Stage Submodular Approach

• Marko Mitrovic
• Ehsan Kazemi 0001
• Morteza Zadimoghaddam
• Amin Karbasi

The sheer scale of modern datasets has resulted in a dire need for summarization techniques that can identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. We focus on a two-stage submodular framework where the goal is to use some given training functions to reduce the ground set so that optimizing new functions (drawn from the same distribution) over the reduced set provides almost as much value as optimizing them over the entire ground set. In this paper, we develop the first streaming and distributed solutions to this problem. In addition to providing strong theoretical guarantees, we demonstrate both the utility and efficiency of our algorithms on real-world tasks including image summarization and ride-share optimization.

ICML Conference 2018 Conference Paper

Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy

• Shipra Agrawal 0001
• Morteza Zadimoghaddam
• Vahab Mirrokni

Inspired by many applications of bipartite matching in online advertising and machine learning, we study a simple and natural iterative proportional allocation algorithm: Maintain a priority score $\priority_a$ for each node $a\in \mathds{A}$ on one side of the bipartition, initialized as $\priority_a=1$. Iteratively allocate the nodes $i\in \impressions$ on the other side to eligible nodes in $\mathds{A}$ in proportion of their priority scores. After each round, for each node $a\in \mathds{A}$, decrease or increase the score $\priority_a$ based on whether it is over- or under- allocated. Our first result is that this simple, distributed algorithm converges to a $(1-\epsilon)$-approximate fractional $b$-matching solution in $O({\log n\over \epsilon^2} )$ rounds. We also extend the proportional allocation algorithm and convergence results to the maximum weighted matching problem, and show that the algorithm can be naturally tuned to produce maximum matching with high entropy. High entropy, in turn, implies additional desirable properties of this matching, e. g. , it satisfies certain diversity and fairness (aka anonymity) properties that are desirable in a variety of applications in online advertising and machine learning.

ICML Conference 2018 Conference Paper

Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints

• Ehsan Kazemi 0001
• Morteza Zadimoghaddam
• Amin Karbasi

Can we efficiently extract useful information from a large user-generated dataset while protecting the privacy of the users and/or ensuring fairness in representation? We cast this problem as an instance of a deletion-robust submodular maximization where part of the data may be deleted or masked due to privacy concerns or fairness criteria. We propose the first memory-efficient centralized, streaming, and distributed methods with constant-factor approximation guarantees against any number of adversarial deletions. We extensively evaluate the performance of our algorithms on real-world applications, including (i) Uber-pick up locations with location privacy constraints; (ii) feature selection with fairness constraints for income prediction and crime rate prediction; and (iii) robust to deletion summarization of census data, consisting of 2, 458, 285 feature vectors. Our experiments show that our solution is robust against even $80%$ of data deletion.

ICML Conference 2017 Conference Paper

Probabilistic Submodular Maximization in Sub-Linear Time

• Serban Stan
• Morteza Zadimoghaddam
• Andreas Krause 0001
• Amin Karbasi

In this paper, we consider optimizing submodular functions that are drawn from some unknown distribution. This setting arises, e. g. , in recommender systems, where the utility of a subset of items may depend on a user-specific submodular utility function. In modern applications, the ground set of items is often so large that even the widely used (lazy) greedy algorithm is not efficient enough. As a remedy, we introduce the problem of sublinear time probabilistic submodular maximization: Given training examples of functions (e. g. , via user feature vectors), we seek to reduce the ground set so that optimizing new functions drawn from the same distribution will provide almost as much value when restricted to the reduced ground set as when using the full set. We cast this problem as a two-stage submodular maximization and develop a novel efficient algorithm for this problem which offers $1/2(1 - 1/e^2)$ approximation ratio for general monotone submodular functions and general matroid constraints. We demonstrate the effectiveness of our approach on several real-world applications where running the maximization problem on the reduced ground set leads to two orders of magnitude speed-up while incurring almost no loss.

AAAI Conference 2017 Conference Paper

Scalable Feature Selection via Distributed Diversity Maximization

• Sepehr Zadeh
• Mehrdad Ghadiri
• Vahab Mirrokni
• Morteza Zadimoghaddam

Feature selection is a fundamental problem in machine learning and data mining. The majority of feature selection algorithms are designed for running on a single machine (centralized setting) and they are less applicable to very large datasets. Although there are some distributed methods to tackle this problem, most of them are distributing the data horizontally which are not suitable for datasets with a large number of features and few number of instances. Thus, in this paper, we introduce a novel vertically distributable feature selection method in order to speed up this process and be able to handle very large datasets in a scalable manner. In general, feature selection methods aim at selecting relevant and non-redundant features (Minimum Redundancy and Maximum Relevance). It is much harder to consider redundancy in a vertically distributed setting than a centralized setting since there is no global access to the whole data. To the best of our knowledge, this is the first attempt toward solving the feature selection problem with a vertically distributed filter method which handles the redundancy with consistently comparable results with centralized methods. In this paper, we formalize the feature selection problem as a diversity maximization problem by introducing a mutual-information-based metric distance on the features. We show the effectiveness of our method by performing an extensive empirical study. In particular, we show that our distributed method outperforms state-of-the-art centralized feature selection algorithms on a variety of datasets. From a theoretical point of view, we have proved that the used greedy algorithm in our method achieves an approximation factor of 1/4 for the diversity maximization problem in a distributed setting with high probability. Furthermore, we improve this to 8/25 expected approximation using multiplicity in our distribution.

NeurIPS Conference 2016 Conference Paper

Fast Distributed Submodular Cover: Public-Private Data Summarization

• Baharan Mirzasoleiman
• Morteza Zadimoghaddam
• Amin Karbasi

In this paper, we introduce the public-private framework of data summarization motivated by privacy concerns in personalized recommender systems and online social services. Such systems have usually access to massive data generated by a large pool of users. A major fraction of the data is public and is visible to (and can be used for) all users. However, each user can also contribute some private data that should not be shared with other users to ensure her privacy. The goal is to provide a succinct summary of massive dataset, ideally as small as possible, from which customized summaries can be built for each user, i. e. it can contain elements from the public data (for diversity) and users' private data (for personalization). To formalize the above challenge, we assume that the scoring function according to which a user evaluates the utility of her summary satisfies submodularity, a widely used notion in data summarization applications. Thus, we model the data summarization targeted to each user as an instance of a submodular cover problem. However, when the data is massive it is infeasible to use the centralized greedy algorithm to find a customized summary even for a single user. Moreover, for a large pool of users, it is too time consuming to find such summaries separately. Instead, we develop a fast distributed algorithm for submodular cover, FASTCOVER, that provides a succinct summary in one shot and for all users. We show that the solution provided by FASTCOVER is competitive with that of the centralized algorithm with the number of rounds that is exponentially smaller than state of the art results. Moreover, we have implemented FASTCOVER with Spark to demonstrate its practical performance on a number of concrete applications, including personalized location recommendation, personalized movie recommendation, and dominating set on tens of millions of data points and varying number of users.

ICML Conference 2016 Conference Paper

Greedy Column Subset Selection: New Bounds and Distributed Algorithms

• Jason M. Altschuler
• Aditya Bhaskara
• Gang Fu
• Vahab Mirrokni
• Afshin Rostamizadeh
• Morteza Zadimoghaddam

The problem of column subset selection has recently attracted a large body of research, with feature selection serving as one obvious and important application. Among the techniques that have been applied to solve this problem, the greedy algorithm has been shown to be quite effective in practice. However, theoretical guarantees on its performance have not been explored thoroughly, especially in a distributed setting. In this paper, we study the greedy algorithm for the column subset selection problem from a theoretical and empirical perspective and show its effectiveness in a distributed setting. In particular, we provide an improved approximation guarantee for the greedy algorithm which we show is tight up to a constant factor, and present the first distributed implementation with provable approximation factors. We use the idea of randomized composable core-sets, developed recently in the context of submodular maximization. Finally, we validate the effectiveness of this distributed algorithm via an empirical study.

ICML Conference 2016 Conference Paper

Horizontally Scalable Submodular Maximization

• Mario Lucic
• Olivier Bachem
• Morteza Zadimoghaddam
• Andreas Krause 0001

A variety of large-scale machine learning problems can be cast as instances of constrained submodular maximization. Existing approaches for distributed submodular maximization have a critical drawback: The capacity - number of instances that can fit in memory - must grow with the data set size. In practice, while one can provision many machines, the capacity of each machine is limited by physical constraints. We propose a truly scalable approach for distributed submodular maximization under fixed capacity. The proposed framework applies to a broad class of algorithms and constraints and provides theoretical guarantees on the approximation factor for any available capacity. We empirically evaluate the proposed algorithm on a variety of data sets and demonstrate that it achieves performance competitive with the centralized greedy solution.

SODA Conference 2015 Conference Paper

Online Stochastic Matching with Unequal Probabilities

• Aranyak Mehta
• Bo Waggoner
• Morteza Zadimoghaddam

The online stochastic matching problem is a variant of online bipartite matching in which edges are labeled with probabilities. A match will “succeed” with the probability along that edge; this models, for instance, the click of a user in search advertisement. The goal is to maximize the expected number of successful matches. This problem was introduced by Mehta and Panigrahi (FOCS 2012), who focused on the case where all probabilities in the graph are equal. They gave a 0. 567-competitive algorithm for vanishing probabilities, relative to a natural benchmark, leaving the general case as an open question. This paper examines the general case where the probabilities may be unequal. We take a new algorithmic approach rather than generalizing that of Mehta and Panigrahi: Our algorithm maintains, at each time, the probability that each offline vertex has succeeded thus far, and chooses assignments so as to maximize marginal contributions to these probabilities. When the algorithm does not observe the realizations of the edges, this approach gives a 0. 5-competitive algorithm, which achieves the known upper bound for such “non-adaptive” algorithms. We then modify this approach to be “semi-adaptive: ” if the chosen target has already succeeded, choose the arrival's “second choice” instead (while still updating the probabilities non-adaptively). With one additional tweak to control the analysis, we show that this algorithm achieves a competitive ratio of 0. 534 for the unequal, vanishing probabilities setting. A “fully-adaptive” version of this algorithm turns out to be identical to an algorithm proposed, but not analyzed, in Mehta and Panigrahi (2012); we do not manage to analyze it either since it introduces too many dependencies between the stochastic processes. Our semi-adaptive algorithm thus can be seen as allowing analysis of competitive ratio while still capturing the power of adaptivity.

STOC Conference 2015 Conference Paper

Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order

• Nitish Korula
• Vahab Mirrokni
• Morteza Zadimoghaddam

In the Submodular Welfare Maximization (SWM) problem, the input consists of a set of n items, each of which must be allocated to one of m agents. Each agent l has a valuation function v l , where v l (S) denotes the welfare obtained by this agent if she receives the set of items S. The functions v l are all submodular; as is standard, we assume that they are monotone and v l (∅) = 0. The goal is to partition the items into m disjoint subsets S 1 , S 2 , ... S m in order to maximize the social welfare, defined as ∑ l = 1 m v l (S l ). A simple greedy algorithm gives a 1/2-approximation to SWM in the offline setting, and this was the best known until Vondrak's recent (1-1/e)-approximation algorithm [34]. In this paper, we consider the online version of SWM. Here, items arrive one at a time in an online manner; when an item arrives, the algorithm must make an irrevocable decision about which agent to assign it to before seeing any subsequent items. This problem is motivated by applications to Internet advertising, where user ad impressions must be allocated to advertisers whose value is a submodular function of the set of users / impressions they receive. There are two natural models that differ in the order in which items arrive. In the fully adversarial setting, an adversary can construct an arbitrary / worst-case instance, as well as pick the order in which items arrive in order to minimize the algorithm's performance. In this setting, the 1/2-competitive greedy algorithm is the best possible. To improve on this, one must weaken the adversary slightly: In the random order model, the adversary can construct a worst-case set of items and valuations, but does not control the order in which the items arrive; instead, they are assumed to arrive in a random order. The random order model has been well studied for online SWM and various special cases, but the best known competitive ratio (even for several special cases) is 1/2 + 1/n [9,10], barely better than the ratio for the adversarial order. Obtaining a competitive ratio of 1/2 + Ω(1) for the random order model has been an important open problem for several years. We solve this open problem by demonstrating that the greedy algorithm has a competitive ratio of at least 0.505 for online SWM in the random order model. This is the first result showing a competitive ratio bounded above 1/2 in the random order model, even for special cases such as the weighted matching or budgeted allocation problems (without the so-called 'large capacity' assumptions). For special cases of submodular functions including weighted matching, weighted coverage functions and a broader class of "second-order supermodular" functions, we provide a different analysis that gives a competitive ratio of 0.51. We analyze the greedy algorithm using a factor-revealing linear program, bounding how the assignment of one item can decrease potential welfare from assigning future items. We also formulate a natural conjecture which, if true, would improve the competitive ratio of the greedy algorithm to at least 0.567.

STOC Conference 2015 Conference Paper

Randomized Composable Core-sets for Distributed Submodular Maximization

• Vahab Mirrokni
• Morteza Zadimoghaddam

An effective technique for solving optimization problems over massive data sets is to partition the data into smaller pieces, solve the problem on each piece and compute a representative solution from it, and finally obtain a solution inside the union of the representative solutions for all pieces. This technique can be captured via the concept of composable core-sets , and has been recently applied to solve diversity maximization problems as well as several clustering problems [7,15,8]. However, for coverage and submodular maximization problems, impossibility bounds are known for this technique [15]. In this paper, we focus on efficient construction of a randomized variant of composable core-sets where the above idea is applied on a random clustering of the data. We employ this technique for the coverage, monotone and non-monotone submodular maximization problems. Our results significantly improve upon the hardness results for non-randomized core-sets, and imply improved results for submodular maximization in a distributed and streaming settings. The effectiveness of this technique has been confirmed empirically for several machine learning applications [22], and our proof provides a theoretical foundation to this idea.

SODA Conference 2013 Conference Paper

Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's"

• Erik D. Demaine
• Morteza Zadimoghaddam

AAAI Conference 2013 Conference Paper

Optimal Coalition Structure Generation in Cooperative Graph Games

• Yoram Bachrach
• Pushmeet Kohli
• Vladimir Kolmogorov
• Morteza Zadimoghaddam

Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inherent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive Weighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs.

SODA Conference 2012 Conference Paper

Simultaneous approximations for adversarial and stochastic online budgeted allocation

• Vahab Mirrokni
• Shayan Oveis Gharan
• Morteza Zadimoghaddam

NeurIPS Conference 2010 Conference Paper

Trading off Mistakes and Don't-Know Predictions

• Amin Sayedi
• Morteza Zadimoghaddam
• Avrim Blum

We discuss an online learning framework in which the agent is allowed to say I don't know'' as well as making incorrect predictions on given examples. We analyze the trade off between saying I don't know'' and making mistakes. If the number of don't know predictions is forced to be zero, the model reduces to the well-known mistake-bound model introduced by Littlestone [Lit88]. On the other hand, if no mistakes are allowed, the model reduces to KWIK framework introduced by Li et. al. [LLW08]. We propose a general, though inefficient, algorithm for general finite concept classes that minimizes the number of don't-know predictions if a certain number of mistakes are allowed. We then present specific polynomial-time algorithms for the concept classes of monotone disjunctions and linear separators.

SODA Conference 2007 Conference Paper

Minimizing movement

• Erik D. Demaine
• MohammadTaghi Hajiaghayi
• Hamid Mahini
• Amin S. Sayedi-Roshkhar
• Shayan Oveis Gharan
• Morteza Zadimoghaddam