Showing 1–23 of 23 results for author: Guruganesh, G

Contracting with a Learning Agent

Authors: Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Joshua R. Wang, S. Matthew Weinberg

Abstract: Many real-life contractual relations differ completely from the clean, static model at the heart of principal-agent theory. Typically, they involve repeated strategic interactions of the principal and agent, taking place under uncertainty and over time. While appealing in theory, players seldom use complex dynamic strategies in practice, often preferring to circumvent complexity and approach uncer… ▽ More Many real-life contractual relations differ completely from the clean, static model at the heart of principal-agent theory. Typically, they involve repeated strategic interactions of the principal and agent, taking place under uncertainty and over time. While appealing in theory, players seldom use complex dynamic strategies in practice, often preferring to circumvent complexity and approach uncertainty through learning. We initiate the study of repeated contracts with a learning agent, focusing on agents who achieve no-regret outcomes. Optimizing against a no-regret agent is a known open problem in general games; we achieve an optimal solution to this problem for a canonical contract setting, in which the agent's choice among multiple actions leads to success/failure. The solution has a surprisingly simple structure: for some $α> 0$, initially offer the agent a linear contract with scalar $α$, then switch to offering a linear contract with scalar $0$. This switch causes the agent to ``free-fall'' through their action space and during this time provides the principal with non-zero reward at zero cost. Despite apparent exploitation of the agent, this dynamic contract can leave \emph{both} players better off compared to the best static contract. Our results generalize beyond success/failure, to arbitrary non-linear contracts which the principal rescales dynamically. Finally, we quantify the dependence of our results on knowledge of the time horizon, and are the first to address this consideration in the study of strategizing against learning agents. △ Less

Submitted 29 January, 2024; originally announced January 2024.

Functional Interpolation for Relative Positions Improves Long Context Transformers

Authors: Shanda Li, Chong You, Guru Guruganesh, Joshua Ainslie, Santiago Ontanon, Manzil Zaheer, Sumit Sanghai, Yiming Yang, Sanjiv Kumar, Srinadh Bhojanapalli

Abstract: Preventing the performance decay of Transformers on inputs longer than those used for training has been an important challenge in extending the context length of these models. Though the Transformer architecture has fundamentally no limits on the input sequence lengths it can process, the choice of position encoding used during training can limit the performance of these models on longer inputs. W… ▽ More Preventing the performance decay of Transformers on inputs longer than those used for training has been an important challenge in extending the context length of these models. Though the Transformer architecture has fundamentally no limits on the input sequence lengths it can process, the choice of position encoding used during training can limit the performance of these models on longer inputs. We propose a novel functional relative position encoding with progressive interpolation, FIRE, to improve Transformer generalization to longer contexts. We theoretically prove that this can represent some of the popular relative position encodings, such as T5's RPE, Alibi, and Kerple. We next empirically show that FIRE models have better generalization to longer contexts on both zero-shot language modeling and long text benchmarks. △ Less

Submitted 2 March, 2024; v1 submitted 6 October, 2023; originally announced October 2023.

Comments: 26 pages; ICLR 2024 camera ready version

The Power of Menus in Contract Design

Authors: Guru Guruganesh, Jon Schneider, Joshua Wang, Junyao Zhao

Abstract: We study the power of menus of contracts in principal-agent problems with adverse selection (agents can be one of several types) and moral hazard (we cannot observe agent actions directly). For principal-agent problems with $T$ types and $n$ actions, we show that the best menu of contracts can obtain a factor $Ω(\max(n, \log T))$ more utility for the principal than the best individual contract, pa… ▽ More We study the power of menus of contracts in principal-agent problems with adverse selection (agents can be one of several types) and moral hazard (we cannot observe agent actions directly). For principal-agent problems with $T$ types and $n$ actions, we show that the best menu of contracts can obtain a factor $Ω(\max(n, \log T))$ more utility for the principal than the best individual contract, partially resolving an open question of Guruganesh et al. (2021). We then turn our attention to randomized menus of linear contracts, where we likewise show that randomized linear menus can be $Ω(T)$ better than the best single linear contract. As a corollary, we show this implies an analogous gap between deterministic menus of (general) contracts and randomized menus of contracts (as introduced by Castiglioni et al. (2022)). △ Less

