Vahab Mirrokni

ICLR Conference 2025 Conference Paper

Addax: Utilizing Zeroth-Order Gradients to Improve Memory Efficiency and Performance of SGD for Fine-Tuning Language Models

• Zeman Li
• Xinwei Zhang 0001
• Peilin Zhong
• Yuan Deng
• Meisam Razaviyayn
• Vahab Mirrokni

Fine-tuning language models (LMs) with the standard Adam optimizer often demands excessive memory, limiting accessibility. The ``in-place'' version of Stochastic Gradient Descent (IP-SGD) and Memory-Efficient Zeroth-order Optimizer (MeZO) have been proposed as solutions to improve memory efficiency. However, IP-SGD still requires a decent amount of memory, and MeZO suffers from slow convergence and degraded final performance due to its zeroth-order nature. This paper introduces Addax, a novel method that improves both memory efficiency and algorithm performance of IP-SGD by integrating it with MeZO. Specifically, Addax computes the zeroth-order or first-order gradient of the data points in the minibatch based on their memory consumption and combines zeroth- and first-order gradient estimates to obtain the updated direction in each step. By computing the zeroth-order order gradient of data points that require more memory and the first-order gradient of the ones that require less memory, Addax overcomes the slow convergence of MeZO and excessive memory requirement of IP-SGD. Additionally, the zeroth-order gradient acts as a regularizer for the first-order gradient, further enhancing the model's final performance. Theoretically, we establish the convergence of Addax under mild assumptions, demonstrating faster convergence and less restrictive hyper-parameter choices than MeZO. Our extensive experiments with diverse LMs and tasks show that Addax consistently outperforms MeZO in terms of accuracy and convergence speed, while having a comparable memory footprint. In particular, our experiments using one A100 GPU on OPT-13B model reveal that, on average, Addax outperforms MeZO in terms of accuracy/F1 score by 14%, and runs $15\times$ faster, while having a comparable memory footprint to MeZO. In our experiments on the larger OPT-30B model, on average, Addax outperforms MeZO in terms of accuracy/F1 score by >16% and runs $30\times$ faster on a single H100 GPU. Moreover, Addax surpasses the performance of standard fine-tuning approaches, such as IP-SGD and Adam, in most tasks in terms of Accuracy/F1 score with significantly less memory requirement.

ICML Conference 2025 Conference Paper

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models

• Ali Behrouz
• Ali Parviz
• Mahdi Karami
• Clayton Sanford
• Bryan Perozzi
• Vahab Mirrokni

Modern sequence models (e. g. , Transformers and linear RNNs) emerged as dominant backbones of recent deep learning frameworks, mainly due to their efficiency, representational power, and/or ability to capture long-range dependencies. Recently, adopting these sequence models for graph-structured data has gained popularity as the alternative to Message Passing Neural Networks (MPNNs). There is, however, a lack of a common foundation about what constitutes a good graph sequence model, and a mathematical description of the benefits and deficiencies in adopting different sequence models for learning on graphs. To this end, we introduce the Graph Sequence Model (GSM), a unifying framework for applying sequence models to graph data. The GSM framework allows us to understand, evaluate, and compare the power of different sequence model backbones in graph tasks. Building on this insight, we propose GSM++, a fast hybrid model that hierarchically tokenizes the graph using Hierarchical Affinity Clustering (HAC) and then encodes these sequences via a hybrid architecture. The theoretical and experimental findings confirm that GSM++ outperforms baseline models on most benchmarks.

ICML Conference 2025 Conference Paper

DeepCrossAttention: Supercharging Transformer Residual Connections

• Mike Heddes
• Adel Javanmard
• Kyriakos Axiotis
• Gang Fu
• MohammadHossein Bateni
• Vahab Mirrokni

Transformer networks have achieved remarkable success across diverse domains, leveraging a variety of architectural innovations, including residual connections. However, traditional residual connections, which simply sum the outputs of previous layers, can dilute crucial information. This work introduces DeepCrossAttention (DCA), an approach that enhances residual learning in transformers. DCA employs learnable, input-dependent weights to dynamically combine layer outputs, enabling the model to selectively focus on the most relevant information in any of the previous layers. Furthermore, DCA incorporates depth-wise cross-attention, allowing for richer interactions between layers at different depths. Our language modeling experiments show that DCA achieves improved perplexity for a given training time. Moreover, DCA obtains the same model quality up to 3x faster while adding a negligible number of parameters (e. g. , 0. 2%). Theoretical analysis confirms that DCA provides an improved trade-off between accuracy and model size when the ratio of collective layer ranks to the ambient dimension falls below a critical threshold.

ICLR Conference 2025 Conference Paper

DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reduction

• Xinwei Zhang 0001
• Zhiqi Bu
• Borja Balle
• Mingyi Hong 0001
• Meisam Razaviyayn
• Vahab Mirrokni

Differential privacy (DP) offers a robust framework for safeguarding individual data privacy. To utilize DP in training modern machine learning models, differentially private optimizers have been widely used in recent years. A popular approach to privatize an optimizer is to clip the individual gradients and add sufficiently large noise to the clipped gradient. This approach led to the development of DP optimizers that have comparable performance with their non-private counterparts in fine-tuning tasks or in tasks with a small number of training parameters. However, a significant performance drop is observed when these optimizers are applied to large-scale training. This degradation stems from the substantial noise injection required to maintain DP, which disrupts the optimizer's dynamics. This paper introduces DiSK, a novel framework designed to significantly enhance the performance of DP optimizers. DiSK employs Kalman filtering, a technique drawn from control and signal processing, to effectively denoise privatized gradients and generate progressively refined gradient estimations. To ensure practicality for large-scale training, we simplify the Kalman filtering process, minimizing its memory and computational demands. We establish theoretical privacy-utility trade-off guarantees for DiSK, and demonstrate provable improvements over standard DP optimizers like DPSGD in terms of iteration complexity upper-bound. Extensive experiments across diverse tasks, including vision tasks such as CIFAR-100 and ImageNet-1k and language fine-tuning tasks such as GLUE, E2E, and DART, validate the effectiveness of DiSK. The results showcase its ability to significantly improve the performance of DP optimizers, surpassing state-of-the-art results under the same privacy constraints on several benchmarks.

NeurIPS Conference 2025 Conference Paper

Efficient Data Selection at Scale via Influence Distillation

• Mahdi Nikdan
• Vincent Cohen-Addad
• Dan Alistarh
• Vahab Mirrokni

Effective data selection is critical for efficient training of modern Large Language Models (LLMs). This paper introduces Influence Distillation, a novel, mathematically-justified framework for data selection that employs second-order information to optimally weight training samples. By distilling each sample's influence on a target distribution, our method assigns model-specific weights that are used to select training data for LLM fine-tuning, guiding it toward strong performance on the target domain. We derive these optimal weights for both Gradient Descent and Adam optimizers. To ensure scalability and reduce computational cost, we propose a $\textit{landmark-based approximation}$: influence is precisely computed for a small subset of "landmark" samples and then efficiently propagated to all other samples to determine their weights. We validate Influence Distillation by applying it to instruction tuning on the Tulu V2 dataset, targeting a range of tasks including GSM8k, SQuAD, and MMLU, across several models from the Llama and Qwen families. Experiments show that Influence Distillation matches or outperforms state-of-the-art performance while achieving up to $3. 5\times$ faster selection.

ICML Conference 2025 Conference Paper

Improving the Variance of Differentially Private Randomized Experiments through Clustering

• Adel Javanmard
• Vahab Mirrokni
• Jean Pouget-Abadie

Estimating causal effects from randomized experiments is only possible if participants are willing to disclose their potentially sensitive responses. Differential privacy, a widely used framework for ensuring an algorithm’s privacy guarantees, can encourage participants to share their responses without the risk of de-anonymization. However, many mechanisms achieve differential privacy by adding noise to the original dataset, which reduces the precision of causal effect estimation. This introduces a fundamental trade-off between privacy and variance when performing causal analyses on differentially private data. In this work, we propose a new differentially private mechanism, Cluster-DP, which leverages a given cluster structure in the data to improve the privacy-variance trade-off. While our results apply to any clustering, we demonstrate that selecting higher-quality clusters—according to a quality metric we introduce—can decrease the variance penalty without compromising privacy guarantees. Finally, we evaluate the theoretical and empirical performance of our Cluster-DP algorithm on both real and simulated data, comparing it to common baselines, including two special cases of our algorithm: its unclustered version and a uniform-prior version.

SODA Conference 2025 Conference Paper

Massively Parallel Minimum Spanning Tree in General Metric Spaces

• Amir Azarmehr
• Soheil Behnezhad
• Rajesh Jayaram
• Jakub Lacki
• Vahab Mirrokni
• Peilin Zhong

ICML Conference 2025 Conference Paper

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures

• Alina Ene
• Alessandro Epasto
• Vahab Mirrokni
• Hoai-An Nguyen
• Huy L. Nguyen 0001
• David P. Woodruff
• Peilin Zhong

In the maximum coverage problem we are given $d$ subsets from a universe $[n]$, and the goal is to output $k$ subsets such that their union covers the largest possible number of distinct items. We present the first algorithm for maximum coverage in the turnstile streaming model, where updates which insert or delete an item from a subset come one-by-one. Notably our algorithm only uses $poly\log n$ update time. We also present turnstile streaming algorithms for targeted and general fingerprinting for risk management where the goal is to determine which features pose the greatest re-identification risk in a dataset. As part of our work, we give a result of independent interest: an algorithm to estimate the complement of the $p^{\text{th}}$ frequency moment of a vector for $p \geq 2$. Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to $210$x over prior work.

IJCAI Conference 2025 Conference Paper

Mechanism Design for Large Language Models (Extended Abstract)

• Paul Dütting
• Vahab Mirrokni
• Renato Paes Leme
• Haifeng Xu
• Song Zuo

We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated content are encoded as large language models (LLMs). We propose an auction format that operates on a token-by-token basis, and allows LLM agents to influence content creation through single dimensional bids. We formulate two desirable incentive properties and prove their equivalence to a monotonicity condition on output aggregation. This equivalence enables a second-price rule design, even absent explicit agent valuation functions. Our design is supported by demonstrations on a publicly available LLM.

NeurIPS Conference 2025 Conference Paper

Nested Learning: The Illusion of Deep Learning Architectures

• Ali Behrouz
• Meisam Razaviyayn
• Peilin Zhong
• Vahab Mirrokni

Over the last decades, developing more powerful neural architectures and simultaneously designing optimization algorithms to effectively train them have been the core of research efforts to enhance the capability of machine learning models. Despite the recent progresses, particularly in developing Language Models (LMs), there are fundamental challenges and unanswered questions about how such models can continually learn/memorize, self-improved, and find ''effective solutions, ''. In this paper, we present a new learning paradigm, called Nested Learning (NL), that coherently represents a model with a set of nested, multi-level, and/or parallel optimization problems, each of which with its own ''context flow''. NL reveals that existing deep learning methods learns from data through \emph{compressing} their own context flow, and explain how in-context learning emerges in large models. NL suggests a path (a new dimension to deep learning) to design more expressive learning algorithms with more ''levels'', resulting in higher-order in-context learning abilities. In addition to its neuroscientifically plausible and mathematically white-box nature, we advocate for its importance by presenting three core contributions: (1) Deep Optimizers: Based on NL, we show that well-known gradient-based optimizers (e. g. , Adam, SGD with Momentum, etc. ) are in fact associative memory modules that aim to compress the gradients with gradient descent. Building on this insight, we present a set of more expressive optimizers with deep memory and/or more powerful learning rules; (2) Self-Modifying Titans: Taking advantage of NL's insights on learning algorithms, we present a novel sequence model that learns how to modify itself by learning its own update algorithm; and (3) Continuum Memory System: We present a new formulation for memory system that generalizes the traditional viewpoint of ``long-term/short-term memory''. Combining our self-modifying sequence model with the continuum memory system, we present a learning module, called Hope, showing promising results in language modeling, continual learning, and long-context reasoning tasks.

NeurIPS Conference 2025 Conference Paper

PiKE: Adaptive Data Mixing for Large-Scale Multi-Task Learning Under Low Gradient Conflicts

• Zeman Li
• Yuan Deng
• Peilin Zhong
• Meisam Razaviyayn
• Vahab Mirrokni

Modern foundation models are trained on diverse datasets to enhance generalization across tasks and domains. A central challenge in this process is determining how to effectively mix and sample data from multiple sources. This naturally leads to a multi-task learning (MTL) perspective. While prior work in MTL has emphasized mitigating gradient conflicts, we observe that large-scale pretraining scenarios—such as multilingual or multi-domain training—often exhibit little to no gradient conflict. Motivated by this observation, we propose $\textbf{PiKE}$ ($\textbf{P}$ositive gradient $\textbf{i}$nteraction-based $\textbf{K}$-task weights $\textbf{E}$stimator), an adaptive data mixing algorithm that dynamically adjusts sampling weights during training. PiKE exploits non-conflicting gradient interactions to minimize a near-tight upper bound on the average loss decrease at each step, while incurring negligible computational overhead. We provide theoretical convergence guarantees and show that PiKE outperforms static and non-adaptive mixing baselines. Furthermore, we extend PiKE to promote balanced learning across tasks. Extensive experiments on large-scale language model pretraining confirm that PiKE achieves faster convergence and improved downstream performance compared to existing approaches.

ICML Conference 2025 Conference Paper

Procurement Auctions via Approximately Optimal Submodular Optimization

• Yuan Deng
• Amin Karbasi
• Vahab Mirrokni
• Renato Paes Leme
• Grigoris Velegkas
• Song Zuo

We study the problem of procurement auctions, in which an auctioneer seeks to acquire services from a group of strategic sellers with private costs. The quality of the services is measured through some submodular function that is known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, in a way that is incentive compatible (IC) and individual rational (IR) for the sellers, and generates non-negative surplus (NAS) for the auctioneer. Our contribution is twofold: i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization and ii) we design computationally efficient frameworks that transform submodular function optimization algorithms to mechanisms that are IC and IR for the sellers, NAS for the auctioneer, and approximation-preserving. Our frameworks are general and work both in the offline setting where the auctioneer can observe the bids and the services of all the sellers simultaneously, and in the online setting where the sellers arrive in an adversarial order and the auctioneer has to make an irrevocable decision whether to purchase their service or not. We further investigate whether it is possible to convert state-of-art submodular optimization algorithms into descending auctions. We focus on the adversarial setting, meaning that the schedule of the descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria $(1/2, 1)$-approximation in welfare can be effectively converted to a descending auction in this setting. We further establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with different state-of-the-art submodular optimization algorithms and comparing their welfare performance through empirical experiments on publicly available datasets that consist of thousands of sellers.

ICML Conference 2025 Conference Paper

Retraining with Predicted Hard Labels Provably Increases Model Accuracy

• Rudrajit Das
• Inderjit S. Dhillon
• Alessandro Epasto
• Adel Javanmard
• Jieming Mao
• Vahab Mirrokni
• Sujay Sanghavi
• Peilin Zhong

The performance of a model trained with noisy labels is often improved by simply retraining the model with its own predicted hard labels (i. e. , $1$/$0$ labels). Yet, a detailed theoretical characterization of this phenomenon is lacking. In this paper, we theoretically analyze retraining in a linearly separable binary classification setting with randomly corrupted labels given to us and prove that retraining can improve the population accuracy obtained by initially training with the given (noisy) labels. To the best of our knowledge, this is the first such theoretical result. Retraining finds application in improving training with local label differential privacy (DP), which involves training with noisy labels. We empirically show that retraining selectively on the samples for which the predicted label matches the given label significantly improves label DP training at no extra privacy cost; we call this consensus-based retraining. For example, when training ResNet-18 on CIFAR-100 with $\epsilon=3$ label DP, we obtain more than $6$% improvement in accuracy with consensus-based retraining.

