Viswanath Nagarajan

JMLR Journal 2024 Journal Article

Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes

• Su Jia
• Fatemeh Navidi
• Viswanath Nagarajan
• R. Ravi

In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can be formulated as the classical Optimal Decision Tree (ODT) problem: Given a set of tests, a set of hypotheses, and an outcome for each pair of test and hypothesis, our objective is to find a low-cost testing procedure (i.e., decision tree) that identifies the true hypothesis. This optimization problem has been extensively studied under the assumption that each test generates a deterministic outcome. However, in numerous applications, for example, clinical trials, the outcomes may be uncertain, which renders the ideas in the deterministic setting invalid. In this work, we study a fundamental variant of the ODT problem in which some test outcomes are noisy, even in the more general case where the noise is persistent, i.e., repeating a test gives the same noisy output. Our approximation algorithms provide guarantees that are nearly best possible and hold for the general case of a large number of noisy outcomes per test or per hypothesis where the performance degrades continuously with this number. Furthermore, most of our results hold for a more general problem called Adaptive Submodular Ranking with Noise (ASRN). We numerically evaluated our algorithms for identifying toxic chemicals and learning linear classifiers and observed that our algorithms have costs very close to the information-theoretic minimum. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

FOCS Conference 2024 Conference Paper

Semi-Bandit Learning for Monotone Stochastic Optimization

• Arpit Agarwal 0001
• Rohan Ghuge
• Viswanath Nagarajan

Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables. Exact or approximation algorithms have been obtained for several fundamental problems in this area. However, a significant limitation of this approach is that it requires full knowledge of the underlying probability distributions. Can we still get good (approximation) algorithms if these distributions are unknown, and the algorithm needs to learn them through repeated interactions? In this paper, we resolve this question for a large class of “monotone” stochastic problems, by providing a generic online learning algorithm with $\sqrt{T\log T}$ regret relative to the best approximation algorithm (under known distributions). Importantly, our online algorithm works in a semi-bandit setting, where in each period, the algorithm only observes samples from the random variables that were actually probed. Our frame-work applies to several fundamental problems in stochastic optimization such as prophet inequality, Pandora's box, stochastic knapsack, stochastic matchings and stochastic submodular optimization.

NeurIPS Conference 2022 Conference Paper

An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem

• Arpit Agarwal
• Rohan Ghuge
• Viswanath Nagarajan

We study the $K$-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the fully adaptive setting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where performing sequential updates may be infeasible. In this work, we ask: is there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for $K$-armed dueling bandits? We answer this in the affirmative under the Condorcet condition, a standard setting of the $K$-armed dueling bandit problem. We obtain asymptotic regret of $O(K^2\log^2(K))$ + $O(K\log(T))$ in $O(\log(T))$ rounds, where $T$ is the time horizon. Our regret bounds nearly match the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments over a variety of real-world datasets, we observe that our algorithm using $O(\log(T))$ rounds achieves almost the same performance as fully sequential algorithms (that use $T$ rounds).

ICML Conference 2022 Conference Paper

Batched Dueling Bandits

• Arpit Agarwal 0001
• Rohan Ghuge
• Viswanath Nagarajan

The K-armed dueling bandit problem, where the feedback is in the form of noisy pairwise comparisons, has been widely studied. Previous works have only focused on the sequential setting where the policy adapts after every comparison. However, in many applications such as search ranking and recommendation systems, it is preferable to perform comparisons in a limited number of parallel batches. We study the batched K-armed dueling bandit problem under two standard settings: (i) existence of a Condorcet winner, and (ii) strong stochastic transitivity and stochastic triangle inequality. For both settings, we obtain algorithms with a smooth trade-off between the number of batches and regret. Our regret bounds match the best known sequential regret bounds (up to poly-logarithmic factors), using only a logarithmic number of batches. We complement our regret analysis with a nearly-matching lower bound. Finally, we also validate our theoretical results via experiments on synthetic and real data.

SODA Conference 2021 Conference Paper

Online Generalized Network Design Under (Dis)Economies of Scale

• Viswanath Nagarajan
• Lily Wang

We consider a general online network design problem where a sequence of N requests arrive over time, each of which needs to use a subset of the available resources E. The cost incurred by a resource e ∊ E is some function f e of its total load ℓ e. The objective is to minimize the total cost Σ e ∊ E f e ( ℓ e ). We focus on cost functions that exhibit (dis)economies of scale, which are of the form if x > 0 (and zero if x = 0), where the exponent α e ≥ 1. Our main result is a deterministic online algorithm with tight competitive ratio when α e is constant. This framework is applicable to many network design problems, including multicommodity routing, Steiner tree/forest connectivity and set-connectivity Even in special cases such as multicommodity routing in undirected graphs with edge-costs, this is the first online algorithm to handle non-uniform resource cost and with a competitive ratio independent of the network size and number of requests. Our online competitive ratio also matches the previous-best offline approximation ratio. Our approach is based on the online primal-dual method for convex programs.