Submitted 22 June, 2023; originally announced June 2023.

Comments: EC 2023

A Fourier Approach to Mixture Learning

Authors: Mingda Qiao, Guru Guruganesh, Ankit Singh Rawat, Avinava Dubey, Manzil Zaheer

Abstract: We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture $\frac{1}{k}\sum_{j=1}^{k}\mathcal{N}(μ_j, I_d)$, the goal is to estimate the means $μ_1, μ_2, \ldots, μ_k \in \mathbb{R}^d$ up to a small error. The hardness of this learning problem can be measured by the separation $Δ$ defined as the minimum distance between all pairs of means. Regev and Vijayaraghava… ▽ More We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture $\frac{1}{k}\sum_{j=1}^{k}\mathcal{N}(μ_j, I_d)$, the goal is to estimate the means $μ_1, μ_2, \ldots, μ_k \in \mathbb{R}^d$ up to a small error. The hardness of this learning problem can be measured by the separation $Δ$ defined as the minimum distance between all pairs of means. Regev and Vijayaraghavan (2017) showed that with $Δ= Ω(\sqrt{\log k})$ separation, the means can be learned using $\mathrm{poly}(k, d)$ samples, whereas super-polynomially many samples are required if $Δ= o(\sqrt{\log k})$ and $d = Ω(\log k)$. This leaves open the low-dimensional regime where $d = o(\log k)$. In this work, we give an algorithm that efficiently learns the means in $d = O(\log k/\log\log k)$ dimensions under separation $d/\sqrt{\log k}$ (modulo doubly logarithmic factors). This separation is strictly smaller than $\sqrt{\log k}$, and is also shown to be necessary. Along with the results of Regev and Vijayaraghavan (2017), our work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, our algorithm runs in time $\mathrm{poly}(k)\cdot f(d, Δ, ε)$, and is thus fixed-parameter tractable in parameters $d$, $Δ$ and $ε$. Our approach is based on estimating the Fourier transform of the mixture at carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution. △ Less

Submitted 5 October, 2022; v1 submitted 5 October, 2022; originally announced October 2022.

Comments: To appear at NeurIPS 2022; v2 corrected author information

Prior-Independent Auctions for Heterogeneous Bidders

Authors: Guru Guruganesh, Aranyak Mehta, Di Wang, Kangning Wang

Abstract: We study the design of prior-independent auctions in a setting with heterogeneous bidders. In particular, we consider the setting of selling to $n$ bidders whose values are drawn from $n$ independent but not necessarily identical distributions. We work in the robust auction design regime, where we assume the seller has no knowledge of the bidders' value distributions and must design a mechanism th… ▽ More We study the design of prior-independent auctions in a setting with heterogeneous bidders. In particular, we consider the setting of selling to $n$ bidders whose values are drawn from $n$ independent but not necessarily identical distributions. We work in the robust auction design regime, where we assume the seller has no knowledge of the bidders' value distributions and must design a mechanism that is prior-independent. While there have been many strong results on prior-independent auction design in the i.i.d. setting, not much is known for the heterogeneous setting, even though the latter is of significant practical importance. Unfortunately, no prior-independent mechanism can hope to always guarantee any approximation to Myerson's revenue in the heterogeneous setting; similarly, no prior-independent mechanism can consistently do better than the second-price auction. In light of this, we design a family of (parametrized) randomized auctions which approximates at least one of these benchmarks: For heterogeneous bidders with regular value distributions, our mechanisms either achieve a good approximation of the expected revenue of an optimal mechanism (which knows the bidders' distributions) or exceeds that of the second-price auction by a certain multiplicative factor. The factor in the latter case naturally trades off with the approximation ratio of the former case. We show that our mechanism is optimal for such a trade-off between the two cases by establishing a matching lower bound. Our result extends to selling $k$ identical items to heterogeneous bidders with an additional $O\big(\ln^2 k\big)$-factor in our trade-off between the two cases. △ Less

Submitted 7 November, 2023; v1 submitted 19 July, 2022; originally announced July 2022.

Comments: Full version of a paper in the Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Maximizing revenue in the presence of intermediaries

Authors: Gagan Aggarwal, Kshipra Bhawalkar, Guru Guruganesh, Andres Perlroth