NeurIPS Conference 2025 Conference Paper

Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing

• Adel Javanmard
• Rudrajit Das
• Alessandro Epasto
• Vahab Mirrokni

Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model’s performance. While prior works have demonstrated the benefits of specific heuristic retraining schemes, the question of how to optimally combine the model's predictions and the provided labels remains largely open. This paper addresses this fundamental question for binary classification tasks. We develop a principled framework based on approximate message passing (AMP) to analyze iterative retraining procedures for two ground truth settings: Gaussian mixture model (GMM) and generalized linear model (GLM). Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels, which when used to retrain the same model, minimizes its prediction error. We also quantify the performance of this optimal retraining strategy over multiple rounds. We complement our theoretical results by proposing a practically usable version of the theoretically-optimal aggregator function and demonstrate its superiority over baseline methods under different label noise models.

ICML Conference 2025 Conference Paper

Synthetic Text Generation for Training Large Language Models via Gradient Matching

• Dang Nguyen
• Zeman Li
• MohammadHossein Bateni
• Vahab Mirrokni
• Meisam Razaviyayn
• Baharan Mirzasoleiman

Synthetic data has the potential to improve the performance, training efficiency, and privacy of real training examples. Nevertheless, existing approaches for synthetic text generation are mostly heuristics and cannot generate human-readable text without compromising the privacy of real data, or provide performance guarantees for training Large Language Models (LLMs). In this work, we propose the first theoretically rigorous approach for generating synthetic human-readable text that provides convergence, performance, and privacy guarantees for fine-tuning LLMs on a target task. To do so, we leverage Alternating Direction Method of Multipliers (ADMM) that iteratively optimizes the embeddings of synthetic examples to match the noisy gradient of the target training or validation data, and maps them to a sequence of text tokens with low perplexity. In doing so, the generated synthetic text guarantees convergence of the model to a close neighborhood of the solution obtained by fine-tuning on real data and preserves their privacy. Experiments on various classification tasks confirm the effectiveness of our proposed approach. Our code is available at https: //github. com/BigML-CS-UCLA/GRADMM.

NeurIPS Conference 2025 Conference Paper

Titans: Learning to Memorize at Test Time

• Ali Behrouz
• Peilin Zhong
• Vahab Mirrokni

Over more than a decade there has been an extensive research effort on how to effectively utilize recurrent models and attention. While recurrent models aim to compress the data into a fixed-size memory (called hidden state), attention allows attending to the entire context window, capturing the direct dependencies of all tokens. This more accurate modeling of dependencies, however, comes with a quadratic cost, limiting the model to a fixed-length context. We present a neural long-term memory module that learns to memorize historical context and helps attention to attend to the current context while utilizing long-past information. We show that this neural memory has the advantage of fast parallelizable training. From a memory perspective, we argue that attention due to its limited context but accurate dependency modeling performs as a short-term memory, while neural memory due to its ability to memorize the data, acts as a long-term, more persistent, memory. Based on these two modules, we introduce a new family of architectures, called Titans, and present three variants to address how one can effectively incorporate memory into this architecture. Our experimental results on language modeling, common-sense reasoning, and time series tasks show that Titans are effective compared to baselines, while they can effectively scale to larger context window in needle-in-haystack tasks.

ICML Conference 2024 Conference Paper

A Field Guide for Pacing Budget and ROS Constraints

• Santiago R. Balseiro
• Kshipra Bhawalkar
• Zhe Feng 0004
• Haihao Lu
• Vahab Mirrokni
• Balasubramanian Sivan
• Di Wang 0005

Budget pacing is a popular service that has been offered by major internet advertising platforms since their inception. In the past few years, autobidding products that provide real-time bidding as a service to advertisers have seen a prominent rise in adoption. A popular autobidding stategy is value maximization subject to return-on-spend (ROS) constraints. For historical or business reasons, the systems that govern these two services, namely budget pacing and ROS pacing, are not necessarily always a single unified and coordinated entity that optimizes a global objective subject to both constraints. The purpose of this work is to theoretically and empirically compare algorithms with different degrees of coordination between these two pacing systems. In particular, we compare (a) a fully-decoupled sequential algorithm; (b) a minimally-coupled min-pacing algorithm; (c) a fully-coupled dual-based algorithm. Our main contribution is to theoretically analyze the min-pacing algorithm and show that it attains similar guarantees to the fully-coupled canonical dual-based algorithm. On the other hand, we show that the sequential algorithm, even though appealing by virtue of being fully decoupled, could badly violate the constraints. We validate our theoretical findings empirically by showing that the min-pacing algorithm performs almost as well as the canonical dual-based algorithm on a semi-synthetic dataset that was generated from a large online advertising platform’s auction data.

NeurIPS Conference 2024 Conference Paper

Autobidder's Dilemma: Why More Sophisticated Autobidders Lead to Worse Auction Efficiency

• Yuan Deng
• Jieming Mao
• Vahab Mirrokni
• Hanrui Zhang
• Song Zuo

The recent increasing adoption of autobidding has inspired the growing interest in analyzing the performance of classic mechanism with value-maximizing autobidders both theoretically and empirically. It is known that optimal welfare can be obtained in first-price auctions if autobidders are restricted to uniform bid-scaling and the price of anarchy is $2$ when non-uniform bid-scaling strategies are allowed. In this paper, we provide a fine-grained price of anarchy analysis for non-uniform bid-scaling strategies in first-price auctions, demonstrating the reason why more powerful (individual) non-uniform bid-scaling strategies may lead to worse (aggregated) performance in social welfare. Our theoretical results match recent empirical findings that a higher level of non-uniform bid-scaling leads to lower welfare performance in first-price auctions.

ICML Conference 2024 Conference Paper

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond

• Kyriakos Axiotis
• Vincent Cohen-Addad
• Monika Henzinger
• Sammy Jerome
• Vahab Mirrokni
• David Saulpic
• David P. Woodruff
• Michael Wunder

We study the data selection problem, whose aim is to select a small representative subset of data that can be used to efficiently train a machine learning model. We present a new data selection approach based on $k$-means clustering and sensitivity sampling. Assuming access to an embedding representation of the data with respect to which the model loss is Holder continuous, our approach provably allows selecting a set of “typical” $k + 1/\varepsilon^2$ elements whose average loss corresponds to the average loss of the whole dataset, up to a multiplicative $(1\pm\varepsilon)$ factor and an additive $\varepsilon \lambda \Phi_k$, where $\Phi_k$ represents the $k$-means cost for the input embeddings and $\lambda$ is the Holder constant. We furthermore demonstrate the performance and scalability of our approach on fine-tuning foundation models and show that it outperforms state-of-the-art methods. We also show how it can be applied on linear regression, leading to a new sampling strategy that surprisingly matches the performance of leverage score sampling, while being conceptually simpler and more scalable.

NeurIPS Conference 2024 Conference Paper

Efficiency of the First-Price Auction in the Autobidding World

• Yuan Deng
• Jieming Mao
• Vahab Mirrokni
• Hanrui Zhang
• Song Zuo

We study the price of anarchy of first-price auctions in the autobidding world, where bidders can be either utility maximizers (i. e. , traditional bidders) or value maximizers (i. e. , autobidders). We show that with autobidders only, the price of anarchy of first-price auctions is $1/2$, and with both kinds of bidders, the price of anarchy degrades to about $0. 457$ (the precise number is given by an optimization). These results complement the recent result by [Jin and Lu, 2022] showing that the price of anarchy of first-price auctions with traditional bidders is $1 - 1/e^2$. We further investigate a setting where the seller can utilize machine-learned advice to improve the efficiency of the auctions. There, we show that as the accuracy of the advice increases, the price of anarchy improves smoothly from about $0. 457$ to $1$.

ICML Conference 2024 Conference Paper

High-Dimensional Geometric Streaming for Nearly Low Rank Data

• Hossein Esfandiari
• Praneeth Kacham
• Vahab Mirrokni
• David P. Woodruff
• Peilin Zhong

We study streaming algorithms for the $\ell_p$ subspace approximation problem. Given points $a_1, \ldots, a_n$ as an insertion-only stream and a rank parameter $k$, the $\ell_p$ subspace approximation problem is to find a $k$-dimensional subspace $V$ such that $(\sum_{i=1}^n d(a_i, V)^p)^{1/p}$ is minimized, where $d(a, V)$ denotes the Euclidean distance between $a$ and $V$ defined as $\min_{v \in V} ||a - v||$. When $p = \infty$, we need to find a subspace $V$ that minimizes $\max_i d(a_i, V)$. For $\ell_{\infty}$ subspace approximation, we give a deterministic strong coreset construction algorithm and show that it can be used to compute a $\mathrm{poly}(k, \log n)$ approximate solution. We show that the distortion obtained by our coreset is nearly tight for any sublinear space algorithm. For $\ell_p$ subspace approximation, we show that suitably scaling the points and then using our $\ell_{\infty}$ coreset construction, we can compute a $\mathrm{poly}(k, \log n)$ approximation. Our algorithms are easy to implement and run very fast on large datasets. We also use our strong coreset construction to improve the results in a recent work of Woodruff and Yasuda (FOCS 2022) which gives streaming algorithms for high-dimensional geometric problems such as width estimation, convex hull estimation, and volume estimation.

ICLR Conference 2024 Conference Paper

HyperAttention: Long-context Attention in Near-Linear Time

• Insu Han
• Rajesh Jayaram
• Amin Karbasi
• Vahab Mirrokni
• David P. Woodruff
• Amir Zandieh

We present an approximate attention mechanism named `HyperAttention` to address the computational challenges posed by the growing complexity of long contexts used in Large Language Models (LLMs). Recent work suggests that in the worst-case scenario, the quadratic time is necessary unless the entries of the attention matrix are bounded or the matrix has low stable rank. We introduce two parameters which measure: (1) the max column norm in the normalized attention matrix, and (2) the ratio of row norms in the unnormalized attention matrix after detecting and removing large entries. We use these fine-grained parameters to capture the hardness of the problem. Despite previous lower bounds, we are able to achieve a linear time sampling algorithm even when the matrix has unbounded entries or a large stable rank, provided the above parameters are small. HyperAttention features a modular design that easily accommodates integration of other fast low-level implementations, particularly FlashAttention. Empirically, employing Locality Sensitive Hashing (LSH) to identify large entries, HyperAttention outperforms existing methods, giving significant speed improvements compared to state-of-the-art solutions like FlashAttention. This development presents substantial implications for enabling LLMs to handle significantly larger contexts.

ICLR Conference 2024 Conference Paper

Learning from Aggregate responses: Instance Level versus Bag Level Loss Functions

• Adel Javanmard
• Lin Chen
• Vahab Mirrokni
• Ashwinkumar Badanidiyuru
• Gang Fu

Due to the rise of privacy concerns, in many practical applications, the training data is aggregated before being shared with the learner to protect the privacy of users' sensitive responses. In an aggregate learning framework, the dataset is grouped into bags of samples, where each bag is available only with an aggregate response, providing a summary of individuals' responses in that bag. In this paper, we study two natural loss functions for learning from aggregate responses: the bag-level loss and the instance-level loss. In the former, the model is learned by minimizing a loss between the aggregate responses and aggregate model predictions, while in the latter, the model aims to fit individual predictions to the aggregate responses. In this work, we show that the instance-level loss can be perceived as a regularized form of the bag-level loss. This observation allows us to compare the two approaches with respect to the bias and variance of the resulting estimators and to introduce a novel interpolating estimator that combines the two approaches. For linear regression tasks, we provide a precise characterization of the risk of the interpolating estimator in an asymptotic regime where the size of the training set grows in proportion to the feature dimension. Our analysis enables us to theoretically understand the effect of different factors, such as bag size, on the model's prediction risk. Additionally, we propose a mechanism for differentially private learning from aggregate responses and derive the optimal bag size in terms of the prediction risk-privacy trade-off. We also carry out thorough experiments to corroborate our theory and show the efficacy of the interpolating estimator.

SODA Conference 2024 Conference Paper

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

• Rajesh Jayaram
• Vahab Mirrokni
• Shyam Narayanan
• Peilin Zhong

We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set X ⊂ ℝ d of n points, the goal is to produce a spanning tree for X with weight within a small factor of optimal. Euclidean MST is one of the most fundamental hierarchical geometric clustering algorithms, and with the proliferation of enormous high-dimensional data sets, such as massive transformer-based embeddings, there is now a critical demand for efficient distributed algorithms to cluster such data sets. In low-dimensional space, where d = O (1), Andoni, Nikolov, Onak, and Yaroslavtsev [STOC ‘14] gave a constant round MPC algorithm that obtains a high accuracy (1 + ɛ)-approximate solution. However, the situation is much more challenging for high-dimensional spaces: the best-known algorithm to obtain a constant approximation requires O (log n ) rounds. Recently Chen, Jayaram, Levi, and Waingarten [STOC ‘22] gave a O (log n ) approximation algorithm in a constant number of rounds based on embeddings into tree metrics. However, to date, no known algorithm achieves both a constant number of rounds and approximation. In this paper, we make strong progress on this front by giving a constant factor approximation in Õ (log log n ) rounds of the MPC model. In contrast to tree-embedding-based approaches, which necessarily must pay Ω(log n )-distortion, our algorithm is based on a new combination of graph-based distributed MST algorithms and geometric space partitions. Additionally, although the approximate MST we return can have a large depth, we show that it can be modified to obtain a O (log log n )-round constant factor approximation to the Euclidean Traveling Salesman Problem (TSP) in the MPC model. Previously, only a O (log n ) round was known for the problem. * The full version of the paper can be accessed at https: //arxiv. org/abs/2308. 00503.

NeurIPS Conference 2024 Conference Paper

MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding

• Laxman Dhulipala
• Majid Hadian
• Rajesh Jayaram
• Jason Lee
• Vahab Mirrokni

Neural embedding models have become a fundamental component of modern information retrieval (IR) pipelines. These models produce a single embedding $x \in \mathbb{R}^d$ per data-point, allowing for fast retrieval via highly optimized maximum inner product search (MIPS) algorithms. Recently, beginning with the landmark ColBERT paper, multi-vector models, which produce a set of embedding per data point, have achieved markedly superior performance for IR tasks. Unfortunately, using these models for IR is computationally expensive due to the increased complexity of multi-vector retrieval and scoring. In this paper, we introduce MUVERA (MUlti-VEctor Retrieval Algorithm), a retrieval mechanism which reduces multi-vector similarity search to single-vector similarity search. This enables the usage of off-the-shelf MIPS solvers for multi-vector retrieval. MUVERA asymmetrically generates Fixed Dimensional Encodings (FDEs) of queries and documents, which are vectors whose inner product approximates multi-vector similarity. We prove that FDEs give high-quality $\epsilon$-approximations, thus providing the first single-vector proxy for multi-vector similarity with theoretical guarantees. Empirically, we find that FDEs achieve the same recall as prior state-of-the-art heuristics while retrieving 2-5$\times$ fewer candidates. Compared to prior state of the art implementations, MUVERA achieves consistently good end-to-end recall and latency across a diverse set of the BEIR retrieval datasets, achieving an average of 10% improved recall with 90% lower latency.

STOC Conference 2024 Conference Paper

Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond

• Hossein Esfandiari
• Praneeth Kacham
• Vahab Mirrokni
• David P. Woodruff
• Peilin Zhong