ICML Conference 2021 Conference Paper

The Power of Adaptivity for Stochastic Submodular Cover

• Rohan Ghuge
• Anupam Gupta 0001
• Viswanath Nagarajan

In the stochastic submodular cover problem, the goal is to select a subset of stochastic items of minimum expected cost to cover a submodular function. Solutions in this setting correspond to a sequential decision process that selects items one by one “adaptively” (depending on prior observations). While such adaptive solutions achieve the best objective, the inherently sequential nature makes them undesirable in many applications. We ask: \emph{how well can solutions with only a few adaptive rounds approximate fully-adaptive solutions? } We consider both cases where the stochastic items are independent, and where they are correlated. For both situations, we obtain nearly tight answers, establishing smooth tradeoffs between the number of adaptive rounds and the solution quality, relative to fully adaptive solutions. Experiments on synthetic and real datasets validate the practical performance of our algorithms, showing qualitative improvements in the solutions as we allow more rounds of adaptivity; in practice, solutions using just a few rounds of adaptivity are nearly as good as fully adaptive solutions.

SODA Conference 2020 Conference Paper

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems

• Rohan Ghuge
• Viswanath Nagarajan

We consider the following general network design problem on directed graphs. The input is an asymmetric metric ( V, c ), root r * ϵ V, monotone submodular function f: 2 V → ℝ + and budget B. The goal is to find an r *-rooted arborescence T of cost at most B that maximizes f ( T ). Our main result is a very simple quasi-polynomial time -approximation algorithm for this problem, where k ≤ | V | is the number of vertices in an optimal solution. To the best of our knowledge, this is the first non-trivial approximation ratio for this problem. As a consequence we obtain an -approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved -approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio [15], but improves significantly on the running time: our algorithm takes time whereas the previous algorithm required time. For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first non-trivial approximation ratio. Under certain complexity assumptions, our approximation ratios are best possible (up to constant factors).

NeurIPS Conference 2019 Conference Paper

Optimal Decision Tree with Noisy Outcomes

• Su Jia
• Viswanath Nagarajan
• Fatemeh Navidi
• R Ravi

A fundamental task in active learning involves performing a sequence of tests to identify an unknown hypothesis that is drawn from a known distribution. This problem, known as optimal decision tree induction, has been widely studied for decades and the asymptotically best-possible approximation algorithm has been devised for it. We study a generalization where certain test outcomes are noisy, even in the more general case when the noise is persistent, i. e. , repeating the test on the scenario gives the same noisy output, disallowing simple repetition as a way to gain confidence. We design new approximation algorithms for both the non-adaptive setting, where the test sequence must be fixed a-priori, and the adaptive setting where the test sequence depends on the outcomes of prior tests. Previous work in the area assumed at most a constant number of noisy outcomes per test and per scenario and provided approximation ratios that were problem dependent (such as the minimum probability of a hypothesis). Our new approximation algorithms provide guarantees that are nearly best-possible and work for the general case of a large number of noisy outcomes per test or per hypothesis where the performance degrades smoothly with this number. Our results adapt and generalize methods used for submodular ranking and stochastic set cover. We evaluate the performance of our algorithms on two natural applications with noise: toxic chemical identification and active learning of linear classifiers. Despite our logarithmic theoretical approximation guarantees, our methods give solutions with cost very close to the information theoretic minimum, demonstrating the effectiveness of our methods.

SODA Conference 2018 Conference Paper

Stochastic Load Balancing on Unrelated Machines

• Anupam Gupta 0001
• Amit Kumar 0001
• Viswanath Nagarajan
• Xiangkun Shen

SODA Conference 2017 Conference Paper

Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions

• Anupam Gupta 0001
• Viswanath Nagarajan
• Sahil Singla 0001

Suppose we are given a submodular function f over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for such problems under both monotone and non-monotone submodular functions. We consider these problems in a stochastic setting, where elements are not all active and we only get value from active elements. Each element e is active independently with some known probability p e, but we don't know the element's status a priori: we find it out only when we probe the element e. Moreover, the sequence of elements we probe must satisfy a given prefix-closed constraint, e. g. , matroid, orienteering, deadline, precedence, or any downward-closed constraint. In this paper we study the gap between adaptive and non-adaptive strategies for f being a submodular or a fractionally subadditive (XOS) function. If this gap is small, we can focus on finding good non-adaptive strategies instead, which are easier to find as well as to represent. We show that the adaptivity gap is a constant for monotone and non-monotone submodular functions, and logarithmic for XOS functions of small width. These bounds are nearly tight. Our techniques show new ways of arguing about the optimal adaptive decision tree for stochastic optimization problems.