Abstract: We study the mechanism design problem of selling $k$ items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who represents a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perfo… ▽ More We study the mechanism design problem of selling $k$ items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who represents a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perform well under a wide variety of possible contracts between intermediaries and buyers. We first study the case of $k$ identical items where each buyer draws its private valuation for an item i.i.d. from a known $λ$-regular distribution. We construct a robust mechanism that, independent of the demand structure and under certain conditions on the contracts between intermediaries and buyers, obtains a constant factor of the revenue that the mechanism designer could obtain had she known the buyers' valuations. In other words, our mechanism's expected revenue achieves a constant factor of the optimal welfare, regardless of the demand structure. Our mechanism is a simple posted-price mechanism that sets a take-it-or-leave-it per-item price that depends on $k$ and the total number of buyers, but does not depend on the demand structure or the downstream contracts. Next we generalize our result to the case when the items are not identical. We assume that the item valuations are separable. For this case, we design a mechanism that obtains at least a constant fraction of the optimal welfare, by using a menu of posted prices. This mechanism is also independent of the demand structure, but makes a relatively stronger assumption on the contracts between intermediaries and buyers, namely that each intermediary prefers outcomes with a higher sum of utilities of the subset of buyers represented by it. △ Less

Submitted 19 November, 2021; originally announced November 2021.

Margin-Independent Online Multiclass Learning via Convex Geometry

Authors: Guru Guruganesh, Allen Liu, Jon Schneider, Joshua Wang

Abstract: We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query to the region corresponding to its correct label. When the true labels are determined via a nearest neighbor partition -- i.e. the… ▽ More We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query to the region corresponding to its correct label. When the true labels are determined via a nearest neighbor partition -- i.e. the label of a point is given by which of $k$ centers it is closest to in Euclidean distance -- we show that one can achieve a loss that is independent of the total number of queries. We complement this result by showing that learning general convex sets requires an almost linear loss per query. Our results build off of regret guarantees for the geometric problem of contextual search. In addition, we develop a novel reduction technique from multiclass classification to binary classification which may be of independent interest. △ Less

Submitted 15 November, 2021; originally announced November 2021.

Learning to Bid in Contextual First Price Auctions

Authors: Ashwinkumar Badanidiyuru, Zhe Feng, Guru Guruganesh

Abstract: In this paper, we investigate the problem about how to bid in repeated contextual first price auctions. We consider a single bidder (learner) who repeatedly bids in the first price auctions: at each time $t$, the learner observes a context $x_t\in \mathbb{R}^d$ and decides the bid based on historical information and $x_t$. We assume a structured linear model of the maximum bid of all the others… ▽ More In this paper, we investigate the problem about how to bid in repeated contextual first price auctions. We consider a single bidder (learner) who repeatedly bids in the first price auctions: at each time $t$, the learner observes a context $x_t\in \mathbb{R}^d$ and decides the bid based on historical information and $x_t$. We assume a structured linear model of the maximum bid of all the others $m_t = α_0\cdot x_t + z_t$, where $α_0\in \mathbb{R}^d$ is unknown to the learner and $z_t$ is randomly sampled from a noise distribution $\mathcal{F}$ with log-concave density function $f$. We consider both \emph{binary feedback} (the learner can only observe whether she wins or not) and \emph{full information feedback} (the learner can observe $m_t$) at the end of each time $t$. For binary feedback, when the noise distribution $\mathcal{F}$ is known, we propose a bidding algorithm, by using maximum likelihood estimation (MLE) method to achieve at most $\widetilde{O}(\sqrt{\log(d) T})$ regret. Moreover, we generalize this algorithm to the setting with binary feedback and the noise distribution is unknown but belongs to a parametrized family of distributions. For the full information feedback with \emph{unknown} noise distribution, we provide an algorithm that achieves regret at most $\widetilde{O}(\sqrt{dT})$. Our approach combines an estimator for log-concave density functions and then MLE method to learn the noise distribution $\mathcal{F}$ and linear weight $α_0$ simultaneously. We also provide a lower bound result such that any bidding policy in a broad class must achieve regret at least $Ω(\sqrt{T})$, even when the learner receives the full information feedback and $\mathcal{F}$ is known. △ Less