In the coordinator model of communication with s servers, given an arbitrary non-negative function f , we study the problem of approximating the sum ∑ i ∈ [ n ] f ( x i ) up to a 1 ± ε factor. Here the vector x ∈ ℝ n is defined to be x = x (1) + ⋯ + x ( s ), where x ( j ) ≥ 0 denotes the non-negative vector held by the j -th server. A special case of the problem is when f ( x ) = x k which corresponds to the well-studied problem of F k moment estimation in the distributed communication model. We introduce a new parameter c f [ s ] which captures the communication complexity of approximating ∑ i ∈ [ n ] f ( x i ) and for a broad class of functions f which includes f ( x ) = x k for k ≥ 2 and other robust functions such as the Huber loss function, we give a two round protocol that uses total communication c f [ s ]/ε 2 bits, up to polylogarithmic factors. For this broad class of functions, our result improves upon the communication bounds achieved by Kannan, Vempala, and Woodruff (COLT 2014) and Woodruff and Zhang (STOC 2012), obtaining the optimal communication up to polylogarithmic factors in the minimum number of rounds. We show that our protocol can also be used for approximating higher-order correlations. Our results are part of a broad framework for optimally sampling from a joint distribution in terms of the marginal distributions held on individual servers. Apart from the coordinator model, algorithms for other graph topologies in which each node is a server have been extensively studied. We argue that directly lifting protocols from the coordinator model to other graph topologies will require some nodes in the graph to send a lot of communication. Hence, a natural question is the type of problems that can be efficiently solved in general graph topologies. We address this question by giving communication efficient protocols in the so-called personalized CONGEST model for solving linear regression and low rank approximation by designing composable sketches . Our sketch construction may be of independent interest and can implement any importance sampling procedure that has a monotonicity property.

ICML Conference 2024 Conference Paper

Perturb-and-Project: Differentially Private Similarities and Marginals

• Vincent Cohen-Addad
• Tommaso d'Orsi
• Alessandro Epasto
• Vahab Mirrokni
• Peilin Zhong

We revisit the objective perturbations framework for differential privacy where noise is added to the input $A\in \mathcal{S}$ and the result is then projected back to the space of admissible datasets $\mathcal{S}$. Through this framework, we first design novel efficient algorithms to privately release pair-wise cosine similarities. Second, we derive a novel algorithm to compute $k$-way marginal queries over $n$ features. Prior work could achieve comparable guarantees only for $k$ even. Furthermore, we extend our results to $t$-sparse datasets, where our efficient algorithms yields novel, stronger guarantees whenever $t\le n^{5/6}/\log n. $ Finally, we provide a theoretical perspective on why fast input perturbation algorithms works well in practice. The key technical ingredients behind our results are tight sum-of-squares certificates upper bounding the Gaussian complexity of sets of solutions.

ICML Conference 2024 Conference Paper

PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels

• Praneeth Kacham
• Vahab Mirrokni
• Peilin Zhong

The quadratic time and memory complexity inherent to self-attention mechanisms, with respect to sequence length, presents a critical computational bottleneck in the training and deployment of large-scale Transformer-based language models. Recent theoretical results indicate the intractability of sub-quadratic softmax attention approximation under reasonable complexity assumptions. This paper addresses this challenge by first demonstrating that polynomial attention with high degree can effectively replace softmax without sacrificing model quality. Next, we develop polynomial sketching techniques from numerical linear algebra to achieve linear-time polynomial attention with approximation guarantees. Crucially, our approach achieves this speedup without requiring the sparsification of attention matrices. We also present a block-based algorithm to apply causal masking efficiently. Combining these techniques, we provide PolySketchFormer, a practical linear-time Transformer architecture for language modeling that offers provable guarantees. We validate PolySketchFormer empirically by training language models capable of handling long contexts. These experiments utilize both synthetic and real-world datasets (PG19, Wikipedia and C4) on Google Cloud TPUs. For context lengths of 32k and GPT-2 style models, our model achieves 2x speedup in training compared to FlashAttention of the fastest configuration, with no observed degradation in quality across our experiments.

ICML Conference 2024 Conference Paper

PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses

• Adel Javanmard
• Matthew Fahrbach
• Vahab Mirrokni

This work studies algorithms for learning from aggregate responses. We focus on the construction of aggregation sets (called bags in the literature) for event-level loss functions. We prove for linear regression and generalized linear models (GLMs) that the optimal bagging problem reduces to one-dimensional size-constrained $k$-means clustering. Further, we theoretically quantify the advantage of using curated bags over random bags. We then propose the $\texttt{PriorBoost}$ algorithm, which adaptively forms bags of samples that are increasingly homogeneous with respect to (unobserved) individual responses to improve model quality. We study label differential privacy for aggregate learning, and we also provide extensive experiments showing that $\texttt{PriorBoost}$ regularly achieves optimal model quality for event-level predictions, in stark contrast to non-adaptive algorithms.

NeurIPS Conference 2024 Conference Paper

SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization

• Taisuke Yasuda
• Kyriakos Axiotis
• Gang Fu
• MohammadHossein Bateni
• Vahab Mirrokni

Neural network pruning is a key technique towards engineering large yet scalable, interpretable, and generalizable models. Prior work on the subject has developed largely along two orthogonal directions: (1) differentiable pruning for efficiently and accurately scoring the importance of parameters, and (2) combinatorial optimization for efficiently searching over the space of sparse models. We unite the two approaches, both theoretically and empirically, to produce a coherent framework for structured neural network pruning in which differentiable pruning guides combinatorial optimization algorithms to select the most important sparse set of parameters. Theoretically, we show how many existing differentiable pruning techniques can be understood as nonconvex regularization for group sparse optimization, and prove that for a wide class of nonconvex regularizers, the global optimum is unique, group-sparse, and provably yields an approximate solution to a sparse convex optimization problem. The resulting algorithm that we propose, SequentialAttention++, advances the state of the art in large-scale neural network block-wise pruning tasks on the ImageNet and Criteo datasets.

NeurIPS Conference 2024 Conference Paper

Understanding Transformer Reasoning Capabilities via Graph Algorithms

• Clayton Sanford
• Bahare Fatemi
• Ethan Hall
• Anton Tsitsulin
• Mehran Kazemi
• Jonathan Halcrow
• Bryan Perozzi
• Vahab Mirrokni

Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities in realistic parameter regimes is lacking. We investigate this question in terms of the network’s depth, width, and number of extra tokens for algorithm execution. Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes. We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks. We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark. These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.

NeurIPS Conference 2023 Conference Paper

$k$-Means Clustering with Distance-Based Privacy

• Alessandro Epasto
• Vahab Mirrokni
• Shyam Narayanan
• Peilin Zhong

In this paper, we initiate the study of Euclidean clustering with Distance-based privacy. Distance-based privacy is motivated by the fact that it is often only needed to protect the privacy of exact, rather than approximate, locations. We provide constant-approximate algorithms for $k$-means and $k$-median clustering, with additive error depending only on the attacker's precision bound $\rho$, rather than the radius $\Lambda$ of the space. In addition, we empirically demonstrate that our algorithm performs significantly better than previous differentially private clustering algorithms, as well as naive distance-based private clustering baselines.

NeurIPS Conference 2023 Conference Paper

Anonymous Learning via Look-Alike Clustering: A Precise Analysis of Model Generalization

• Adel Javanmard
• Vahab Mirrokni

While personalized recommendations systems have become increasingly popular, ensuring user data protection remains a top concern in the development of these learning systems. A common approach to enhancing privacy involves training models using anonymous data rather than individual data. In this paper, we explore a natural technique called "look-alike clustering", which involves replacing sensitive features of individuals with the cluster's average values. We provide a precise analysis of how training models using anonymous cluster centers affects their generalization capabilities. We focus on an asymptotic regime where the size of the training set grows in proportion to the features dimension. Our analysis is based on the Convex Gaussian Minimax Theorem (CGMT) and allows us to theoretically understand the role of different model components on the generalization error. In addition, we demonstrate that in certain high-dimensional regimes, training over anonymous cluster centers acts as a regularization and improves generalization error of the trained models. Finally, we corroborate our asymptotic theory with finite-sample numerical experiments where we observe a perfect match when the sample size is only of order of a few hundreds.

ICML Conference 2023 Conference Paper

Approximately Optimal Core Shapes for Tensor Decompositions

• Mehrdad Ghadiri
• Matthew Fahrbach
• Gang Fu
• Vahab Mirrokni

This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximation guarantees for its reconstruction error via connections to higher-order singular values. Specifically, we introduce a novel Tucker packing problem, which we prove is NP-hard, and give a polynomial-time approximation scheme based on a reduction to the 2-dimensional knapsack problem with a matroid constraint. We also generalize our techniques to tree tensor network decompositions. We implement our algorithm using an integer programming solver, and show that its solution quality is competitive with (and sometimes better than) the greedy algorithm that uses the true Tucker decomposition loss at each step, while also running up to 1000x faster.

ICML Conference 2023 Conference Paper

Differentially Private Hierarchical Clustering with Provable Approximation Guarantees

• Jacob Imola
• Alessandro Epasto
• Mohammad Mahdian
• Vincent Cohen-Addad
• Vahab Mirrokni

Hierarchical Clustering is a popular unsupervised machine learning method with decades of history and numerous applications. We initiate the study of differentially-private approximation algorithms for hierarchical clustering under the rigorous framework introduced by Dasgupta (2016). We show strong lower bounds for the problem: that any $\epsilon$-DP algorithm must exhibit $O(|V|^2/ \epsilon)$-additive error for an input dataset $V$. Then, we exhibit a polynomial-time approximation algorithm with $O(|V|^{2. 5}/ \epsilon)$-additive error, and an exponential-time algorithm that meets the lower bound. To overcome the lower bound, we focus on the stochastic block model, a popular model of graphs, and, with a separation assumption on the blocks, propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly. Finally, we perform an empirical study of our algorithms and validate their performance.

ICML Conference 2023 Conference Paper

Learning Rate Schedules in the Presence of Distribution Shift

• Matthew Fahrbach
• Adel Javanmard
• Vahab Mirrokni
• Pratik Worah

We design learning rate schedules that minimize regret for SGD-based online learning in the presence of a changing data distribution. We fully characterize the optimal learning rate schedule for online linear regression via a novel analysis with stochastic differential equations. For general convex loss functions, we propose new learning rate schedules that are robust to distribution shift, and give upper and lower bounds for the regret that only differ by constants. For non-convex loss functions, we define a notion of regret based on the gradient norm of the estimated models and propose a learning schedule that minimizes an upper bound on the total expected regret. Intuitively, one expects changing loss landscapes to require more exploration, and we confirm that optimal learning rate schedules typically have higher learning rates in the presence of distribution shift. Finally, we provide experiments that illustrate these learning rate schedules and their regret.

ICML Conference 2023 Conference Paper

Multi-channel Autobidding with Budget and ROI Constraints

• Yuan Deng
• Negin Golrezaei
• Patrick Jaillet
• Jason Cheuk Nam Liang
• Vahab Mirrokni

In digital online advertising, advertisers procure ad impressions simultaneously on multiple platforms, or so-called channels, such as Google Ads, Meta Ads Manager, etc. , each of which consists of numerous ad auctions. We study how an advertiser maximizes total conversion (e. g. ad clicks) while satisfying aggregate return-on-investment (ROI) and budget constraints across all channels. In practice, an advertiser does not have control over, and thus cannot globally optimize, which individual ad auctions she participates in for each channel, and instead authorizes a channel to procure impressions on her behalf: the advertiser can only utilize two levers on each channel, namely setting a per-channel budget and per-channel target ROI. In this work, we first analyze the effectiveness of each of these levers for solving the advertiser’s global multi-channel problem. We show that when an advertiser only optimizes over per-channel ROIs, her total conversion can be arbitrarily worse than what she could have obtained in the global problem. Further, we show that the advertiser can achieve the global optimal conversion when she only optimizes over per-channel budgets. In light of this finding, under a bandit feedback setting that mimics real-world scenarios where advertisers have limited information on ad auctions in each channels and how channels procure ads, we present an efficient learning algorithm that produces per-channel budgets whose resulting conversion approximates that of the global optimal problem.

SODA Conference 2023 Conference Paper

Optimal Fully Dynamic k -Center Clustering for Adaptive and Oblivious Adversaries

• MohammadHossein Bateni
• Hossein Esfandiari
• Hendrik Fichtenberger
• Monika Henzinger
• Rajesh Jayaram
• Vahab Mirrokni
• Andreas Wiese

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 points. In this paper, we resolve the complexity of fully dynamic k -center clustering against both adaptive and oblivious adversaries. Against oblivious adversaries, we present the first algorithm for fully dynamic k -center in an arbitrary metric space that maintains an optimal (2 + ε)-approximation in O ( k · polylog( n, Δ)) amortized update time. Here, n is an upper bound on the number of active points at any time, and Δ is the aspect ratio of the metric space. Previously, the best known amortized update time was O ( k 2 · polylog( n, Δ)), and is due to Chan, Gourqin, and Sozio (2018). Moreover, we demonstrate that our runtime is optimal up to polylog( n, Δ) factors. In fact, we prove that even offline algorithms for k -clustering tasks in arbitrary metric spaces, including k -medians, k -means, and k -center, must make at least Ω( nk ) distance queries to achieve any non-trivial approximation factor. This implies a lower bound of Ω( k ) which holds even for the insertions-only setting. For adaptive adversaries, we give the first deterministic algorithm for fully dynamic k -center which achieves a approximation in O ( k -polylog( n, Δ)) amortized update time. Further, we demonstrate that any algorithm which achieves a -approximation against adaptive adversaries requires f (k, n) update time, for any arbitrary function f. Thus, in the regime where, we close the complexity of the problem up to polylog( n, Δ) factors in the update time. Our lower bound extends to other k -clustering tasks in arbitrary metric spaces, including k -medians and k -means. Finally, despite the aforementioned lower bounds, we demonstrate that an update time sublinear in k is possible against oblivious adversaries for metric spaces which admit locally sensitive hash functions (LSH), resulting in improved algorithms for a large class of metrics including Euclidean space, ℓ p -spaces, the Hamming Metric, and the Jaccard Metric. We also give the first fully dynamic O (1)-approximation algorithms for the closely related k -sum-of-radii and k -sum-of-diameter problems, with O (poly( k, log Δ)) update time.

ICLR Conference 2023 Conference Paper

Replicable Bandits

• Hossein Esfandiari
• Alkis Kalavasis
• Amin Karbasi
• Andreas Krause 0001
• Vahab Mirrokni
• Grigoris Velegkas

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 environment is called replicable if it pulls, with high probability, the exact same sequence of arms in two different and independent executions (i.e., under independent reward realizations). We show that not only do replicable policies exist, but also they achieve almost the same optimal (non-replicable) regret bounds in terms of the time horizon. More specifically, in the stochastic multi-armed bandits setting, we develop a policy with an optimal problem-dependent regret bound whose dependence on the replicability parameter is also optimal. Similarly, for stochastic linear bandits (with finitely and infinitely many arms) we develop replicable policies that achieve the best-known problem-independent regret bounds with an optimal dependency on the replicability parameter. Our results show that even though randomization is crucial for the exploration-exploitation trade-off, an optimal balance can still be achieved while pulling the exact same arms in two different rounds of executions.

NeurIPS Conference 2023 Conference Paper

Replicable Clustering

• Hossein Esfandiari
• Amin Karbasi
• Vahab Mirrokni
• Grigoris Velegkas
• Felix Zhou

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 definition, a clustering algorithm is replicable if, with high probability, its output induces the exact same partition of the sample space after two executions on different inputs drawn from the same distribution, when its internal randomness is shared across the executions. We propose such algorithms for the statistical $k$-medians, statistical $k$-means, and statistical $k$-centers problems by utilizing approximation routines for their combinatorial counterparts in a black-box manner. In particular, we demonstrate a replicable $O(1)$-approximation algorithm for statistical Euclidean $k$-medians ($k$-means) with $\operatorname{poly}(d)$ sample complexity. We also describe an $O(1)$-approximation algorithm with an additional $O(1)$-additive error for statistical Euclidean $k$-centers, albeit with $\exp(d)$ sample complexity. In addition, we provide experiments on synthetic distributions in 2D using the $k$-means++ implementation from sklearn as a black-box that validate our theoretical results.

ICML Conference 2023 Conference Paper

