61 citations · 179 across the 39 of their papers we have counts for
40 papers
Replicable Composition
Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari +2
Replicability requires that algorithmic conclusions remain consistent when rerun on independently drawn data. A central structural question is composition: given problems each…
High-Dimensional Geometric Streaming for Nearly Low Rank Data
Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham +2
We study streaming algorithms for the subspace approximation problem. Given points as an insertion-only stream and a rank parameter , the su…
Optimal Communication for Classic Functions in the Coordinator Model and Beyond
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni +2
In the coordinator model of communication with servers, given an arbitrary non-negative function , we study the problem of approximating the sum up…
Robust and differentially private stochastic linear bandits
Vasileios Charisopoulos, Hossein Esfandiari, Vahab Mirrokni
In this paper, we study the stochastic linear bandit problem under the additional requirements of differential privacy, robustness and batched observations. In particular, we assum…
Optimal Fully Dynamic -Center Clustering for Adaptive and Oblivious Adversaries
MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger +4
In fully dynamic clustering problems, a clustering of a given data set in a metric space must be maintained while it is modified through insertions and deletions of individual poin…
Replicable Clustering
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni +2
We design replicable algorithms in the context of statistical clustering under the recently introduced notion of replicability from Impagliazzo et al. [2022]. According to this def…
Anonymous Bandits for Multi-User Systems
Hossein Esfandiari, Vahab Mirrokni, Jon Schneider
In this work, we present and study a new framework for online learning in systems with multiple users that provide user anonymity. Specifically, we extend the notion of bandits to…
Replicable Bandits
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi +3
In this paper, we introduce the notion of replicable policies in the context of stochastic bandits, one of the canonical problems in interactive learning. A policy in the bandit en…
Smooth Anonymity for Sparse Graphs
Alessandro Epasto, Hossein Esfandiari, Vahab Mirrokni +1
When working with user data providing well-defined privacy guarantees is paramount. In this work, we aim to manipulate and share an entire sparse dataset with a third party private…
Tackling Provably Hard Representative Selection via Graph Neural Networks
Mehran Kazemi, Anton Tsitsulin, Hossein Esfandiari +4
Representative Selection (RS) is the problem of finding a small subset of exemplars from a dataset that is representative of the dataset. In this paper, we study RS for attributed…
Improved Approximations for Euclidean -means and -median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni +1
Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean -median and -means problems. We propose a new primal-dual alg…
Optimal Fully Dynamic -Centers Clustering
MohammadHossein Bateni, Hossein Esfandiari, Rajesh Jayaram +1
We present the first algorithm for fully dynamic -centers clustering in an arbitrary metric space that maintains an optimal approximation in $O(k \cdot \operatorname{polyl…
Label differential privacy via clustering
Hossein Esfandiari, Vahab Mirrokni, Umar Syed +1
We present new mechanisms for \emph{label differential privacy}, a relaxation of differentially private machine learning that only protects the privacy of the labels in the trainin…
Tight and Robust Private Mean Estimation with Few Users
Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an -differentially private mechanism using as few users a…
Almost Tight Approximation Algorithms for Explainable Clustering
Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal…
Online Allocation and Display Ads Optimization with Surplus Supply
Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari +3
In this work, we study a scenario where a publisher seeks to maximize its total revenue across two sales channels: guaranteed contracts that promise to deliver a certain number of…
Feature Cross Search via Submodular Optimization
Lin Chen, Hossein Esfandiari, Gang Fu +2
In this paper, we study feature cross search as a fundamental primitive in feature engineering. The importance of feature cross search especially for the linear model has been know…
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +3
We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we…
Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming
Joey Huchette, Haihao Lu, Hossein Esfandiari +1
We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. Fi…
Adaptivity in Adaptive Submodularity
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni
Adaptive sequential decision making is one of the central challenges in machine learning and artificial intelligence. In such problems, the goal is to design an interactive policy…
Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond
Lin Chen, Hossein Esfandiari, Thomas Fu +1
Computing approximate nearest neighbors in high dimensional spaces is a central problem in large-scale data mining with a wide range of applications in machine learning and data sc…
Prophets, Secretaries, and Maximizing the Probability of Choosing the Best
Hossein Esfandiari, MohammadTaghi HajiAghayi, Brendan Lucier +1
Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what pri…
Streaming Balanced Clustering
Hossein Esfandiari, Vahab Mirrokni, Peilin Zhong
Clustering of data points in metric space is among the most fundamental problems in computer science with plenty of applications in data mining, information retrieval and machine l…
Near-Optimal Massively Parallel Graph Connectivity
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +2
Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we…