Evimaria Terzi

TIST Journal 2025 Journal Article

Introduction to the “Best Papers of WSDM 2023” Special Issue

• Hady W. Lauw
• Marc Najork
• Evimaria Terzi
• Panayiotis Tsaparas

NeurIPS Conference 2025 Conference Paper

Online Two-Stage Submodular Maximization

• Iasonas Nikolaou
• Miltiadis Stouras
• Stratis Ioannidis
• Evimaria Terzi

Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) (Balkanski et al. 2016) is to restrict the ground set so an objective selected u. a. r. from the collection attains a high maximal value, on average, when optimized over the restricted ground set. We introduce the Online Two-Stage Submodular Maximization (O2SSM) problem, in which the submodular objectives are revealed in an online fashion. We study this problem for weighted threshold potential functions, a large and important subclass of monotone submodular functions that includes influence maximization, data summarization, and facility location, to name a few. We design an algorithm that achieves sublinear $(1 - 1/e)^2$-regret under general matroid constraints and $(1 - 1/e)(1-e^{-k}k^k/k! )$-regret in the case of uniform matroids of rank $k$; the latter also yields a state-of-the-art bound for the (offline) 2SSM problem. We empirically validate the performance of our online algorithm with experiments on real datasets.

AAAI Conference 2024 Conference Paper

Online Submodular Maximization via Online Convex Optimization

• Tareq Si Salem
• Gözde Özcan
• Iasonas Nikolaou
• Evimaria Terzi
• Stratis Ioannidis

We study monotone submodular maximization under general matroid constraints in the online setting. We prove that online optimization of a large class of submodular functions, namely, threshold potential functions, reduces to online convex optimization (OCO). This is precisely because functions in this class admit a concave relaxation; as a result, OCO policies, coupled with an appropriate rounding scheme, can be used to achieve sublinear regret in the combinatorial setting. We also show that our reduction extends to many different versions of the online learning problem, including the dynamic regret, bandit, and optimistic-learning settings.

NeurIPS Conference 2013 Conference Paper

What do row and column marginals reveal about your dataset?

• Behzad Golshan
• John Byers
• Evimaria Terzi

Numerous datasets ranging from group memberships within social networks to purchase histories on e-commerce sites are represented by binary matrices. While this data is often either proprietary or sensitive, aggregated data, notably row and column marginals, is often viewed as much less sensitive, and may be furnished for analysis. Here, we investigate how these data can be exploited to make inferences about the underlying matrix H. Instead of assuming a generative model for H, we view the input marginals as constraints on the dataspace of possible realizations of H and compute the probability density function of particular entries H(i, j) of interest. We do this, for all the cells of H simultaneously, without generating realizations but rather via implicitly sampling the datasets that satisfy the input marginals. The end result is an efficient algorithm with running time equal to the time required by standard sampling techniques to generate a single dataset from the same dataspace. Our experimental evaluation demonstrates the efficiency and the efficacy of our framework in multiple settings.