Robust and 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 assume an adversary randomly chooses a constant fraction of the observed rewards in each batch, replacing them with arbitrary numbers. We present differentially private and robust variants of the arm elimination algorithm using logarithmic batch queries under two privacy models and provide regret bounds in both settings. In the first model, every reward in each round is reported by a potentially different client, which reduces to standard local differential privacy (LDP). In the second model, every action is "owned" by a different client, who may aggregate the rewards over multiple queries and privatize the aggregate response instead. To the best of our knowledge, our algorithms are the first simultaneously providing differential privacy and adversarial robustness in the stochastic linear bandits problem.

ICML Conference 2023 Conference Paper

Robust Budget Pacing with a Single Sample

• Santiago R. Balseiro
• Rachitesh Kumar
• Vahab Mirrokni
• Balasubramanian Sivan
• Di Wang 0005

Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent non-stationarity in an advertiser’s value and also competing advertisers’ values over time, a commonly used approach is to learn a target expenditure plan that specifies a target spend as a function of time, and then run a controller that tracks this plan. This raises the question: how many historical samples are required to learn a good expenditure plan? We study this question by considering an advertiser repeatedly participating in $T$ second-price auctions, where the tuple of her value and the highest competing bid is drawn from an unknown time-varying distribution. The advertiser seeks to maximize her total utility subject to her budget constraint. Prior work has shown the sufficiency of $T\log T$ samples per distribution to achieve the optimal $O(\sqrt{T})$-regret. We dramatically improve this state-of-the-art and show that just one sample per distribution is enough to achieve the near-optimal $\tilde O(\sqrt{T})$-regret, while still being robust to noise in the sampling distributions.

JMLR Journal 2023 Journal Article

Robust Load Balancing with Machine Learned Advice

• Sara Ahmadian
• Hossein Esfandiari
• Vahab Mirrokni
• Binghui Peng

Motivated by the exploding growth of web-based services and the importance of efficiently managing the computational resources of such systems, we introduce and study a theoretical model for load balancing of very large databases such as commercial search engines. Our model is a more realistic version of the well-received \bab model with an additional constraint that limits the number of servers that carry each piece of the data. This additional constraint is necessary when, on one hand, the data is so large that we can not copy the whole data on each server. On the other hand, the query response time is so limited that we can not ignore the fact that the number of queries for each piece of the data changes over time, and hence we can not simply split the data over different machines. In this paper, we develop an almost optimal load balancing algorithm that works given an estimate of the load of each piece of the data. Our algorithm is almost perfectly robust to wrong estimates, to the extent that even when all of the loads are adversarially chosen the performance of our algorithm is $1-1/e$, which is provably optimal. Along the way, we develop various techniques for analyzing the balls-into-bins process under certain correlations and build a novel connection with the multiplicative weights update scheme. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

ICLR Conference 2023 Conference Paper

Sequential Attention for Feature Selection

• Taisuke Yasuda 0002
• MohammadHossein Bateni
• Lin Chen
• Matthew Fahrbach
• Gang Fu
• Vahab Mirrokni

Feature selection is the problem of selecting a subset of features for a machine learning model that maximizes model quality subject to a budget constraint. For neural networks, prior methods, including those based on $\ell_1$ regularization, attention, and other techniques, typically select the entire feature subset in one evaluation round, ignoring the residual value of features during selection, i.e., the marginal contribution of a feature given that other features have already been selected. We propose a feature selection algorithm called Sequential Attention that achieves state-of-the-art empirical results for neural networks. This algorithm is based on an efficient one-pass implementation of greedy forward selection and uses attention weights at each step as a proxy for feature importance. We give theoretical insights into our algorithm for linear regression by showing that an adaptation to this setting is equivalent to the classical Orthogonal Matching Pursuit (OMP) algorithm, and thus inherits all of its provable guarantees. Our theoretical and empirical analyses offer new explanations towards the effectiveness of attention and its connections to overparameterization, which may be of independent interest.

TMLR Journal 2023 Journal Article

Tackling Provably Hard Representative Selection via Graph Neural Networks

• Mehran Kazemi
• Anton Tsitsulin
• Hossein Esfandiari
• MohammadHossein Bateni
• Deepak Ramachandran
• Bryan Perozzi
• Vahab Mirrokni

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 graphs, and focus on finding representative nodes that optimize the accuracy of a model trained on the selected representatives. Theoretically, we establish a new hardness result for RS (in the absence of a graph structure) by proving that a particular, highly practical variant of it (RS for Learning) is hard to approximate in polynomial time within any reasonable factor, which implies a significant potential gap between the optimum solution of widely-used surrogate functions and the actual accuracy of the model. We then study the setting where a (homophilous) graph structure is available, or can be constructed, between the data points. We show that with an appropriate modeling approach, the presence of such a structure can turn a hard RS (for learning) problem into one that can be effectively solved. To this end, we develop RS-GNN, a representation learning-based RS model based on Graph Neural Networks. Empirically, we demonstrate the effectiveness of RS-GNN on problems with predefined graph structures as well as problems with graphs induced from node feature similarities, by showing that RS-GNN achieves significant improvements over established baselines on a suite of eight benchmarks.

SODA Conference 2022 Conference Paper

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 of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al. [11]. Specifically, we focus on the k -means and k -median problems and provide nearly tight upper and lower bounds. First, we provide an O (log k log log k )-approximation algorithm for explainable k -median, improving on the best known algorithm of O ( k ) [11] and nearly matching the known Ω(log k ) lower bound [11]. In addition, in low-dimensional spaces d ≪ log k, we show that our algorithm also provides an O ( d log 2 d )-approximate solution for explainable k -median. This improves over the best known bound of O(d log k ) for low dimensions [19], and is a constant for constant dimensional spaces. To complement this, we show a nearly matching Ω( d ) lower bound. Next, we study the k -means problem in this context and provide an O ( k log k )-approximation algorithm for explainable k -means, improving over the O ( k 2 ) bound of Dasgupta et al. and the O(dk log k ) bound of [19]. To complement this we provide an almost tight Ω( k ) lower bound, improving over the Ω(log k ) lower bound of Dasgupta et al. Given an approximate solution to the classic k -means and k -median, our algorithm for k -median runs in time O ( kd log 2 k ) and our algorithm for k -means runs in time O(k 2 d ).

NeurIPS Conference 2022 Conference Paper

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 obey the standard $k$-anonymity constraint by requiring each observation to be an aggregation of rewards for at least $k$ users. This provides a simple yet effective framework where one can learn a clustering of users in an online fashion without observing any user's individual decision. We initiate the study of anonymous bandits and provide the first sublinear regret algorithms and lower bounds for this setting.

NeurIPS Conference 2022 Conference Paper

Cluster Randomized Designs for One-Sided Bipartite Experiments

• Jennifer Brennan
• Vahab Mirrokni
• Jean Pouget-Abadie

The conclusions of randomized controlled trials may be biased when the outcome of one unit depends on the treatment status of other units, a problem known as \textit{interference}. In this work, we study interference in the setting of one-sided bipartite experiments in which the experimental units---where treatments are randomized and outcomes are measured---do not interact directly. Instead, their interactions are mediated through their connections to \textit{interference units} on the other side of the graph. Examples of this type of interference are common in marketplaces and two-sided platforms. The \textit{cluster-randomized design} is a popular method to mitigate interference when the graph is known, but it has not been well-studied in the one-sided bipartite experiment setting. In this work, we formalize a natural model for interference in one-sided bipartite experiments using the exposure mapping framework. We first exhibit settings under which existing cluster-randomized designs fail to properly mitigate interference under this model. We then show that minimizing the bias of the difference-in-means estimator under our model results in a balanced partitioning clustering objective with a natural interpretation. We further prove that our design is minimax optimal over the class of linear potential outcomes models with bounded interference. We conclude by providing theoretical and experimental evidence of the robustness of our design to a variety of interference graphs and potential outcomes models.

NeurIPS Conference 2022 Conference Paper

Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank

• Alessandro Epasto
• Vahab Mirrokni
• Bryan Perozzi
• Anton Tsitsulin
• Peilin Zhong

Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of graph representations such as node ranking, labeling, and graph embedding. However, while data privacy is one of the most important recent concerns, existing PPR algorithms are not designed to protect user privacy. PPR is highly sensitive to the input graph edges: the difference of only one edge may cause a big change in the PPR vector, potentially leaking private user data. In this work, we propose an algorithm which outputs an approximate PPR and has provably bounded sensitivity to input edges. In addition, we prove that our algorithm achieves similar accuracy to non-private algorithms when the input graph has large degrees. Our sensitivity-bounded PPR directly implies private algorithms for several tools of graph learning, such as, differentially private (DP) PPR ranking, DP node classification, and DP node embedding. To complement our theoretical analysis, we also empirically verify the practical performances of our algorithms.

NeurIPS Conference 2022 Conference Paper

Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth

• Laxman Dhulipala
• David Eisenstat
• Jakub Lacki
• Vahab Mirrokni
• Jessica Shi

Obtaining scalable algorithms for \emph{hierarchical agglomerative clustering} (HAC) is of significant interest due to the massive size of real-world datasets. At the same time, efficiently parallelizing HAC is difficult due to the seemingly sequential nature of the algorithm. In this paper, we address this issue and present ParHAC, the first efficient parallel HAC algorithm with sublinear depth for the widely-used average-linkage function. In particular, we provide a $(1+\epsilon)$-approximation algorithm for this problem on $m$ edge graphs using $\tilde{O}(m)$ work and poly-logarithmic depth. Moreover, we show that obtaining similar bounds for \emph{exact} average-linkage HAC is not possible under standard complexity-theoretic assumptions. We complement our theoretical results with a comprehensive study of the ParHAC algorithm in terms of its scalability, performance, and quality, and compare with several state-of-the-art sequential and parallel baselines. On a broad set of large publicly-available real-world datasets, we find that ParHAC obtains a 50. 1x speedup on average over the best sequential baseline, while achieving quality similar to the exact HAC algorithm. We also show that ParHAC can cluster one of the largest publicly available graph datasets with 124 billion edges in a little over three hours using a commodity multicore machine.

STOC Conference 2022 Conference Paper

Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets

• Vincent Cohen-Addad
• Hossein Esfandiari
• Vahab Mirrokni
• Shyam Narayanan

Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean k -median and k -means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward. Our algorithm achieves an approximation ratio of 2.406 and 5.912 for Euclidean k -median and k -means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat.

SODA Conference 2022 Conference Paper

Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches

• Alessandro Epasto
• Mohammad Mahdian
• Vahab Mirrokni
• Peilin Zhong

Streaming computation plays an important role in large-scale data analysis. The sliding window model is a model of streaming computation which also captures the recency of the data. In this model, data arrives one item at a time, but only the latest W data items are considered for a particular problem. The goal is to output a good solution at the end of the stream by maintaining a small summary during the stream. In this work, we propose a new algorithmic framework for designing efficient sliding window algorithms via bucketing-based sketches. Based on this new framework, we develop space-efficient sliding window algorithms for k -cover, k -clustering and diversity maximization problems. For each of the above problems, our algorithm achieves (1 ± ∊ )-approximation. Compared with the previous work, it improves both the approximation ratio and the space.

SODA Conference 2022 Conference Paper

Massively Parallel and Dynamic Algorithms for Minimum Size Clustering

• Alessandro Epasto
• Mohammad Mahdian
• Vahab Mirrokni
• Peilin Zhong

Clustering of data in metric spaces is a fundamental problem and has many applications in data mining and it is often used as an unsupervised learning tool inside other machine learning systems. In many scenarios where we are concerned with the privacy implications of clustering users, clusters are required to have minimum-size constraint. A canonical example of min-size clustering is in enforcing anonymization and the protection of the privacy of user data. Our work is motivated by real-world applications (such as the Federated Learning of Cohorts project–FLoC) where a min size clustering algorithm needs to handle very large amount of data and the data may also change over time. Thus efficient parallel or dynamic algorithms are desired. In this paper, we study the r -gather problem, a natural formulation of minimum-size clustering in metric spaces. The goal of r -gather is to partition n points into clusters such that each cluster has size at least r, and the maximum radius of the clusters is minimized. This additional constraint completely changes the algorithmic nature of the problem, and many clustering techniques fail. Also previous dynamic and parallel algorithms do not achieve desirable complexity. We propose algorithms both in the Massively Parallel Computation (MPC) model and in the dynamic setting. Our MPC algorithm handles input points from the Euclidean space ℝ d. It computes an O (1)-approximate solution of r -gather in O (log ∊ n ) rounds using total space O(n 1 + γ · d ) for arbitrarily small constants ∊, γ > 0. In addition our algorithm is fully scalable, i. e. , there is no lower bound on the memory per machine. Our dynamic algorithm maintains an O (1)-approximate r -gather solution under insertions/deletions of points in a metric space with doubling dimension d. The update time is r ·2 O ( d ) ·log O (1) Λ and the query time is 2 O ( d ) · log O (1) Λ, where Λ is the ratio between the largest and the smallest distance. To obtain our results, we reveal connections between r -gather and r -nearest neighbors and provide several geometric and graph algorithmic tools including a near neighbor graph construction, and results on the maximal independent set / ruling set of the power graph in the MPC model, which might be both of independent interest. To show their generality, we extend our algorithm to solve several variants of r -gather in the MPC model, including r -gather with outliers and r -gather with total distance cost. Finally, we show effectiveness of these algorithmic techniques via a preliminary empirical study for Interest-Based Advertisement applications.

ICML Conference 2022 Conference Paper

Massively Parallel k-Means Clustering for Perturbation Resilient Instances

• Vincent Cohen-Addad
• Vahab Mirrokni
• Peilin Zhong

We consider $k$-means clustering of $n$ data points in Euclidean space in the Massively Parallel Computation (MPC) model, a computational model which is an abstraction of modern massively parallel computing system such as MapReduce. Recent work provides evidence that getting $O(1)$-approximate $k$-means solution for general input points using $o(\log n)$ rounds in the MPC model may be impossible under certain conditions [Ghaffari, Kuhn \& Uitto’2019]. However, the real-world data points usually have better structures. One instance of interest is the set of data points which is perturbation resilient [Bilu \& Linial’2010]. In particular, a point set is $\alpha$-perturbation resilient for $k$-means if perturbing pairwise distances by multiplicative factors in the range $[1, \alpha]$ does not change the optimum $k$-means clusters. We bypass the worst case lower bound by considering the perturbation resilient input points and showing $o(\log n)$ rounds $k$-means clustering algorithms for these instances in the MPC model. Specifically, we show a fully scalable $(1+\varepsilon)$-approximate $k$-means clustering algorithm for $O(\alpha)$-perturbation resilient instance in the MPC model using $O(1)$ rounds and ${O}_{\varepsilon, d}(n^{1+1/\alpha^2+o(1)})$ total space. If the space per machine is sufficiently larger than $k$, i. e. , at least $k\cdot n^{\Omega(1)}$, we also develop an optimal $k$-means clustering algorithm for $O(\alpha)$-perturbation resilient instance in MPC using $O(1)$ rounds and ${O}_d(n^{1+o(1)}\cdot(n^{1/\alpha^2}+k))$ total space.

NeurIPS Conference 2022 Conference Paper

Near-Optimal Private and Scalable $k$-Clustering

• Vincent Cohen-Addad
• Alessandro Epasto
• Vahab Mirrokni
• Shyam Narayanan
• Peilin Zhong