SODA Conference 2016 Conference Paper

Algorithms and Adaptivity Gaps for Stochastic Probing

• Anupam Gupta 0001
• Viswanath Nagarajan
• Sahil Singla 0001

A stochastic probing problem consists of a set of elements whose values are independent random variables. The algorithm knows the distributions of these variables, but not the actual outcomes. The only way to learn the actual outcomes is to probe these elements. However, there are constraints on which set of elements may be probed. (E. g. , we may have to travel in some metric to probe elements but have limited time.) These constraints are called outer constraints. We want to develop an algorithm that picks some set of elements to maximize the (expected) value, subject to the picked subset of elements satisfying some other set of constraints, called the inner constraints. In the past, probing problems were studied for the case when both inner and outer constraints were intersections of matroids; these modeled kidney matching and Bayesian auctions applications. One limitation of past work was their reliance on linear-programming-like techniques, which made going beyond matroid-like structures difficult. In this work, we give a very general adaptivity gap result that holds for all prefix-closed outer constraints, as long as the inner constraints are intersections of matroids. The adaptivity gap is O (log n ) for any constant number of inner matroid constraints. The prefix-closedness captures most “reasonable” outer constraints, like orienteering, connectivity, and precedence. Based on this we obtain the first approximation algorithms for a number of stochastic probing problems, which have applications, e. g. , to path-planning and precedence-constrained scheduling.

FOCS Conference 2016 Conference Paper

Online Algorithms for Covering and Packing Problems with Convex Objectives

• Yossi Azar
• Niv Buchbinder
• T. -H. Hubert Chan
• Shahar Chen
• Ilan Reuven Cohen
• Anupam Gupta 0001
• Zhiyi Huang 0002
• Ning Kang 0001

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: min xϵ R + n f(x) s. t. Ax ≥ 1, where f: R + n → R + is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: max yϵR+ m Σ j=1 m yj - g(A T y), where g: R + n →R + is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

STOC Conference 2014 Conference Paper

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

• Ravishankar Krishnaswamy
• Viswanath Nagarajan
• Kirk Pruhs
• Cliff Stein 0001

We consider circuit routing with an objective of minimizing energy, in a network of routers that are speed scalable and that may be shutdown when idle. It is known that this energy minimization problem can be reduced to a capacitated flow network design problem, where vertices have a common capacity but arbitrary costs, and the goal is to choose a minimum cost collection of vertices whose induced subgraph will support the specified flow requirements. For the multicast (single-sink) capacitated design problem we give a polynomial-time algorithm that is O (log 3 n )- approximate with O (log 4 n ) congestion. This translates back to a O (log 4α+3 n )-approximation for the multicast energy-minimization routing problem, where α is the polynomial exponent in the dynamic power used by a router. For the unicast (multicommodity) capacitated design problem we give a polynomial-time algorithm that is O (log 5 n )-approximate with O (log 12 n ) congestion, which translates back to a O (log 12α+5 n )-approximation for the unicast energy-minimization routing problem.

SODA Conference 2014 Conference Paper

Hallucination Helps: Energy Efficient Virtual Circuit Routing

• Antonios Antoniadis 0001
• Sungjin Im
• Ravishankar Krishnaswamy
• Benjamin Moseley
• Viswanath Nagarajan
• Kirk Pruhs
• Cliff Stein 0001

SODA Conference 2012 Conference Paper

Approximation algorithms for stochastic orienteering

• Anupam Gupta 0001
• Ravishankar Krishnaswamy
• Viswanath Nagarajan
• R. Ravi 0001

FOCS Conference 2011 Conference Paper

Min-max Graph Partitioning and Small Set Expansion

• Nikhil Bansal 0001
• Uriel Feige
• Robert Krauthgamer
• Konstantin Makarychev
• Viswanath Nagarajan
• Joseph Naor
• Roy Schwartz 0002

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are: (i) the k parts need to be of equal size, and (ii) the parts must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k)-approximation algorithm. This improves over an O(log 2 n) approximation for the second version due to Svitkina and Tardos, and roughly O(k log n) approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty subset S of V of size at most pn with minimum edge-expansion. We give an O(√log n log (1/p)) bicriteria approximation algorithm for the general case of Small Set Expansion and O(1) approximation algorithm for graphs that exclude any fixed minor.

SODA Conference 2011 Conference Paper

The Matroid Median Problem

