Vivek Madan

ICLR Conference 2023 Conference Paper

Don't forget the nullspace! Nullspace occupancy as a mechanism for out of distribution failure

• Daksh Idnani
• Vivek Madan
• Naman Goyal 0001
• David J. Schwab
• Ramakrishna Vedantam

Out of distribution (OoD) generalization has received considerable interest in recent years. In this work, we identify a particular failure mode of OoD generalization for discriminative classifiers that is based on test data (from a new domain) lying in the nullspace of features learnt from source data. We demonstrate the existence of this failure mode across multiple networks trained across RotatedMNIST, PACS, TerraIncognita, DomainNet and ImageNet-R datasets. We then study different choices for characterizing the feature space and show that projecting intermediate representations onto the span of directions that obtain maximum training accuracy provides consistent improvements in OoD performance. Finally, we show that such nullspace behavior also provides an insight into neural networks trained on poisoned data. We hope our work galvanizes interest in the relationship between the nullspace occupancy failure mode and generalization.

FOCS Conference 2020 Conference Paper

Maximizing Determinants under Matroid Constraints

• Vivek Madan
• Aleksandar Nikolov
• Mohit Singh
• Uthaipon Tao Tantipongpipat

Given a set of vectors $\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\in \mathbb{R}^{d}$ and a matroid $\mathcal{M}=([n], \mathcal{I})$, we study the problem of finding a basis $S$ of $\mathcal{M}$ such that $\det(\sum\nolimits_{i\in S}\mathbf{v}_{i}\mathbf{v}_{i}^{\top})$ is maximized. This problem appears in a diverse set of areas, such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an $e^{2k}$ -estimation for any matroid of rank $k$ [8] and a $(1+\epsilon)^{d}$ -approximation for a uniform matroid of rank $k \geq d+\frac{d}{\epsilon}$ [30], where the rank $k\geq d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm for the general problem with an approximation guarantee that depends only on the dimension $d$ of the vectors, and not on the size $k$ of the output set. In particular, we show an $(O(d))^{d}$ -estimation and an $(O(d))^{d^{3}}$ -approximation for any matroid, giving a significant improvement over prior work when $k\gg d$. Our result relies on showing that there exists an optimal solution to a convex programming relaxation for the problem which has sparse support; in particular, no more than $O(d^{2})$ variables of the solution have fractional values. The sparsity results rely on the interplay between the first order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a new randomized rounding algorithm that crucially exploits the sparsity of solutions to the convex program. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials [8], [4] and show new relationships between different convex programs [33], [6] studied for the problem. Finally, we show how to use the estimation algorithm to give an efficient deterministic approximation algorithm. Once again, the algorithm crucially relies on sparsity of the fractional solution to guarantee that the approximation factor depends solely on the dimension $d$.

SODA Conference 2018 Conference Paper

A tight -approximation for Linear 3-Cut

• Kristóf Bérczi
• Karthekeyan Chandrasekaran
• Tamás Király
• Vivek Madan

SODA Conference 2017 Conference Paper

Approximating Multicut and the Demand Graph

• Chandra Chekuri
• Vivek Madan

In the minimum Multicut problem, the input is an edge- weighted supply graph G = ( V, E ) and a demand graph H = ( V, F ). Either G and H are directed (Di r -M ül C) or both are undirected (Un dir -M ül C). The goal is to remove a minimum weight set of supply edges E ’ ⊆ E such that in G — E’ there is no path from s to t for any demand edge ( s, t ) ∊ F. Un dir -M ül C admits O (log k )-approximation where k is the number of edges in H while the best known approximation for Di r -M ül C is min{ k, Õ (|V | 11/23 )}. These approximations are obtained by proving corresponding results on the multicommodity flow-cut gap. In this paper we consider the role that the structure of the demand graph plays in determining the approximability of Multicut. We obtain several new positive and negative results. In undirected graphs our main result is a 2- approximation in n O (t) time when the demand graph excludes an induced matching of size t. This gives a constant factor approximation for a specific demand graph that motivated this work, and is based on a reduction to uniform metric labeling and not via the flow-cut gap. In contrast to the positive result for undirected graphs, we prove that in directed graphs such approximation algorithms can not exist. We prove that, assuming the Unique Games Conjecture (UGC), that for a large class of fixed demand graphs Di r -M ül C cannot be approximated to a factor better than the worst- case flow-cut gap. As a consequence we prove that for any fixed k, assuming UGC, Di r -M ül C with k demand pairs is hard to approximate to within a factor better than k. On the positive side, we obtain a k approximation when the demand graph excludes certain graphs as an induced subgraph. This generalizes the known 2 approximation for directed Multiway Cut to a larger class of demand graphs.

SODA Conference 2016 Conference Paper

Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation

• Chandra Chekuri
• Vivek Madan

We consider subset feedback edge and vertex set problems in undirected graphs. The input to these problems is an undirected graph G = ( V, E ) and a set S = { s 1, s 2, …, s k } ⊂ V of k terminals. A cycle in G is interesting if it contains a terminal. In the Subset Feedback Edge Set problem (S ubset -FES) the input graph is edge-weighted and the goal is to remove a minimum weight set of edges such that no interesting cycle remains. In the Subset Feedback Vertex Set problem (S ubset -FVS) the input graph is node-weighted and the goal is to remove a minimum weight set of nodes such that no interesting cycle remains. A 2-approximation is known for S ubset -FES [12] and a 8-approximation is known for S ubset -FVS [13]. The algorithm and analysis for S ubset -FVS is complicated. One reason for the difficulty in addressing feedback set problems in undirected graphs has been the lack of LP relaxations with constant factor integrality gaps; the natural LP has an integrality gap of ⊝(log n ). In this paper, we introduce new LP relaxations for S ubset -FES and S ubset -FVS and show that their integrality gap is at most 13. Our LP formulation and rounding are simple although the analysis is non-obvious.

SODA Conference 2016 Conference Paper

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

• Chandra Chekuri
• Vivek Madan

We study the multiway cut problem in directed graphs and one of its special cases, the node-weighted multiway cut problem in undirected graphs. In D irected M ultiway C ut (D ir -MC) the input is an edge-weighted directed graph G = ( V, E ) and a set of k terminal nodes { s 1, s 2, …, s k } ⊆ V; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from s i to s j for any i ≠ j. In N ode - weighted M ultiway C ut (N ode - wt -MC) the input is a node-weighted undirected graph G and a set of k terminal nodes { s 1, s 2, …, s k } ⊆ V; the goal is to find a min-weight subset of nodes whose removal ensures that there is no path from s i to s j for any i ≠ j. D ir -MC admits a 2-approximation [28] and N ode - wt -MC admits a -approximation [21], both via rounding of LP relaxations. Previous rounding algorithms for these problems, from nearly twenty years ago, are based on careful rounding of an optimum solution to an LP relaxation. This is particularly true for D ir -MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [28]. In this paper we describe extremely simple and near linear-time rounding algorithms for D ir -MC and N ode - wt -MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with any feasible solution to the relaxation. Consequently, in addition to obtaining “book” proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for D ir -MC when k = 2 and prove that the integrality gap of the LP relaxation is 2 even in planar directed graphs.