We study the differentially private (DP) $k$-means and $k$-median clustering problems of $n$ points in $d$-dimensional Euclidean space in the massively parallel computation (MPC) model. We provide two near-optimal algorithms where the near-optimality is in three aspects: they both achieve (1). $O(1)$ parallel computation rounds, (2). near-linear in $n$ and polynomial in $k$ total computational work (i. e. , near-linear running time when $n$ is a sufficient polynomial in $k$), (3). $O(1)$ relative approximation and $\text{poly}(k, d)$ additive error. Note that $\Omega(1)$ relative approximation is provably necessary even for any polynomial-time non-private algorithm, and $\Omega(k)$ additive error is a provable lower bound for any polynomial-time DP $k$-means/median algorithm. Our two algorithms provide a tradeoff between the relative approximation and the additive error: the first has $O(1)$ relative approximation and $\sim (k^{2. 5} + k^{1. 01} \sqrt{d})$ additive error, and the second one achieves $(1+\gamma)$ relative approximation to the optimal non-private algorithm for an arbitrary small constant $\gamma>0$ and with $\text{poly}(k, d)$ additive error for a larger polynomial dependence on $k$ and $d$. To achieve our result, we develop a general framework which partitions the data and reduces the DP clustering problem for the entire dataset to the DP clustering problem for each part. To control the blow-up of the additive error introduced by each part, we develop a novel charging argument which might be of independent interest.

NeurIPS Conference 2022 Conference Paper

Posted Pricing and Dynamic Prior-independent Mechanisms with Value Maximizers

• Yuan Deng
• Vahab Mirrokni
• Hanrui Zhang

We study posted price auctions and dynamic prior-independent mechanisms for (ROI-constrained) value maximizers. In contrast to classic (quasi-linear) utility maximizers, these agents aim to maximize their total value subject to a minimum ratio of value per unit of payment made. When personalized posted prices are allowed, posted price auctions for value maximizers can be reduced to posted price auctions for utility maximizers. However, for anonymous posted prices, the well-known $\frac 1 2$ approximation for utility maximizers is impossible for value maximizers and we provide a posted price mechanism with $\frac12(1 - 1/e)$ approximation. Moreover, we demonstrate how to apply our results to design prior-independent mechanisms in a dynamic environment; and to the best of our knowledge, this gives the first constant revenue approximation with multiple value maximizers. Finally, we provide an extension to combinatorial auctions with submodular / XOS agents.

SODA Conference 2022 Conference Paper

Robust Load Balancing with Machine Learned Advice

• Sara Ahmadian
• Hossein Esfandiari
• Vahab Mirrokni
• Binghui Peng

Motivated by the exploding growth of web-based services and the importance of efficiently managing the computational resources of such systems, we introduce and study a theoretical model for load balancing of very large databases such as commercial search engines. Our model is a more realistic version of the well-received balls-into-bins model with an additional constraint that limits the number of servers that carry each piece of the data. This additional constraint is necessary when, on one hand, the data is so large that we can not copy the whole data on each server. On the other hand, the query response time is so limited that we can not ignore the fact that the number of queries for each piece of the data changes over time, and hence we can not simply split the data over different machines In this paper, we develop an almost optimal load balancing algorithm that works given an estimate of the load of each piece of the data. Our algorithm is almost perfectly robust to wrong estimates, to the extent that even when all of the loads are adversarially chosen the performance of our algorithm is 1–1/ e, which is provably optimal. Along the way, we develop various techniques for analyzing the balls-into-bins process under certain correlations and build a novel connection with the multiplicative weights update scheme.

NeurIPS Conference 2022 Conference Paper

Stars: Tera-Scale Graph Building for Clustering and Learning

• CJ Carey
• Jonathan Halcrow
• Rajesh Jayaram
• Vahab Mirrokni
• Warren Schudy
• Peilin Zhong

A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, classification, graph learning, and nearest neighbor search. For these tasks, it is critical to build graphs which are sparse yet still representative of the underlying data. The benefits of sparsity are twofold: firstly, constructing dense graphs is infeasible in practice for large datasets, and secondly, the runtime of downstream tasks is directly influenced by the sparsity of the similarity graph. In this work, we present Stars: a highly scalable method for building extremely sparse graphs via two-hop spanners, which are graphs where similar points are connected by a path of length at most two. Stars can construct two-hop spanners with significantly fewer similarity comparisons, which are a major bottleneck for learning based models where comparisons are expensive to evaluate. Theoretically, we demonstrate that Stars builds a graph in nearly-linear time, where approximate nearest neighbors are contained within two-hop neighborhoods. In practice, we have deployed Stars for multiple data sets allowing for graph building at the Tera-Scale, i. e. , for graphs with hundreds of billions of nodes and tens of trillions of edges. We evaluate the performance of Stars for clustering and graph learning, and demonstrate 10~1000-fold improvements in pairwise similarity comparisons and significant running time speedups with negligible quality loss.

ICML Conference 2022 Conference Paper

Tight and Robust Private Mean Estimation with Few Users

• Shyam Narayanan
• Vahab Mirrokni
• Hossein Esfandiari

In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an $(\varepsilon, \delta)$-differentially private mechanism using as few users as possible. In particular, we provide a nearly optimal trade-off between the number of users and the number of samples per user required for private mean estimation, even when the number of users is as low as $O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$. Interestingly, this bound on the number of users is independent of the dimension (though the number of samples per user is allowed to depend polynomially on the dimension), unlike the previous work that requires the number of users to depend polynomially on the dimension. This resolves a problem first proposed by Amin et al. (2019). Moreover, our mechanism is robust against corruptions in up to $49%$ of the users. Finally, our results also apply to optimal algorithms for privately learning discrete distributions with few users, answering a question of Liu et al. (2020), and a broader range of problems such as stochastic convex optimization and a variant of stochastic gradient descent via a reduction to differentially private mean estimation.

AAAI Conference 2021 Conference Paper

Almost Linear Time Density Level Set Estimation via DBSCAN

• Hossein Esfandiari
• Vahab Mirrokni
• Peilin Zhong

In this work we focus on designing a fast algorithm for λdensity level set estimation via DBSCAN clustering. Previous work (Jiang ICML’17, and Jang and Jiang ICML’19) shows that under some natural assumptions DBSCAN and its variant DBSCAN++ can be used to estimate the λ-density level set with near-optimal Hausdorff distance, i. e. , with rate e O(n−1/(2β+D) ). However, to achieve this near-optimal rate, the current fastest DBSCAN algorithm needs near quadratic running time. This running time is not practical for large datasets. Usually when we are working with large datasets we desire linear or almost linear time algorithms. With this motivation, in this work, we present a modified DBSCAN algorithm with near optimal Hausdorff distance for density level set estimation with e O(n) running time. In our empirical study, we show that our algorithm provides significant speedup over the previous algorithms, while achieving comparable solution quality.

AAAI Conference 2021 Conference Paper

Extreme k-Center Clustering

• MohammadHossein Bateni
• Hossein Esfandiari
• Manuela Fischer
• Vahab Mirrokni

Metric clustering is a fundamental primitive in machine learning with several applications for mining massive datasets. An important example of metric clustering is the k-center problem. While this problem has been extensively studied in distributed settings, all previous algorithms use Ω(k) space per machine and Ω(nk) total work. In this paper, we develop the first highly scalable approximation algorithm for k-center clustering, with e O(nε ) space per machine and e O(n1+ ) total work, for arbitrary small constant ε. It produces an O(log log log n)approximate solution with k(1+o(1)) centers in O(log log n) rounds of computation.

ICML Conference 2021 Conference Paper

Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time

• Laxman Dhulipala
• David Eisenstat
• Jakub Lacki
• Vahab Mirrokni
• Jessica Shi 0001

We study the widely-used hierarchical agglomerative clustering (HAC) algorithm on edge-weighted graphs. We define an algorithmic framework for hierarchical agglomerative graph clustering that provides the first efficient $\tilde{O}(m)$ time exact algorithms for classic linkage measures, such as complete- and WPGMA-linkage, as well as other measures. Furthermore, for average-linkage, arguably the most popular variant of HAC, we provide an algorithm that runs in $\tilde{O}(n\sqrt{m})$ time. For this variant, this is the first exact algorithm that runs in subquadratic time, as long as $m=n^{2-\epsilon}$ for some constant $\epsilon > 0$. We complement this result with a simple $\epsilon$-close approximation algorithm for average-linkage in our framework that runs in $\tilde{O}(m)$ time. As an application of our algorithms, we consider clustering points in a metric space by first using $k$-NN to generate a graph from the point set, and then running our algorithms on the resulting weighted graph. We validate the performance of our algorithms on publicly available datasets, and show that our approach can speed up clustering of point datasets by a factor of 20. 7–76. 5x.

SODA Conference 2021 Conference Paper

Non-Excludable Dynamic Mechanism Design

• Santiago R. Balseiro
• Vahab Mirrokni
• Renato Paes Leme
• Song Zuo

Dynamic mechanism design expands the scope of allocations that can be implemented and the performance that can be attained compared to static mechanisms. Even under stringent participation constraints and restrictions on transfers, recent work demonstrated that it is possible for a designer to extract the surplus of all players as revenue when players have quasilinear utilities and the number of interactions is large. Much of the analysis has focused on excludable environments (i. e. , any player can be excluded from trade without affecting the utilities of others). The mechanisms presented in the literature, however, do not extend to non-excludable environments. Two prototypical examples of such environments are: (i) public projects, where all players must have the same allocation; and (ii) non-disposable goods, where each item must be allocated to some player. We show a general mechanism that can asymptotically extract full surplus as revenue in such environments. Moreover, we provide a tight characterization for general environments, and identify necessary and sufficient conditions on the possibility of asymptotic full surplus extraction. Our characterization is based on the geometry of achievable utility sets – convex sets that delineate the expected utilities that can be implemented by static mechanisms. Our results provide a reduction from dynamic to static mechanism design: the geometry of the achievable utility set of static mechanisms determines whether it is possible to fully extract surplus in the limit.

NeurIPS Conference 2021 Conference Paper

Parallelizing Thompson Sampling

• Amin Karbasi
• Vahab Mirrokni
• Mohammad Shadravan

How can we make use of information parallelism in online decision-making problems while efficiently balancing the exploration-exploitation trade-off? In this paper, we introduce a batch Thompson Sampling framework for two canonical online decision-making problems with partial feedback, namely, stochastic multi-arm bandit and linear contextual bandit. Over a time horizon $T$, our batch Thompson Sampling policy achieves the same (asymptotic) regret bound of a fully sequential one while carrying out only $O(\log T)$ batch queries. To achieve this exponential reduction, i. e. , reducing the number of interactions from $T$ to $O(\log T)$, our batch policy dynamically determines the duration of each batch in order to balance the exploration-exploitation trade-off. We also demonstrate experimentally that dynamic batch allocation outperforms natural baselines.

AAAI Conference 2021 Conference Paper

Regret Bounds for Batched Bandits

• Hossein Esfandiari
• Amin Karbasi
• Abbas Mehrabian
• Vahab Mirrokni

We present simple algorithms for batched stochastic multiarmed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets that improve and extend the best known regret bounds of Gao, Han, Ren, and Zhou (NeurIPS 2019), for any number of batches. In particular, our algorithms in both settings achieve the optimal expected regrets by using only a logarithmic number of batches. We also study the batched adversarial multi-armed bandit problem for the first time and provide the optimal regret, up to logarithmic factors, of any algorithm with predetermined batch sizes.

ICML Conference 2021 Conference Paper

Regularized Online Allocation Problems: Fairness and Beyond

• Santiago R. Balseiro
• Haihao Lu
• Vahab Mirrokni

Online allocation problems with resource constraints have a rich history in computer science and operations research. In this paper, we introduce the regularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize total rewards and the value of the regularizer subject to the resource constraints. Our primary motivation is the online allocation of internet advertisements wherein firms seek to maximize additive objectives such as the revenue or efficiency of the allocation. By introducing a regularizer, firms can account for the fairness of the allocation or, alternatively, punish under-delivery of advertisements—two common desiderata in internet advertising markets. We design an algorithm when arrivals are drawn independently from a distribution that is unknown to the decision maker. Our algorithm is simple, fast, and attains the optimal order of sub-linear regret compared to the optimal allocation with the benefit of hindsight. Numerical experiments confirm the effectiveness of the proposed algorithm and of the regularizers in an internet advertising application.

ICML Conference 2021 Conference Paper

Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing

• Yuan Deng
• Sébastien Lahaie
• Vahab Mirrokni
• Song Zuo

Online advertisements are primarily sold via repeated auctions with reserve prices. In this paper, we study how to set reserves to boost revenue based on the historical bids of strategic buyers, while controlling the impact of such a policy on the incentive compatibility of the repeated auctions. Adopting an incentive compatibility metric which quantifies the incentives to shade bids, we propose a novel class of reserve pricing policies and provide analytical tradeoffs between their revenue performance and bid-shading incentives. The policies are inspired by the exponential mechanism from the literature on differential privacy, but our study uncovers mechanisms with significantly better revenue-incentive tradeoffs than the exponential mechanism in practice. We further empirically evaluate the tradeoffs on synthetic data as well as real ad auction data from a major ad exchange to verify and support our theoretical findings.

NeurIPS Conference 2021 Conference Paper

Robust Auction Design in the Auto-bidding World

• Santiago Balseiro
• Yuan Deng
• Jieming Mao
• Vahab Mirrokni
• Song Zuo

In classic auction theory, reserve prices are known to be effective for improving revenue for the auctioneer against quasi-linear utility maximizing bidders. The introduction of reserve prices, however, usually do not help improve total welfare of the auctioneer and the bidders. In this paper, we focus on value maximizing bidders with return on spend constraints---a paradigm that has drawn considerable attention recently as more advertisers adopt auto-bidding algorithms in advertising platforms---and show that the introduction of reserve prices has a novel impact on the market. Namely, by choosing reserve prices appropriately the auctioneer can improve not only the total revenue but also the total welfare. Our results also demonstrate that reserve prices are robust to bidder types, i. e. , reserve prices work well for different bidder types, such as value maximizers and utility maximizers, without using bidder type information. We generalize these results for a variety of auction mechanisms such as VCG, GSP, and first-price auctions. Moreover, we show how to combine these results with additive boosts to improve the welfare of the outcomes of the auction further. Finally, we complement our theoretical observations with an empirical study confirming the effectiveness of these ideas using data from online advertising auctions.

NeurIPS Conference 2021 Conference Paper

Synthetic Design: An Optimization Approach to Experimental Design with Synthetic Controls

• Nick Doudchenko
• Khashayar Khosravi
• Jean Pouget-Abadie
• Sébastien Lahaie
• Miles Lubin
• Vahab Mirrokni
• Jann Spiess
• Guido Imbens

We investigate the optimal design of experimental studies that have pre-treatment outcome data available. The average treatment effect is estimated as the difference between the weighted average outcomes of the treated and control units. A number of commonly used approaches fit this formulation, including the difference-in-means estimator and a variety of synthetic-control techniques. We propose several methods for choosing the set of treated units in conjunction with the weights. Observing the NP-hardness of the problem, we introduce a mixed-integer programming formulation which selects both the treatment and control sets and unit weightings. We prove that these proposed approaches lead to qualitatively different experimental units being selected for treatment. We use simulations based on publicly available data from the US Bureau of Labor Statistics that show improvements in terms of mean squared error and statistical power when compared to simple and commonly used alternatives such as randomized trials.

ICML Conference 2020 Conference Paper

Bandits with Adversarial Scaling

• Thodoris Lykouris
• Vahab Mirrokni
• Renato Paes Leme

We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest.

NeurIPS Conference 2020 Conference Paper

Contextual Reserve Price Optimization in Auctions via Mixed Integer Programming

• Joey Huchette
• Haihao Lu
• Hossein Esfandiari
• Vahab Mirrokni

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. First, we show that it is not possible to solve this problem in polynomial time unless the Exponential Time Hypothesis fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. Moreover, we show that this MIP formulation is ideal (i. e. the strongest possible formulation) for the revenue function of a single impression. Since it can be computationally expensive to exactly solve the MIP formulation in practice, we also study the performance of its linear programming (LP) relaxation. Though it may work well in practice, we show that, unfortunately, in the worst case the optimal objective of the LP relaxation can be O(number of samples) times larger than the optimal objective of the true problem. Finally, we present computational results, showcasing that the MIP formulation, along with its LP relaxation, are able to achieve superior in- and out-of-sample performance, as compared to state-of-the-art algorithms on both real and synthetic datasets. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems.