• Ravishankar Krishnaswamy
• Amit Kumar 0001
• Viswanath Nagarajan
• Yogish Sabharwal
• Barna Saha

In the classical k -median problem, we are given a metric space and would like to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper, we consider the following generalization of the problem: instead of opening at most k centers, what if each center belongs to one of T different types, and we are allowed to open at most k i centers of type i (for each i = 1, 2, …, T ). The case T = 1 is the classical k -median, and the case of T = 2 is the red-blue median problem for which Hajiaghayi et al. [ESA 2010] recently gave a constant-factor approximation algorithm. Even more generally, what if the set of open centers had to form an independent set from a matroid? In this paper, we give a constant factor approximation algorithm for such matroid median problems. Our algorithm is based on rounding a natural LP relaxation in two stages: in the first step, we sparsify the structure of the fractional solution while increasing the objective function value by only a constant factor. This enables us to write another LP in the second phase, for which the sparsified LP solution is feasible. We then show that this second phase LP is in fact integral; the integrality proof is based on a connection to matroid intersection. We also consider the penalty version (alternately, the so-called prize collecting version) of the matroid median problem and obtain a constant factor approximation algorithm for it. Finally, we look at the Knapsack Median problem (in which the facilities have costs and the set of open facilities need to fit into a Knapsack) and get a bicriteria approximation algorithm which violates the Knapsack bound by a small additive amount.

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.

SODA Conference 2009 Conference Paper

On the maximum quadratic assignment problem

• Viswanath Nagarajan
• Maxim Sviridenko

SODA Conference 2008 Conference Paper

A plant location guide for the unsure

• Barbara M. Anthony
• Vineet Goyal
• Anupam Gupta 0001
• Viswanath Nagarajan

STOC Conference 2008 Conference Paper

Additive guarantees for degree bounded directed network design

• Nikhil Bansal 0001
• Rohit Khandekar
• Viswanath Nagarajan

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity with degree bounds: given a directed graph G=(V,E) with non-negative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds a v , b v v∈ V on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm that for any 0 ≤ ε ≤ 1/2, computes an f-connected subgraph with in-degrees at most ⌈ a v /1-ε ⌉ + 4, out-degrees at most ⌈ b v /1-ε ⌉ + 4, and cost at most 1/ε times the optimum. This includes, as a special case, the minimum-cost degree-bounded arborescence problem. We also obtain similar results for the (more general) class of crossing supermodular requirements. Our result extends and improves the (3a v +4, 3b v +4, 3)-approximation of Lau et al. Setting ε=0, our result gives the first purely additive guarantee for the unweighted versions of these problems. Our algorithm is based on rounding an LP relaxation for the problem. We also prove that the above cost-degree trade-off (even for the degree-bounded arborescence problem) is optimal relative to the natural LP relaxation. For every 0<ε <1, we show an instance where any arborescence with out-degrees at most b v /1-ε + O(1) has cost at least 1-o(1)/ε times the optimal LP value. For the special case of finding a minimum degree arborescence (without costs), we give a stronger +2 additive approximation. This improves on a result of Lau et al. [13] that gives a 2Δ*+2 guarantee, and Klein et al. [11] that gives a (1+ε)Δ*+O(log 1+ε n) bound, where Δ* is the degree of the optimal arborescence. As a corollary of our result, we (almost) settle a conjecture of Bang-Jensen et al. [1] on low-degree arborescences. Our algorithms use the iterative rounding technique of Jain, which was used by Lau et al. and Singh and Lau in the context of degree-bounded network design. It is however non-trivial to extend these techniques to the directed setting without incurring a multiplicative violation in the degree bounds. This is due to the fact that known polyhedral characterization of arborescences has the cut-constraints which, along with degree-constraints, are unsuitable for arguing the existence of integral variables in a basic feasible solution. We overcome this difficulty by enhancing the iterative rounding steps and by means of stronger counting arguments. Our counting technique is quite general, and it also simplifies the proofs of many previous results. We also apply the technique to undirected graphs. We consider the minimum crossing spanning tree problem: given an undirected edge-weighted graph G, edge-subsets E i i=1 k , and non-negative integers b i i=1 k , find a minimum-cost spanning tree (if it exists) in G that contains at most b i edges from each set E i . We obtain a +(r-1) additive approximation for this problem, when each edge lies in at most r sets; this considerably improves the result of Bilo et al. A special case of this problem is degree-bounded minimum spanning tree, and our result gives a substantially easier proof of the recent +1 approximation of Singh and Lau.

SODA Conference 2006 Conference Paper

Approximating the k -multicut problem

• Daniel Golovin
• Viswanath Nagarajan
• Mohit Singh