Submitted 10 November, 2021; v1 submitted 7 September, 2021; originally announced September 2021.

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

Authors: Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme, Jon Schneider

Abstract: We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility… ▽ More We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \mathcal{X}_t} \langle x, w^* \rangle$. We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low "regret" -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns. We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\mathrm{poly}(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner's formula for the centroid of a convex set) which may be of independent interest. △ Less

Submitted 9 June, 2021; originally announced June 2021.

Scalable Hierarchical Agglomerative Clustering

Authors: Nicholas Monath, Avinava Dubey, Guru Guruganesh, Manzil Zaheer, Amr Ahmed, Andrew McCallum, Gokhan Mergen, Marc Najork, Mert Terzihan, Bryon Tjanaka, Yuan Wang, Yuchen Wu

Abstract: The applicability of agglomerative clustering, for inferring both hierarchical and flat clustering, is limited by its scalability. Existing scalable hierarchical clustering methods sacrifice quality for speed and often lead to over-merging of clusters. In this paper, we present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of da… ▽ More The applicability of agglomerative clustering, for inferring both hierarchical and flat clustering, is limited by its scalability. Existing scalable hierarchical clustering methods sacrifice quality for speed and often lead to over-merging of clusters. In this paper, we present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points. We perform a detailed theoretical analysis, showing that under mild separability conditions our algorithm can not only recover the optimal flat partition, but also provide a two-approximation to non-parametric DP-Means objective. This introduces a novel application of hierarchical clustering as an approximation algorithm for the non-parametric clustering objective. We additionally relate our algorithm to the classic hierarchical agglomerative clustering method. We perform extensive empirical experiments in both hierarchical and flat clustering settings and show that our proposed approach achieves state-of-the-art results on publicly available clustering benchmarks. Finally, we demonstrate our method's scalability by applying it to a dataset of 30 billion queries. Human evaluation of the discovered clusters show that our method finds better quality of clusters than the current state-of-the-art. △ Less

Submitted 30 September, 2021; v1 submitted 22 October, 2020; originally announced October 2020.

Comments: Appeared in KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Contracts under Moral Hazard and Adverse Selection

Authors: Guru Guruganesh, Jon Schneider, Joshua Wang

Abstract: In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical principal-agent problem in a setting where the agent can be of one of several types (affecting the outcome of actions they might take). This combines the contract theory phenomena of "moral hazard" (incomplete information about… ▽ More In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical principal-agent problem in a setting where the agent can be of one of several types (affecting the outcome of actions they might take). This combines the contract theory phenomena of "moral hazard" (incomplete information about actions) with that of "adverse selection" (incomplete information about types). We examine this problem through the computational lens. We show that in this setting it is APX-hard to compute either the profit-maximizing single contract or the profit-maximizing menu of contracts (as opposed to in the absence of types, where one can efficiently compute the optimal contract). We then show that the performance of the best linear contract scales especially well in the number of types: if agent has $n$ available actions and $T$ possible types, the best linear contract achieves an $O(n\log T)$ approximation of the best possible profit. Finally, we apply our framework to prove tight worst-case approximation bounds between a variety of benchmarks of mechanisms for the principal. △ Less

Submitted 13 October, 2020; originally announced October 2020.

ACM Class: G.2.m

Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions

Authors: Zhe Feng, Guru Guruganesh, Christopher Liaw, Aranyak Mehta, Abhishek Sethi

Abstract: The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study th… ▽ More The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as well. We study repeated game between bidders in which a single item is sold at each time step and the bidder's value is drawn from an unknown distribution. We show that if the bidders use any mean-based learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms such as Exp3, UCB, $ε$-Greedy etc. Also, we analyze the convergence of the individual iterates produced by such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate our theoretical findings and also find a similar convergence when we use other strategies such as Deep Q-Learning. △ Less

Submitted 13 September, 2020; originally announced September 2020.

Big Bird: Transformers for Longer Sequences

Authors: Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, Amr Ahmed

Abstract: Transformers-based models, such as BERT, have been one of the most successful deep learning models for NLP. Unfortunately, one of their core limitations is the quadratic dependency (mainly in terms of memory) on the sequence length due to their full attention mechanism. To remedy this, we propose, BigBird, a sparse attention mechanism that reduces this quadratic dependency to linear. We show that… ▽ More Transformers-based models, such as BERT, have been one of the most successful deep learning models for NLP. Unfortunately, one of their core limitations is the quadratic dependency (mainly in terms of memory) on the sequence length due to their full attention mechanism. To remedy this, we propose, BigBird, a sparse attention mechanism that reduces this quadratic dependency to linear. We show that BigBird is a universal approximator of sequence functions and is Turing complete, thereby preserving these properties of the quadratic, full attention model. Along the way, our theoretical analysis reveals some of the benefits of having $O(1)$ global tokens (such as CLS), that attend to the entire sequence as part of the sparse attention mechanism. The proposed sparse attention can handle sequences of length up to 8x of what was previously possible using similar hardware. As a consequence of the capability to handle longer context, BigBird drastically improves performance on various NLP tasks such as question answering and summarization. We also propose novel applications to genomics data. △ Less

Submitted 8 January, 2021; v1 submitted 28 July, 2020; originally announced July 2020.

Journal ref: Neural Information Processing Systems (NeurIPS) 2020

Dimension-Free Bounds on Chasing Convex Functions

Authors: C. J. Argue, Anupam Gupta, Guru Guruganesh

Abstract: We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small function cost for these actions, as well as a small cost for moving between actions. While the general problem requires a polynomial dependence on the dimension, we show how to get dimension-independent bounds for well-behaved… ▽ More We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small function cost for these actions, as well as a small cost for moving between actions. While the general problem requires a polynomial dependence on the dimension, we show how to get dimension-independent bounds for well-behaved functions. In particular, we consider the case where the convex functions are $κ$-well-conditioned, and give an algorithm that achieves an $O(\sqrt κ)$-competitiveness. Moreover, when the functions are supported on $k$-dimensional affine subspaces--e.g., when the function are the indicators of some affine subspaces--we get $O(\min(k, \sqrt{k \log T}))$-competitive algorithms for request sequences of length $T$. We also show some lower bounds, that well-conditioned functions require $Ω(κ^{1/3})$-competitiveness, and $k$-dimensional functions require $Ω(\sqrt{k})$-competitiveness. △ Less

Submitted 28 May, 2020; originally announced May 2020.

Chasing Convex Bodies with Linear Competitive Ratio

Authors: C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang

Abstract: We study the problem of chasing convex bodies online: given a sequence of convex bodies $K_t\subseteq \mathbb{R}^d$ the algorithm must respond with points $x_t\in K_t$ in an online fashion (i.e., $x_t$ is chosen before $K_{t+1}$ is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a $2^{O(d)}$-competitive algorit… ▽ More We study the problem of chasing convex bodies online: given a sequence of convex bodies $K_t\subseteq \mathbb{R}^d$ the algorithm must respond with points $x_t\in K_t$ in an online fashion (i.e., $x_t$ is chosen before $K_{t+1}$ is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a $2^{O(d)}$-competitive algorithm for this problem. We give an algorithm that is $O(\min(d, \sqrt{d \log T}))$-competitive for any sequence of length $T$. △ Less

Submitted 6 January, 2020; v1 submitted 28 May, 2019; originally announced May 2019.

Stochastic Online Metric Matching

Authors: Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc

Abstract: We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of th… ▽ More We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching. Such stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight $O(\log n)$-competitiveness for the random-order arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of $O(\log n)$ has long been conjectured and remains a tantalizing open question. In this paper, we show improved results in the i.i.d arrival model. We show how the i.i.d model can be used to give substantially better algorithms: our main result is an $O((\log \log \log n)^2)$-competitive algorithm in this model. Along the way we give a $9$-competitive algorithm for the line and tree metrics. Both results imply a strict separation between the i.i.d model and the adversarial and random order models, both for general metrics and these much-studied metrics. △ Less

Submitted 19 April, 2019; originally announced April 2019.

Comments: Full version of ICALP 2019 paper

ACM Class: F.2.2

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems

Authors: Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh

Abstract: Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite… ▽ More Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut, for many others, e.g., Max-SAT and Max-DiCut, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semidefinite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut, Max-2SAT, and MaxDiCut, and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations △ Less

Submitted 19 October, 2019; v1 submitted 19 December, 2018; originally announced December 2018.

Fully-Dynamic Bin Packing with Limited Repacking

Authors: Anupam Gupta, Guru Guruganesh, Amit Kumar, David Wajc

Abstract: We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio \emph{while repacking items sparingly} between updates. Formally, each item $i$ has a \emph{movement cost} $c_i\geq 0$, and we want to use $α\cdot OPT$ bins and incur a movement cost $γ\cdot c_i$, either in the worst case… ▽ More We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio \emph{while repacking items sparingly} between updates. Formally, each item $i$ has a \emph{movement cost} $c_i\geq 0$, and we want to use $α\cdot OPT$ bins and incur a movement cost $γ\cdot c_i$, either in the worst case, or in an amortized sense, for $α, γ$ as small as possible. We call $γ$ the \emph{recourse} of the algorithm. This is motivated by cloud storage applications, where fully-dynamic Bin Packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure. △ Less

Submitted 16 May, 2018; v1 submitted 6 November, 2017; originally announced November 2017.

Comments: To appear in ICALP 2018. Improved worst-case recourse for unit costs added (Theorem 2.7)

ACM Class: F.2.3

Understanding the Correlation Gap for Matchings

Authors: Guru Guruganesh, Euiwoong Lee

Abstract: Given a set of vertices $V$ with $|V| = n$, a weight vector $w \in (\mathbb{R}^+ \cup \{ 0 \})^{\binom{V}{2}}$, and a probability vector $x \in [0, 1]^{\binom{V}{2}}$ in the matching polytope, we study the quantity $\frac{E_{G}[ ν_w(G)]}{\sum_{(u, v) \in \binom{V}{2}} w_{u, v} x_{u, v}}$ where $G$ is a random graph where each edge $e$ with weight $w_e$ appears with probability $x_e$ independently,… ▽ More Given a set of vertices $V$ with $|V| = n$, a weight vector $w \in (\mathbb{R}^+ \cup \{ 0 \})^{\binom{V}{2}}$, and a probability vector $x \in [0, 1]^{\binom{V}{2}}$ in the matching polytope, we study the quantity $\frac{E_{G}[ ν_w(G)]}{\sum_{(u, v) \in \binom{V}{2}} w_{u, v} x_{u, v}}$ where $G$ is a random graph where each edge $e$ with weight $w_e$ appears with probability $x_e$ independently, and let $ν_w(G)$ denotes the weight of the maximum matching of $G$. This quantity is closely related to correlation gap and contention resolution schemes, which are important tools in the design of approximation algorithms, algorithmic game theory, and stochastic optimization. We provide lower bounds for the above quantity for general and bipartite graphs, and for weighted and unweighted settings. he best known upper bound is $0.54$ by Karp and Sipser, and the best lower bound is $0.4$. We show that it is at least $0.47$ for unweighted bipartite graphs, at least $0.45$ for weighted bipartite graphs, and at lea st $0.43$ for weighted general graphs. To achieve our results, we construct local distribution schemes on the dual which may be of independent interest. △ Less

Submitted 17 October, 2017; originally announced October 2017.

ACM Class: F.2.2; G.2.2

Single-sink Fractionally Subadditive Network Design

Authors: Guru Guruganesh, Jennifer Iglesias, R. Ravi, Laura Sanità

Abstract: We study a generalization of the Steiner tree problem, where we are given a weighted network $G$ together with a collection of $k$ subsets of its vertices and a root $r$. We wish to construct a minimum cost network such that the network supports one unit of flow to the root from every node in a subset simultaneously. The network constructed does not need to support flows from all the subsets simul… ▽ More We study a generalization of the Steiner tree problem, where we are given a weighted network $G$ together with a collection of $k$ subsets of its vertices and a root $r$. We wish to construct a minimum cost network such that the network supports one unit of flow to the root from every node in a subset simultaneously. The network constructed does not need to support flows from all the subsets simultaneously. We settle an open question regarding the complexity of this problem for $k=2$, and give a $\frac{3}{2}$-approximation algorithm that improves over a (trivial) known 2-approximation. Furthermore, we prove some structural results that prevent many well-known techniques from doing better than the known $O(\log n)$-approximation. Despite these obstacles, we conjecture that this problem should have an $O(1)$-approximation. We also give an approximation result for a variant of the problem where the solution is required to be a path. △ Less

Submitted 10 July, 2017; v1 submitted 5 July, 2017; originally announced July 2017.

ACM Class: F.2.2; G.2.2

Online Matroid Intersection: Beating Half for Random Arrival

Authors: Guru Guruganesh, Sahil Singla

Abstract: For two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ defined on the same ground set $E$, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element,… ▽ More For two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ defined on the same ground set $E$, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element, while always maintaining a common independent set. While the natural greedy algorithm---pick an element whenever possible---is half competitive, nothing better was previously known; even for the special case of online bipartite matching in the edge arrival model. We present the first randomized online algorithm that has a $\frac12 + δ$ competitive ratio in expectation, where $δ>0$ is a constant. The expectation is over the random order and the coin tosses of the algorithm. As a corollary, we also obtain the first linear time algorithm that beats half competitiveness for offline matroid intersection. △ Less

Submitted 19 February, 2018; v1 submitted 19 December, 2015; originally announced December 2015.

Comments: 39 pages, 3 figures, 1 notation table, Part of this appeared in IPCO 2017

On the Lovász Theta function for Independent Sets in Sparse Graphs

Authors: Nikhil Bansal, Anupam Gupta, Guru Guruganesh

Abstract: We consider the maximum independent set problem on graphs with maximum degree~$d$. We show that the integrality gap of the Lovász $\vartheta$-function based SDP is $\widetilde{O}(d/\log^{3/2} d)$. This improves on the previous best result of $\widetilde{O}(d/\log d)$, and almost matches the integrality gap of $\widetilde{O}(d/\log^2 d)$ recently shown for stronger SDPs, namely those obtained using… ▽ More We consider the maximum independent set problem on graphs with maximum degree~$d$. We show that the integrality gap of the Lovász $\vartheta$-function based SDP is $\widetilde{O}(d/\log^{3/2} d)$. This improves on the previous best result of $\widetilde{O}(d/\log d)$, and almost matches the integrality gap of $\widetilde{O}(d/\log^2 d)$ recently shown for stronger SDPs, namely those obtained using poly-$(\log(d))$ levels of the $SA^+$ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of $K_r$-free graphs for large values of $r$. We also show how to obtain an algorithmic version of the above-mentioned $SA^+$-based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of $\widetilde{O}(d/\log^2 d)$ matches the best unique-games-based hardness result up to lower-order poly-$(\log\log d)$ factors. △ Less

Submitted 23 April, 2015; v1 submitted 18 April, 2015; originally announced April 2015.

Comments: Extended abstract to appear at the STOC 2015 conference

Improved Region-Growing and Combinatorial Algorithms for $k$-Route Cut Problems

Authors: Guru Guruganesh, Laura Sanita, Chaitanya Swamy

Abstract: We study the {\em $k$-route} generalizations of various cut problems, the most general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein we have $r$ source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below $k$. The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cut problem ($k$-… ▽ More We study the {\em $k$-route} generalizations of various cut problems, the most general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein we have $r$ source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below $k$. The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cut problem ($k$-$(s,t)$-cut), are similarly defined. We present various approximation and hardness results for these $k$-route cut problems that improve the state-of-the-art for these problems in several cases. (i) For {\em $k$-route multiway cut}, we devise simple, but surprisingly effective, combinatorial algorithms that yield bicriteria approximation guarantees that markedly improve upon the previous-best guarantees. (ii) For {\em $k$-route multicut}, we design algorithms that improve upon the previous-best approximation factors by roughly an $O(\sqrt{\log r})$-factor, when $k=2$, and for general $k$ and unit costs and any fixed violation of the connectivity threshold $k$. The main technical innovation is the definition of a new, powerful \emph{region growing} lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a {\em different metric} for each source-sink pair. (iii) We complement these results by showing that the {\em $k$-route $s$-$t$ cut} problem is at least as hard to approximate as the {\em densest-$k$-subgraph} (DkS) problem on uniform hypergraphs. △ Less

Submitted 19 October, 2014; originally announced October 2014.

ACM Class: F.2.2; G.1.6; G.2