ICML Conference 2020 Conference Paper

Dual Mirror Descent for Online Allocation Problems

• Santiago R. Balseiro
• Haihao Lu
• Vahab Mirrokni

We consider online allocation problems with concave revenue functions and resource constraints, which are central problems in revenue management and online advertising. In these settings, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates revenue. The revenue function and resource consumption of each request are drawn independently and at random from a probability distribution that is unknown to the decision maker. The objective is to maximize cumulative revenues subject to a constraint on the total consumption of resources. We design a general class of algorithms that achieve sub-linear expected regret compared to the hindsight optimal allocation. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover dual sub-gradient descent and dual exponential weights algorithm. The resulting algorithms are simple, efficient, and shown to attain the optimal order of regret when the length of the horizon and the initial number of resources are scaled proportionally. We discuss applications to online bidding in repeated auctions with budget constraints and online proportional matching with high entropy.

SODA Conference 2020 Conference Paper

Fully Dynamic Matching: Beating 2-Approximation in Δ ϵ Update Time

• Soheil Behnezhad
• Jakub Lacki
• Vahab Mirrokni

In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a 2 – Ω(1) approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant ϵ > 0, there is a randomized algorithm that with high probability maintains a 2 – Ω(1) approximate maximum matching of a fully-dynamic general graph in worst-case update time O (Δ ϵ + polylog n ), where Δ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had O ( m 1/4 ) update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time O ( n ϵ ) was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].

NeurIPS Conference 2020 Conference Paper

Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions

• Alessandro Epasto
• Mohammad Mahdian
• Vahab Mirrokni
• Emmanouil Zampetakis

A soft-max function has two main efficiency measures: (1) approximation - which corresponds to how well it approximates the maximum function, (2) smoothness - which shows how sensitive it is to changes of its input. Our goal is to identify the optimal approximation-smoothness tradeoffs for different measures of approximation and smoothness. This leads to novel soft-max functions, each of which is optimal for a different application. The most commonly used soft-max function, called exponential mechanism, has optimal tradeoff between approximation measured in terms of expected additive approximation and smoothness measured with respect to Renyi Divergence. We introduce a soft-max function, called piece-wise linear soft-max, with optimal tradeoff between approximation, measured in terms of worst-case additive approximation and smoothness, measured with respect to l_q-norm. The worst-case approximation guarantee of the piece-wise linear mechanism enforces sparsity in the output of our soft-max function, a property that is known to be important in Machine Learning applications Martins et al. 16, Laha et al. 18 and is not satisfied by the exponential mechanism. Moreover, the l_q-smoothness is suitable for applications in Mechanism Design and Game Theory where the piece-wise linear mechanism outperforms the exponential mechanism. Finally, we investigate another soft-max function, called power mechanism, with optimal tradeoff between expected multiplicative approximation and smoothness with respect to the Renyi Divergence, which provides improved theoretical and practical results in differentially private submodular optimization.

ICML Conference 2020 Conference Paper

Robust Pricing in Dynamic Mechanism Design

• Yuan Deng
• Sébastien Lahaie
• Vahab Mirrokni

Motivated by the repeated sale of online ads via auctions, optimal pricing in repeated auctions has attracted a large body of research. While dynamic mechanisms offer powerful techniques to improve on both revenue and efficiency by optimizing auctions across different items, their reliance on exact distributional information of buyers’ valuations (present and future) limits their use in practice. In this paper, we propose robust dynamic mechanism design. We develop a new framework to design dynamic mechanisms that are robust to both estimation errors in value distributions and strategic behavior. We apply the framework in learning environments, leading to the first policy that achieves provably low regret against the optimal dynamic mechanism in contextual auctions, where the dynamic benchmark has full and accurate distributional information.

NeurIPS Conference 2020 Conference Paper

Smoothly Bounding User Contributions in Differential Privacy

• Alessandro Epasto
• Mohammad Mahdian
• Jieming Mao
• Vahab Mirrokni
• Lijie Ren

A differentially private algorithm guarantees that the input of a single user won’t significantly change the output distribution of the algorithm. When a user contributes more data points, more information can be collected to improve the algorithm’s performance. But at the same time, more noise might need to be added to the algorithm in order to keep the algorithm differentially private and this might hurt the algorithm’s performance. Amin et al. (2019) initiates the study on bounding user contributions and proposes a very natural algorithm which limits the number of samples each user can contribute by a threshold. For a better trade-off between utility and privacy guarantee, we propose a method which smoothly bounds user contributions by setting appropriate weights on data points and apply it to estimating the mean/quantiles, linear regression, and empirical risk minimization. We show that our algorithm provably outperforms the sample limiting algorithm. We conclude with experimental evaluations which validate our theoretical results.

NeurIPS Conference 2019 Conference Paper

A Robust Non-Clairvoyant Dynamic Mechanism for Contextual Auctions

• Yuan Deng
• Sébastien Lahaie
• Vahab Mirrokni

Dynamic mechanisms offer powerful techniques to improve on both revenue and efficiency by linking sequential auctions using state information, but these techniques rely on exact distributional information of the buyers’ valuations (present and future), which limits their use in learning settings. In this paper, we consider the problem of contextual auctions where the seller gradually learns a model of the buyer's valuation as a function of the context (e. g. , item features) and seeks a pricing policy that optimizes revenue. Building on the concept of a bank account mechanism---a special class of dynamic mechanisms that is known to be revenue-optimal---we develop a non-clairvoyant dynamic mechanism that is robust to both estimation errors in the buyer's value distribution and strategic behavior on the part of the buyer. We then tailor its structure to achieve a policy with provably low regret against a constant approximation of the optimal dynamic mechanism in contextual auctions. Our result substantially improves on previous results that only provide revenue guarantees against static benchmarks.

ICML Conference 2019 Conference Paper

Categorical Feature Compression via Submodular Optimization

• MohammadHossein Bateni
• Lin Chen
• Hossein Esfandiari
• Thomas Fu
• Vahab Mirrokni
• Afshin Rostamizadeh

In the era of big data, learning from categorical features with very large vocabularies (e. g. , 28 million for the Criteo click prediction dataset) has become a practical challenge for machine learning researchers and practitioners. We design a highly-scalable vocabulary compression algorithm that seeks to maximize the mutual information between the compressed categorical feature and the target binary labels and we furthermore show that its solution is guaranteed to be within a $1-1/e \approx 63%$ factor of the global optimal solution. Although in some settings, entropy-based set functions are known to be submodular, this is not the case for the mutual information objective we consider (mutual information with respect to the target labels). To address this, we introduce a novel re-parametrization of the mutual information objective, which we prove is submodular, and also design a data structure to query the submodular function in amortized $O(\log n )$ time (where $n$ is the input vocabulary size). Our complete algorithm is shown to operate in $O(n \log n )$ time. Additionally, we design a distributed implementation in which the query data structure is decomposed across $O(k)$ machines such that each machine only requires $O(\frac n k)$ space, while still preserving the approximation guarantee and using only logarithmic rounds of computation. We also provide analysis of simple alternative heuristic compression methods to demonstrate they cannot achieve any approximation guarantee. Using the large-scale Criteo learning task, we demonstrate better performance in retaining mutual information and also verify competitive learning performance compared to other baseline methods.

NeurIPS Conference 2019 Conference Paper

Contextual Bandits with Cross-Learning

• Santiago Balseiro
• Negin Golrezaei
• Mohammad Mahdian
• Vahab Mirrokni
• Jon Schneider

