Silvio Lattanzi
Silvio received his bachelor (2005), master (2007) and PhD(2011) degree from the Computer Science department of Sapienza University of Rome, under the supervision of Alessandro Panconesi. Silvio joined Google Research in the New York office in January 2011. Since April 2017 Silvio moved to Google Research Zurich.
Authored Publications
Sort By
Deletion Robust Non-Monotone Submodular Maximization over Matroids
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Journal of Machine Learning Research, 26 (2025), pp. 1-28
Preview abstract
Maximizing a submodular function is a fundamental task in machine learning and 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 $(4.597+O(\eps))$-approximation algorithm with summary size $O( \frac{k+d}{\eps^2}\log \frac{k}{\eps})$ that is improved to a $(3.582+O(\eps))$-approximation with $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$ summary size when the objective is monotone. In the streaming setting we provide a $(9.435 + O(\eps))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$; the approximation factor is then improved to $(5.582+O(\eps))$ in the monotone case.
View details
The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Ola Svensson
ACM Symposium on Theory of Computing (STOC 2025), ACM, pp. 1406-1417
Preview abstract
In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible
approximation ratio that is attainable when the algorithm is allowed to make, at most, a constant number of updates per step. We show a tight information-theoretic bound of $2/3$ for general monotone submodular functions and an improved (also tight) bound of $3/4$ for coverage functions. Since both these bounds are attained by non poly-time algorithms, we also give a poly-time randomized algorithm that achieves a $0.51$-approximation. Combined with an
information-theoretic hardness of $1/2$ for deterministic algorithms from prior work, our work thus shows a separation between deterministic and randomized algorithms, both information theoretically and for poly-time algorithms.
View details
The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Ola Svensson
Proceedings of the 57th Annual ACM Symposium on Theory of Computing (2025), 1406–1417
Preview abstract
In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible
approximation ratio that is attainable when the algorithm is allowed to make, at most, a constant number of updates per step. We show a tight information-theoretic bound of $2/3$ for general monotone submodular functions and an improved (also tight) bound of $3/4$ for coverage functions. Since both these bounds are attained by non poly-time algorithms, we also give a poly-time randomized algorithm that achieves a $0.51$-approximation. Combined with an
information-theoretic hardness of $1/2$ for deterministic algorithms from prior work, our work thus shows a separation between deterministic and randomized algorithms, both information theoretically and for poly-time algorithms.
View details
Almost Optimal Fully Dynamic k-Center Clustering with Recourse
Sayan Bhattacharya
Martin Costa
Ermiya Farokhnejad
2025 International Conference on Machine Learning (2025)
Preview abstract
In this paper, we consider the \emph{metric $k$-center} problem in the fully dynamic setting, where we are given a metric space $(V,d)$ evolving via a sequence of point insertions and deletions and our task is to maintain a subset $S \subseteq V$ of at most $k$ points that minimizes the objective $\max_{x \in V} \min_{y \in S}d(x, y)$. We want to design our algorithm so that we minimize its \emph{approximation ratio}, \emph{recourse} (the number of changes it makes to the solution $S$) and \emph{update time} (the time it takes to handle an update).
We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, \emph{obtaining near-optimal approximation, recourse and update time simultaneously}. We obtain our result by combining a variant of the dynamic $k$-center algorithm of Bateni et al.~[SODA'23] with the dynamic sparsifier of Bhattacharya et al.~[NeurIPS'23].
View details
Consistent Submodular Maximization
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Proceedings of the 41st International Conference on Machine Learning (2024), pp. 11979-11991
Preview abstract
Maximizing monotone submodular functions under cardinality constraints is a classic algorithmic problem with several applications in data mining and machine learning. In this paper we study this problem in a dynamic setting with consistency constrains. In this setting, elements arrive in a streaming fashion and one is interested in maintaining a constant approximation to the optimal solution and in having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide several algorithms in this setting 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.
View details
Consistent Submodular Maximization
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Proceedings of the 41st International Conference on Machine Learning, PMLR (2024), pp. 11979-11991
Preview abstract
Maximizing monotone submodular functions under cardinality constraints is a classic algorithmic problem with several applications in data mining and machine learning. In this paper we study this problem in a dynamic setting with consistency constrains. In this setting, elements arrive in a streaming fashion and one is interested in maintaining a constant approximation to the optimal solution and in having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide several algorithms in this setting 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.
View details
Consistent Submodular Maximization
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Proceedings of the 41st International Conference on Machine Learning, PMLR (2024), pp. 11979-11991
Preview abstract
Maximizing monotone submodular functions under cardinality constraints is a classic algorithmic problem with several applications in data mining and machine learning. In this paper we study this problem in a dynamic setting with consistency constrains. In this setting, elements arrive in a streaming fashion and one is interested in maintaining a constant approximation to the optimal solution and in having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide several algorithms in this setting 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.
View details
Consistent Submodular Maximization
Paul Duetting
Federico Fusco
Ashkan Norouzi Fard
Proceedings of the 41st International Conference on Machine Learning (2024)
Preview abstract
Maximizing monotone submodular functions under cardinality constraints is a classic algorithmic problem with several applications in data mining and machine learning. In this paper we study this problem in a dynamic setting with consistency constrains. In this setting, elements arrive in a streaming fashion and one is interested in maintaining a constant approximation to the optimal solution and in having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide several algorithms in this setting 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.
View details
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
Sayan Bhattacharya
Martin Costa
Naveen Garg
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) (2024)
Preview abstract
In the dynamic metric $k$-median problem, we wish to maintain a set of $k$ centers $S \subseteq V$ in an input metric space $(V, d)$ that gets updated via point insertions/deletions, so as to minimize the objective $\sum_{x \in V} \min_{y \in S} d(x, y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, ``recourse'' (the number of changes in $S$ per update) and ``update time'' (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic $O(1)$ approximation algorithm with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time.
Dynamic $k$-median is a canonical example of a class of problems known as dynamic $k$-clustering, that has received significant attention in recent years [Fichtenberger et al, SODA'21], [Bateni et al, SODA'23], [Lacki et al, SODA'24]. To the best of our knowledge, however, all these previous papers either attempt to minimize the algorithm's recourse while ignoring its update time, or minimize the algorithm's update time while ignoring its recourse. For dynamic $k$-median in particular, the state-of-the-art results get $\tilde{O}(k^2)$ update time and $O(k)$ recourse~[Cohen-Addad et al, ICML'19], [Henzinger and Kale, ESA'20], [Bhattacharya et al, NeurIPS'23]. But, this recourse bound of $O(k)$ can be trivially obtained by recomputing an optimal solution from scratch after every update, provided we ignore the update time. In addition, the update time of $\tilde{O}(k^2)$ is polynomially far away from the desired bound of $\tilde{O}(k)$. We come {\em arbitrarily close} to resolving the main open question on this topic, with the following results.
(I) We develop a new framework of {\em randomized local search} that is suitable for adaptation in a dynamic setting. For every $\epsilon > 0$, this gives us a dynamic $k$-median algorithm with $O(1/\epsilon)$ approximation ratio, $\tilde{O}(k^{\epsilon})$ recourse and $\tilde{O}(k^{1+\epsilon})$ update time. This framework also generalizes to dynamic $k$-clustering with $\ell^p$-norm objectives. As a corollary, we obtain similar bounds for the dynamic $k$-means problem, and a new trade-off between approximation ratio, recourse and update time for the dynamic $k$-center problem.
(II) If it suffices to maintain only an estimate of the {\em value} of the optimal $k$-median objective, then we obtain a $O(1)$ approximation algorithm with $\tilde{O}(k)$ update time. We achieve this result via adapting the Lagrangian Relaxation framework of [Jain and Vazirani, JACM'01], and a facility location algorithm of [Mettu and Plaxton, FOCS'00] in the dynamic setting.
View details
Preview abstract
Learning graph cluster structure using few queries is a classical question in property testing, with the fundamental special case, namely expansion testing, considered in the seminal work of Goldreich and Ron[STOC'96].
The most recent result in this line of work, due to Gluch et al.[SODA'21], designs {\em clustering oracles} for $(k, \e)$-clusterable graphs. These oracles, given a graph whose vertex set can be partitioned into a disjoint union of $k$ clusters (i.e., good expanders) with outer conductances bounded by $\e\ll 1$, provide query access to an $O(\e \log k)$-approximation to this ground truth clustering in time $\approx 2^{\text{poly}(k/\e)} n^{1/2+O(\e)}$ per query.
In this paper we show that it is possible to learn the {\em hierarchical} cluster structure of $(k, \e)$-clusterable graphs in sublinear time. First, we show how to simulate the hierarchical clustering algorithm of Charikar-Chatziafratis[SODA'17] to approximate the Dasgupta cost of a $k$-clusterable graph to within a factor of $O(\sqrt{\log k})$ in $\approx \text{poly}(k)\cdot n^{1/2+O(\e)}$ time assuming oracle access to the clustering. Second, we introduce a natural hierarchical model of clusterable graphs, and give a bona fide clustering oracle for this model, i.e. a small space data structure that can answer hierarchical clustering queries in $\approx\text{poly}(k) \cdot n^{1/2+O(\e)}$ time per query. Notably, in both cases the query time depends on polynomially on the number $k$ of clusters. The second result is the main technical contribution of the paper, and relies on several structural properties of hierarchically clusterable graphs that we hope will be of independent interest in sublinear time spectral graph algorithms.
View details