In the classical contextual bandits problem, in each round $t$, a learner observes some context $c$, chooses some action $a$ to perform, and receives some reward $r_{a, t}(c)$. We consider the variant of this problem where in addition to receiving the reward $r_{a, t}(c)$, the learner also learns the values of $r_{a, t}(c')$ for all other contexts $c'$; i. e. , the rewards that would have been achieved by performing that action under different contexts. This variant arises in several strategic settings, such as learning how to bid in non-truthful repeated auctions (in this setting the context is the decision maker's private valuation for each auction). We call this problem the contextual bandits problem with cross-learning. The best algorithms for the classical contextual bandits problem achieve $\tilde{O}(\sqrt{CKT})$ regret against all stationary policies, where $C$ is the number of contexts, $K$ the number of actions, and $T$ the number of rounds. We demonstrate algorithms for the contextual bandits problem with cross-learning that remove the dependence on $C$ and achieve regret $\tilde{O}(\sqrt{KT})$ (when contexts are stochastic with known distribution), $\tilde{O}(K^{1/3}T^{2/3})$ (when contexts are stochastic with unknown distribution), and $\tilde{O}(\sqrt{KT})$ (when contexts are adversarial but rewards are stochastic). We simulate our algorithms on real auction data from an ad exchange running first-price auctions (showing that they outperform traditional contextual bandit algorithms).

SODA Conference 2019 Conference Paper

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

• Sepehr Assadi
• MohammadHossein Bateni
• Aaron Bernstein
• Vahab Mirrokni
• Cliff Stein 0001

There is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on massive graphs. For massive inputs, several different computational models have been introduced, including the streaming model, the distributed communication model, and the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In each model, algorithms are analyzed in terms of resources such as space used or rounds of communication needed, in addition to the more traditional approximation ratio. In this paper, we give a single unified approach that yields better approximation algorithms for matching and vertex cover in all these models. The highlights include: The first one pass, significantly-better-than-2-approximation for matching in random arrival streams that uses subquadratic space, namely a (1. 5 + ε )-approximation streaming algorithm that uses Õ ( n 15 ) space for constant ε > 0. The first 2-round, better-than-2-approximation for matching in the MPC model that uses subquadratic space per machine, namely a (1. 5 + ε )-approximation algorithm with memory per machine for constant ε > 0. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a (1+ ∊ )-approximation to matching and an O (1)-approximation to vertex cover in only O (log log n ) MPC rounds and O ( n /polylog( n )) memory per machine. These results settle multiple open questions posed by Czumaj et al. [STOC 2018]. We obtain our results by a novel combination of two previously disjoint set of techniques, namely randomized composable coresets and edge degree constrained subgraphs (EDCS). We significantly extend the power of these techniques and prove several new structural results. For example, we show that an EDCS is a sparse certificate for large matchings and small vertex covers that is quite robust to sampling and composition.

ICML Conference 2019 Conference Paper

Distributed Weighted Matching via Randomized Composable Coresets

• Sepehr Assadi
• MohammadHossein Bateni
• Vahab Mirrokni

Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms has been challenging due to the sequential nature of efficient algorithms for this problem. In this paper, we develop a simple distributed algorithm for the problem on general graphs with approximation guarantee of 2 + eps that (nearly) matches that of the sequential greedy algorithm. A key advantage of this algorithm is that it can be easily implemented in only two rounds of computation in modern parallel computation frameworks such as MapReduce. We also demonstrate the efficiency of our algorithm in practice on various graphs (some with half a trillion edges) by achieving objective values always close to what is achievable in the centralized setting.

SODA Conference 2019 Conference Paper

Dynamic Double Auctions: Towards First Best

• Santiago R. Balseiro
• Vahab Mirrokni
• Renato Paes Leme
• Song Zuo

We study the problem of designing dynamic double auctions for two-sided markets in which a platform intermediates the trade between one seller offering independent items to multiple buyers, repeatedly over a finite horizon, when agents have private values. Motivated by online advertising and ride-hailing markets, we seek to design mechanisms satisfying the following properties: no positive transfers, i. e. , the platform never asks the seller to make payments nor buyers are ever paid and periodic individual rationality, i. e. , every agent should derive a non-negative utility from every trade opportunity. We provide mechanisms satisfying these requirements that are asymptotically efficient and budget-balanced with high probability as the number of trading opportunities grows. Moreover, we show that the average expected profit obtained by the platform under these mechanisms asymptotically approaches first best (the maximum possible welfare generated by the market).

NeurIPS Conference 2019 Conference Paper

Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions

• Negin Golrezaei
• Adel Javanmard
• Vahab Mirrokni

Motivated by pricing in ad exchange markets, we consider the problem of robust learning of reserve prices against strategic buyers in repeated contextual second-price auctions. Buyers' valuations \new{for} an item depend on the context that describes the item. However, the seller is not aware of the relationship between the context and buyers' valuations, i. e. , buyers' preferences. The seller's goal is to design a learning policy to set reserve prices via observing the past sales data, and her objective is to minimize her regret for revenue, where the regret is computed against a clairvoyant policy that knows buyers' heterogeneous preferences. Given the seller's goal, utility-maximizing buyers have the incentive to bid untruthfully in order to manipulate the seller's learning policy. We propose two learning policies that are robust to such strategic behavior. These policies use the outcomes of the auctions, rather than the submitted bids, to estimate the preferences while controlling the long-term effect of the outcome of each auction on the future reserve prices. The first policy called Contextual Robust Pricing (CORP) is designed for the setting where the market noise distribution is known to the seller and achieves a T-period regret of $O(d\log(Td) \log (T))$, where $d$ is the dimension of {the} contextual information. The second policy, which is a variant of the first policy, is called Stable CORP (SCORP). This policy is tailored to the setting where the market noise distribution is unknown to the seller and belongs to an ambiguity set. We show that the SCORP policy has a T-period regret of $O(\sqrt{d\log(Td)}\; T^{2/3})$.

NeurIPS Conference 2019 Conference Paper

Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond

• Lin Chen
• Hossein Esfandiari
• Gang Fu
• Vahab Mirrokni

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 science. A popular and effective technique in computing nearest neighbors approximately is the locality-sensitive hashing (LSH) scheme. In this paper, we aim to develop LSH schemes for distance functions that measure the distance between two probability distributions, particularly for f-divergences as well as a generalization to capture mutual information loss. First, we provide a general framework to design LHS schemes for f-divergence distance functions and develop LSH schemes for the generalized Jensen-Shannon divergence and triangular discrimination in this framework. We show a two-sided approximation result for approximation of the generalized Jensen-Shannon divergence by the Hellinger distance, which may be of independent interest. Next, we show a general method of reducing the problem of designing an LSH scheme for a Krein kernel (which can be expressed as the difference of two positive definite kernels) to the problem of maximum inner product search. We exemplify this method by applying it to the mutual information loss, due to its several important applications such as model compression.

FOCS Conference 2019 Conference Paper

Near-Optimal Massively Parallel Graph Connectivity

• Soheil Behnezhad
• Laxman Dhulipala
• Hossein Esfandiari
• Jakub Lacki
• Vahab Mirrokni

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 consider this problem in parallel settings. Particularly, we focus on the Massively Parallel Computations (MPC) model, which is the standard theoretical model for modern parallel frameworks such as MapReduce, Hadoop, or Spark. We consider the truly sublinear regime of MPC for graph problems where the space per machine is n δ for some desirably small constant δ ϵ (0, 1). We present an algorithm that for graphs with diameter D in the wide range [log ε n, n], takes O(log D) rounds to identify the connected components and takes O(log log n) rounds for all other graphs. The algorithm is randomized, succeeds with high probability, does not require prior knowledge of D, and uses an optimal total space of O(m). We complement this by showing a conditional lower-bound based on the widely believed TwoCycle conjecture that Ω(log D) rounds are indeed necessary in this setting. Studying parallel connectivity algorithms received a resurgence of interest after the pioneering work of Andoni etal [FOCS 2018] who presented an algorithm with O(log D log log n) round-complexity. Our algorithm improves this result for the whole range of values of D and almost settles the problem due to the conditional lower-bound. Additionally, we show that with minimal adjustments, our algorithm can also be implemented in a variant of (CRCW) PRAM in asymptotically the same number of rounds.

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.

AAAI Conference 2019 Conference Paper

Optimal Dynamic Auctions Are Virtual Welfare Maximizers

• Vahab Mirrokni
• Renato Paes Leme
• Pingzhong Tang
• Song Zuo

We are interested in the setting where a seller sells sequentially arriving items, one per period, via a dynamic auction. At the beginning of each period, each buyer draws a private valuation for the item to be sold in that period and this valuation is independent across buyers and periods. The auction can be dynamic in the sense that the auction at period t can be conditional on the bids in that period and all previous periods, subject to certain appropriately defined incentive compatible and individually rational conditions. Perhaps not surprisingly, the revenue optimal dynamic auctions are computationally hard to find and existing literatures that aim to approximate the optimal auctions are all based on solving complex dynamic programs. It remains largely open on the structural interpretability of the optimal dynamic auctions. In this paper, we show that any optimal dynamic auction is a virtual welfare maximizer subject to some monotone allocation constraints. In particular, the explicit definition of the virtual value function above arises naturally from the primal-dual analysis by relaxing the monotone constraints. We further develop an ironing technique that gets rid of the monotone allocation constraints. Quite different from Myerson’s ironing approach, our technique is more technically involved due to the interdependence of the virtual value functions across buyers. We nevertheless show that ironing can be done approximately and efficiently, which in turn leads to a Fully Polynomial Time Approximation Scheme of the optimal dynamic auction.

AAAI Conference 2019 Conference Paper

Pareto Efficient Auctions with Interest Rates

• Gagan Goel
• Vahab Mirrokni
• Renato Paes Leme

We consider auction settings in which agents have limited access to monetary resources but are able to make payments larger than their available resources by taking loans with a certain interest rate. This setting is a strict generalization of budget constrained utility functions (which corresponds to infinite interest rates). Our main result is an incentive compatible and Pareto-efficient auction for a divisible multi-unit setting with 2 players who are able to borrow money with the same interest rate. The auction is an ascending price clock auction that bears some similarities to the clinching auction but at the same time is a considerable departure from this framework: allocated goods can be de-allocated in future and given to other agents and prices for previously allocated goods can be raised.

IJCAI Conference 2019 Conference Paper

Preferred Deals in General Environments

• Yuan Deng
• Sébastien Lahaie
• Vahab Mirrokni

A preferred deal is a special contract for selling impressions of display ad inventory. By accepting a deal, a buyer agrees to buy a minimum amount of impressions at a fixed price per impression, and is granted priority access to the impressions before they are sent to an open auction on an ad exchange. We consider the problem of designing preferred deals (inventory, price, quantity) in the presence of general convex constraints, including budget constraints, and propose an approximation algorithm to maximize the revenue obtained from the deals. We then evaluate our algorithm using auction data from a major advertising exchange and our empirical results show that the algorithm achieves around 95% of the optimal revenue.

SODA Conference 2019 Conference Paper

Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

• Matthew Fahrbach
• Vahab Mirrokni
• Morteza Zadimoghaddam

NeurIPS Conference 2019 Conference Paper

Variance Reduction in Bipartite Experiments through Correlation Clustering

• Jean Pouget-Abadie
• Kevin Aydin
• Warren Schudy
• Kay Brodersen
• Vahab Mirrokni

Causal inference in randomized experiments typically assumes that the units of randomization and the units of analysis are one and the same. In some applications, however, these two roles are played by distinct entities linked by a bipartite graph. The key challenge in such bipartite settings is how to avoid interference bias, which would typically arise if we simply randomized the treatment at the level of analysis units. One effective way of minimizing interference bias in standard experiments is through cluster randomization, but this design has not been studied in the bipartite setting where conventional clustering schemes can lead to poorly powered experiments. This paper introduces a novel clustering objective and a corresponding algorithm that partitions a bipartite graph so as to maximize the statistical power of a bipartite experiment on that graph. Whereas previous work relied on balanced partitioning, our formulation suggests the use of a correlation clustering objective. We use a publicly-available graph of Amazon user-item reviews to validate our solution and illustrate how it substantially increases the statistical power in bipartite experiments.

ICML Conference 2018 Conference Paper

Accelerating Greedy Coordinate Descent Methods

• Haihao Lu
• Robert M. Freund
• Vahab Mirrokni

We introduce and study two algorithms to accelerate greedy coordinate descent in theory and in practice: Accelerated Semi-Greedy Coordinate Descent (ASCD) and Accelerated Greedy Coordinate Descent (AGCD). On the theory side, our main results are for ASCD: we show that ASCD achieves $O(1/k^2)$ convergence, and it also achieves accelerated linear convergence for strongly convex functions. On the empirical side, while both AGCD and ASCD outperform Accelerated Randomized Coordinate Descent on most instances in our numerical experiments, we note that AGCD significantly outperforms the other two methods in our experiments, in spite of a lack of theoretical guarantees for this method. To complement this empirical finding for AGCD, we present an explanation why standard proof techniques for acceleration cannot work for AGCD, and we further introduce a technical condition under which AGCD is guaranteed to have accelerated convergence. Finally, we confirm that this technical condition holds in our numerical experiments.

ICML Conference 2018 Conference Paper

Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions

• Shuaiwen Wang
• Wenda Zhou
• Haihao Lu
• Arian Maleki
• Vahab Mirrokni

We study the parameter tuning problem for the penalized regression model. Finding the optimal choice of the regularization parameter is a challenging problem in high-dimensional regimes where both the number of observations n and the number of parameters p are large. We propose two frameworks to obtain a computationally efficient approximation ALO of the leave-one-out cross validation (LOOCV) risk for nonsmooth losses and regularizers. Our two frameworks are based on the primal and dual formulations of the penalized regression model. We prove the equivalence of the two approaches under smoothness conditions. This equivalence enables us to justify the accuracy of both methods under such conditions. We use our approaches to obtain a risk estimate for several standard problems, including generalized LASSO, nuclear norm regularization and support vector machines. We experimentally demonstrate the effectiveness of our results for non-differentiable cases.

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

Parallel and Streaming Algorithms for K-Core Decomposition

• Hossein Esfandiari
• Silvio Lattanzi
• Vahab Mirrokni

The k-core decomposition is a fundamental primitive in many machine learning and data mining applications. We present the first distributed and the first streaming algorithms to compute and maintain an approximate k-core decomposition with provable guarantees. Our algorithms achieve rigorous bounds on space complexity while bounding the number of passes or number of rounds of computation. We do so by presenting a new powerful sketching technique for k-core decomposition, and then by showing it can be computed efficiently in both streaming and MapReduce models. Finally, we confirm the effectiveness of our sketching technique empirically on a number of publicly available graphs.

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.

STOC Conference 2018 Conference Paper

Stochastic bandits robust to adversarial corruptions

• Thodoris Lykouris
• Vahab Mirrokni
• Renato Paes Leme

We introduce a new model of stochastic bandits with adversarial corruptions which aims to capture settings where most of the input follows a stochastic pattern but some fraction of it can be adversarially changed to trick the algorithm, e.g., click fraud, fake reviews and email spam. The goal of this model is to encourage the design of bandit algorithms that (i) work well in mixed adversarial and stochastic models, and (ii) whose performance deteriorates gracefully as we move from fully stochastic to fully adversarial models. In our model, the rewards for all arms are initially drawn from a distribution and are then altered by an adaptive adversary. We provide a simple algorithm whose performance gracefully degrades with the total corruption the adversary injected in the data, measured by the sum across rounds of the biggest alteration the adversary made in the data in that round; this total corruption is denoted by C . Our algorithm provides a guarantee that retains the optimal guarantee (up to a logarithmic term) if the input is stochastic and whose performance degrades linearly to the amount of corruption C , while crucially being agnostic to it. We also provide a lower bound showing that this linear degradation is necessary if the algorithm achieves optimal performance in the stochastic setting (the lower bound works even for a known amount of corruption, a special case in which our algorithm achieves optimal performance without the extra logarithm).

AAAI Conference 2017 Conference Paper

A Study of Compact Reserve Pricing Languages

• MohammadHossein Bateni
• Hossein Esfandiary
• Vahab Mirrokni
• Saeed Seddighin

Online advertising allows advertisers to implement fine-tuned targeting of users. While such precise targeting leads to more effective advertising, it introduces challenging multidimensional pricing and bidding problems for publishers and advertisers. In this context, advertisers and publishers need to deal with an exponential number of possibilities. As a result, designing efficient and compact multidimensional bidding and pricing systems and algorithms are practically important for online advertisement. Compact bidding languages have already been studied in the context of multiplicative bidding. In this paper, we study the compact pricing problem. More specifically, we first define the multiplicative reserve price optimization problem (MRPOP) and show that unlike the unrestricted reserve price system, it is NP-hard to find the best reserve price solution in this setting. Next, we present an efficient algorithm to compute a solution for MRPOP that achieves a logarithmic approximation of the optimum solution of the unrestricted setting, where we can set a reserve price for each individual impression type (i. e. , one element in the Cartesian product of all features). We do so by characterizing the properties of an optimum solution. Furthermore, our empirical study confirms the effectiveness of multiplicative pricing in practice. In fact, the simulations show that our algorithm obtains 90–98% of the value of the best solution that sets the reserve prices for each auction individually (i. e. , the optimum set of reserve prices). Finally, in order to establish the tightness of our results in the adversarial setting, we demonstrate that there is no compact pricing system (i. e. , a pricing system using O(n1− ) bits to set n reserve prices) that loses, in the worst case, less than a logarithmic factor compared to the optimum set of reserve prices. Notice that this hardness result is not restricted to the multiplicative setting and holds for any compact pricing system. In summary, not only does the multiplicative reserve price system show great promise in our empirical study, but it is also theoretically optimal up to a constant factor in the adversarial setting. ∗ Supported in part by NSF CAREER award CCF-1053605, NSF BIGDATA grant IIS-1546108, NSF AF: Medium grant CCF- 1161365, DARPA GRAPHS/AFOSR grant FA9550-12-1-0423, and another DARPA SIMPLEX grant. Copyright c 2017, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved.

NeurIPS Conference 2017 Conference Paper

Affinity Clustering: Hierarchical Clustering at Scale

• MohammadHossein Bateni
• Soheil Behnezhad
• Mahsa Derakhshan
• MohammadTaghi Hajiaghayi
• Raimondas Kiveris
• Silvio Lattanzi
• Vahab Mirrokni

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e. g. , for graphs with trillions of edges.

NeurIPS Conference 2017 Conference Paper

Dynamic Revenue Sharing

• Santiago Balseiro
• Max Lin
• Vahab Mirrokni
• Renato Leme
• IIIS Song Zuo

Many online platforms act as intermediaries between a seller and a set of buyers. Examples of such settings include online retailers (such as Ebay) selling items on behalf of sellers to buyers, or advertising exchanges (such as AdX) selling pageviews on behalf of publishers to advertisers. In such settings, revenue sharing is a central part of running such a marketplace for the intermediary, and fixed-percentage revenue sharing schemes are often used to split the revenue among the platform and the sellers. In particular, such revenue sharing schemes require the platform to (i) take at most a constant fraction \alpha of the revenue from auctions and (ii) pay the seller at least the seller declared opportunity cost c for each item sold. A straightforward way to satisfy the constraints is to set a reserve price at c / (1 - \alpha) for each item, but it is not the optimal solution on maximizing the profit of the intermediary. While previous studies (by Mirrokni and Gomes, and by Niazadeh et al) focused on revenue-sharing schemes in static double auctions, in this paper, we take advantage of the repeated nature of the auctions. In particular, we introduce dynamic revenue sharing schemes where we balance the two constraints over different auctions to achieve higher profit and seller revenue. This is directly motivated by the practice of advertising exchanges where the fixed-percentage revenue-share should be met across all auctions and not in each auction. In this paper, we characterize the optimal revenue sharing scheme that satisfies both constraints in expectation. Finally, we empirically evaluate our revenue sharing scheme on real data.

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.

ICML Conference 2017 Conference Paper

Tight Bounds for Approximate Carathéodory and Beyond

• Vahab Mirrokni
• Renato Paes Leme
• Adrian Vladu
• Sam Chiu-wai Wong

We present a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope’s vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem, which states that any point inside a polytope contained in the $\ell_p$ ball of radius $D$ can be approximated to within $\epsilon$ in $\ell_p$ norm by a convex combination of $O\left(D^2 p/\epsilon^2\right)$ vertices of the polytope for $p \geq 2$. While for the particular case of $p=2$, this can be achieved by the well-known Perceptron algorithm, we follow a more principled approach which generalizes to arbitrary $p\geq 2$; furthermore, this naturally extends to domains with more complicated geometry, as it is the case for providing an approximate Birkhoff-von Neumann decomposition. Secondly, we show that the sparsity bound is tight for $\ell_p$ norms, using an argument based on anti-concentration for the binomial distribution, thus resolving an open question posed by Barman. Experimentally, we verify that our deterministic optimization-based algorithms achieve in practice much better sparsity than previously known sampling-based algorithms. We also show how to apply our techniques to SVM training and rounding fractional points in matroid and flow polytopes.

NeurIPS Conference 2016 Conference Paper

Bi-Objective Online Matching and Submodular Allocations

• Hossein Esfandiari
• Nitish Korula
• Vahab Mirrokni

Online allocation problems have been widely studied due to their numerous practical applications (particularly to Internet advertising), as well as considerable theoretical interest. The main challenge in such problems is making assignment decisions in the face of uncertainty about future input; effective algorithms need to predict which constraints are most likely to bind, and learn the balance between short-term gain and the value of long-term resource availability. In many important applications, the algorithm designer is faced with multiple objectives to optimize. In particular, in online advertising it is fairly common to optimize multiple metrics, such as clicks, conversions, and impressions, as well as other metrics which may be largely uncorrelated such as ‘share of voice’, and ‘buyer surplus’. While there has been considerable work on multi-objective offline optimization (when the entire input is known in advance), very little is known about the online case, particularly in the case of adversarial input. In this paper, we give the first results for bi-objective online submodular optimization, providing almost matching upper and lower bounds for allocating items to agents with two submodular value functions. We also study practically relevant special cases of this problem related to Internet advertising, and obtain improved results. All our algorithms are nearly best possible, as well as being efficient and easy to implement in practice.

IJCAI Conference 2016 Conference Paper

Dynamic Auctions with Bank Accounts

• Vahab Mirrokni
• Renato Paes Leme
• Pingzhong Tang
• Song Zuo

Consider a buyer with independent additive valuations for a set of goods, and a seller who is constrained to sell one item at a time in an online fashion. If the seller is constrained to run independent auctions for each item, then he would run Myerson's optimal auction for each item. If the seller is allowed to use the full power of dynamic mechanism design and have the auction for each item depend on the outcome of the previous auctions, he is able to perform much better. The main issues in implementing such strategies in online settings where items arrive over time are that the auction might be too complicated or it makes too strong assumptions on the buyer's rationality or seller's commitment over time. This motivates us to explore a restricted family of dynamic auctions that can be implemented in an online fashion and without too much commitment from the seller ahead of time. In particular, we study a set of auction in which the space of single-shot auctions is augmented with a structure that we call bank account, a real number for each node that summarizes the history so far. This structure allows the seller to store deficits or surpluses of buyer utility from each individual auction and even them out on the long run. This is akin to enforcing individual rationality constraint on average rather than per auction. We also study the effect of enforcing a maximum limit to the values that bank account might grow, which means that we enforce that besides the auction being individually rational on average it is also not far from being individually rational at any given interval. Interestingly, even with these restrictions, we can achieve significantly better revenue and social welfare compared to separate Myerson auctions.

SODA Conference 2016 Conference Paper

Expanders via Local Edge Flips

• Zeyuan Allen-Zhu
• Aditya Bhaskara
• Silvio Lattanzi
• Vahab Mirrokni
• Lorenzo Orecchia

Designing distributed and scalable algorithms to improve network connectivity is a central topic in peer-to-peer networks. In this paper we focus on the following well-known problem: given an n -node d -regular network for d = Ω(log n ), we want to design a decentralized, local algorithm that transforms the graph into one that has good connectivity properties (low diameter, expansion, etc.) without affecting the sparsity of the graph. To this end, Mahlmann and Schindelhauer introduced the random “flip” transformation, where in each time step, a random pair of vertices that have an edge decide to ‘swap a neighbor’. They conjectured that performing O ( nd ) such flips at random would convert any connected d -regular graph into a d -regular expander graph, with high probability. However, the best known upper bound for the number of steps is roughly O ( n 17 d 23 ), obtained via a delicate Markov chain comparison argument. Our main result is to prove that a natural instantiation of the random flip produces an expander in at most steps, with high probability. Our argument uses a potential-function analysis based on the matrix exponential, together with the recent beautiful results on the higher-order Cheeger inequality of graphs. We also show that our technique can be used to analyze another well-studied random process known as the ‘random switch’, and show that it produces an expander in O ( nd ) steps with high probability.

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.

NeurIPS Conference 2016 Conference Paper

Linear Relaxations for Finding Diverse Elements in Metric Spaces

• Aditya Bhaskara
• Mehrdad Ghadiri
• Vahab Mirrokni
• Ola Svensson

Choosing a diverse subset of a large collection of points in a metric space is a fundamental problem, with applications in feature selection, recommender systems, web search, data summarization, etc. Various notions of diversity have been proposed, tailored to different applications. The general algorithmic goal is to find a subset of points that maximize diversity, while obeying a cardinality (or more generally, matroid) constraint. The goal of this paper is to develop a novel linear programming (LP) framework that allows us to design approximation algorithms for such problems. We study an objective known as {\em sum-min} diversity, which is known to be effective in many applications, and give the first constant factor approximation algorithm. Our LP framework allows us to easily incorporate additional constraints, as well as secondary objectives. We also prove a hardness result for two natural diversity objectives, under the so-called {\em planted clique} assumption. Finally, we study the empirical performance of our algorithm on several standard datasets. We first study the approximation quality of the algorithm by comparing with the LP objective. Then, we compare the quality of the solutions produced by our method with other popular diversity maximization algorithms.

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 2015 Conference Paper

Robust Price of Anarchy Bounds via LP and Fenchel Duality

• Janardhan Kulkarni
• Vahab Mirrokni

Bounding the price of anarchy (PoA), which quantifies the degradation in the quality of outcomes in a (pure) Nash equilibrium of a game, is one of the fundamental questions in computational game theory. However, for a large class of games, a pure NE may not always exist and hence a natural question to pursue is to quantify the inefficiency for weaker notions of equilibrium such as mixed Nash equilibrium, correlated equilibrium or coarse correlated equilibrium, all of which are known to exist for finite games. Several techniques have been developed for bounding the price of anarchy, yet, only a handful of them are applicable for proving the PoA bounds for general equilibrium concepts. Most notable among such techniques is Roughgarden's elegant smoothness framework, which led to the concept of robust price of anarchy. The term refers to the inefficiency bounds applicable to general equilibrium notions such as coarse correlated equilibrium. In this paper, we develop a new framework based on LP and Fenchel duality for bounding the robust price of anarchy for a large class of games. We use our framework to give the first PoA bounds for temporal routing games on graphs and energy minimization games in machine scheduling. Most notably, we present the first coordination mechanisms with bounded PoA for temporal routing over general graphs, show a related lowerbound result, and an improved bound on the price of stability for this game. Previously, coordination mechanisms with bounded PoA were only known for restricted classes of graphs such as trees or parallel edges. Furthermore, we demonstrate the wide applicability of our framework by giving new proofs of the PoA bounds for three classical games – weighted affine congestion games, competitive facility location games and simultaneous second price auctions. Our price anarchy bounds for these games match the ones known in the literature or obtained using the smoothness framework. All our proofs use the following technique: we first show that for a wide class of games, one can formulate the underlying optimization problem as a linear (or convex) program such that the (Fenchel) dual of the relaxation encodes the equilibrium condition. Further, the dual program has a specific structure with variables for players and resources, which can be naturally interpreted as the cost incurred by the players and the congestion of the resource in an equilibrium outcome. This lets us argue that our definition of dual variables satisfy the dual constraints and using the weak duality theorem we establish the PoA bounds.

NeurIPS Conference 2014 Conference Paper

Distributed Balanced Clustering via Mapping Coresets

• MohammadHossein Bateni
• Aditya Bhaskara
• Silvio Lattanzi
• Vahab Mirrokni

Large-scale clustering of data points in metric spaces is an important problem in mining big data sets. For many applications, we face explicit or implicit size constraints for each cluster which leads to the problem of clustering under capacity constraints or the balanced clustering'' problem. Although the balanced clustering problem has been widely studied, developing a theoretically sound distributed algorithm remains an open problem. In the present paper we develop a general framework based on mapping coresets'' to tackle this issue. For a wide range of clustering objective functions such as k-center, k-median, and k-means, our techniques give distributed algorithms for balanced clustering that match the best known single machine approximation ratios.

TCS Journal 2014 Journal Article

On non-progressive spread of influence through social networks

• MohammadAmin Fazli
• Mohammad Ghodsi
• Jafar Habibi
• Pooya Jalaly
• Vahab Mirrokni
• Sina Sadeghian

The spread of influence in social networks is studied in two main categories: progressive models and non-progressive models (see, e. g. , the seminal work of Kempe et al. [8]). While the progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive models are more appropriate for non-monopolistic settings, e. g. , modeling diffusion of two competing technologies over a social network. Despite the extensive work on progressive models, non-progressive models have not been considered as much. In this paper, we study the spread of influence in the non-progressive model under the strict majority threshold: given a graph G with a set of initially infected nodes, each of which gets infected at time τ iff a majority of its neighbors are infected at time τ − 1. Our goal in the MinPTS problem is to find a minimum-cardinality initial set of infected nodes that would eventually converge to the steady state where all nodes of G are infected. We prove that while the MinPTS problem is NP-complete for a restricted family of graphs, it admits a constant-factor approximation algorithm for power-law graphs. We do so by proving the lower and upper bounds on the optimal solution of the MinPTS problem in terms of the minimum and maximum degrees of nodes in the graph. The upper bound is achieved in turn by applying a natural greedy algorithm. Our experimental evaluation of the greedy algorithm also shows its superior performance compared to other algorithms for a set of real-world graphs as well as the random power-law graphs. Finally, we study the convergence properties of these algorithms and show that the non-progressive model converges in at most O ( | E ( G ) | ) steps.

ICML Conference 2013 Conference Paper

A Local Algorithm for Finding Well-Connected Clusters

• Zeyuan Allen-Zhu
• Silvio Lattanzi
• Vahab Mirrokni

Motivated by applications of large-scale graph clustering, we study random-walk-based LOCAL algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. In particular, we develop a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data. More specifically, our method outperforms prior work when the cluster is WELL-CONNECTED. In fact, the better it is well-connected inside, the more significant improvement we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering.

SODA Conference 2013 Conference Paper

Clinching Auction with Online Supply

• Gagan Goel
• Vahab Mirrokni
• Renato Paes Leme

TCS Journal 2013 Journal Article

Equilibrium pricing with positive externalities

• Nima AhmadiPourAnari
• Shayan Ehsani
• Mohammad Ghodsi
• Nima Haghpanah
• Nicole Immorlica
• Hamid Mahini
• Vahab Mirrokni

We study the problem of selling an item to strategic buyers in the presence of positive historical externalities, where the value of a product increases as more people buy and use it. This increase in the value of the product is the result of resolving bugs or security holes after more usage. We consider a continuum of buyers that are partitioned into types where each type has a valuation function based on the actions of other buyers. Given a fixed sequence of prices, or price trajectory, buyers choose a day on which to purchase the product, i. e. they have to decide whether to purchase the product early in the game or later after more people already own it. We model this strategic setting as a game, study existence and uniqueness of the equilibria, and design an FPTAS to compute an approximately revenue-maximizing pricing trajectory for the seller in two special cases: the symmetric settings in which there is just a single buyer type, and the linear settings that are characterized by an initial type-independent bias and a linear type-dependent influenceability coefficient.

STOC Conference 2012 Conference Paper

Polyhedral clinching auctions and the adwords polytope

• Gagan Goel
• Vahab Mirrokni
• Renato Paes Leme

A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying the above properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots. We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multi-unit auctions with decreasing marginal utilities in the presence of budget constraints.

SODA Conference 2012 Conference Paper

Simultaneous approximations for adversarial and stochastic online budgeted allocation

• Vahab Mirrokni
• Shayan Oveis Gharan
• Morteza Zadimoghaddam

STOC Conference 2011 Conference Paper

Inner product spaces for MinSum coordination mechanisms

• Richard Cole 0001
• José Correa 0001
• Vasilis Gkatzelis
• Vahab Mirrokni
• Neil Olver

We study coordination mechanisms aiming to minimize the weighted sum of completion times of jobs in the context of selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain these approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. The method entails mapping strategy vectors into a carefully chosen inner product space; costs are shown to correspond to the norm in this space, and the Nash condition also has a simple description. With this structure in place, we are able to prove a number of results, as follows. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given fixed assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed. We prove that ProportionalSharing, a preemptive strongly local policy, achieves an approximation ratio of 2.618 for the weighted sum of completion times, and an approximation ratio of 2.5 in the unweighted case. We also observe that these bounds are tight. Next, we consider Rand, a natural non-preemptive but randomized policy. We show that it achieves an approximation ratio of at most 2.13; moreover, if the sum of the weighted completion times is negligible compared to the cost of the optimal solution, this improves to π/2. Finally, we show that both ProportionalSharing and Rand induce potential games, and thus always have a pure Nash equilibrium (unlike Smith's Rule). This allows us to design the first combinatorial constant-factor approximation algorithm minimizing weighted completion time for unrelated machine scheduling. It achieves a factor of 2+ε for any ε > 0, and involves imitating best response dynamics using a variant of ProportionalSharing as the policy.

SODA Conference 2009 Conference Paper

Approximating submodular functions everywhere

• Michel X. Goemans
• Nicholas J. A. Harvey
• Satoru Iwata 0001
• Vahab Mirrokni

Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e. g. , exact minimization or approximate maximization. In this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly( n ) oracle queries. Our main result is a deterministic algorithm that makes poly( n ) oracle queries and derives a function such that, for every set S, ( S ) approximates f ( S ) within a factor α ( n ), where for rank functions of matroids and for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than, even for rank functions of a matroid.

STOC Conference 2009 Conference Paper

Non-monotone submodular maximization under matroid and knapsack constraints

• Jon Lee 0001
• Vahab Mirrokni
• Viswanath Nagarajan
• Maxim Sviridenko

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

FOCS Conference 2009 Conference Paper

Online Stochastic Matching: Beating 1-1/e

• Jon Feldman
• Aranyak Mehta
• Vahab Mirrokni
• S. Muthukrishnan 0001

We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of 1- 1/e ¿ 0. 632, a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the 1 - 1/e bound. Our main result is a 0. 67-approximation online algorithm for stochastic bipartite matching, breaking this 1 - ¿ barrier. Furthermore, we show that no online algorithm can produce a 1 - ¿ approximation for an arbitrarily small e for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.

ICML Conference 2009 Conference Paper

Tutorial summary: Convergence of natural dynamics to equilibria

• Eyal Even-Dar
• Vahab Mirrokni

SODA Conference 2008 Conference Paper

(Almost) optimal coordination mechanisms for unrelated machine scheduling

• Yossi Azar
• Kamal Jain
• Vahab Mirrokni

STOC Conference 2008 Conference Paper

The myth of the folk theorem

• Christian Borgs
• Jennifer T. Chayes
• Nicole Immorlica
• Adam Tauman Kalai
• Vahab Mirrokni
• Christos H. Papadimitriou

A well-known result in game theory known as "the Folk Theorem" suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any (approximate) Nash equilibrium for a three-player infinitely-repeated game is computationally intractable (even when all payoffs are in {-1,0,1}), unless all of PPAD can be solved in randomized polynomial time. This is done by showing that finding Nash equilibria of (k+1)-player infinitely-repeated games is as hard as finding Nash equilibria of k-player one-shot games, for which PPAD-hardness is known (Daskalakis, Goldberg and Papadimitriou, 2006; Chen, Deng and Teng, 2006; Chen, Teng and Valiant, 2007). This also explains why no computationally-efficient learning dynamics, such as the "no regret" algorithms, can be "rational" (in general games with three or more players) in the sense that, when one's opponents use such a strategy, it is not in general a best reply to follow suit.

FOCS Conference 2007 Conference Paper

Maximizing Non-Monotone Submodular Functions

• Uriel Feige
• Vahab Mirrokni
• Jan Vondrák

Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.

SODA Conference 2006 Conference Paper

Tight approximation algorithms for maximum general assignment problems

• Lisa Fleischer
• Michel X. Goemans
• Vahab Mirrokni
• Maxim Sviridenko

SODA Conference 2005 Conference Paper

Limitations of cross-monotonic cost sharing schemes

• Nicole Immorlica
• Mohammad Mahdian
• Vahab Mirrokni

FOCS Conference 2005 Conference Paper

Sink Equilibria and Convergence

• Michel X. Goemans
• Vahab Mirrokni
• Adrian Vetta

We introduce the concept of a sink equilibrium. A sink equilibrium is a strongly connected component with no outgoing arcs in the strategy profile graph associated with a game. The strategy profile graph has a vertex set induced by the set of pure strategy profiles; its arc set corresponds to transitions between strategy profiles that occur with nonzero probability. (Here our focus will just be on the special case in which the strategy profile graph is actually a best response graph; that is, its arc set corresponds exactly to best response moves that result from myopic or greedy behaviour). We argue that there is a natural convergence process to sink equilibria in games where agents use pure strategies. This leads to an alternative measure of the social cost of a lack of coordination, the price of sinking, which measures the worst case ratio between the value of a sink equilibrium and the value of the socially optimal solution. We define the value of a sink equilibrium to be the expected social value of the steady state distribution induced by a random walk on that sink. We illustrate the value of this measure in three ways. Firstly, we show that it may more accurately reflects the inefficiency of uncoordinated solutions in competitive games when the use of pure strategies is the norm. In particular, we give an example (a valid-utility game) in which the game converges to solutions which are a factor n worse than socially optimal. The price of sinking is indeed n, but the price of anarchy is close to 1. Secondly, sink equilibria always exist. Thus, even in games in which pure strategy Nash equilibria (PSNE) do not exist, we can still calculate the price of sinking. Thirdly, we show that bounding the price of sinking can have important implications for the speed of convergence to socially good solutions in games where the agents make best response moves in a random order. We present two examples to illustrate our ideas. (i) Unsplittable selfish routing (and weighted congestion games): we prove that the price of sinking for the weighted unsplittable flow version of the selfish routing problem (for bounded-degree polynomial latency functions) is at most O(2/sup 2d/ d/sup 2d + 3/). In comparison, we give instances of these games without any PSNE. Moreover, our proof technique implies fast convergence to socially good (approximate) solutions. This is in contrast to the negative result of Fabrikant, Papadimitriou, and Talwar (2004) showing the existence of exponentially long best-response paths. (ii) Valid-utility games: we show that for valid-utility games the price of sinking is at most n+1; thus the worst case price of sinking in a valid-utility game is between it and n+1. We use our proof to show fast convergence to constant factor approximate solutions in basic-utility games. In addition, we present a hardness result which shows that, in general, there might be states that are exponentially far from any sink equilibrium in valid-utility games. We prove this by showing that the problem of finding a sink equilibrium (or a PSNE) in valid-utility games is PLS-complete.

SODA Conference 2004 Conference Paper

On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems

• Nicole Immorlica
• David R. Karger
• Maria Minkoff
• Vahab Mirrokni